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

Class BlossomVTree

java.lang.Object
org.jgrapht.alg.matching.blossom.v5.BlossomVTree
class BlossomVTree extends 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:

  • Field Details

    • 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

    • root

      BlossomVNode root
      The root of this tree

    • nextTree

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

    • plusPlusEdges

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

    • plusInfinityEdges

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

    • minusBlossoms

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

    • id

      int id
      Variable for debug purposes

  • Constructor Details

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

    • 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 String toString()
      Overrides:
      toString in class 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