- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.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:
- 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
andnext
. For one tree the edge is an outgoing tree edge; for the other, an incoming. In the first case it belongs to thetree.first[0]
linked list; in the second, to thetree.first[1]
linked list.Let
tree
be a tail of the edge, andoppositeTree
a head of the edge. Thenedge.head[0] == oppositeTree
andedge.head[1] == tree
.
-
-
Field Summary
Fields Modifier and Type Field Description (package private) BlossomVTree[]
head
Two-element array of trees this edge is incident to.(package private) BlossomVTreeEdge[]
next
A two-element array of references to the next elements in the circular doubly linked lists of tree edges.(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
plusMinusEdges0
A heap of (-, +) cross-tree edges(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
plusMinusEdges1
A heap of (+, -) cross-tree edges(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
plusPlusEdges
A heap of (+, +) cross-tree edges(package private) BlossomVTreeEdge[]
prev
A two-element array of references to the previous elements in the circular doubly linked lists of tree edges.
-
Constructor Summary
Constructors Constructor Description BlossomVTreeEdge()
Constructs a new tree edge by initializing arrays and heaps
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
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<java.lang.Double,BlossomVEdge>
getCurrentMinusPlusHeap(int currentDir)
Returns the current heap of (-, +) cross-tree edges.org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
getCurrentPlusMinusHeap(int currentDir)
Returns the current heap of (+, -) cross-tree edges.void
removeFromCurrentMinusPlusHeap(BlossomVEdge edge)
Removesedge
from the current heap of (-, +) cross-tree edges.void
removeFromCurrentPlusMinusHeap(BlossomVEdge edge)
Removesedge
from the current heap of (+, -) cross-tree edges.void
removeFromPlusPlusHeap(BlossomVEdge edge)
Removesedge
from the heap of (+, +) cross-tree edges.void
removeFromTreeEdgeList()
Removes this edge from both doubly linked lists of tree edges.java.lang.String
toString()
-
-
-
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
-
-
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 classjava.lang.Object
-
addToCurrentMinusPlusHeap
public void addToCurrentMinusPlusHeap(BlossomVEdge edge, int direction)
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
public void addToCurrentPlusMinusHeap(BlossomVEdge edge, int direction)
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
public void addPlusPlusEdge(BlossomVEdge edge)
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
public void removeFromCurrentMinusPlusHeap(BlossomVEdge edge)
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
public void removeFromCurrentPlusMinusHeap(BlossomVEdge edge)
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
public void removeFromPlusPlusHeap(BlossomVEdge edge)
Removesedge
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 fromgetCurrentPlusMinusHeap(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 fromgetCurrentMinusPlusHeap(currentDir)
- Parameters:
currentDir
- the current direction of this edge- Returns:
- returns current heap of (+, -) cross-tree edges
-
-