graph::HKGraph Class Reference

Represents Bipartite graph for Hopcroft Karp implementation. More...

Collaboration diagram for graph::HKGraph:

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'

Detailed Description

Represents Bipartite graph for Hopcroft Karp implementation.

Definition at line 66 of file hopcroft_karp.cpp.

Constructor & Destructor Documentation

HKGraph()

graph::HKGraph::HKGraph	(	int	m,
		int	n )

Constructor for initialization.

Parameters

m	is the number of vertices on left side of Bipartite Graph
n	is the number of vertices on right side of Bipartite Graph

Definition at line 231 of file hopcroft_karp.cpp.

                             {
    this->m = m;
    this->n = n;
    adj = std::vector<std::list<int> >(m + 1);
}

Member Function Documentation

addEdge()

void graph::HKGraph::addEdge	(	int	u,
		int	v )

function to add edge from u to v

Parameters

u	is the position of first vertex
v	is the position of second vertex

Definition at line 242 of file hopcroft_karp.cpp.

{
    adj[u].push_back(v); // Add v to u’s list.
}

bfs()

bool graph::HKGraph::bfs

(

)

This function checks for the possibility of augmented path availability.

Returns

true if there is an augmenting path available

false if there is no augmenting path available

Definition at line 133 of file hopcroft_karp.cpp.

{
    std::queue<int> q; // an integer queue for bfs
 
    // First layer of vertices (set distance as 0)
    for (int u = 1; u <= m; u++)
    {
        // If this is a free vertex, add it to queue
        if (pair_u[u] == NIL){
            
            dist[u] = 0; // u is not matched so distance is 0
            q.push(u);
        }
 
        else{
            dist[u] = INF; // set distance as infinite so that this vertex is considered next time for availibility
    }
    }
 
    
    dist[NIL] = INF; // Initialize distance to NIL as infinite
 
    // q is going to contain vertices of left side only.
    while (!q.empty())
    {
        int u = q.front();  // dequeue a vertex
        q.pop();
 
        // If this node is not NIL and can provide a shorter path to NIL then
        if (dist[u] < dist[NIL])
        {
            // Get all the adjacent vertices of the dequeued vertex u
            std::list<int>::iterator it;
            for (it = adj[u].begin(); it != adj[u].end(); ++it)
            {
                int v = *it;
 
                // If pair of v is not considered so far i.e. (v, pair_v[v]) is not yet explored edge.
                if (dist[pair_v[v]] == INF)
                {
                    dist[pair_v[v]] = dist[u] + 1; 
                    q.push(pair_v[v]);    // Consider the pair and push it to queue
                }
            }
        }
    }
 
   
   
    return (dist[NIL] != INF);   // If we could come back to NIL using alternating path of distinct vertices then there is an augmenting path available
}

dfs()

bool graph::HKGraph::dfs

(

int

u

)

This functions checks whether an augmenting path is available exists beginning with free vertex u.

Parameters

u	represents position of vertex

Returns

true if there is an augmenting path beginning with free vertex u

false if there is no augmenting path beginning with free vertex u

Definition at line 191 of file hopcroft_karp.cpp.

{
    if (u != NIL)
    {
        std::list<int>::iterator it;
        for (it = adj[u].begin(); it != adj[u].end(); ++it)
        {
            
            int v = *it; // Adjacent vertex of u
 
            // Follow the distances set by BFS search
            if (dist[pair_v[v]] == dist[u] + 1)
            {
                // If dfs for pair of v also return true then new matching possible, store the matching
                if (dfs(pair_v[v]) == true)
                {   
                    pair_v[v] = u;
                    pair_u[u] = v;
                    return true;
                }
            }
        }
 
        
        dist[u] = INF; // If there is no augmenting path beginning with u then set distance to infinite.
        return false;
    }
    return true;
}

hopcroftKarpAlgorithm()

int graph::HKGraph::hopcroftKarpAlgorithm

(

)

This function counts the number of augmenting paths between left and right sides of the Bipartite graph.

Returns

size of maximum matching

Definition at line 95 of file hopcroft_karp.cpp.

{
 
    // pair_u[u] stores pair of u in matching on left side of Bipartite Graph.
    // If u doesn't have any pair, then pair_u[u] is NIL
    pair_u = std::vector<int>(m + 1,NIL); 
 
    // pair_v[v] stores pair of v in matching on right side of Biparite Graph.
    // If v doesn't have any pair, then pair_u[v] is NIL
    pair_v = std::vector<int>(n + 1,NIL); 
 
    dist = std::vector<int>(m + 1);  // dist[u] stores distance of left side vertices
 
    int result = 0;  // Initialize result
 
    // Keep updating the result while there is an augmenting path possible.
    while (bfs())
    {
        // Find a free vertex to check for a matching
        for (int u = 1; u <= m; u++){
 
            // If current vertex is free and there is
            // an augmenting path from current vertex
            // then increment the result
            if (pair_u[u] == NIL && dfs(u)){
                result++;
        }
    }
    }
    return result;
}

Member Data Documentation

adj

std::vector<std::list<int> > graph::HKGraph::adj

private

adj[u] stores adjacents of left side and 0 is used for dummy vertex

Definition at line 73 of file hopcroft_karp.cpp.

dist

std::vector<int> graph::HKGraph::dist

private

dist represents the distance between vertex 'u' and vertex 'v'

Definition at line 77 of file hopcroft_karp.cpp.

INF

const int graph::HKGraph::INF {INT_MAX}

private

Definition at line 71 of file hopcroft_karp.cpp.

{INT_MAX};

m

int graph::HKGraph::m {}

private

m is the number of vertices on left side of Bipartite Graph

Definition at line 68 of file hopcroft_karp.cpp.

{};  

n

int graph::HKGraph::n {}

private

n is the number of vertices on right side of Bipartite Graph

Definition at line 69 of file hopcroft_karp.cpp.

{};  

NIL

const int graph::HKGraph::NIL {0}

private

Definition at line 70 of file hopcroft_karp.cpp.

{0};

pair_u

std::vector<int> graph::HKGraph::pair_u

private

value of vertex 'u' ranges from 1 to m

Definition at line 75 of file hopcroft_karp.cpp.

pair_v

std::vector<int> graph::HKGraph::pair_v

private

value of vertex 'v' ranges from 1 to n

Definition at line 76 of file hopcroft_karp.cpp.

---

The documentation for this class was generated from the following file:

• graph/hopcroft_karp.cpp