- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.BlossomVDualUpdater<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
class BlossomVDualUpdater<V,E> extends java.lang.Object
This class is used byKolmogorovWeightedPerfectMatching
to perform dual updates, thus increasing the dual objective function value and creating new tight edges.This class currently supports three types of dual updates: single tree, multiple trees fixed delta, and multiple tree variable delta. The first one is used to updates duals of a single tree, when at least one of the
BlossomVOptions.updateDualsBefore
orBlossomVOptions.updateDualsAfter
is true. The latter two are used to update the duals globally and are defined by theBlossomVOptions
.There are two type of constraints on a dual change of a tree: in-tree and cross-tree. In-tree constraints are imposed by the infinity edges, (+, +) in-tree edges and "-" blossoms. Cross-tree constraints are imposed by (+, +), (+, -) and (-, +) cross-tree edges. With respect to this classification of constraints the following strategies of changing the duals can be used:
- Single tree strategy greedily increases the duals of the tree with respect to the in-tree and cross-tree constraints. This can result in a zero-change update. If a tight (+, +) cross-tree edge is encountered during this operation, an immediate augmentation is performed afterwards.
- Multiple tree fixed delta approach considers only in-tree constraints and constraints imposed by the (+, +) cross-tree edges. Since this approach increases the trees' epsilons by the same amount, it doesn't need to consider other two dual constraints. If a tight (+, +) cross-tree edge is encountered during this operation, an immediate augmentation is performed afterwards.
- Multiple tree variable delta approach considers all types of constraints. It determines a connected components in the auxiliary graph, where only tight (-, +) and (+, -) cross-tree edges are present. For these connected components it computes the same dual change, therefore the constraints imposed by the (-, +) and (+, -) cross-tree edges can't be violated. If a tight (+, +) cross-tree edge is encountered during this operation, an immediate augmentation is performed afterwards.
-
-
Field Summary
Fields Modifier and Type Field Description private BlossomVPrimalUpdater<V,E>
primalUpdater
Instance ofBlossomVPrimalUpdater
for performing immediate augmentations after dual updates when they are applicable.private BlossomVState<V,E>
state
State information needed for the algorithm
-
Constructor Summary
Constructors Constructor Description BlossomVDualUpdater(BlossomVState<V,E> state, BlossomVPrimalUpdater<V,E> primalUpdater)
Creates a new instance of the BlossomVDualUpdater
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private double
getEps(BlossomVTree tree)
Computes and returns the value which can be assigned to thetree.eps
so that it doesn't violate in-tree constraints.private BlossomVEdge
multipleTreeFixedDelta()
Updates duals by iterating through trees and greedily increasing their dual variables.double
updateDuals(BlossomVOptions.DualUpdateStrategy type)
Performs global dual update.private BlossomVEdge
updateDualsConnectedComponents()
Updates the duals via connected components.boolean
updateDualsSingle(BlossomVTree tree)
Updates the duals of the single tree.
-
-
-
Field Detail
-
state
private BlossomVState<V,E> state
State information needed for the algorithm
-
primalUpdater
private BlossomVPrimalUpdater<V,E> primalUpdater
Instance ofBlossomVPrimalUpdater
for performing immediate augmentations after dual updates when they are applicable. These speed up the overall algorithm.
-
-
Constructor Detail
-
BlossomVDualUpdater
public BlossomVDualUpdater(BlossomVState<V,E> state, BlossomVPrimalUpdater<V,E> primalUpdater)
Creates a new instance of the BlossomVDualUpdater- Parameters:
state
- the state common toBlossomVPrimalUpdater
,BlossomVDualUpdater
andKolmogorovWeightedPerfectMatching
primalUpdater
- primal updater used by the algorithm
-
-
Method Detail
-
updateDuals
public double updateDuals(BlossomVOptions.DualUpdateStrategy type)
Performs global dual update. Operates on the whole graph and updates duals according to the strategy defined byBlossomVOptions.dualUpdateStrategy
.- Parameters:
type
- the strategy to use for updating the duals- Returns:
- the sum of all changes of dual variables of the trees
-
getEps
private double getEps(BlossomVTree tree)
Computes and returns the value which can be assigned to thetree.eps
so that it doesn't violate in-tree constraints. In other words,getEps(tree) - tree.eps
is the resulting dual change wrt. in-tree constraints. The computed value is always greater than or equal to thetree.eps
, can violate the cross-tree constraints, and can be equal toKolmogorovWeightedPerfectMatching.INFINITY
.- Parameters:
tree
- the tree to process- Returns:
- a value which can be safely assigned to tree.eps
-
updateDualsSingle
public boolean updateDualsSingle(BlossomVTree tree)
Updates the duals of the single tree. This method takes into account both in-tree and cross-tree constraints. If possible, it also finds a cross-tree (+, +) edge of minimum slack and performs an augmentation.- Parameters:
tree
- the tree to update duals of- Returns:
- true iff some progress was made and there was no augmentation performed, false otherwise
-
updateDualsConnectedComponents
private BlossomVEdge updateDualsConnectedComponents()
Updates the duals via connected components. The connected components are a set of trees which are connected via tight (+, -) cross tree edges. For these components the same dual change is chosen. As a result, the circular constraints are guaranteed to be avoided. This is the point where theupdateDualsSingle(org.jgrapht.alg.matching.blossom.v5.BlossomVTree)
approach can fail.
-
multipleTreeFixedDelta
private BlossomVEdge multipleTreeFixedDelta()
Updates duals by iterating through trees and greedily increasing their dual variables.
-
-