- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.BlossomVNode
-
class BlossomVNode extends java.lang.Object
This class is a data structure for Kolmogorov's Blossom V algorithm.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 isBlossomVNode#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 isBlossomVNode.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:
KolmogorovWeightedPerfectMatching
- Node's state information, i.e.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
BlossomVNode.IncidentEdgeIterator
An iterator for traversing the edges incident to this node.static class
BlossomVNode.Label
Represents nodes' labels
-
Field Summary
Fields Modifier and Type Field Description (package private) BlossomVEdge
bestEdge
A (+, inf) edge incident to this node.(package private) BlossomVNode
blossomGrandparent
Reference of some blossom that is higher than this node.(package private) BlossomVNode
blossomParent
Reference of the blossom this node is contained in.(package private) BlossomVEdge
blossomSibling
Reference of the next node in the blossom structure in the circular singly linked list of blossom nodes.(package private) double
dual
Current dual variable of this node.(package private) BlossomVEdge[]
first
Two-element array of references of the first elements in the linked lists of edges that are incident to this node.(package private) BlossomVNode
firstTreeChild
The first child in the linked list of children of this node.(package private) org.jheaps.AddressableHeap.Handle<java.lang.Double,BlossomVNode>
handle
Node from the heap this node is stored in(package private) boolean
isBlossom
True if this node is a blossom node (also called a "pseudonode", the notions are equivalent)(package private) boolean
isMarked
Support variable.(package private) boolean
isOuter
True if this node is outer, i.e.(package private) boolean
isProcessed
Support variable to identify the nodes which have been "processed" in some sense by the algorithm.(package private) boolean
isTreeRoot
True if this node is a tree root, implies that this node is outer and isn't matched(package private) BlossomVNode.Label
label
Current label of this node.(package private) BlossomVEdge
matched
An edge which is incident to this node and currently belongs to the matching(package private) BlossomVEdge
parentEdge
An edge to the parent node in the tree structure.(package private) int
pos
Position of this node in the arraystate.nodes
.(package private) BlossomVTree
tree
Reference to the tree this node belongs to(package private) BlossomVNode
treeSiblingNext
Reference of the next tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).(package private) BlossomVNode
treeSiblingPrev
Reference of the previous tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).
-
Constructor Summary
Constructors Constructor Description BlossomVNode(int pos)
Constructs a new "+" node with aBlossomVNode.Label.PLUS
label.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
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
BlossomVNode
getOppositeMatched()
Helper method, returns a node this node is matched to.BlossomVNode
getPenultimateBlossom()
Computes and returns the penultimate blossom of this node, i.e.BlossomVNode
getPenultimateBlossomAndFixBlossomGrandparent()
Computes and returns the penultimate blossom of this node.BlossomVNode
getTreeGrandparent()
Helper method, returns the tree grandparent of this nodeBlossomVNode
getTreeParent()
Helper method, returns the tree parent of this node or null if this node has no tree parentdouble
getTrueDual()
Returns the true dual variable of this node.BlossomVNode.IncidentEdgeIterator
incidentEdgesIterator()
Returns an iterator over all incident edges of this nodeboolean
isInfinityNode()
Checks whether this node is an infinity nodeboolean
isMinusNode()
Checks whether this node is a minus nodeboolean
isPlusNode()
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
removeFromChildList()
If this node is a tree root then this method removes this node from the tree root doubly linked list.java.lang.String
toString()
-
-
-
Field Detail
-
handle
org.jheaps.AddressableHeap.Handle<java.lang.Double,BlossomVNode> handle
Node from the heap this node is stored in
-
isTreeRoot
boolean isTreeRoot
True if this node is a tree root, implies that this node is outer and isn't matched
-
isBlossom
boolean isBlossom
True if this node is a blossom node (also called a "pseudonode", the notions are equivalent)
-
isOuter
boolean isOuter
True if this node is outer, i.e. it isn't contracted in some blossom and belongs to the surface graph
-
isProcessed
boolean isProcessed
Support 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 isMarked
Support 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 label
Current label of this node. Is valid if this node is outer.
-
first
BlossomVEdge[] first
Two-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 dual
Current 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 matched
An edge which is incident to this node and currently belongs to the matching
-
bestEdge
BlossomVEdge bestEdge
A (+, 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 tree
Reference to the tree this node belongs to
-
parentEdge
BlossomVEdge parentEdge
An edge to the parent node in the tree structure.
-
firstTreeChild
BlossomVNode firstTreeChild
The first child in the linked list of children of this node.
-
treeSiblingNext
BlossomVNode treeSiblingNext
Reference 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 treeSiblingPrev
Reference 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 blossomParent
Reference of the blossom this node is contained in. The blossom parent is always one layer higher than this node.
-
blossomGrandparent
BlossomVNode blossomGrandparent
Reference 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 blossomSibling
Reference 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 pos
Position of this node in the arraystate.nodes
. This helps to determine generic counterpart of this node in constant time.
-
-
Constructor Detail
-
BlossomVNode
public BlossomVNode(int pos)
Constructs a new "+" node with aBlossomVNode.Label.PLUS
label.
-
-
Method Detail
-
addEdge
public void addEdge(BlossomVEdge edge, int dir)
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
public void removeEdge(BlossomVEdge edge, int dir)
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
public BlossomVNode getTreeGrandparent()
Helper method, returns the tree grandparent of this node- Returns:
- the tree grandparent of this node
-
getTreeParent
public BlossomVNode 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
public void addChild(BlossomVNode child, BlossomVEdge parentEdge, boolean grow)
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
public BlossomVNode 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
public void moveChildrenTo(BlossomVNode blossom)
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
public BlossomVNode 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
public BlossomVNode 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
public BlossomVNode.IncidentEdgeIterator incidentEdgesIterator()
Returns an iterator over all incident edges of this node- Returns:
- a new instance of IncidentEdgeIterator for this node
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-