Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.

Implementation of Hopcroft–Karp algorithm. More...
#include <iostream>
#include <cstdlib>
#include <queue>
#include <list>
#include <climits>
#include <memory>
#include <cassert>
Classes  
class  graph::HKGraph 
Represents Bipartite graph for Hopcroft Karp implementation. More...  
Namespaces  
namespace  graph 
Graph Algorithms.  
Functions  
void  tests () 
int  main () 
Main function.  
Implementation of Hopcroft–Karp algorithm.
The Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching, it runs in O(E√V) time in worst case.
A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any oddlength cycles.
Given a matching M, edges that are part of matching are called Matching edges and edges that are not part of M (or connect free nodes) are called NotMatching edges.
Given a bipartite graphs G = ( V = ( X , Y ) , E ) whose partition has the parts X and Y, with E denoting the edges of the graph, the goal is to find a matching with as many edges as possible. Equivalently, a matching that covers as many vertices as possible.
Given a matching M, an augmenting path is an alternating path that starts from and ends on free vertices. All single edge paths that start and end with free vertices are augmenting paths.
A matching M is not maximum if there exists an augmenting path. It is also true other way, i.e, a matching is maximum if no augmenting path exists.
1) Initialize the Maximal Matching M as empty. 2) While there exists an Augmenting Path P Remove matching edges of P from M and add notmatching edges of P to M (This increases size of M by 1 as P starts and ends with a free vertex i.e. a node that is not part of matching.) 3) Return M.
int main  (  void  ) 
Main function.
void tests  (  ) 
Selftest implementation