Hopcroft Karp algorithm in C++
The Hopcroft Karp algorithm also called the Hopcroft Karp Karzanov algorithm, takes a bipartite graph as input and produces a maximum-cardinality matching as output – it gives a set of edges that have a property that no two edges share an endpoint. The time complexity of this algorithm is O (|E|√(|V|)) time in the worst case, where E is the set of edges, and V is the set of vertices in a Graph G, and this algorithm makes the assumption that |E| = Ω (|V|). If we talk about dense graphs, the time complexity becomes O (|V|2.5), and if we talk about random graphs that are sparse have a time complexity of O (|E| log |V|) having high probability.
John Hopcroft and Richard Karp (1973) and Alexandar Karzanov (1973) independently discovered the Hopcroft-Karp algorithm. In the previous methods, such as the Hungarian algorithm used for matching and the work of Edmonds (1965), the size of the Hopcroft Karp algorithm repeatedly increases partial matching by finding augmenting paths. These paths are nothing but the sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edges are not in the partial matching. Finding a path that is augmented allows the size of matching that is partial to increase by simply toggling the edges of the augmenting path. The algorithm Ford Fulkerson algorithm, a simple algorithm for bipartite matching, finds one augmenting path per iteration; the Hopcroft Karp algorithm instead finds a maximal set of shortest augmenting paths so as to ensure that exactly O (√(|V|) is required instead of O (|V|) iterations. In an arbitrary graph, the performance of O (|E|√(|V|) can be achieved with Micali and Vazirani's more complicated algorithm. The Hopcroft-Karp algorithm is a particular case of Dinic’s algorithm for the maximum flow problem.
Augmenting Paths:
A vertex is called a free vertex that is not the endpoint of an edge in some partial matching M. The basic concept that the algorithm is based on is the augmenting path, a path that starts at a free vertex, ends at a free vertex and alternates between unmatched and matched edges within the path.
If there is a matching M and an augmenting path P relative to M, then the symmetric difference of the two sets of edges, M + P, would form a matching with size |M| + 1. With the help of augmenting paths, an algorithm may increase the size of the matching.
Suppose that a matching M is not optimal and let the symmetric difference P M + M* where M* is an optimal matching. Since M and M* are both matchings, every vertex has a degree at most 2 in P. So P must form a collection of disjoint cycles that have a path that contains an equal number of matched and unmatched edges in M, of augmenting paths for M, and of augmenting paths for M*; but the result is impossible as M* is optimal. Now, the path and the cycles that contain equal numbers of matched and unmatched vertices do not contribute to the difference in size between M and M*, so this difference is equal to the number of augmenting paths for M in P. So, whenever there exists a matching M* that is larger than the current matching M, there must also exit an augmenting path. If there is no path found that is not augmented, the algorithm may safely terminate since, in this case, M must be optimal. An augmenting path is a problem that is related to matching and is closely related to the augmenting paths that arise in maximum flow problems. The bipartite matching problem can be transformed into a maximum flow instance by satisfying the conditions that altering paths of the matching problem become augmenting paths of the flow problem.
Algorithm:
- Initialize Maximal Matching M as empty.
- While there exists an Augmenting Path, p
- Remove matching edges of p from M and add not-matching edges of p to M
- Return M.
In detail, let a graph G with two sets of bipartition U and V, M be the set of matching from U to V at any time. This algorithm is run in phases. Each phase includes the following steps:
- A BFS (Breadth First Search) in the graph partitions the nodes of the graph into layers. The vertices in U that are free are used as the starting vertices of this search, and the first layer of partitioning is formed. There are only edges that are unmatched at the first level of the search since the free vertices in U are, by definition, not adjacent to any matched edges. At any level of the search, the edges that are traversed are required to alternate between matched and unmatched edges. That is, when you search from a vertex in U for successors, only unmatched edges may be traversed, while from a vertex in V, only matched edges may be traversed. The search ends at the first layer, k, where one or more free nodes in V are reached.
- A node that is free in V at the k layer is collected into a set F. That is, a node v is inserted into F if and only if it ends in the shortest augmenting path.
- The algorithm finds a set of vertex disjoints that are maximal augmenting paths of length k. This set can be computed by DFS (Depth First Search) from F to free nodes in U, with the help of layering of breadth-first to guide the search: the depth-first search allows only to follow the edges that lead to an unused node in the previous layer and paths in the Depth-first search tree must be matched and unmatched nodes. Once an augmenting path is found that includes one of the nodes in F, the depth-first search forms the next starting node is continued. Any node that is encountered while the depth-first search tree can be marked as used immediately as if there is no path from it to the node U from the current point of the depth-first search, then that node can not be used to reach U at any other point in the depth-first search. This confirms the depth-first search's O (|E|) running time.
- Every path found in this way is used to enlarge M.
Analysis:
Each phase in the Hopcroft Karp algorithm contains a single BFS (breadth-first search) and a single depth-first search (DFS). Hence, a single step can be implemented in O(|E|) time. Thus, the first t √(|V|), in the graph with |V| node and |E| edges, take a computational time of O (|E|√(|V|).
The length of each phase increases the shortest augmenting path by at least one: a maximal set of augmenting paths is founded by the phase of the given length, so the path must be longer than any remaining augmenting path. Therefore, once the original (√(|V|) part of the Hopcroft Karp algorithm is complete, the remaining augmenting path that is shortest has at least √(|V|) nodes in it. If every path in the collection has a length of at least (√|V|), there can be √(|V|)paths in most collections, and the size of the optimal matching can differ at most (√|V|) edges from the size of M.
As the algorithm performance of a total of at most 2 √|V|) phases, it takes a total computational time of O (|E|√|V|) in the worst case.
Comparison with other bipartite matching algorithms:
For sparse graphs, the Hopcroft Karp algorithm always has the worst-case performance, but in the case of dense graphs, (|E| = Ω (|V|2).
Pseudocode:
/*
G = U ∪ V ∪ {NIL}
where U and V are the left and right sides of the bipartite graph, and NIL is a special null vertex
*/
function BFS() is
for each u in U, do
if Pair_U[u] = NIL then
Dist[u] := 0
Enqueue(Q, u)
else
Dist[u] := ∞
Dist[NIL] := ∞
while Empty(Q) = false do
u := Dequeue(Q)
if Dist[u] < Dist[NIL] then
for each v in Adj[u] do
if Dist[Pair_V[v]] = ∞ then
Dist[Pair_V[v]] := Dist[u] + 1
Enqueue(Q, Pair_V[v])
return Dist[NIL] ≠ ∞
function DFS(u) is
if u ≠ NIL, then
for each v in Adj[u] do
if Dist[Pair_V[v]] = Dist[u] + 1 then
if DFS(Pair_V[v]) = true then
Pair_V[v] := u
Pair_U[u] := v
return true
Dist[u] := ∞
return false
return true
function Hopcroft–Karp is
for each u in U do
Pair_U[u] := NIL
for each v in V do
Pair_V[v] := NIL
matching := 0
while BFS() = true do
for each u in U do
if Pair_U[u] = NIL then
if DFS(u) = true then
matching := matching + 1
return matching
Implementation of Hopcroft Karp algorithm in C++
// C++ implementation of Hopcroft Karp algorithm for
// maximum matching
#include<bits/stdc++.h>
using namespace std;
#define NIL 0
#define INF INT_MAX
// A class to represent Bipartite graph for Hopcroft
// Karp implementation
class BipGraph
{
// m and n are the number of vertices on the left
// and right sides of Bipartite Graph
int m, n;
// adj[u] stores adjacents of left side
// vertex 'u'. The value of u ranges from 1 to m.
// 0 is used for dummy vertex
list<int> *adj;
// These are basically pointers to arrays needed
// for hopcroftKarp()
int *pairU, *pairV, *dist;
public:
BipGraph(int m, int n); // Constructor
void addEdge(int u, int v); // To add edge
// Returns true if there is an augmenting path
bool bfs();
// Adds augmenting path if there is one beginning
// with u
bool dfs(int u);
// Returns size of maximum matching
int hopcroftKarp();
};
// Returns size of maximum matching
int BipGraph::hopcroftKarp()
{
// pairU[u] stores a pair of u in matching where u
// is a vertex on the left side of the Bipartite Graph.
// If u doesn't have any pair, then pairU[u] is NIL
pairU = new int[m+1];
// pairV[v] stores a pair of v in matching. If v
// doesn't have any pair, then pairU[v] is NIL
pairV = new int[n+1];
// dist[u] stores the distance of left side vertices
// dist[u] is one more than dist[u'] if u is next
// to u'in augmenting path
dist = new int[m+1];
// Initialize NIL as a pair of all vertices
for (int u=0; u<=m; u++)
pairU[u] = NIL;
for (int v=0; v<=n; v++)
pairV[v] = NIL;
// Initialize result
int result = 0;
// Keep updating the result while there is an
// augmenting path.
while (bfs())
{
// Find a free vertex
for (int u=1; u<=m; u++)
// If a current vertex is free and there is
// an augmenting path from the current vertex
if (pairU[u]==NIL && dfs(u))
result++;
}
return result;
}
// Returns true if there is an augmenting path. Else returns
// false
bool BipGraph::bfs()
{
queue<int> Q; //an integer queue
// First layer of vertices (set distance as 0)
for (int u=1; u<=m; u++)
{
// If this is a free vertex, add it to the queue
if (pairU[u]==NIL)
{
// u is not matched
dist[u] = 0;
Q.push(u);
}
// Else set distance as infinite so that this vertex
// is considered next time
else dist[u] = INF;
}
// Initialize distance to NIL as infinite
dist[NIL] = INF;
// Q is going to contain vertices of the left side only.
while (!Q.empty())
{
// Dequeue a vertex
int u = Q.front();
Q.pop();
// If this node is not NIL and can provide a shorter path to NIL
if (dist[u] < dist[NIL])
{
// Get all adjacent vertices of the dequeued vertex u
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); ++i)
{
int v = *i;
// If a pair of v is not considered so far
// (v, pairV[V]) is not yet explored edge.
if (dist[pairV[v]] == INF)
{
// Consider the pair and add it to the queue
dist[pairV[v]] = dist[u] + 1;
Q.push(pairV[v]);
}
}
}
}
// If we could come back to NIL using alternating paths of distinct
// vertices, then there is an augmenting path
return (dist[NIL] != INF);
}
// Returns true if there is an augmenting path beginning with free vertex u
bool BipGraph::dfs(int u)
{
if (u != NIL)
{
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); ++i)
{
// Adjacent to u
int v = *i;
// Follow the distances set by BFS
if (dist[pairV[v]] == dist[u]+1)
{
// If dfs for pair of v also returns
// true
if (dfs(pairV[v]) == true)
{
pairV[v] = u;
pairU[u] = v;
return true;
}
}
}
// If there is no augmenting path beginning with u.
dist[u] = INF;
return false;
}
return true;
}
// Constructor
BipGraph::BipGraph(int m, int n)
{
this->m = m;
this->n = n;
adj = new list<int>[m+1];
}
// To add an edge from u to v and v to u
void BipGraph::addEdge(int u, int v)
{
adj[u].push_back(v); // Add u to v’s list.
}
// Driver Program
int main()
{
BipGraph g(4, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 1);
g.addEdge(3, 2);
g.addEdge(4, 2);
g.addEdge(4, 4);
cout << "Size of maximum matching is " << g.hopcroftKarp();
return 0;
}
Output:
The size of the maximum matching is 4