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 (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
-
-
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 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, 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 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 typeE
- graph edge type- Parameters:
graph
- the graphmatching
- a matchingoddSetCover
- an odd set cover- Returns:
- true if the matching is optimal, false otherwise
-
-