org.jgrapht.alg.matching

Class GreedyWeightedMatching<V,E>

java.lang.Object

org.jgrapht.alg.matching.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.

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

• 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

See Also:

PathGrowingWeightedMatching

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
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

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