 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
MatchingAlgorithm<V,
E>
This algorithm can be run in two modes: with and without edge cost normalization. Without
normalization, the algorithm first orders the edge set in nonincreasing 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 nonincreasing 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, 259269, 1999.
 D.E. Drake, S. Hougardy, A Simple Approximation Algorithm for the Weighted Matching Problem, Information Processing Letters 85, 211213, 2003.
 Author:
 Dimitrios Michail
 See Also:

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
ConstructorDescriptionGreedyWeightedMatching
(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 TypeMethodDescriptionGet a matching that is a $\frac{1}{2}$approximation of the maximum weighted matching.

Constructor Details

GreedyWeightedMatching
Create and execute a new instance of the greedy maximum weight matching algorithm. Floating point values are compared usingMatchingAlgorithm.DEFAULT_EPSILON
tolerance. Parameters:
graph
 the input graphnormalizeEdgeCosts
 boolean indicating whether edge normalization has to be used.

GreedyWeightedMatching
Create and execute a new instance of the greedy maximum weight matching algorithm. Parameters:
graph
 the input graphnormalizeEdgeCosts
 boolean indicating whether edge normalization has to be used.epsilon
 tolerance when comparing floating point values


Method Details

getMatching
Get a matching that is a $\frac{1}{2}$approximation of the maximum weighted matching. Specified by:
getMatching
in interfaceMatchingAlgorithm<V,
E>  Returns:
 a matching
