V - the graph vertex typeE - the graph edge typepublic class KolmogorovMinimumWeightPerfectMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
Let $G = (V, E, c)$ be an undirected graph with a real-valued cost function defined on it. A matching is an edge-disjoint subset of edges $M \subseteq E$. A matching is perfect if $2|M| = |V|$. In the minimum weight perfect matching problem the goal is to minimize the weighted sum of the edges in the perfect matching. This class supports pseudographs, but a problem on a pseudograph can be easily reduced to a problem on a simple graph. Moreover, this reduction can heavily influence the running time since only an edge with minimum weight between two vertices can belong to the matching. Currently, users are responsible for doing this reduction themselves before invoking the algorithm.
Note that if the graph is unweighted and dense, EdmondsMaximumCardinalityMatching may be
a better choice.
For more information about the algorithm see the following paper: Kolmogorov, V. Math. Prog. Comp. (2009) 1: 43. https://doi.org/10.1007/s12532-009-0002-8, and the original implementation: http://pub.ist.ac.at/~vnk/software/blossom5-v2.05.src.tar.gz
The algorithm can be divided into two phases: initialization and the main algorithm. The initialization phase is responsible for converting the specified graph into the form convenient for the algorithm and for finding an initial matching to speed up the main part. Furthermore, the main part of the algorithm can be further divided into primal and dual updates. The primal phases are aimed at augmenting the matching so that the value of the objective function of the primal linear program increases. Dual updates are aimed at increasing the objective function of the dual linear program. The algorithm iteratively performs these primal and dual operations to build alternating trees of tight edges and augment the matching. Thus, at any stage of the algorithm the matching consists of tight edges. This means that the resulting perfect matching meets complementary slackness conditions, and is therefore optimal.
At construction time the set of options can be specified to define the strategies used by the
algorithm to perform initialization, dual updates, etc. This can be done with the
BlossomVOptions. This class supports retrieving statistics for the algorithm performance;
see getStatistics(). It provides the time elapsed
during primal operations and dual updates, as well as the number of these primal operations
performed.
The solution to a minimum weight perfect matching problem instance comes with a certificate of
optimality, which is represented by a solution to a dual linear program; see
KolmogorovMinimumWeightPerfectMatching.DualSolution. This class encapsulates a mapping from the node sets of odd cardinality to
the corresponding dual variables. This mapping doesn't contain the sets whose dual variables are
$0$. The computation of the dual solution is performed lazily and doesn't affect the running time
of finding a minimum weight perfect matching.
This class supports testing the optimality of the solution via
testOptimality(). It also supports retrieval of
the computation error when the edge weights are real values via
getError(). Both optimality test and error
computation are performed lazily and don't affect the running time of the main algorithm. If the
problem instance doesn't contain a perfect matching at all, the algorithm doesn't find a minimum
weight maximum matching; instead, it throws an exception.
BlossomVPrimalUpdater,
BlossomVDualUpdater| Modifier and Type | Class and Description |
|---|---|
static class |
KolmogorovMinimumWeightPerfectMatching.DualSolution<V,E>
A solution to the dual linear program formulated on the
graph |
static class |
KolmogorovMinimumWeightPerfectMatching.Statistics
Describes the performance characteristics of the algorithm and numeric data about the number
of performed dual operations during the main phase of the algorithm
|
MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>| Modifier and Type | Field and Description |
|---|---|
static double |
EPS
Default epsilon used in the algorithm
|
static double |
INFINITY
Default infinity value used in the algorithm
|
static double |
NO_PERFECT_MATCHING_THRESHOLD
Defines the threshold for throwing an exception about no perfect matching existence
|
DEFAULT_EPSILON| Constructor and Description |
|---|
KolmogorovMinimumWeightPerfectMatching(Graph<V,E> graph)
Constructs a new instance of the algorithm using the default options.
|
KolmogorovMinimumWeightPerfectMatching(Graph<V,E> graph,
BlossomVOptions options)
Constructs a new instance of the algorithm with the specified
options |
| Modifier and Type | Method and Description |
|---|---|
KolmogorovMinimumWeightPerfectMatching.DualSolution<V,E> |
getDualSolution()
Returns the computed solution to the dual linear program with respect to the minimum weight
perfect matching linear program formulation.
|
double |
getError()
Computes the error in the solution to the dual linear program.
|
MatchingAlgorithm.Matching<V,E> |
getMatching()
Computes and returns a minimum weight perfect matching in the
graph. |
KolmogorovMinimumWeightPerfectMatching.Statistics |
getStatistics()
Returns the statistics describing the performance characteristics of the algorithm.
|
boolean |
testOptimality()
Performs an optimality test after the perfect matching is computed.
|
public static final double EPS
public static final double INFINITY
public static final double NO_PERFECT_MATCHING_THRESHOLD
public KolmogorovMinimumWeightPerfectMatching(Graph<V,E> graph)
graph - the graph for which to find a minimum weight perfect matchingpublic KolmogorovMinimumWeightPerfectMatching(Graph<V,E> graph, BlossomVOptions options)
optionsgraph - the graph for which to find a minimum weight perfect matchingoptions - the options which define the strategies for the initialization and dual
updatespublic MatchingAlgorithm.Matching<V,E> getMatching()
graph. See the class
description for the relative definitions and algorithm description.getMatching in interface MatchingAlgorithm<V,E>graphpublic KolmogorovMinimumWeightPerfectMatching.DualSolution<V,E> getDualSolution()
graphpublic boolean 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
EPS
In general, this method should always return true unless the algorithm implementation has a bug.
public double getError()
public KolmogorovMinimumWeightPerfectMatching.Statistics getStatistics()
Copyright © 2018. All rights reserved.