Package edu.princeton.cs.algs4

Class BipartiteMatching

  • public class BipartiteMatching
extends Object
    The BipartiteMatching class represents a data type for computing a maximum (cardinality) matching and a minimum (cardinality) vertex cover in a bipartite graph. A bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A matching in a graph is a subset of its edges with no common vertices. A maximum matching is a matching with the maximum number of edges. A perfect matching is a matching which matches all vertices in the graph. A vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any bipartite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover. The maximum matching problem in nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

    This implementation uses the alternating-path algorithm. It is equivalent to reducing to the maximum-flow problem and running the augmenting-path algorithm on the resulting flow network, but it does so with less overhead. The constructor takes O((E + V) V) time, where E is the number of edges and V is the number of vertices in the graph. It uses Θ(V) extra space (not including the graph).

    See also HopcroftKarp, which solves the problem in O(E sqrt(V)) using the Hopcroft-Karp algorithm and BipartiteMatchingToMaxflow, which solves the problem in O((E + V) V) time via a reduction to maxflow.

    For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

      Constructors 
      Constructor Description
      BipartiteMatching​(Graph G)
      Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean inMinVertexCover​(int v)
      Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
      boolean isMatched​(int v)
      Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
      boolean isPerfect()
      Returns true if the graph contains a perfect matching.
      static void main​(String[] args)
      Unit tests the HopcroftKarp data type.
      int mate​(int v)
      Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
      int size()
      Returns the number of edges in a maximum matching.

    • Constructor Detail

      • BipartiteMatching

        public BipartiteMatching​(Graph G)
        Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.
        Parameters:
        G - the bipartite graph
        Throws:
        IllegalArgumentException - if G is not bipartite

    • Method Detail

      • mate

        public int mate​(int v)
        Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
        Parameters:
        v - the vertex
        Returns:
        the vertex to which vertex v is matched in the maximum matching; -1 if the vertex is not matched
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • isMatched

        public boolean isMatched​(int v)
        Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
        Parameters:
        v - the vertex
        Returns:
        true if vertex v is matched in maximum matching; false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • size

        public int size()
        Returns the number of edges in a maximum matching.
        Returns:
        the number of edges in a maximum matching

      • isPerfect

        public boolean isPerfect()
        Returns true if the graph contains a perfect matching. That is, the number of edges in a maximum matching is equal to one half of the number of vertices in the graph (so that every vertex is matched).
        Returns:
        true if the graph contains a perfect matching; false otherwise

      • inMinVertexCover

        public boolean inMinVertexCover​(int v)
        Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
        Parameters:
        v - the vertex
        Returns:
        true if vertex v is in the minimum vertex cover; false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • main

        public static void main​(String[] args)
        Unit tests the HopcroftKarp data type. Takes three command-line arguments V1, V2, and E; creates a random bipartite graph with V1 + V2 vertices and E edges; computes a maximum matching and minimum vertex cover; and prints the results.
        Parameters:
        args - the command-line arguments