org.jgrapht.alg.matching.blossom.v5

Class KolmogorovWeightedMatching<V,E>

java.lang.Object

org.jgrapht.alg.matching.blossom.v5.KolmogorovWeightedMatching<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>

public class KolmogorovWeightedMatching<V,E>
extends 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, see KolmogorovWeightedPerfectMatching.

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

Author:

Timofey Chudakov

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 inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

DEFAULT_EPSILON

Constructor Summary

Constructors

Constructor and 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 specified options.
KolmogorovWeightedMatching(Graph<V,E> initialGraph, BlossomVOptions options, ObjectiveSense objectiveSense) Constructs a new instance of the algorithm with the specified options.
KolmogorovWeightedMatching(Graph<V,E> initialGraph, ObjectiveSense objectiveSense) Constructs a new instance of the algorithm using the default options.

Method Summary

Modifier and Type	Method and 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 the initialGraph depending on the goal of the algorithm.
boolean	testOptimality() Performs an optimality test after the perfect matching is computed.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 the maximize parameter.

Parameters:

initialGraph - the graph for which to find a weighted matching

objectiveSense - objective sense of the algorithm

KolmogorovWeightedMatching

public KolmogorovWeightedMatching(Graph<V,E> initialGraph,
                                  BlossomVOptions options)

Constructs a new instance of the algorithm with the specified 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

options - 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 specified options. The goal of the constructed algorithm is to maximize or minimize the weight of the resulting matching depending on the maximize parameter.

Parameters:

initialGraph - the graph for which to find a weighted matching

options - the options which define the strategies for the initialization and dual updates

objectiveSense - 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 the initialGraph depending on the goal of the algorithm.

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

weighted matching in the initialGraph

testOptimality

public boolean testOptimality()

Performs an optimality test after the perfect matching is computed. This test is done via KolmogorovWeightedPerfectMatching.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 via KolmogorovWeightedPerfectMatching.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