Class GraphMatching

java.lang.Object
com.google.common.truth.GraphMatching

final class GraphMatching extends Object
Helper routines related to graph matchings.
  • Constructor Details

    • GraphMatching

      private GraphMatching()
  • Method Details

    • maximumCardinalityBipartiteMatching

      static <U, V> com.google.common.collect.ImmutableBiMap<U,V> maximumCardinalityBipartiteMatching(com.google.common.collect.Multimap<U,V> graph)
      Finds a maximum cardinality matching of a bipartite graph. The vertices of one part of the bipartite graph are identified by objects of type U using object equality. The vertices of the other part are similarly identified by objects of type V. The input bipartite graph is represented as a Multimap<U, V>: each entry represents an edge, with the key representing the vertex in the first part and the value representing the value in the second part. (Note that, even if U and V are the same type, equality between a key and a value has no special significance: effectively, they are in different domains.) Fails if any of the vertices (keys or values) are null. The output matching is similarly represented as a BiMap<U, V> (the property that a matching has no common vertices translates into the bidirectional uniqueness property of the BiMap).

      If there are multiple matchings which share the maximum cardinality, an arbitrary one is returned.