Class HopcroftKarpMaximumCardinalityBipartiteMatching<V,E>

java.lang.Object
org.jgrapht.alg.matching.HopcroftKarpMaximumCardinalityBipartiteMatching<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
MatchingAlgorithm<V,E>

public class HopcroftKarpMaximumCardinalityBipartiteMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
Implementation of the well-known Hopcroft Karp algorithm to compute a matching of maximum cardinality in a bipartite graph. The algorithm runs in $O(|E| \cdot \sqrt{|V|})$ time. This implementation accepts undirected graphs which may contain self-loops and multiple edges. To compute a maximum cardinality matching in general (non-bipartite) graphs, use SparseEdmondsMaximumCardinalityMatching instead.

The Hopcroft Karp matching algorithm computes augmenting paths of increasing length, until no augmenting path exists in the graph. At each iteration, the algorithm runs a Breadth First Search from the exposed (free) vertices, until an augmenting path is found. Next, a Depth First Search is performed to find all (vertex disjoint) augmenting paths of the same length. The matching is augmented along all discovered augmenting paths simultaneously.

The original algorithm is described in: Hopcroft, John E.; Karp, Richard M. (1973), "An n5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing 2 (4): 225–231, doi:10.1137/0202019 A coarse overview of the algorithm is given in: http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm

  • Field Details

    • graph

      private final Graph<V,E> graph
    • partition1

      private final Set<V> partition1
    • partition2

      private final Set<V> partition2
    • vertices

      private List<V> vertices
    • vertexIndexMap

      private Map<V,Integer> vertexIndexMap
    • matchedVertices

      private int matchedVertices
    • DUMMY

      private static final int DUMMY
      See Also:
    • INF

      private static final int INF
      See Also:
    • matching

      private int[] matching
    • dist

      private int[] dist
    • queue

      private FixedSizeIntegerQueue queue
  • Constructor Details

    • HopcroftKarpMaximumCardinalityBipartiteMatching

      public HopcroftKarpMaximumCardinalityBipartiteMatching(Graph<V,E> graph, Set<V> partition1, Set<V> partition2)
      Constructs a new instance of the Hopcroft Karp bipartite matching algorithm. The input graph must be bipartite. For efficiency reasons, this class does not check whether the input graph is bipartite. Invoking this class on a non-bipartite graph results in undefined behavior. To test whether a graph is bipartite, use GraphTests.isBipartite(Graph).
      Parameters:
      graph - bipartite graph
      partition1 - the first partition of vertices in the bipartite graph
      partition2 - the second partition of vertices in the bipartite graph
  • Method Details

    • init

      private void init()
      Initialize data structures
    • warmStart

      private void warmStart()
      Greedily compute an initial feasible matching
    • bfs

      private boolean bfs()
      BFS function which finds the shortest augmenting path. The length of the shortest augmenting path is stored in dist[DUMMY].
      Returns:
      true if an augmenting path was found, false otherwise
    • dfs

      private boolean dfs(int u)
      Find all vertex disjoint augmenting paths of length dist[DUMMY]. To find paths of dist[DUMMY] length, we simply follow nodes that are 1 distance increments away from each other.
      Parameters:
      u - vertex from which the DFS is started
      Returns:
      true if an augmenting path from vertex u was found, false otherwise
    • getMatching

      public MatchingAlgorithm.Matching<V,E> getMatching()
      Description copied from interface: MatchingAlgorithm
      Compute a matching for a given graph.
      Specified by:
      getMatching in interface MatchingAlgorithm<V,E>
      Returns:
      a matching