Class KolmogorovWeightedPerfectMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.KolmogorovWeightedPerfectMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class KolmogorovWeightedPerfectMatching<V,E> extends java.lang.Object implements MatchingAlgorithm<V,E>
This class computes weighted perfect matchings in general graphs using the Blossom V algorithm. If maximum or minimum weight matching algorithms is needed, seeKolmogorovWeightedMatching
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 weighted perfect matching problem the goal is to maximize or minimize the weighted sum of the edges in the 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 a maximum or minimum weight between two vertices can belong to the matching in the corresponding optimization problems. Currently, users are responsible for doing this reduction themselves before invoking the algorithm.
Note that if the graph is unweighted and dense,
SparseEdmondsMaximumCardinalityMatching
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
. During the construction time the objective sense of the optimization problem can be specified, i.e. whether to maximize of minimize the weight of the resulting perfect matching. Default objective sense of the algorithm is to minimize the weight of the resulting perfect matching. If the objective sense of the algorithm is to maximize the weight of the matching, the problem is reduced to minimum weight perfect matching problem by multiplying all edge weights by $-1$. This class supports retrieving statistics for the algorithm performance, seegetStatistics()
. 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 weighted perfect matching problem instance comes with a certificate of optimality, which is represented by a solution to a dual linear program; see
KolmogorovWeightedPerfectMatching.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 weighted perfect matching.Here we describe the certificates of optimality more precisely. Let the graph $G = (V, E)$ be an undirected graph with cost function $c: V \mapsto \mathbb{R}$ defined on it. Let $\mathcal{O}$ be the set of all subsets of $V$ of odd cardinality containing at least 3 vertices, and $\delta(S), S \subset V$ be the set of boundary edges of $V$. Then minimum weight perfect matching problem has the following linear programming formulation: \[ \begin{align} \mbox{minimize} \qquad & \sum_{e\in E}c_e \cdot x_e &\\ s.t. \qquad & \sum_{e\in \delta^(i)} x_e = 1 & \forall i\in V\\ & \sum_{e\in \delta(S)}x_e \ge 1 & \forall S\in \mathcal{O} \\ & x_e \ge 0 & \forall e\in E \end{align}\] The corresponding dual linear program has the following form: \[ \begin{align} \mbox{maximize} \qquad & \sum_{x \in V}y_e &\\ s.t. \qquad & y_u + y_v + \sum_{S\in \mathcal{O}: e \in \delta(S)}y_S \le c_e & \forall\ e = \{u, v\}\in E\\ & x_S \ge 0 & \forall S\in \mathcal{O} \end{align} \] Let's use the following notation: $slack(e) = c_e - y_u - y_v - \sum_{S\in \mathcal{O}: e \in \delta(S)}y_S$. Complementary slackness conditions have the following form: \[ \begin{align} slack(e) > 0 &\Rightarrow x_e = 0 \\ y_S > 0 &\Rightarrow \sum_{e\in \delta(S)}x_e = 1 \end{align} \] Therefore, the slacks of all edges will be non-negative and the slacks of matched edges will be $0$.
The maximum weight perfect matching problem has the following linear programming formulation: \[ \begin{align} \mbox{maximize} \qquad & \sum_{e\in E}c_e \cdot x_e &\\ s.t. \qquad &\sum_{e\in \delta^(i)} x_e = 1 & \forall i\in V\\ & \sum_{e\in \delta(S)}x_e \ge 1 & \forall S\in \mathcal{O} \\ & x_e \ge 0 & \forall e\in E \end{align} \] The corresponding dual linear program has the following form: \[ \begin{align} \mbox{minimize} \qquad & \sum_{x \in V}y_e &\\ s.t. \qquad & y_u + y_v + \sum_{S\in \mathcal{O}: e \in \delta(S)}y_S \ge c_e & \forall\ e = \{u, v\}\in E\\ & x_S \le 0 & \forall S\in \mathcal{O} \end{align} \] Complementary slackness conditions have the following form: \[ \begin{align} slack(e) < 0 &\Rightarrow x_e = 0 \\ y_S < 0 &\Rightarrow \sum_{e\in \delta(S)}x_e = 1 \end{align} \] Therefore, the slacks of all edges will be non-positive and the slacks of matched edges will be $0$.
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 viagetError()
. 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
KolmogorovWeightedPerfectMatching.DualSolution<V,E>
A solution to the dual linear program formulated on thegraph
static class
KolmogorovWeightedPerfectMatching.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-
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 (package private) static boolean
DEBUG
When set to true, verbose debugging output will be producedstatic BlossomVOptions
DEFAULT_OPTIONS
Default optionsprivate KolmogorovWeightedPerfectMatching.DualSolution<V,E>
dualSolution
Defines solution to the dual linear program formulated on thegraph
private BlossomVDualUpdater<V,E>
dualUpdater
Performs dual updates using the strategy defined by theoptions
static double
EPS
Default epsilon used in the algorithmprivate Graph<V,E>
graph
The graph we are matching onstatic double
INFINITY
Default infinity value used in the algorithmprivate Graph<V,E>
initialGraph
Initial graph specified during the construction timeprivate MatchingAlgorithm.Matching<V,E>
matching
The computed matching of thegraph
(package private) static java.lang.String
NO_PERFECT_MATCHING
Exception message if no perfect matching is possiblestatic double
NO_PERFECT_MATCHING_THRESHOLD
Defines the threshold for throwing an exception about no perfect matching existenceprivate ObjectiveSense
objectiveSense
The objective sense of the algorithm, i.e.private BlossomVOptions
options
BlossomVOptions used by the algorithm to match the problem instanceprivate BlossomVPrimalUpdater<V,E>
primalUpdater
Performs primal operations (grow, augment, shrink and expand)(package private) BlossomVState<V,E>
state
Current state of the algorithm-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Constructor Summary
Constructors Constructor Description KolmogorovWeightedPerfectMatching(Graph<V,E> graph)
Constructs a new instance of the algorithm using the default options.KolmogorovWeightedPerfectMatching(Graph<V,E> graph, BlossomVOptions options)
Constructs a new instance of the algorithm with the specifiedoptions
.KolmogorovWeightedPerfectMatching(Graph<V,E> graph, BlossomVOptions options, ObjectiveSense objectiveSense)
Constructs a new instance of the algorithm with the specifiedoptions
.KolmogorovWeightedPerfectMatching(Graph<V,E> graph, 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 private void
clearMarked()
Clears the marking of all nodes and pseudonodesprivate void
clearMarked(BlossomVNode node)
Clears the marking ofnode
and all its ancestors up until the first unmarked vertex is encounteredprivate void
finish()
Finishes the algorithm after all nodes are matched.private java.util.Set<V>
getBlossomNodes(BlossomVNode pseudonode, java.util.Map<BlossomVNode,java.util.Set<V>> blossomNodes)
Computes the set of original contracted vertices in thepseudonode
and puts computes value into theblossomNodes
.KolmogorovWeightedPerfectMatching.DualSolution<V,E>
getDualSolution()
Returns the computed solution to the dual linear program with respect to the weighted 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 weighted perfect matching in thegraph
.KolmogorovWeightedPerfectMatching.Statistics
getStatistics()
Returns the statistics describing the performance characteristics of the algorithm.private KolmogorovWeightedPerfectMatching.DualSolution<V,E>
lazyComputeDualSolution()
Computes a solution to a dual linear program formulated on the initial graph.private void
lazyComputeWeightedPerfectMatching()
Lazily runs the algorithm on the specified graph.private Pair<BlossomVNode,BlossomVNode>
lca(BlossomVNode a, BlossomVNode b)
Returns $(b, b)$ in the case where the verticesa
andb
have a common ancestor blossom $b$.private void
prepareForDualSolution()
Sets the blossomGrandparent references so that from a pseudonode we can make one step down to some node that belongs to that pseudonodeprivate void
printMap()
Debug methodprivate void
printState()
Prints the state of the algorithm.private void
printTrees()
Debug methodprivate void
setCurrentEdgesAndTryToAugment(BlossomVTree tree)
Sets the currentEdge and currentDirection variables for all trees adjacent to thetree
private double
testNonNegativity()
Tests whether a non-negative dual variable is assigned to every blossomboolean
testOptimality()
Performs an optimality test after the perfect matching is computed.private double
totalDual(BlossomVNode start, BlossomVNode end)
Computes the sum of all duals fromstart
inclusive toend
inclusive
-
-
-
Field Detail
-
EPS
public static final double EPS
Default epsilon used in the algorithm- See Also:
- Constant Field Values
-
INFINITY
public static final double INFINITY
Default infinity value used in the algorithm- See Also:
- Constant Field Values
-
NO_PERFECT_MATCHING_THRESHOLD
public static final double NO_PERFECT_MATCHING_THRESHOLD
Defines the threshold for throwing an exception about no perfect matching existence- See Also:
- Constant Field Values
-
DEFAULT_OPTIONS
public static final BlossomVOptions DEFAULT_OPTIONS
Default options
-
DEBUG
static final boolean DEBUG
When set to true, verbose debugging output will be produced- See Also:
- Constant Field Values
-
NO_PERFECT_MATCHING
static final java.lang.String NO_PERFECT_MATCHING
Exception message if no perfect matching is possible- See Also:
- Constant Field Values
-
initialGraph
private final Graph<V,E> initialGraph
Initial graph specified during the construction time
-
state
BlossomVState<V,E> state
Current state of the algorithm
-
primalUpdater
private BlossomVPrimalUpdater<V,E> primalUpdater
Performs primal operations (grow, augment, shrink and expand)
-
dualUpdater
private BlossomVDualUpdater<V,E> dualUpdater
Performs dual updates using the strategy defined by theoptions
-
matching
private MatchingAlgorithm.Matching<V,E> matching
The computed matching of thegraph
-
dualSolution
private KolmogorovWeightedPerfectMatching.DualSolution<V,E> dualSolution
Defines solution to the dual linear program formulated on thegraph
-
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 perfect matching
-
-
Constructor Detail
-
KolmogorovWeightedPerfectMatching
public KolmogorovWeightedPerfectMatching(Graph<V,E> graph)
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 perfect matching.- Parameters:
graph
- the graph for which to find a weighted perfect matching
-
KolmogorovWeightedPerfectMatching
public KolmogorovWeightedPerfectMatching(Graph<V,E> graph, 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 perfect matching depending on themaximize
parameter.- Parameters:
graph
- the graph for which to find a weighted perfect matchingobjectiveSense
- objective sense of the algorithm
-
KolmogorovWeightedPerfectMatching
public KolmogorovWeightedPerfectMatching(Graph<V,E> graph, BlossomVOptions options)
Constructs a new instance of the algorithm with the specifiedoptions
. The objective sense of the constructed algorithm is to minimize the weight of the resulting matching- Parameters:
graph
- the graph for which to find a weighted perfect matchingoptions
- the options which define the strategies for the initialization and dual updates
-
KolmogorovWeightedPerfectMatching
public KolmogorovWeightedPerfectMatching(Graph<V,E> graph, 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 perfect matching depending on themaximize
parameter.- Parameters:
graph
- the graph for which to find a weighted perfect 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 weighted perfect matching in thegraph
. See the class description for the relative definitions and algorithm description.- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a weighted perfect matching for the
graph
-
getDualSolution
public KolmogorovWeightedPerfectMatching.DualSolution<V,E> getDualSolution()
Returns the computed solution to the dual linear program with respect to the weighted perfect matching linear program formulation.- Returns:
- the solution to the dual linear program formulated on the
graph
-
testOptimality
public boolean testOptimality()
Performs an optimality test after the perfect matching is computed.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.
- 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. 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
-
lazyComputeWeightedPerfectMatching
private void lazyComputeWeightedPerfectMatching()
Lazily runs the algorithm on the specified graph.
-
setCurrentEdgesAndTryToAugment
private void setCurrentEdgesAndTryToAugment(BlossomVTree tree)
Sets the currentEdge and currentDirection variables for all trees adjacent to thetree
- Parameters:
tree
- the tree whose adjacent trees' variables are modified
-
testNonNegativity
private double testNonNegativity()
Tests whether a non-negative dual variable is assigned to every blossom- Returns:
- true iff the condition described above holds
-
totalDual
private double totalDual(BlossomVNode start, BlossomVNode end)
Computes the sum of all duals fromstart
inclusive toend
inclusive- Parameters:
start
- the node to start fromend
- the node to end with- Returns:
- the sum = start.dual + start.blossomParent.dual + ... + end.dual
-
lca
private Pair<BlossomVNode,BlossomVNode> lca(BlossomVNode a, BlossomVNode b)
Returns $(b, b)$ in the case where the verticesa
andb
have a common ancestor blossom $b$. Otherwise, returns the outermost parent blossoms of nodesa
andb
- Parameters:
a
- a vertex whose lca is to be found with respect to another vertexb
- the other vertex whose lca is to be found- Returns:
- either an lca blossom of
a
andb
or their outermost blossoms
-
clearMarked
private void clearMarked(BlossomVNode node)
Clears the marking ofnode
and all its ancestors up until the first unmarked vertex is encountered- Parameters:
node
- the node to start from
-
clearMarked
private void clearMarked()
Clears the marking of all nodes and pseudonodes
-
finish
private void finish()
Finishes the algorithm after all nodes are matched. The main problem it solves is that the matching after the end of primal and dual operations may not be valid in the contracted blossoms.Property: if a matching is changed in the parent blossom, the matching in all lower blossoms can become invalid. Therefore, we traverse all nodes, find an unmatched node (it is necessarily contracted), go up to the first blossom whose matching hasn't been fixed (we set blossomGrandparent references to point to the previous nodes on the path). Then we start to change the matching accordingly all the way down to the initial node.
Let's call an edge that is matched to a blossom root a "blossom edge". To make the matching valid we move the blossom edge one layer down at a time so that in the end its endpoints are valid initial nodes of the graph. After this transformation we can't traverse the blossomSibling references any more. That is why we initially compute a mapping of every pseudonode to the set of nodes that are contracted in it. This map is needed to construct a dual solution after the matching in the graph becomes valid.
-
prepareForDualSolution
private void prepareForDualSolution()
Sets the blossomGrandparent references so that from a pseudonode we can make one step down to some node that belongs to that pseudonode
-
getBlossomNodes
private java.util.Set<V> getBlossomNodes(BlossomVNode pseudonode, java.util.Map<BlossomVNode,java.util.Set<V>> blossomNodes)
Computes the set of original contracted vertices in thepseudonode
and puts computes value into theblossomNodes
. Ifnode
contains other pseudonodes which haven't been processed already, recursively computes the same set for them.- Parameters:
pseudonode
- the pseudonode whose contracted nodes are computedblossomNodes
- the mapping from pseudonodes to the original nodes contained in them
-
lazyComputeDualSolution
private KolmogorovWeightedPerfectMatching.DualSolution<V,E> lazyComputeDualSolution()
Computes a solution to a dual linear program formulated on the initial graph.- Returns:
- the solution to the dual linear program
-
printState
private void printState()
Prints the state of the algorithm. This is a debug method.
-
printTrees
private void printTrees()
Debug method
-
printMap
private void printMap()
Debug method
-
getStatistics
public KolmogorovWeightedPerfectMatching.Statistics getStatistics()
Returns the statistics describing the performance characteristics of the algorithm.- Returns:
- the statistics describing the algorithms characteristics
-
-