Class BlossomVTreeEdge

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

  • Field Details

    • 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<Double, BlossomVEdge> plusPlusEdges
      A heap of (+, +) cross-tree edges

    • plusMinusEdges0

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

    • plusMinusEdges1

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

  • Constructor Details

    • BlossomVTreeEdge

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

  • Method Details

    • removeFromTreeEdgeList

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

    • toString

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