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>
public class GreedyMaximumCardinalityMatching<V,E> extends java.lang.Object implements 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
Constructors Constructor Description GreedyMaximumCardinalityMatching(Graph<V,E> graph, boolean sort)
Creates a new GreedyMaximumCardinalityMatching instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MatchingAlgorithm.Matching<V,E>
getMatching()
Get a matching that is a $\frac{1}{2}$-approximation of the maximum cardinality matching.
-
-
-
Method Detail
-
getMatching
public MatchingAlgorithm.Matching<V,E> 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
-
-