Class GraphMatching.HopcroftKarp<U,V>

java.lang.Object
com.google.common.truth.GraphMatching.HopcroftKarp<U,V>
Enclosing class:
GraphMatching

private static class GraphMatching.HopcroftKarp<U,V> extends 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 final com.google.common.collect.Multimap<U,V>
     
  • Constructor Summary

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

    Modifier and Type
    Method
    Description
    private com.google.common.base.Optional<Integer>
    breadthFirstSearch(com.google.common.collect.BiMap<U,V> matching, Map<U,Integer> layers)
    Performs the Breadth-First Search phase of the algorithm.
    private boolean
    depthFirstSearch(com.google.common.collect.BiMap<U,V> matching, Map<U,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>
    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 Details

    • graph

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

    • HopcroftKarp

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

    • 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<Integer> breadthFirstSearch(com.google.common.collect.BiMap<U,V> matching, Map<U,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, Map<U,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