Class GraphMatching


  • final class GraphMatching
    extends java.lang.Object
    Helper routines related to graph matchings.
    • Constructor Detail

      • GraphMatching

        private GraphMatching()
    • 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 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.