Module org.jgrapht.core
Package org.jgrapht.alg.matching
Class GreedyMaximumCardinalityMatching<V,E>
java.lang.Object
org.jgrapht.alg.matching.GreedyMaximumCardinalityMatching<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
MatchingAlgorithm<V,
E>
The greedy algorithm for computing a maximum cardinality matching. The algorithm can run in two
modes: sorted or unsorted. When unsorted, the matching is obtained by iterating through the edges
and adding an edge if it doesn't conflict with the edges already in the matching. When sorted,
the edges are first sorted by the sum of degrees of their endpoints. After that, the algorithm
proceeds in the same manner. Running this algorithm in sorted mode can sometimes produce better
results, albeit at the cost of some additional computational overhead.
Independent of the mode, the resulting matching is maximal, and is therefore guaranteed to contain at least half of the edges that a maximum cardinality matching has ($\frac{1}{2}$ approximation). Runtime complexity: $O(m)$ when the edges are not sorted, $O(m + m \log n)$ otherwise, where $n$ is the number of vertices, and $m$ the number of edges.
 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
ConstructorDescriptionGreedyMaximumCardinalityMatching
(Graph<V, E> graph, boolean sort) Creates a new GreedyMaximumCardinalityMatching instance. 
Method Summary
Modifier and TypeMethodDescriptionGet a matching that is a $\frac{1}{2}$approximation of the maximum cardinality matching.

Constructor Details

GreedyMaximumCardinalityMatching
Creates a new GreedyMaximumCardinalityMatching instance. Parameters:
graph
 graphsort
 sort the edges prior to starting the greedy algorithm


Method Details

getMatching
Get a matching that is a $\frac{1}{2}$approximation of the maximum cardinality matching. Specified by:
getMatching
in interfaceMatchingAlgorithm<V,
E>  Returns:
 a matching
