Class GraphMatching.HopcroftKarp<U,​V>

  • Enclosing class:
    GraphMatching

    private static class GraphMatching.HopcroftKarp<U,​V>
    extends java.lang.Object
    Helper which implements the Hopcroft–Karp algorithm.

    The worst-case complexity is O(E V^0.5) where the graph contains E edges and V vertices. For dense graphs, where E is O(V^2), this is V^2.5 (and non-dense graphs perform better than dense graphs with the same number of vertices).

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private com.google.common.collect.Multimap<U,​V> graph  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private HopcroftKarp​(com.google.common.collect.Multimap<U,​V> graph)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private com.google.common.base.Optional<java.lang.Integer> breadthFirstSearch​(com.google.common.collect.BiMap<U,​V> matching, java.util.Map<U,​java.lang.Integer> layers)
      Performs the Breadth-First Search phase of the algorithm.
      private boolean depthFirstSearch​(com.google.common.collect.BiMap<U,​V> matching, java.util.Map<U,​java.lang.Integer> layers, int freeRhsVertexLayer, U lhs)
      Performs the Depth-First Search phase of the algorithm.
      (package private) static <U,​V>
      GraphMatching.HopcroftKarp<U,​V>
      overBipartiteGraph​(com.google.common.collect.Multimap<U,​V> graph)
      Factory method which returns an instance ready to perform the algorithm over the bipartite graph described by the given multimap.
      (package private) com.google.common.collect.ImmutableBiMap<U,​V> perform()
      Performs the algorithm, and returns a bimap describing the matching found.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private final com.google.common.collect.Multimap<U,​V> graph
    • Constructor Detail

      • HopcroftKarp

        private HopcroftKarp​(com.google.common.collect.Multimap<U,​V> graph)
    • Method Detail

      • overBipartiteGraph

        static <U,​V> GraphMatching.HopcroftKarp<U,​V> overBipartiteGraph​(com.google.common.collect.Multimap<U,​V> graph)
        Factory method which returns an instance ready to perform the algorithm over the bipartite graph described by the given multimap.
      • perform

        com.google.common.collect.ImmutableBiMap<U,​V> perform()
        Performs the algorithm, and returns a bimap describing the matching found.
      • breadthFirstSearch

        private com.google.common.base.Optional<java.lang.Integer> breadthFirstSearch​(com.google.common.collect.BiMap<U,​V> matching,
                                                                                      java.util.Map<U,​java.lang.Integer> layers)
        Performs the Breadth-First Search phase of the algorithm. Specifically, treats the bipartite graph as a directed graph where every unmatched edge (i.e. every edge not in the current matching) is directed from the LHS vertex to the RHS vertex and every matched edge is directed from the RHS vertex to the LHS vertex, and performs a BFS which starts from all of the free LHS vertices (i.e. the LHS vertices which are not in the current matching) and stops either at the end of a layer where a free RHS vertex is found or when the search is exhausted if no free RHS vertex is found. Keeps track of which layer of the BFS each LHS vertex was found in (for those LHS vertices visited during the BFS), so the free LHS vertices are in layer 1, those reachable by following an unmatched edge from any free LHS vertex to any non-free RHS vertex and then the matched edge back to a LHS vertex are in layer 2, etc. Note that every path in a successful search starts with a free LHS vertex and ends with a free RHS vertex, with every intermediate vertex being non-free.
        Parameters:
        matching - A bimap describing the matching to be used for the BFS, which is not modified by this method
        layers - A map to be filled with the layer of each LHS vertex visited during the BFS, which should be empty when passed into this method and will be modified by this method
        Returns:
        The number of the layer in which the first free RHS vertex was found, if any, and the absent value if the BFS was exhausted without finding any free RHS vertex
      • depthFirstSearch

        private boolean depthFirstSearch​(com.google.common.collect.BiMap<U,​V> matching,
                                         java.util.Map<U,​java.lang.Integer> layers,
                                         int freeRhsVertexLayer,
                                         U lhs)
        Performs the Depth-First Search phase of the algorithm. The DFS is guided by the BFS phase, i.e. it only uses paths which were used in the BFS. That means the steps in the DFS proceed from an LHS vertex via an unmatched edge to an RHS vertex and from an RHS vertex via a matched edge to an LHS vertex only if that LHS vertex is one layer deeper in the BFS than the previous one. It starts from the specified LHS vertex and stops either when it finds one of the free RHS vertices located by the BFS or when the search is exhausted. If a free RHS vertex is found then all the unmatched edges in the search path and added to the matching and all the matched edges in the search path are removed from the matching; in other words, the direction (which is determined by the matched/unmatched status) of every edge in the search path is flipped. Note several properties of this update to the matching:
        • Because the search path must contain one more unmatched than matched edges, the effect of this modification is to increase the size of the matching by one.
        • This modification results in the free LHS vertex at the start of the path and the free RHS vertex at the end of the path becoming non-free, while the intermediate non-free vertices stay non-free.
        • None of the edges used in this search path may be used in any further DFS. They cannot be used in the same direction as they were in this DFS because their directions are flipped; and they cannot be used in their new directions because we only use edges leading to the next layer of the BFS and, after flipping the directions, these edges now lead to the previous layer.
        • As a consequence of the previous property, repeated invocations of this method will find only paths which were used in the BFS and which were not used in any previous DFS (i.e. the set of edges used in the paths found by repeated DFSes are disjoint).
        Parameters:
        matching - A bimap describing the matching to be used for the BFS, which will be modified by this method as described above
        layers - A map giving the layer of each LHS vertex visited during the BFS, which will not be modified by this method
        freeRhsVertexLayer - The number of the layer in which the first free RHS vertex was found
        lhs - The LHS vertex from which to start the DFS
        Returns:
        Whether or not the DFS was successful