V
 the graph vertex typeE
 the graph edge typepublic class EdmondsMaximumCardinalityMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
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
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:
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:
MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>
DEFAULT_EPSILON
Constructor and Description 

EdmondsMaximumCardinalityMatching(Graph<V,E> graph)
Constructs a new instance of the algorithm.

EdmondsMaximumCardinalityMatching(Graph<V,E> graph,
MatchingAlgorithm<V,E> initializer)
Constructs a new instance of the algorithm.

Modifier and Type  Method and 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.

public EdmondsMaximumCardinalityMatching(Graph<V,E> graph)
GreedyMaximumCardinalityMatching
is used
to quickly generate a near optimal initial solution.graph
 undirected graph (graph does not have to be simple)public EdmondsMaximumCardinalityMatching(Graph<V,E> graph, MatchingAlgorithm<V,E> initializer)
graph
 undirected graph (graph does not have to be simple)initializer
 heuristic matching algorithm used to quickly generate a (near optimal)
initial feasible solution.public MatchingAlgorithm.Matching<V,E> getMatching()
getMatching
in interface MatchingAlgorithm<V,E>
public boolean isMaximumMatching(MatchingAlgorithm.Matching<V,E> matching)
getMatching()
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.
matching
 matchingCopyright © 2019. All rights reserved.