Module org.jgrapht.core
Class KolmogorovWeightedMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.KolmogorovWeightedMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class KolmogorovWeightedMatching<V,E> extends java.lang.Object implements MatchingAlgorithm<V,E>
This class computes weighted matchings in general graphs. Depending on the constructor parameter the weight of the resulting matching is maximized or minimized. If maximum of minimum weight perfect algorithm is needed, seeKolmogorovWeightedPerfectMatching
.This class reduces both maximum and minimum weight matching problems to the maximum and minimum weight perfect matching problems correspondingly. See
KolmogorovWeightedPerfectMatching
for relative definitions and algorithm description- See Also:
KolmogorovWeightedPerfectMatching
-
-
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 private Graph<V,E>
graph
The graph created during the reductionprivate Graph<V,E>
initialGraph
The graph we are matching onprivate MatchingAlgorithm.Matching<V,E>
matching
The computed matching of thegraph
private ObjectiveSense
objectiveSense
The objective sense of the algorithm, i.e.private BlossomVOptions
options
BlossomVOptions used by the algorithm to match the problem instanceprivate KolmogorovWeightedPerfectMatching<V,E>
perfectMatching
The perfect matching algorithm used during for the problem reduction-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Constructor Summary
Constructors Constructor Description KolmogorovWeightedMatching(Graph<V,E> initialGraph)
Constructs a new instance of the algorithm using the default options.KolmogorovWeightedMatching(Graph<V,E> initialGraph, BlossomVOptions options)
Constructs a new instance of the algorithm with the specifiedoptions
.KolmogorovWeightedMatching(Graph<V,E> initialGraph, BlossomVOptions options, ObjectiveSense objectiveSense)
Constructs a new instance of the algorithm with the specifiedoptions
.KolmogorovWeightedMatching(Graph<V,E> initialGraph, ObjectiveSense objectiveSense)
Constructs a new instance of the algorithm using the default options.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
getError()
Computes the error in the solution to the dual linear program.MatchingAlgorithm.Matching<V,E>
getMatching()
Computes and returns a matching of maximum or minimum weight in theinitialGraph
depending on the goal of the algorithm.private void
lazyComputeMaximumWeightMatching()
Lazy computes optimal matching in theinitialGraph
by reducing the problem to the optimal perfect matching problem.boolean
testOptimality()
Performs an optimality test after the perfect matching is computed.
-
-
-
Field Detail
-
matching
private MatchingAlgorithm.Matching<V,E> matching
The computed matching of thegraph
-
perfectMatching
private KolmogorovWeightedPerfectMatching<V,E> perfectMatching
The perfect matching algorithm used during for the problem reduction
-
options
private BlossomVOptions options
BlossomVOptions used by the algorithm to match the problem instance
-
objectiveSense
private ObjectiveSense objectiveSense
The objective sense of the algorithm, i.e. whether to maximize or minimize the weight of the resulting matching
-
-
Constructor Detail
-
KolmogorovWeightedMatching
public KolmogorovWeightedMatching(Graph<V,E> initialGraph)
Constructs a new instance of the algorithm using the default options. The goal of the constructed algorithm is to minimize the weight of the resulting matching.- Parameters:
initialGraph
- the graph for which to find a weighted matching
-
KolmogorovWeightedMatching
public KolmogorovWeightedMatching(Graph<V,E> initialGraph, ObjectiveSense objectiveSense)
Constructs a new instance of the algorithm using the default options. The goal of the constructed algorithm is to maximize or minimize the weight of the resulting matching depending on themaximize
parameter.- Parameters:
initialGraph
- the graph for which to find a weighted matchingobjectiveSense
- objective sense of the algorithm
-
KolmogorovWeightedMatching
public KolmogorovWeightedMatching(Graph<V,E> initialGraph, BlossomVOptions options)
Constructs a new instance of the algorithm with the specifiedoptions
. The goal of the constructed algorithm is to minimize the weight of the resulting matching.- Parameters:
initialGraph
- the graph for which to find a weighted matchingoptions
- the options which define the strategies for the initialization and dual updates
-
KolmogorovWeightedMatching
public KolmogorovWeightedMatching(Graph<V,E> initialGraph, BlossomVOptions options, ObjectiveSense objectiveSense)
Constructs a new instance of the algorithm with the specifiedoptions
. The goal of the constructed algorithm is to maximize or minimize the weight of the resulting matching depending on themaximize
parameter.- Parameters:
initialGraph
- the graph for which to find a weighted matchingoptions
- the options which define the strategies for the initialization and dual updatesobjectiveSense
- objective sense of the algorithm
-
-
Method Detail
-
getMatching
public MatchingAlgorithm.Matching<V,E> getMatching()
Computes and returns a matching of maximum or minimum weight in theinitialGraph
depending on the goal of the algorithm.- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- weighted matching in the
initialGraph
-
lazyComputeMaximumWeightMatching
private void lazyComputeMaximumWeightMatching()
Lazy computes optimal matching in theinitialGraph
by reducing the problem to the optimal perfect matching problem.
-
testOptimality
public boolean testOptimality()
Performs an optimality test after the perfect matching is computed. This test is done viaKolmogorovWeightedPerfectMatching.testOptimality()
More precisely, checks whether dual variables of all pseudonodes and resulting slacks of all edges are non-negative and that slacks of all matched edges are exactly 0. Since the algorithm uses floating point arithmetic, this check is done with precision of
KolmogorovWeightedPerfectMatching.EPS
In general, this method should always return true unless the algorithm implementation has a bug.
- Returns:
- true iff the assigned dual variables satisfy the dual linear program formulation AND complementary slackness conditions are also satisfied. The total error must not exceed EPS
-
getError
public double getError()
Computes the error in the solution to the dual linear program. This computation is done viaKolmogorovWeightedPerfectMatching.getError()
. More precisely, the total error equals the sum of:- Absolute value of edge slack if negative or the edge is matched
- Absolute value of pseudonode variable if negative
- Returns:
- the total numeric error
-
-