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:
- 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.
- a heap of (+, -) cross-tree edges
- a heap of (-, +) cross-tree edges
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 Summary
FieldsModifier and TypeFieldDescription(package private) BlossomVTree[]
Two-element array of trees this edge is incident to.(package private) BlossomVTreeEdge[]
A two-element array of references to the next elements in the circular doubly linked lists of tree edges.(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> A heap of (-, +) cross-tree edges(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> A heap of (+, -) cross-tree edges(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> A heap of (+, +) cross-tree edges(package private) BlossomVTreeEdge[]
A two-element array of references to the previous elements in the circular doubly linked lists of tree edges. -
Constructor Summary
ConstructorsConstructorDescriptionConstructs a new tree edge by initializing arrays and heaps -
Method Summary
Modifier and TypeMethodDescriptionvoid
addPlusPlusEdge
(BlossomVEdge edge) Addsedge
to the heap of (+, +) cross-tree edges.void
addToCurrentMinusPlusHeap
(BlossomVEdge edge, int direction) Addsedge
to the heap of (-, +) cross-tree edges.void
addToCurrentPlusMinusHeap
(BlossomVEdge edge, int direction) Addsedge
to the heap of (+, -) cross-tree edges.org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> getCurrentMinusPlusHeap
(int currentDir) Returns the current heap of (-, +) cross-tree edges.org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> getCurrentPlusMinusHeap
(int currentDir) Returns the current heap of (+, -) cross-tree edges.void
Removesedge
from the current heap of (-, +) cross-tree edges.void
Removesedge
from the current heap of (+, -) cross-tree edges.void
Removesedge
from the heap of (+, +) cross-tree edges.void
Removes this edge from both doubly linked lists of tree edges.toString()
-
Field Details
-
head
BlossomVTree[] headTwo-element array of trees this edge is incident to. -
prev
BlossomVTreeEdge[] prevA 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[] nextA 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> plusPlusEdgesA heap of (+, +) cross-tree edges -
plusMinusEdges0
org.jheaps.MergeableAddressableHeap<Double,BlossomVEdge> plusMinusEdges0A heap of (-, +) cross-tree edges -
plusMinusEdges1
org.jheaps.MergeableAddressableHeap<Double,BlossomVEdge> plusMinusEdges1A 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
-
addToCurrentMinusPlusHeap
Addsedge
to the heap of (-, +) cross-tree edges. As explained in the class description, this method choosesplusMinusEdges0
orplusMinusEdges1
based upon thedirection
. 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
Addsedge
to the heap of (+, -) cross-tree edges. As explained in the class description, this method choosesplusMinusEdges0
orplusMinusEdges1
based upon thedirection
. 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
Addsedge
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
Removesedge
from the current heap of (-, +) cross-tree edges. As explained in the class description, this method choosesplusMinusEdges0
orplusMinusEdges1
based upon thedirection
.- Parameters:
edge
- an edge to remove
-
removeFromCurrentPlusMinusHeap
Removesedge
from the current heap of (+, -) cross-tree edges. As explained in the class description, this method choosesplusMinusEdges0
orplusMinusEdges1
based upon thedirection
.- Parameters:
edge
- an edge to remove
-
removeFromPlusPlusHeap
Removesedge
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 fromgetCurrentPlusMinusHeap(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 fromgetCurrentMinusPlusHeap(currentDir)
- Parameters:
currentDir
- the current direction of this edge- Returns:
- returns current heap of (+, -) cross-tree edges
-