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

Class BlossomVTreeEdge

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

    Is used to maintain an auxiliary graph whose nodes correspond to alternating trees in the Blossom V algorithm. Let's denote the current tree $T$ and some other tree $T'$. Every tree edge contains three heaps:

    1. a heap of (+, +) cross-tree edges. This heap contains all edges between two "+" nodes where one node belongs to tree $T$ and another to $T'$. The (+, +) cross-tree edges are used to augment the matching.
    2. a heap of (+, -) cross-tree edges
    3. a heap of (-, +) cross-tree edges
    Note: from the tree edge perspective there is no difference between a heap of (+, -) and (-, +) cross-tree edges. That's why we distinguish these heaps by the direction of the edge. Here the direction is considered with respect to the trees $T$ and $T'$ based upon the notation introduced above.

    Every tree edge is directed from one tree to another and every tree edge belongs to the two doubly linked lists of tree edges. The presence of a tree edge in these lists in maintained by the two-element arrays prev and next. For one tree the edge is an outgoing tree edge; for the other, an incoming. In the first case it belongs to the tree.first[0] linked list; in the second, to the tree.first[1] linked list.

    Let tree be a tail of the edge, and oppositeTree a head of the edge. Then edge.head[0] == oppositeTree and edge.head[1] == tree.

    See Also:
    KolmogorovWeightedPerfectMatching, BlossomVTree, BlossomVEdge

    • Field Detail

      • head

        BlossomVTree[] head
        Two-element array of trees this edge is incident to.

      • prev

        BlossomVTreeEdge[] prev
        A two-element array of references to the previous elements in the circular doubly linked lists of tree edges. The lists are circular with one exception: the lastElement.next[dir] == null. Each list belongs to one of the endpoints of this edge.

      • next

        BlossomVTreeEdge[] next
        A two-element array of references to the next elements in the circular doubly linked lists of tree edges. The lists are circular with one exception: the lastElementInTheList.next[dir] == null. Each list belongs to one of the endpoints of this edge.

      • plusPlusEdges

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

      • plusMinusEdges0

        org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVEdge> plusMinusEdges0
        A heap of (-, +) cross-tree edges

      • plusMinusEdges1

        org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVEdge> plusMinusEdges1
        A heap of (+, -) cross-tree edges

    • Constructor Detail

      • BlossomVTreeEdge

        public BlossomVTreeEdge()
        Constructs a new tree edge by initializing arrays and heaps

    • Method Detail

      • removeFromTreeEdgeList

        public void removeFromTreeEdgeList()
        Removes this edge from both doubly linked lists of tree edges.

      • toString

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

      • addToCurrentMinusPlusHeap

        public void addToCurrentMinusPlusHeap​(BlossomVEdge edge,
                                      int direction)
        Adds edge to the heap of (-, +) cross-tree edges. As explained in the class description, this method chooses plusMinusEdges0 or plusMinusEdges1 based upon the direction. The key is edge.slack
        Parameters:
        edge - an edge to add to the current heap of (-, +) cross-tree edges.
        direction - direction of this tree edge wrt. current tree and opposite tree

      • addToCurrentPlusMinusHeap

        public void addToCurrentPlusMinusHeap​(BlossomVEdge edge,
                                      int direction)
        Adds edge to the heap of (+, -) cross-tree edges. As explained in the class description, this method chooses plusMinusEdges0 or plusMinusEdges1 based upon the direction. The key is edge.slack
        Parameters:
        edge - an edge to add to the current heap of (+, -) cross-tree edges.
        direction - direction of this tree edge wrt. current tree and opposite tree

      • addPlusPlusEdge

        public void addPlusPlusEdge​(BlossomVEdge edge)
        Adds edge to the heap of (+, +) cross-tree edges. The key is edge.slack
        Parameters:
        edge - an edge to add to the heap of (+, +) cross-tree edges

      • removeFromCurrentMinusPlusHeap

        public void removeFromCurrentMinusPlusHeap​(BlossomVEdge edge)
        Removes edge from the current heap of (-, +) cross-tree edges. As explained in the class description, this method chooses plusMinusEdges0 or plusMinusEdges1 based upon the direction.
        Parameters:
        edge - an edge to remove

      • removeFromCurrentPlusMinusHeap

        public void removeFromCurrentPlusMinusHeap​(BlossomVEdge edge)
        Removes edge from the current heap of (+, -) cross-tree edges. As explained in the class description, this method chooses plusMinusEdges0 or plusMinusEdges1 based upon the direction.
        Parameters:
        edge - an edge to remove

      • removeFromPlusPlusHeap

        public void removeFromPlusPlusHeap​(BlossomVEdge edge)
        Removes edge from the heap of (+, +) cross-tree edges.
        Parameters:
        edge - an edge to remove

      • getCurrentMinusPlusHeap

        public org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVEdge> getCurrentMinusPlusHeap​(int currentDir)
        Returns the current heap of (-, +) cross-tree edges. Always returns a heap different from getCurrentPlusMinusHeap(currentDir)
        Parameters:
        currentDir - the current direction of this edge
        Returns:
        returns current heap of (-, +) cross-tree edges

      • getCurrentPlusMinusHeap

        public org.jheaps.MergeableAddressableHeap<java.lang.Double,​BlossomVEdge> getCurrentPlusMinusHeap​(int currentDir)
        Returns the current heap of (+, -) cross-tree edges. Always returns a heap different from getCurrentMinusPlusHeap(currentDir)
        Parameters:
        currentDir - the current direction of this edge
        Returns:
        returns current heap of (+, -) cross-tree edges