Class HopcroftKarpBipartiteMatching<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    MatchingAlgorithm<V,​E>

    public class HopcroftKarpBipartiteMatching<V,​E>
    extends java.lang.Object
    implements MatchingAlgorithm<V,​E>
    This class is an implementation of the Hopcroft-Karp algorithm which finds a maximum matching in an undirected simple bipartite graph. The algorithm runs in O(|E|*√|V|) time. 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 Note: the behavior of this class is undefined when the input isn't a bipartite graph, i.e. when there are edges within a single partition!
    • Field Detail

      • partition1

        private java.util.Set<? extends V> partition1
      • partition2

        private java.util.Set<? extends V> partition2
      • matching

        private java.util.Set<E> matching
      • unmatchedVertices1

        private java.util.Set<V> unmatchedVertices1
      • unmatchedVertices2

        private java.util.Set<V> unmatchedVertices2
    • Constructor Detail

      • HopcroftKarpBipartiteMatching

        public HopcroftKarpBipartiteMatching​(Graph<V,​E> graph,
                                             java.util.Set<V> partition1,
                                             java.util.Set<V> partition2)
        Construct a new instance of the Hopcroft-Karp algorithm for the computation of maximum matchings in bipartite graphs.
        Parameters:
        graph - the input graph
        partition1 - the first partition of the vertex set
        partition2 - the second partition of the vertex set
    • Method Detail

      • checkInputData

        private boolean checkInputData()
        Checks whether the input data meets the requirements: simple undirected graph and bipartite partitions.
      • greedyMatch

        private void greedyMatch()
        Greedily match the vertices in partition1 to the vertices in partition2. For each vertex in partition 1, check whether there is an edge to an unmatched vertex in partition 2. If so, add the edge to the matching.
      • maxMatching

        private void maxMatching()
        This method is the main method of the class. First it finds a greedy matching. Next it tries to improve the matching by finding all the augmenting paths. This leads to a maximum matching.
      • symmetricDifference

        private void symmetricDifference​(java.util.LinkedList<V> augmentingPath)
        Given are the current matching and a new augmenting path p. p.getFirst() and p.getLast() are newly matched vertices. This method updates the edges which are part of the existing matching with the new augmenting path. As a result, the size of the matching increases with 1.
        Parameters:
        augmentingPath -
      • getAugmentingPaths

        private java.util.List<java.util.LinkedList<V>> getAugmentingPaths()
      • dfs

        private java.util.LinkedList<V> dfs​(V startVertex,
                                            java.util.Map<V,​java.util.Set<V>> layeredMap)
      • interSectionNotEmpty

        private boolean interSectionNotEmpty​(java.util.Set<V> vertexSet1,
                                             java.util.Set<V> vertexSet2)
        Helper method which checks whether the intersection of 2 sets is empty.
        Parameters:
        vertexSet1 -
        vertexSet2 -
        Returns:
        true if the intersection is NOT empty.