Module org.jgrapht.core
Package org.jgrapht.alg.matching.blossom.v5

Class BlossomVTree

  • class BlossomVTree
extends java.lang.Object
    This class is a data structure for Kolmogorov's Blossom V algorithm.

    Represents an alternating tree of tight edges which is used to find an augmenting path of tight edges in order to perform an augmentation and increase the cardinality of the matching. The nodes on odd layers are necessarily connected to their children via matched edges. Thus, these nodes have always exactly one child. The nodes on even layers can have arbitrarily many children.

    The tree structure information is contained in BlossomVNode, this class only contains the reference to the root of the tree. It also contains three heaps:

    • A heap of (+, inf) edges. These edges are also called infinity edges. If there exists a tight infinity edge, then it can be grown. Thus, this heap is used to determine an infinity edge of minimum slack.
    • A heap of (+, +) in-tree edges. These are edges between "+" nodes from the same tree. If a (+, +) in-tree edges is tight, it can be used to perform the shrink operation and introduce a new blossom. Thus, this heap is used to determine a (+, +) in-tree edge of minimum slack in a given tree.
    • A heap of "-" blossoms. If there exists a blossom with zero actual dual variable, it can be expanded. Thus, this heap is used to determine a "-" blossom with minimum dual variable

    Each tree contains a variable which accumulates dual changes applied to it. The dual changes aren't spread until a tree is destroyed by an augmentation. For every node in the tree its true dual variable is equal to node.dual + node.tree.eps if it is a "+" node; otherwise it equals node.dual - node.tree.eps. This applies only to the surface nodes that belong to some tree.

    This class also contains implementations of two iterators: BlossomVTree.TreeEdgeIterator and BlossomVTree.TreeNodeIterator. They are used to conveniently traverse the tree edges incident to a particular tree, and to traverse the nodes of a tree in a depth-first order.

    See Also:
    BlossomVNode, BlossomVTreeEdge, KolmogorovWeightedPerfectMatching

    • Field Detail

      • currentId

        private static int currentId
        Variable for debug purposes

      • first

        BlossomVTreeEdge[] first
        Two-element array of the first elements in the circular doubly linked lists of incident tree edges in each direction.

      • currentEdge

        BlossomVTreeEdge currentEdge
        This variable is used to quickly determine the edge between two trees during primal operations.

        Let $T$ be a tree that is being processed in the main loop. For every tree $T'$ that is adjacent to $T$ this variable is set to the BlossomVTreeEdge that connects both trees. This variable also helps to indicate whether a pair of trees is adjacent or not. This variable is set to null when no primal operation can be applied to the tree $T$.

      • currentDirection

        int currentDirection
        Direction of the tree edge connecting this tree and the currently processed tree

      • eps

        double eps
        Dual change that hasn't been spread among the nodes in this tree. This technique is called lazy delta spreading

      • accumulatedEps

        double accumulatedEps
        Accumulated dual change. Is used during dual updates

      • nextTree

        BlossomVTree nextTree
        Next tree in the connected component, is used during updating the duals via connected components

      • plusPlusEdges

        org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVEdge> plusPlusEdges
        The heap of (+,+) edges of this tree

      • plusInfinityEdges

        org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVEdge> plusInfinityEdges
        The heap of (+, inf) edges of this tree

      • minusBlossoms

        org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVNode> minusBlossoms
        The heap of "-" blossoms of this tree

      • id

        int id
        Variable for debug purposes

    • Constructor Detail

      • BlossomVTree

        public BlossomVTree()
        Empty constructor

      • BlossomVTree

        public BlossomVTree​(BlossomVNode root)
        Constructs a new tree with the root
        Parameters:
        root - the root of this tree

    • Method Detail

      • addTreeEdge

        public static BlossomVTreeEdge addTreeEdge​(BlossomVTree from,
                                           BlossomVTree to)
        Adds a new tree edge from from to to. Sets the to.currentEdge and to.currentDirection with respect to the tree from
        Parameters:
        from - the tail of the directed tree edge
        to - the head of the directed tree edge

      • setCurrentEdges

        public void setCurrentEdges()
        Sets the currentEdge and currentDirection variables for all trees adjacent to this tree

      • clearCurrentEdges

        public void clearCurrentEdges()
        Clears the currentEdge variable of all adjacent to the tree trees

      • printTreeNodes

        public void printTreeNodes()
        Prints all the nodes of this tree

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • addPlusPlusEdge

        public void addPlusPlusEdge​(BlossomVEdge edge)
        Ensures correct addition of an edge to the heap
        Parameters:
        edge - a (+, +) edge

      • addPlusInfinityEdge

        public void addPlusInfinityEdge​(BlossomVEdge edge)
        Ensures correct addition of an edge to the heap
        Parameters:
        edge - a (+, inf) edge

      • addMinusBlossom

        public void addMinusBlossom​(BlossomVNode blossom)
        Ensures correct addition of a blossom to the heap
        Parameters:
        blossom - a "-" blossom

      • removePlusPlusEdge

        public void removePlusPlusEdge​(BlossomVEdge edge)
        Removes the edge from the heap of (+, +) edges
        Parameters:
        edge - the edge to remove

      • removePlusInfinityEdge

        public void removePlusInfinityEdge​(BlossomVEdge edge)
        Removes the edge from the heap of (+, inf) edges
        Parameters:
        edge - the edge to remove

      • removeMinusBlossom

        public void removeMinusBlossom​(BlossomVNode blossom)
        Removes the blossom from the heap of "-" blossoms
        Parameters:
        blossom - the blossom to remove

      • treeNodeIterator

        public BlossomVTree.TreeNodeIterator treeNodeIterator()
        Returns a new instance of TreeNodeIterator for this tree
        Returns:
        new TreeNodeIterator for this tree

      • treeEdgeIterator

        public BlossomVTree.TreeEdgeIterator treeEdgeIterator()
        Returns a new instance of TreeEdgeIterator for this tree
        Returns:
        new TreeEdgeIterators for this tree