Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Represents Bipartite graph for Hopcroft Karp implementation. More...
Public Member Functions | |
HKGraph () | |
Default Constructor for initialization. | |
HKGraph (int m, int n) | |
Constructor for initialization. | |
void | addEdge (int u, int v) |
function to add edge from u to v | |
bool | bfs () |
This function checks for the possibility of augmented path availability. | |
bool | dfs (int u) |
This functions checks whether an augmenting path is available exists beginning with free vertex u. | |
int | hopcroftKarpAlgorithm () |
This function counts the number of augmenting paths between left and right sides of the Bipartite graph. | |
Private Attributes | |
int | m {} |
m is the number of vertices on left side of Bipartite Graph | |
int | n {} |
n is the number of vertices on right side of Bipartite Graph | |
const int | NIL {0} |
const int | INF {INT_MAX} |
std::vector< std::list< int > > | adj |
adj[u] stores adjacents of left side and 0 is used for dummy vertex | |
std::vector< int > | pair_u |
value of vertex 'u' ranges from 1 to m | |
std::vector< int > | pair_v |
value of vertex 'v' ranges from 1 to n | |
std::vector< int > | dist |
dist represents the distance between vertex 'u' and vertex 'v' | |
Represents Bipartite graph for Hopcroft Karp implementation.
graph::HKGraph::HKGraph | ( | int | m, |
int | n ) |
Constructor for initialization.
m | is the number of vertices on left side of Bipartite Graph |
n | is the number of vertices on right side of Bipartite Graph |
void graph::HKGraph::addEdge | ( | int | u, |
int | v ) |
function to add edge from u to v
u | is the position of first vertex |
v | is the position of second vertex |
bool graph::HKGraph::bfs | ( | ) |
This function checks for the possibility of augmented path availability.
true
if there is an augmenting path available false
if there is no augmenting path available bool graph::HKGraph::dfs | ( | int | u | ) |
This functions checks whether an augmenting path is available exists beginning with free vertex u.
u | represents position of vertex |
true
if there is an augmenting path beginning with free vertex u false
if there is no augmenting path beginning with free vertex u int graph::HKGraph::hopcroftKarpAlgorithm | ( | ) |
This function counts the number of augmenting paths between left and right sides of the Bipartite graph.
|
private |
|
private |
m is the number of vertices on left side of Bipartite Graph
|
private |
n is the number of vertices on right side of Bipartite Graph
|
private |