It represents a vertex of graph, and contains three major blocks of data needed for the algorithm.
- Node's state information, i.e.
label
,isTreeRoot
, etc. This information is maintained dynamically and is changed byBlossomVPrimalUpdater
- Information needed to maintain alternating tree structure. It is designed to be able to quickly plant subtrees, split and concatenate child lists, traverse the tree up and down
- information needed to maintain a "pyramid" of contracted nodes. The common use-cases are to traverse the nodes of a blossom, to move from some node up to the outer blossom (or penultimate blossom, if the outer one is being expanded)
Each node has a dual variable. This is the only information that can be changed by the
BlossomVDualUpdater
. This variable is updated lazily due to performance reasons.
The edges incident to a node are stored in two linked lists. The first linked list is used for
outgoing edges; the other, for incoming edges. The notions of outgoing and incoming edges are
symmetric in the context of this algorithm since the initial graph is undirected. The first
element in the list of outgoing edges is BlossomVNode#first[0]
, the first element in the
list of incoming edges is BlossomVNode#first[1]
.
A node is called a plus node if it belongs to the even layer of some alternating tree
(root has layer 0). Then its label is BlossomVNode.Label.PLUS
. A node is called a minus node if
it belongs to the odd layer of some alternating tree. Then its label is BlossomVNode.Label.MINUS
. A
node is called an infinity or free node if it doesn't belong to any alternating
tree. A node is called outer it belongs to the surface graph, i.e. it is not contracted. A
node is called a blossom or pseudonode if it emerged from contracting an odd
circuit. This implies that this node doesn't belong to the original graph. A node is called
matched, if it is matched to some other node. If a node is free, it means that it is
matched. If a node is not a free node, then it necessarily belongs to some tree. If a node isn't
matched, it necessarily is a tree root.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionclass
An iterator for traversing the edges incident to this node.static enum
Represents nodes' labels -
Field Summary
FieldsModifier and TypeFieldDescription(package private) BlossomVEdge
A (+, inf) edge incident to this node.(package private) BlossomVNode
Reference of some blossom that is higher than this node.(package private) BlossomVNode
Reference of the blossom this node is contained in.(package private) BlossomVEdge
Reference of the next node in the blossom structure in the circular singly linked list of blossom nodes.(package private) double
Current dual variable of this node.(package private) BlossomVEdge[]
Two-element array of references of the first elements in the linked lists of edges that are incident to this node.(package private) BlossomVNode
The first child in the linked list of children of this node.(package private) org.jheaps.AddressableHeap.Handle
<Double, BlossomVNode> Node from the heap this node is stored in(package private) boolean
True if this node is a blossom node (also called a "pseudonode", the notions are equivalent)(package private) boolean
Support variable.(package private) boolean
True if this node is outer, i.e.(package private) boolean
Support variable to identify the nodes which have been "processed" in some sense by the algorithm.(package private) boolean
True if this node is a tree root, implies that this node is outer and isn't matched(package private) BlossomVNode.Label
Current label of this node.(package private) BlossomVEdge
An edge which is incident to this node and currently belongs to the matching(package private) BlossomVEdge
An edge to the parent node in the tree structure.(package private) int
Position of this node in the arraystate.nodes
.(package private) BlossomVTree
Reference to the tree this node belongs to(package private) BlossomVNode
Reference of the next tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).(package private) BlossomVNode
Reference of the previous tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this). -
Constructor Summary
ConstructorsConstructorDescriptionBlossomVNode
(int pos) Constructs a new "+" node with aBlossomVNode.Label.PLUS
label. -
Method Summary
Modifier and TypeMethodDescriptionvoid
addChild
(BlossomVNode child, BlossomVEdge parentEdge, boolean grow) Appends thechild
to the end of the linked list of children of this node.void
addEdge
(BlossomVEdge edge, int dir) Insert theedge
into linked list of incident edges of this node in the specified directiondir
Helper method, returns a node this node is matched to.Computes and returns the penultimate blossom of this node, i.e.Computes and returns the penultimate blossom of this node.Helper method, returns the tree grandparent of this nodeHelper method, returns the tree parent of this node or null if this node has no tree parentdouble
Returns the true dual variable of this node.Returns an iterator over all incident edges of this nodeboolean
Checks whether this node is an infinity nodeboolean
Checks whether this node is a minus nodeboolean
Checks whether this node is a plus nodevoid
moveChildrenTo
(BlossomVNode blossom) Appends the child list of this node to the beginning of the child list of theblossom
.void
removeEdge
(BlossomVEdge edge, int dir) Removes theedge
from the linked list of edges incident to this node.void
If this node is a tree root then this method removes this node from the tree root doubly linked list.toString()
-
Field Details
-
handle
org.jheaps.AddressableHeap.Handle<Double,BlossomVNode> handleNode from the heap this node is stored in -
isTreeRoot
boolean isTreeRootTrue if this node is a tree root, implies that this node is outer and isn't matched -
isBlossom
boolean isBlossomTrue if this node is a blossom node (also called a "pseudonode", the notions are equivalent) -
isOuter
boolean isOuterTrue if this node is outer, i.e. it isn't contracted in some blossom and belongs to the surface graph -
isProcessed
boolean isProcessedSupport variable to identify the nodes which have been "processed" in some sense by the algorithm. Is used in the shrink and expand operations.For example, during the shrink operation we traverse the odd circuit and apply dual changes. All nodes from this odd circuit are marked, i.e.
node.isMarked == true
. When a node on this circuit is traversed, we setnode.isProcessed
totrue
. When a (+, +) inner edge is encountered, we can determine whether the opposite endpoint has been processed or not depending on the value of this variable. Without this variable inner (+, +) edges can be processed twice (which is wrong). -
isMarked
boolean isMarkedSupport variable. In particular, it is used in shrink and expand operation to quickly determine whether a node belongs to the current blossom or not. Is similar to theisProcessed
-
label
BlossomVNode.Label labelCurrent label of this node. Is valid if this node is outer. -
first
BlossomVEdge[] firstTwo-element array of references of the first elements in the linked lists of edges that are incident to this node. first[0] is the first outgoing edge, first[1] is the first incoming edge, seeBlossomVEdge
. -
dual
double dualCurrent dual variable of this node. If the node belongs to a tree and is an outer node, then this value may not be valid. The true dual variable is $dual + tree.eps$ if this is a "+" node and $dual - tree.eps$ if this is a "-" node. -
matched
BlossomVEdge matchedAn edge which is incident to this node and currently belongs to the matching -
bestEdge
BlossomVEdge bestEdgeA (+, inf) edge incident to this node. This variable is used during fractional matching initialization and is assigned only to the infinity nodes. In fact, it is used to determine for a particular infinity node the "cheapest" edge to connect it to the tree. The "cheapest" means the edge with minimum slack. When the dual change is bounded by the dual constraints on the (+, inf) edges, we choose the "cheapest" best edge, increase the duals of the tree if needed, and grow this edge. -
tree
BlossomVTree treeReference to the tree this node belongs to -
parentEdge
BlossomVEdge parentEdgeAn edge to the parent node in the tree structure. -
firstTreeChild
BlossomVNode firstTreeChildThe first child in the linked list of children of this node. -
treeSiblingNext
BlossomVNode treeSiblingNextReference of the next tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this). Is null if this node is the last child of the parent node.If this node is a tree root, references the next tree root in the doubly linked list of tree roots or is null if this is the last tree root.
-
treeSiblingPrev
BlossomVNode treeSiblingPrevReference of the previous tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this). If this node is the first child of the parent node (i.e. parentEdge.getOpposite(this).firstTreeChild == this), references the last sibling.If this node is a tree root, references the previous tree root in the doubly linked list of tree roots. The first element in the linked list of tree roots is a dummy node which is stored in
nodes[nodeNum]
. This is done to quickly determine the first actual tree root vianodes[nodeNum].treeSiblingNext
. -
blossomParent
BlossomVNode blossomParentReference of the blossom this node is contained in. The blossom parent is always one layer higher than this node. -
blossomGrandparent
BlossomVNode blossomGrandparentReference of some blossom that is higher than this node. This variable is used for the path compression technique. It is used to quickly find the penultimate grandparent of this node, i.e. a grandparent whose blossomParent is an outer node. -
blossomSibling
BlossomVEdge blossomSiblingReference of the next node in the blossom structure in the circular singly linked list of blossom nodes. Is used to traverse the blossom nodes in a cyclic order. -
pos
int posPosition of this node in the arraystate.nodes
. This helps to determine generic counterpart of this node in constant time.
-
-
Constructor Details
-
BlossomVNode
public BlossomVNode(int pos) Constructs a new "+" node with aBlossomVNode.Label.PLUS
label.
-
-
Method Details
-
addEdge
Insert theedge
into linked list of incident edges of this node in the specified directiondir
- Parameters:
edge
- edge to insert in the linked list of incident edgesdir
- the direction of this edge with respect to this node
-
removeEdge
Removes theedge
from the linked list of edges incident to this node. Updates the first[dir] reference if needed.- Parameters:
edge
- the edge to removedir
- the directions of theedge
with respect to this node
-
getTreeGrandparent
Helper method, returns the tree grandparent of this node- Returns:
- the tree grandparent of this node
-
getTreeParent
Helper method, returns the tree parent of this node or null if this node has no tree parent- Returns:
- node's tree parent or null if this node has no tree parent
-
addChild
Appends thechild
to the end of the linked list of children of this node. TheparentEdge
becomes the parent edge of thechild
.Variable
grow
is used to determine whether thechild
was an infinity node and now is being added in tree structure. Then we have to setchild.firstTreeChild
tonull
so that all its tree structure variables are changed. This allows us to avoid overwriting the fields during tree destroying.- Parameters:
child
- the new child of this nodeparentEdge
- the edge between this node andchild
grow
- true ifchild
is being grown
-
getOppositeMatched
Helper method, returns a node this node is matched to.- Returns:
- a node this node is matched to.
-
removeFromChildList
public void removeFromChildList()If this node is a tree root then this method removes this node from the tree root doubly linked list. Otherwise, removes this vertex from the doubly linked list of tree children and updates parent.firstTreeChild accordingly. -
moveChildrenTo
Appends the child list of this node to the beginning of the child list of theblossom
.- Parameters:
blossom
- the node to which the children of the current node are moved
-
getPenultimateBlossom
Computes and returns the penultimate blossom of this node, i.e. the blossom which isn't outer but whose blossomParent is outer. This method also applies path compression technique to the blossomGrandparent references. More precisely, it finds the penultimate blossom of this node and changes blossomGrandparent references of the previous nodes to point to the resulting penultimate blossom.- Returns:
- the penultimate blossom of this node
-
getPenultimateBlossomAndFixBlossomGrandparent
Computes and returns the penultimate blossom of this node. The return value of this method always equals to the value returned bygetPenultimateBlossom()
. However, the main difference is that this method changes the blossomGrandparent references to point to the node that is previous to the resulting penultimate blossom. This method is used during the expand operation.- Returns:
- the penultimate blossom of this node
-
isPlusNode
public boolean isPlusNode()Checks whether this node is a plus node- Returns:
- true if the label of this node is
BlossomVNode.Label.PLUS
, false otherwise
-
isMinusNode
public boolean isMinusNode()Checks whether this node is a minus node- Returns:
- true if the label of this node is
BlossomVNode.Label.MINUS
, false otherwise
-
isInfinityNode
public boolean isInfinityNode()Checks whether this node is an infinity node- Returns:
- true if the label of this node is
BlossomVNode.Label.INFINITY
, false otherwise
-
getTrueDual
public double getTrueDual()Returns the true dual variable of this node. If this node is outer and belongs to some tree then it is subject to the lazy delta spreading technique. Otherwise, its dual is valid.- Returns:
- the actual dual variable of this node
-
incidentEdgesIterator
Returns an iterator over all incident edges of this node- Returns:
- a new instance of IncidentEdgeIterator for this node
-
toString
-