Package org.jgrapht.alg.matching

Class SparseEdmondsMaximumCardinalityMatching<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    MatchingAlgorithm<V,​E>
    public class SparseEdmondsMaximumCardinalityMatching<V,​E>
extends Object
implements MatchingAlgorithm<V,​E>
    Edmonds' blossom algorithm for maximum cardinality matching in general undirected graphs.

    A matching in a graph $G(V,E)$ is a subset of edges $M$ such that no two edges in $M$ have a vertex in common. A matching has at most $\frac{1}{2}|V|$ edges. A node $v$ in $G$ is matched by matching $M$ if $M$ contains an edge incident to $v$. A matching is perfect if all nodes are matched. By definition, a perfect matching consists of exactly $\frac{1}{2}|V|$ edges. This algorithm will return a perfect matching if one exists. If no perfect matching exists, then the largest (non-perfect) matching is returned instead. In the special case that the input graph is bipartite, consider using HopcroftKarpMaximumCardinalityBipartiteMatching instead.

    To compute a maximum cardinality matching, at most $n$ augmenting path computations are performed. Each augmenting path computation takes $O(m \alpha(m,n))$ time, where $\alpha(m,n)$ is the inverse of the Ackerman function, $n$ is the number of vertices, and $m$ the number of edges. This results in a total runtime complexity of O(n m alpha(m,n)). In practice, the number of augmenting path computations performed is far smaller than $n$, since an efficient heuristic is used to compute a near-optimal initial solution. The heuristic by default is the GreedyMaximumCardinalityMatching but can be changed using the appropriate constructor.

    The runtime complexity of this implementation could be improved to $O(n m)$ when the UnionFind data structure used in this implementation is replaced by the linear-time set union data structure proposed in: Gabow, H.N., Tarjan, R.E. A linear-time algorithm for a special case of disjoint set union. Proc. Fifteenth Annual ACM Symposium on Theory of Computing, 1982, pp. 246-251.

    Edmonds' original algorithm first appeared in Edmonds, J. Paths, trees, and flowers. Canadian Journal of Mathematics 17, 1965, pp. 449-467, and had a runtime complexity of $O(n^4)$.

    This is the algorithm and implementation described in the LEDA book. See the LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999.

    For future reference - A more efficient algorithm exists: S. Micali and V. Vazirani. An $O(\sqrt{n}m)$ algorithm for finding maximum matching in general graphs. Proc. 21st Ann. Symp. on Foundations of Computer Science, IEEE, 1980, pp. 17–27. This is the most efficient algorithm known for computing maximum cardinality matchings in general graphs. More details on this algorithm can be found in:

    Author:
    Dimitrios Michail, Joris Kinable

    • Constructor Detail

      • SparseEdmondsMaximumCardinalityMatching

        public SparseEdmondsMaximumCardinalityMatching​(Graph<V,​E> graph)
        Constructs a new instance of the algorithm. GreedyMaximumCardinalityMatching is used to quickly generate a near optimal initial solution.
        Parameters:
        graph - the input graph

      • SparseEdmondsMaximumCardinalityMatching

        public SparseEdmondsMaximumCardinalityMatching​(Graph<V,​E> graph,
                                               MatchingAlgorithm<V,​E> initializer)
        Constructs a new instance of the algorithm.
        Parameters:
        graph - undirected graph (graph does not have to be simple)
        initializer - heuristic matching algorithm used to quickly generate a (near optimal) initial feasible solution

    • Method Detail

      • getOddSetCover

        public Map<V,​Integer> getOddSetCover()
        Get an odd set cover which proves the optimality of the computed matching.

        In order to check for optimality one needs to check that the odd-set-cover is a node labeling that (a) covers the graph and (b) whose capacity is equal to the cardinality of the matching. For (a) we check that every edge is either incident to a node with label 1 or connects two nodes labeled $i$ for some $i \ge 2$. For (b) we count for each $i$ the number $n_i$ of nodes with label $i$ and compute $S = n_1 + \sum_{i \ge 2} \floor{n_i/2}$.

        Method {isOptimalMatching(Graph, Set, Map) performs this check given a matching and an odd-set-cover.

        Returns:
        an odd set cover whose capacity is the same as the matching's cardinality

      • isOptimalMatching

        public static <V,​E> boolean isOptimalMatching​(Graph<V,​E> graph,
                                                    Set<E> matching,
                                                    Map<V,​Integer> oddSetCover)
        Check whether a matching is optimal. The method first checks whether the matching is indeed a matching. Then it checks whether the odd-set-cover provided is a node labeling that covers the graph and whose capacity is equal to the cardinality of the matching. First, we count for each $i$ the number $n_i$ of nodes with label $i$, and then compute $S = n_1 + \sum_{i \ge 2} \floor{n_i/2}$. $S$ should be equal to the size of the matching. Then, we check that every edge is incident to a node label one or connects two nodes labeled $i$ for some $i \ge 2$. This method runs in linear time.
        Type Parameters:
        V - graph vertex type
        E - graph edge type
        Parameters:
        graph - the graph
        matching - a matching
        oddSetCover - an odd set cover
        Returns:
        true if the matching is optimal, false otherwise