hopcroft_karp.cpp

Go to the documentation of this file.

 
 
#include <iostream>
#include <cstdlib> 
#include <queue>
#include <list>
#include <climits>
#include <memory>
#include <cassert>

 namespace graph { 

class HKGraph
{
    int m{};  
    int n{};  
    const int NIL{0};
    const int INF{INT_MAX};
 
    std::vector<std::list<int> >adj;  
 
    std::vector<int> pair_u; 
    std::vector<int> pair_v; 
    std::vector<int> dist;   
 
public:
    HKGraph();             // Default Constructor
    HKGraph(int m, int n);     // Constructor
    void addEdge(int u, int v); // To add edge
    
    bool bfs(); // Returns true if there is an augmenting path    
    bool dfs(int u); // Adds augmenting path if there is one beginning with u  
    
    int hopcroftKarpAlgorithm();  // Returns size of maximum matching
};
 

int HKGraph::hopcroftKarpAlgorithm()
{
 
    // 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;
}
 

bool HKGraph::bfs()
{
    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
}

bool HKGraph::dfs(int u)
{
    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;
}

HKGraph::HKGraph() = default;

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

void HKGraph::addEdge(int u, int v)
{
    adj[u].push_back(v); // Add v to u’s list.
}
 
} // namespace graph
 
using graph::HKGraph;

void tests(){
     // Sample test case 1
         int v1a = 3, v1b = 5;  // vertices of left side, right side and edges
         HKGraph g1(v1a, v1b); // execute the algorithm 
 
         g1.addEdge(0,1);
         g1.addEdge(1,4);
 
         int expected_res1 = 0; // for the above sample data, this is the expected output
         int res1 = g1.hopcroftKarpAlgorithm();
 
         assert(res1 == expected_res1); // assert check to ensure that the algorithm executed correctly for test 1
    
     // Sample test case 2
             int v2a = 4, v2b = 4;  // vertices of left side, right side and edges
         HKGraph g2(v2a, v2b); // execute the algorithm 
 
             g2.addEdge(1,1);
         g2.addEdge(1,3);
         g2.addEdge(2,3);
         g2.addEdge(3,4);
         g2.addEdge(4,3);
             g2.addEdge(4,2);
    
         int expected_res2 = 0; // for the above sample data, this is the expected output
         int res2 = g2.hopcroftKarpAlgorithm();
 
         assert(res2 == expected_res2); // assert check to ensure that the algorithm executed correctly for test 2
    
      // Sample test case 3
             int v3a = 6, v3b = 6;  // vertices of left side, right side and edges
         HKGraph g3(v3a, v3b); // execute the algorithm 
 
             g3.addEdge(0,1);
         g3.addEdge(1,4);
         g3.addEdge(1,5);
         g3.addEdge(5,0);
 
         int expected_res3 = 0; // for the above sample data, this is the expected output
         int res3 = g3.hopcroftKarpAlgorithm();
 
         assert(res3 == expected_res3); // assert check to ensure that the algorithm executed correctly for test 3
    
    
        
}

int main()
{
    tests();  // perform self-tests
 
    int v1 = 0, v2 = 0, e = 0;
    std::cin >> v1 >> v2 >> e; // vertices of left side, right side and edges
    HKGraph g(v1, v2);  
    int u = 0, v = 0;
    for (int i = 0; i < e; ++i)
    {
        std::cin >> u >> v;
        g.addEdge(u, v);
    }
  
    int res = g.hopcroftKarpAlgorithm();
    std::cout << "Maximum matching is " << res <<"\n";
 
    return 0;
 
}