org.jgrapht.alg.matching

## Class GreedyWeightedMatching<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
All Implemented Interfaces:
MatchingAlgorithm<V,E>

```public class GreedyWeightedMatching<V,E>
extends Object
implements MatchingAlgorithm<V,E>```
The greedy algorithm for computing a maximum weight matching in an arbitrary graph. The algorithm is a 1/2-approximation algorithm and runs in O(n + m log n) where n is the number of vertices and m is the number of edges of the graph. This implementation accepts directed and undirected graphs which may contain self-loops and multiple edges. There is no assumption on the edge weights, i.e. they can also be negative or zero.

The greedy algorithm is the algorithm that first orders the edge set in non-increasing order of weights and then greedily constructs a maximal cardinality matching out of the edges with positive weight. A maximal cardinality matching (not to be confused with maximum cardinality) is a matching that cannot be increased in cardinality without removing an edge first.

For more information about approximation algorithms for the maximum weight matching problem in arbitrary graphs see:

• R. Preis, Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. Symposium on Theoretical Aspects of Computer Science, 259-269, 1999.
• D.E. Drake, S. Hougardy, A Simple Approximation Algorithm for the Weighted Matching Problem, Information Processing Letters 85, 211-213, 2003.
Since:
September 2016
Author:
Dimitrios Michail
`PathGrowingWeightedMatching`

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

`MatchingAlgorithm.Matching<E>, MatchingAlgorithm.MatchingImpl<E>`

• ### Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

`DEFAULT_EPSILON`
• ### Constructor Summary

Constructors
Constructor and Description
`GreedyWeightedMatching(Graph<V,E> graph)`
Create and execute a new instance of the greedy maximum weight matching algorithm.
```GreedyWeightedMatching(Graph<V,E> graph, double epsilon)```
Create and execute a new instance of the greedy maximum weight matching algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`MatchingAlgorithm.Matching<E>` `computeMatching()`
Get a matching that is a 1/2-approximation of the maximum weighted matching.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Methods inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

`getMatching`
• ### Constructor Detail

• #### GreedyWeightedMatching

`public GreedyWeightedMatching(Graph<V,E> graph)`
Create and execute a new instance of the greedy maximum weight matching algorithm. Floating point values are compared using `MatchingAlgorithm.DEFAULT_EPSILON` tolerance.
Parameters:
`graph` - the input graph
• #### GreedyWeightedMatching

```public GreedyWeightedMatching(Graph<V,E> graph,
double epsilon)```
Create and execute a new instance of the greedy maximum weight matching algorithm.
Parameters:
`graph` - the input graph
`epsilon` - tolerance when comparing floating point values
• ### Method Detail

• #### computeMatching

`public MatchingAlgorithm.Matching<E> computeMatching()`
Get a matching that is a 1/2-approximation of the maximum weighted matching.
Specified by:
`computeMatching` in interface `MatchingAlgorithm<V,E>`
Returns:
a matching