V
 the graph vertex typeE
 the graph edge typepublic class PathGrowingWeightedMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
The algorithm is due to Drake and Hougardy, described in detail in the following paper:
This particular implementation uses by default two additional heuristics discussed by the authors
which also take linear time but improve the quality of the matchings. These heuristics can be
disabled by calling the constructor PathGrowingWeightedMatching(Graph, boolean)
.
Disabling the heuristics has the effect of fewer passes over the edge set of the input graph,
probably at the expense of the total weight of the matching.
For a discussion on engineering approximate weighted matching algorithms see the following paper:
GreedyWeightedMatching
MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>
Modifier and Type  Field and Description 

static boolean 
DEFAULT_USE_HEURISTICS
Default value on whether to use extra heuristics to improve the result.

DEFAULT_EPSILON
Constructor and Description 

PathGrowingWeightedMatching(Graph<V,E> graph)
Construct a new instance of the path growing algorithm.

PathGrowingWeightedMatching(Graph<V,E> graph,
boolean useHeuristics)
Construct a new instance of the path growing algorithm.

PathGrowingWeightedMatching(Graph<V,E> graph,
boolean useHeuristics,
double epsilon)
Construct a new instance of the path growing algorithm.

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.

public static final boolean DEFAULT_USE_HEURISTICS
public PathGrowingWeightedMatching(Graph<V,E> graph)
MatchingAlgorithm.DEFAULT_EPSILON
tolerance. By default two additional linear time heuristics
are used in order to improve the quality of the matchings.graph
 the input graphpublic PathGrowingWeightedMatching(Graph<V,E> graph, boolean useHeuristics)
MatchingAlgorithm.DEFAULT_EPSILON
tolerance.graph
 the input graphuseHeuristics
 if true an improved version with additional heuristics is executed. The
running time remains linear but performs a few more passes over the input. While the
approximation factor remains $\frac{1}{2}$, in most cases the heuristics produce
matchings of higher quality.public PathGrowingWeightedMatching(Graph<V,E> graph, boolean useHeuristics, double epsilon)
graph
 the input graphuseHeuristics
 if true an improved version with additional heuristics is executed. The
running time remains linear but performs a few more passes over the input. While the
approximation factor remains $\frac{1}{2}$, in most cases the heuristics produce
matchings of higher quality.epsilon
 tolerance when comparing floating point valuespublic MatchingAlgorithm.Matching<V,E> getMatching()
getMatching
in interface MatchingAlgorithm<V,E>
Copyright © 2019. All rights reserved.