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

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

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class DenseEdmondsMaximumCardinalityMatching<V,E> extends java.lang.Object implements MatchingAlgorithm<V,E>
This implementation of Edmonds' blossom algorithm computes maximum cardinality matchings in 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}{2V}$ 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}{2V}$ edges. This algorithm will return a perfect matching if one exists. If no perfect matching exists, then the largest (nonperfect) matching is returned instead. This algorithm does NOT compute a maximum weight matching. In the special case that the input graph is bipartite, consider usingHopcroftKarpMaximumCardinalityBipartiteMatching
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 an 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(nm 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. This implementation is highly efficient: a maximum matching in a graph of 2000 vertices and 1.5 million edges is calculated in a few milliseconds on a desktop computer.
The runtime complexity of this implementation could be improved to $O(nm)$ 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 implementation however follows more closely the description provided in Tarjan, R.E. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983, chapter 9. In addition, the following sources were used for the implementation:
 Java implementation by John Mayfield
 Java implementation by Keith Schwarz
 C++ implementation Boost library
 Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A. Combinatorial Optimization. Wiley 1997, chapter 5
 Gabow, H.N. Data Structures for Weighted Matching and Extensions to bmatching and ffactors, 2016
For future reference  A more efficient algorithm than the one implemented in this class exists: Micali, S., Vazirani, V. 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:
 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 DenseEdmondsMaximumCardinalityMatching(Graph<V,E> graph)
Constructs a new instance of the algorithm.DenseEdmondsMaximumCardinalityMatching(Graph<V,E> graph, MatchingAlgorithm<V,E> initializer)
Constructs a new instance of the algorithm.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MatchingAlgorithm.Matching<V,E>
getMatching()
Returns a matching of maximum cardinality.boolean
isMaximumMatching(MatchingAlgorithm.Matching<V,E> matching)
Checks whether the given matching is of maximum cardinality.



Constructor Detail

DenseEdmondsMaximumCardinalityMatching
public DenseEdmondsMaximumCardinalityMatching(Graph<V,E> graph)
Constructs a new instance of the algorithm.GreedyMaximumCardinalityMatching
is used to quickly generate a near optimal initial solution. Parameters:
graph
 undirected graph (graph does not have to be simple)

DenseEdmondsMaximumCardinalityMatching
public DenseEdmondsMaximumCardinalityMatching(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()
Returns a matching of maximum cardinality. Each time this method is invoked, the matching is computed from scratch. Consequently, it is possible to make changes to the graph and to reinvoke this method on the altered graph. Specified by:
getMatching
in interfaceMatchingAlgorithm<V,E>
 Returns:
 a matching of maximum cardinality.

isMaximumMatching
public boolean isMaximumMatching(MatchingAlgorithm.Matching<V,E> matching)
Checks whether the given matching is of maximum cardinality. A matching $m$ is maximum if there does not exist a different matching $m'$ in the graph which is of larger cardinality. This method is solely intended for verification purposes. Any matching returned by thegetMatching()
method in this class is guaranteed to be maximum.To attest whether the matching is maximum, we use the TutteBerge Formula which provides a tight bound on the cardinality of the matching. The TutteBerge Formula states: $m(G) = \frac{1}{2} \min_{X \subseteq V} ( X  c_{\text{odd}}(G  X) + V), where $m(G)$ is the size of the matching, $X$ a subset of vertices, $GX$ the induced graph on vertex set $V(G) \setminus X$, and $c_{\text{odd}}(G)$ the number of connected components of odd cardinality in graph $G$.
Note: to compute this bound, we do not iterate over all possible subsets $X$ (this would be too expensive). Instead, $X$ is computed as a byproduct of Edmonds' algorithm. Consequently, the runtime of this method equals the time required to test for the existence of a single augmenting path.
This method does NOT check whether the matching is valid. Parameters:
matching
 matching Returns:
 true if the matching is maximum, false otherwise.

