Package org.jgrapht.alg.matching
Class PathGrowingWeightedMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.PathGrowingWeightedMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class PathGrowingWeightedMatching<V,E> extends java.lang.Object implements MatchingAlgorithm<V,E>
A linear time $\frac{1}{2}$-approximation algorithm for finding a maximum weight matching in an arbitrary graph. Linear time here means $O(m)$ where m is the cardinality of the edge set, even if the graph contains isolated vertices. $\frac{1}{2}$-approximation means that for any graph instance, the algorithm computes a matching whose weight is at least half of the weight of a maximum weight matching. The 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 algorithm is due to Drake and Hougardy, described in detail in the following paper:
- D.E. Drake, S. Hougardy, A Simple Approximation Algorithm for the Weighted Matching Problem, Information Processing Letters 85, 211-213, 2003.
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:
- Jens Maue and Peter Sanders. Engineering algorithms for approximate weighted matching. International Workshop on Experimental and Efficient Algorithms, Springer, 2007.
- Author:
- Dimitrios Michail
- See Also:
GreedyWeightedMatching
-
-
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 Modifier and Type Field Description static boolean
DEFAULT_USE_HEURISTICS
Default value on whether to use extra heuristics to improve the result.-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Constructor Summary
Constructors Constructor 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.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MatchingAlgorithm.Matching<V,E>
getMatching()
Get a matching that is a $\frac{1}{2}$-approximation of the maximum weighted matching.
-
-
-
Field Detail
-
DEFAULT_USE_HEURISTICS
public static final boolean DEFAULT_USE_HEURISTICS
Default value on whether to use extra heuristics to improve the result.- See Also:
- Constant Field Values
-
-
Constructor Detail
-
PathGrowingWeightedMatching
public PathGrowingWeightedMatching(Graph<V,E> graph)
Construct a new instance of the path growing algorithm. Floating point values are compared usingMatchingAlgorithm.DEFAULT_EPSILON
tolerance. By default two additional linear time heuristics are used in order to improve the quality of the matchings.- Parameters:
graph
- the input graph
-
PathGrowingWeightedMatching
public PathGrowingWeightedMatching(Graph<V,E> graph, boolean useHeuristics)
Construct a new instance of the path growing algorithm. Floating point values are compared usingMatchingAlgorithm.DEFAULT_EPSILON
tolerance.- Parameters:
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.
-
PathGrowingWeightedMatching
public PathGrowingWeightedMatching(Graph<V,E> graph, boolean useHeuristics, double epsilon)
Construct a new instance of the path growing algorithm.- Parameters:
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 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 interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
-