Package com.google.common.truth
Class GraphMatching
- java.lang.Object
-
- com.google.common.truth.GraphMatching
-
final class GraphMatching extends java.lang.Object
Helper routines related to graph matchings.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
GraphMatching.HopcroftKarp<U,V>
Helper which implements the Hopcroft–Karp algorithm.
-
Constructor Summary
Constructors Modifier Constructor Description private
GraphMatching()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description (package private) static <U,V>
com.google.common.collect.ImmutableBiMap<U,V>maximumCardinalityBipartiteMatching(com.google.common.collect.Multimap<U,V> graph)
-
-
-
Method Detail
-
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 typeU
using object equality. The vertices of the other part are similarly identified by objects of typeV
. The input bipartite graph is represented as aMultimap<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 ifU
andV
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 aBiMap<U, V>
(the property that a matching has no common vertices translates into the bidirectional uniqueness property of theBiMap
).If there are multiple matchings which share the maximum cardinality, an arbitrary one is returned.
-
-