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 runs in $O(m + 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 (parallel) edges. There is no assumption on the edge weights, i.e. they can also be negative or zero.

This algorithm can be run in two modes: with and without edge cost normalization. Without normalization, the algorithm 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. The resulting matching is guaranteed to be a $\frac{1}{2}$-Approximation.
With normalization, the edges are sorted in non-increasing order of their normalized costs $\frac{c(u,v)}{d(u)+d(v)}$ instead, after which the algorithm proceeds in the same manner. Here, $c(u,v)$ is the cost of edge $(u,v)$, and $d(u)$ resp $d(v)$ are the degrees of vertices $u$ resp $v$. Running this algorithm in normalized mode often (but not always!) produces a better result than running the algorithm without normalization. Note however that the normalized version does NOT produce a $\frac{1}{2}$-approximation. See this proof for details. The runtime complexity remains the same, independent of whether normalization is used.

• R. Preis, Linear Time $\frac{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.
Author:
Dimitrios Michail
PathGrowingWeightedMatching

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

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

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

DEFAULT_EPSILON
• ### Constructor Summary

Constructors
Constructor and Description
GreedyWeightedMatching(Graph<V,E> graph, boolean normalizeEdgeCosts)
Create and execute a new instance of the greedy maximum weight matching algorithm.
GreedyWeightedMatching(Graph<V,E> graph, boolean normalizeEdgeCosts, 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<V,E> getMatching()
Get a matching that is a $\frac{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
• ### Constructor Detail

• #### GreedyWeightedMatching

public GreedyWeightedMatching(Graph<V,E> graph,
boolean normalizeEdgeCosts)
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
normalizeEdgeCosts - boolean indicating whether edge normalization has to be used.
• #### GreedyWeightedMatching

public GreedyWeightedMatching(Graph<V,E> graph,
boolean normalizeEdgeCosts,
double epsilon)
Create and execute a new instance of the greedy maximum weight matching algorithm.
Parameters:
graph - the input graph
normalizeEdgeCosts - boolean indicating whether edge normalization has to be used.
epsilon - tolerance when comparing floating point values
• ### Method Detail

• #### getMatching

public MatchingAlgorithm.Matching<V,E> getMatching()
Get a matching that is a $\frac{1}{2}$-approximation of the maximum weighted matching.
Specified by:
getMatching in interface MatchingAlgorithm<V,E>
Returns:
a matching