Class BlossomVDualUpdater<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    class BlossomVDualUpdater<V,​E>
    extends java.lang.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:
    BlossomVPrimalUpdater, KolmogorovWeightedPerfectMatching
    • Field Detail

      • 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.
    • 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 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.