- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.BlossomVTree
-
class BlossomVTree extends java.lang.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 equalsnode.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
andBlossomVTree.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
BlossomVTree.TreeEdgeIterator
An iterator over tree edges incident to this tree.static class
BlossomVTree.TreeNodeIterator
An iterator over tree nodes.
-
Field Summary
Fields Modifier and Type Field Description (package private) double
accumulatedEps
Accumulated dual change.(package private) int
currentDirection
Direction of the tree edge connecting this tree and the currently processed tree(package private) BlossomVTreeEdge
currentEdge
This variable is used to quickly determine the edge between two trees during primal operations.private static int
currentId
Variable for debug purposes(package private) double
eps
Dual change that hasn't been spread among the nodes in this tree.(package private) BlossomVTreeEdge[]
first
Two-element array of the first elements in the circular doubly linked lists of incident tree edges in each direction.(package private) int
id
Variable for debug purposes(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVNode>
minusBlossoms
The heap of "-" blossoms of this tree(package private) BlossomVTree
nextTree
Next tree in the connected component, is used during updating the duals via connected components(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
plusInfinityEdges
The heap of (+, inf) edges of this tree(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
plusPlusEdges
The heap of (+,+) edges of this tree(package private) BlossomVNode
root
The root of this tree
-
Constructor Summary
Constructors Constructor Description BlossomVTree()
Empty constructorBlossomVTree(BlossomVNode root)
Constructs a new tree with theroot
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addMinusBlossom(BlossomVNode blossom)
Ensures correct addition of a blossom to the heapvoid
addPlusInfinityEdge(BlossomVEdge edge)
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
clearCurrentEdges()
Clears the currentEdge variable of all adjacent to thetree
treesvoid
printTreeNodes()
Prints all the nodes of this treevoid
removeMinusBlossom(BlossomVNode blossom)
Removes theblossom
from the heap of "-" blossomsvoid
removePlusInfinityEdge(BlossomVEdge edge)
Removes theedge
from the heap of (+, inf) edgesvoid
removePlusPlusEdge(BlossomVEdge edge)
Removes theedge
from the heap of (+, +) edgesvoid
setCurrentEdges()
Sets the currentEdge and currentDirection variables for all trees adjacent to this treejava.lang.String
toString()
BlossomVTree.TreeEdgeIterator
treeEdgeIterator()
Returns a new instance of TreeEdgeIterator for this treeBlossomVTree.TreeNodeIterator
treeNodeIterator()
Returns a new instance of TreeNodeIterator for this tree
-
-
-
Field Detail
-
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 tonull
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<java.lang.Double,BlossomVEdge> plusPlusEdges
The heap of (+,+) edges of this tree
-
plusInfinityEdges
org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge> plusInfinityEdges
The heap of (+, inf) edges of this tree
-
minusBlossoms
org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVNode> minusBlossoms
The heap of "-" blossoms of this tree
-
id
int id
Variable for debug purposes
-
-
Constructor Detail
-
BlossomVTree
public BlossomVTree()
Empty constructor
-
BlossomVTree
public BlossomVTree(BlossomVNode root)
Constructs a new tree with theroot
- Parameters:
root
- the root of this tree
-
-
Method Detail
-
addTreeEdge
public static BlossomVTreeEdge addTreeEdge(BlossomVTree from, BlossomVTree to)
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
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.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 theedge
from the heap of (+, +) edges- Parameters:
edge
- the edge to remove
-
removePlusInfinityEdge
public void removePlusInfinityEdge(BlossomVEdge edge)
Removes theedge
from the heap of (+, inf) edges- Parameters:
edge
- the edge to remove
-
removeMinusBlossom
public void removeMinusBlossom(BlossomVNode blossom)
Removes theblossom
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
-
-