org.jgrapht.alg.matching

Class GreedyMaximumCardinalityMatching<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>

public class GreedyMaximumCardinalityMatching<V,E>
extends 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 and Description
GreedyMaximumCardinalityMatching(Graph<V,E> graph, boolean sort) Creates a new GreedyMaximumCardinalityMatching instance.

Method Summary

Modifier and Type	Method and Description
MatchingAlgorithm.Matching<V,E>	getMatching() Get a matching that is a $\frac{1}{2}$-approximation of the maximum cardinality matching.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GreedyMaximumCardinalityMatching

public GreedyMaximumCardinalityMatching(Graph<V,E> graph,
                                        boolean sort)

Creates a new GreedyMaximumCardinalityMatching instance.

Parameters:

graph - graph

sort - sort the edges prior to starting the greedy algorithm

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 interface MatchingAlgorithm<V,E>

Returns:

a matching