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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionclass
An iterator over tree edges incident to this tree.static class
An iterator over tree nodes. -
Field Summary
FieldsModifier and TypeFieldDescription(package private) double
Accumulated dual change.(package private) int
Direction of the tree edge connecting this tree and the currently processed tree(package private) BlossomVTreeEdge
This variable is used to quickly determine the edge between two trees during primal operations.private static int
Variable for debug purposes(package private) double
Dual change that hasn't been spread among the nodes in this tree.(package private) BlossomVTreeEdge[]
Two-element array of the first elements in the circular doubly linked lists of incident tree edges in each direction.(package private) int
Variable for debug purposes(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVNode> The heap of "-" blossoms of this tree(package private) BlossomVTree
Next tree in the connected component, is used during updating the duals via connected components(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> The heap of (+, inf) edges of this tree(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVEdge> The heap of (+,+) edges of this tree(package private) BlossomVNode
The root of this tree -
Constructor Summary
ConstructorsConstructorDescriptionEmpty constructorBlossomVTree
(BlossomVNode root) Constructs a new tree with theroot
-
Method Summary
Modifier and TypeMethodDescriptionvoid
addMinusBlossom
(BlossomVNode blossom) Ensures correct addition of a blossom to the heapvoid
Ensures correct addition of an edge to the heapvoid
addPlusPlusEdge
(BlossomVEdge edge) Ensures correct addition of an edge to the heapstatic BlossomVTreeEdge
addTreeEdge
(BlossomVTree from, BlossomVTree to) Adds a new tree edge fromfrom
toto
.void
Clears the currentEdge variable of all adjacent to thetree
treesvoid
Prints all the nodes of this treevoid
removeMinusBlossom
(BlossomVNode blossom) Removes theblossom
from the heap of "-" blossomsvoid
Removes theedge
from the heap of (+, inf) edgesvoid
Removes theedge
from the heap of (+, +) edgesvoid
Sets the currentEdge and currentDirection variables for all trees adjacent to this treetoString()
Returns a new instance of TreeEdgeIterator for this treeReturns a new instance of TreeNodeIterator for this tree
-
Field Details
-
currentId
private static int currentIdVariable for debug purposes -
first
BlossomVTreeEdge[] firstTwo-element array of the first elements in the circular doubly linked lists of incident tree edges in each direction. -
currentEdge
BlossomVTreeEdge currentEdgeThis 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 tonull
when no primal operation can be applied to the tree $T$. -
currentDirection
int currentDirectionDirection of the tree edge connecting this tree and the currently processed tree -
eps
double epsDual change that hasn't been spread among the nodes in this tree. This technique is called lazy delta spreading -
accumulatedEps
double accumulatedEpsAccumulated dual change. Is used during dual updates -
root
BlossomVNode rootThe root of this tree -
nextTree
BlossomVTree nextTreeNext tree in the connected component, is used during updating the duals via connected components -
plusPlusEdges
org.jheaps.MergeableAddressableHeap<Double,BlossomVEdge> plusPlusEdgesThe heap of (+,+) edges of this tree -
plusInfinityEdges
org.jheaps.MergeableAddressableHeap<Double,BlossomVEdge> plusInfinityEdgesThe heap of (+, inf) edges of this tree -
minusBlossoms
org.jheaps.MergeableAddressableHeap<Double,BlossomVNode> minusBlossomsThe heap of "-" blossoms of this tree -
id
int idVariable for debug purposes
-
-
Constructor Details
-
BlossomVTree
public BlossomVTree()Empty constructor -
BlossomVTree
Constructs a new tree with theroot
- Parameters:
root
- the root of this tree
-
-
Method Details
-
addTreeEdge
Adds a new tree edge fromfrom
toto
. Sets the to.currentEdge and to.currentDirection with respect to the treefrom
- Parameters:
from
- the tail of the directed tree edgeto
- 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 thetree
trees -
printTreeNodes
public void printTreeNodes()Prints all the nodes of this tree -
toString
-
addPlusPlusEdge
Ensures correct addition of an edge to the heap- Parameters:
edge
- a (+, +) edge
-
addPlusInfinityEdge
Ensures correct addition of an edge to the heap- Parameters:
edge
- a (+, inf) edge
-
addMinusBlossom
Ensures correct addition of a blossom to the heap- Parameters:
blossom
- a "-" blossom
-
removePlusPlusEdge
Removes theedge
from the heap of (+, +) edges- Parameters:
edge
- the edge to remove
-
removePlusInfinityEdge
Removes theedge
from the heap of (+, inf) edges- Parameters:
edge
- the edge to remove
-
removeMinusBlossom
Removes theblossom
from the heap of "-" blossoms- Parameters:
blossom
- the blossom to remove
-
treeNodeIterator
Returns a new instance of TreeNodeIterator for this tree- Returns:
- new TreeNodeIterator for this tree
-
treeEdgeIterator
Returns a new instance of TreeEdgeIterator for this tree- Returns:
- new TreeEdgeIterators for this tree
-