Class SparseEdmondsMaximumCardinalityMatching<V,E>
 java.lang.Object

 org.jgrapht.alg.matching.SparseEdmondsMaximumCardinalityMatching<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class SparseEdmondsMaximumCardinalityMatching<V,E> extends java.lang.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 (nonperfect) 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 nearoptimal 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 lineartime set union data structure proposed in: Gabow, H.N., Tarjan, R.E. A lineartime algorithm for a special case of disjoint set union. Proc. Fifteenth Annual ACM Symposium on Theory of Computing, 1982, pp. 246251.
Edmonds' original algorithm first appeared in Edmonds, J. Paths, trees, and flowers. Canadian Journal of Mathematics 17, 1965, pp. 449467, 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


Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>


Field Summary

Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON


Constructor Summary
Constructors Constructor Description SparseEdmondsMaximumCardinalityMatching(Graph<V,E> graph)
Constructs a new instance of the algorithm.SparseEdmondsMaximumCardinalityMatching(Graph<V,E> graph, MatchingAlgorithm<V,E> initializer)
Constructs a new instance of the algorithm.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description MatchingAlgorithm.Matching<V,E>
getMatching()
Compute a matching for a given graph.java.util.Map<V,java.lang.Integer>
getOddSetCover()
Get an odd set cover which proves the optimality of the computed matching.static <V,E>
booleanisOptimalMatching(Graph<V,E> graph, java.util.Set<E> matching, java.util.Map<V,java.lang.Integer> oddSetCover)
Check whether a matching is optimal.



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

getMatching
public MatchingAlgorithm.Matching<V,E> getMatching()
Description copied from interface:MatchingAlgorithm
Compute a matching for a given graph. Specified by:
getMatching
in interfaceMatchingAlgorithm<V,E>
 Returns:
 a matching

getOddSetCover
public java.util.Map<V,java.lang.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 oddsetcover 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 oddsetcover. 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, java.util.Set<E> matching, java.util.Map<V,java.lang.Integer> oddSetCover)
Check whether a matching is optimal. The method first checks whether the matching is indeed a matching. Then it checks whether the oddsetcover 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 typeE
 graph edge type Parameters:
graph
 the graphmatching
 a matchingoddSetCover
 an odd set cover Returns:
 true if the matching is optimal, false otherwise

