Class DenseEdmondsMaximumCardinalityMatching<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
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 near-optimal 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 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 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 b-matching and f-factors, 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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Storage of the forest, even and odd levels.private static class
Simple representation of a matchingNested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<V,
E>, MatchingAlgorithm.MatchingImpl<V, E> -
Field Summary
FieldsModifier and TypeFieldDescriptionFor each odd vertex condensed into a blossom, a bridge is defined.private final MatchingAlgorithm
<V, E> Storage of the forest, even and odd levelsprivate int
private static final int
Special 'NIL' vertex.private int[]
Pre-allocated array which stores augmenting paths.private FixedSizeIntegerQueue
Queue of 'even' (exposed) verticesUnion-Find to store blossoms.private BitSet
private BitSet
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
Constructor Summary
ConstructorsConstructorDescriptionConstructs a new instance of the algorithm.DenseEdmondsMaximumCardinalityMatching
(Graph<V, E> graph, MatchingAlgorithm<V, E> initializer) Constructs a new instance of the algorithm. -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
augment()
Search for an augmenting path.private void
augment
(int v) Construct a path from vertex $v$ to the root of its tree, and use the resulting path to augment the matching.private void
blossom
(int v, int w) Creates a new blossom using bridge $(v,w)$.private void
blossomSupports
(int v, int w, int base) This method creates one side of the blossom: the path from vertex $v$ to the base of the blossom.private int
buildPath
(int[] path, int i, int start, int end) Builds the path backwards from the specified start vertex to the end vertex.Returns a matching of maximum cardinality.private void
init()
Prepares the data structuresboolean
isMaximumMatching
(MatchingAlgorithm.Matching<V, E> matching) Checks whether the given matching is of maximum cardinality.private int
nearestCommonAncestor
(int v, int w) Computes the base of the blossom formed by bridge edge $(v,w)$.private int
parent
(int v) Compute the nearest even ancestor of even node $v$.private void
reverse
(int[] path, int i, int j) Utility function to reverse part of an arrayprivate void
warmStart
(MatchingAlgorithm<V, E> initializer) Calculates an initial feasible matching.
-
Field Details
-
graph
-
initializer
-
vertices
-
vertexIndexMap
-
matching
-
matchedVertices
private int matchedVertices -
levels
Storage of the forest, even and odd levels -
NIL
private static final int NILSpecial 'NIL' vertex.- See Also:
-
queue
Queue of 'even' (exposed) vertices -
uf
Union-Find to store blossoms. -
bridges
For each odd vertex condensed into a blossom, a bridge is defined. Suppose the examination of edge $[v,w]$ causes a blossom to form containing odd vertex $x$. We define bridge(x) to be $[v,w]$ if $x$ is an ancestor of $v$ before the blossom is formed, or $[w,v]$ if $x$ is an ancestor of $w$. -
path
private int[] pathPre-allocated array which stores augmenting paths. -
vAncestors
-
wAncestors
-
-
Constructor Details
-
DenseEdmondsMaximumCardinalityMatching
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
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 Details
-
init
private void init()Prepares the data structures -
warmStart
Calculates an initial feasible matching.- Parameters:
initializer
- algorithm used to compute the initial matching
-
augment
private boolean augment()Search for an augmenting path.- Returns:
- true if an augmenting path was found, false otherwise
-
blossom
private void blossom(int v, int w) Creates a new blossom using bridge $(v,w)$. The blossom is an odd cycle. Nodes $v$ and $w$ are both even vertices.- Parameters:
v
- endpoint of the bridgew
- another endpoint the bridge
-
blossomSupports
private void blossomSupports(int v, int w, int base) This method creates one side of the blossom: the path from vertex $v$ to the base of the blossom. The vertices encountered on this path are grouped together (union). The odd vertices are added to the processing queue (odd vertices in a blossom become even) and a pointer to the bridge $(v,w)$ is stored for each odd vertex. Notice the orientation of the bridge: the first vertex of the bridge returned by bridge.get(x) is always on the same side of the blossom as $x$.- Parameters:
v
- an endpoint of the blossom bridgew
- another endpoint of the blossom bridgebase
- the base of the blossom
-
nearestCommonAncestor
private int nearestCommonAncestor(int v, int w) Computes the base of the blossom formed by bridge edge $(v,w)$. The base vertex is the nearest common ancestor of $v$ and $w$.- Parameters:
v
- one side of the bridgew
- other side of the bridge- Returns:
- base of the blossom
-
parent
private int parent(int v) Compute the nearest even ancestor of even node $v$. If $v$ is the root of a tree, then this method returns $v$ itself.- Parameters:
v
- even vertex- Returns:
- the nearest even ancestor of $v$
-
augment
private void augment(int v) Construct a path from vertex $v$ to the root of its tree, and use the resulting path to augment the matching.- Parameters:
v
- starting vertex (leaf in the tree)
-
buildPath
private int buildPath(int[] path, int i, int start, int end) Builds the path backwards from the specified start vertex to the end vertex. If the path reaches a blossom then the path through the blossom is lifted to the original graph.- Parameters:
path
- path storagei
- offset (in path)start
- start vertexend
- end vertex- Returns:
- the total length of the path.
-
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 re-invoke this method on the altered graph.- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,
E> - Returns:
- a matching of maximum cardinality.
-
isMaximumMatching
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 Tutte-Berge Formula which provides a tight bound on the cardinality of the matching. The Tutte-Berge 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, $G-X$ 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 by-product 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.
-
reverse
private void reverse(int[] path, int i, int j) Utility function to reverse part of an array
-