Class BlossomVDualUpdater<V,E>

java.lang.Object
org.jgrapht.alg.matching.blossom.v5.BlossomVDualUpdater<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type

class BlossomVDualUpdater<V,E> extends Object
This class is used by KolmogorovWeightedPerfectMatching 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 or BlossomVOptions.updateDualsAfter is true. The latter two are used to update the duals globally and are defined by the BlossomVOptions.

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.
See Also:
  • Field Details

    • state

      private BlossomVState<V,E> state
      State information needed for the algorithm
    • primalUpdater

      private BlossomVPrimalUpdater<V,E> primalUpdater
      Instance of BlossomVPrimalUpdater for performing immediate augmentations after dual updates when they are applicable. These speed up the overall algorithm.
  • Constructor Details

  • Method Details

    • updateDuals

      public double updateDuals(BlossomVOptions.DualUpdateStrategy type)
      Performs global dual update. Operates on the whole graph and updates duals according to the strategy defined by BlossomVOptions.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 the tree.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 the tree.eps, can violate the cross-tree constraints, and can be equal to KolmogorovWeightedPerfectMatching.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 the updateDualsSingle(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.