Class HopcroftKarpBipartiteMatching<V,​E>

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

    @Deprecated
    public class HopcroftKarpBipartiteMatching<V,​E>
    extends java.lang.Object
    implements MatchingAlgorithm<V,​E>
    Deprecated.
    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 final java.util.Set<V> partition1
        Deprecated.
      • partition2

        private final java.util.Set<V> partition2
        Deprecated.
      • matching

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

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

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

      • HopcroftKarpBipartiteMatching

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

      • checkInputData

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

        private void greedyMatch()
        Deprecated.
        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()
        Deprecated.
        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)
        Deprecated.
        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()
        Deprecated.
      • dfs

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

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

        public java.util.Set<E> getMatching()
        Deprecated.
        Description copied from interface: MatchingAlgorithm
        Returns set of edges making up the matching
        Specified by:
        getMatching in interface MatchingAlgorithm<V,​E>
        Returns:
        a matching