Class Node
- java.lang.Object
-
- org.jacop.constraints.netflow.simplex.Node
-
public final class Node extends java.lang.Object
A node (vertex) in the network.- Version:
- 4.8
-
-
Field Summary
Fields Modifier and Type Field Description Arc[]
adjacencyList
adjacency list (recorded when degree reaches 2)Arc
artificial
connects this node to the rootint
balance
balance of the last feasible flowint
degree
number of connected arcsint
deltaBalance
change in balance for the next flow computationint
depth
int
initialBalance
for debug only(package private) boolean
marked
marks the cut (S,T) for dual pivotjava.lang.String
name
a label, great for debuggingNode
parent
int
potential
the potential (or dual variable) of the network simplexNode
thread
Arc
toParent
-
Constructor Summary
Constructors Constructor Description Node(java.lang.String name, int balance)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
computePotentials()
Recomputes the potential & depth values in the subtree rooted at this node.Node
lca(Node that)
Finds the root of the smallest subtree that contains both this node and that node.void
markTree(boolean setMark)
Sets or clears a mark on a subtree rooted at this nodeNode
predecessorOnThread()
Finds the predecessor of this node on the thread.Node
rightMostLeaf()
Finds the last node on the thread that has a larger depth than this node.java.lang.String
toString()
-
-
-
Field Detail
-
initialBalance
public final int initialBalance
for debug only
-
name
public final java.lang.String name
a label, great for debugging
-
potential
public int potential
the potential (or dual variable) of the network simplex
-
balance
public int balance
balance of the last feasible flow
-
deltaBalance
public int deltaBalance
change in balance for the next flow computation
-
artificial
public Arc artificial
connects this node to the root
-
toParent
public Arc toParent
-
parent
public Node parent
-
thread
public Node thread
-
depth
public int depth
-
marked
boolean marked
marks the cut (S,T) for dual pivot
-
degree
public int degree
number of connected arcs
-
adjacencyList
public Arc[] adjacencyList
adjacency list (recorded when degree reaches 2)
-
-
Method Detail
-
lca
public Node lca(Node that)
Finds the root of the smallest subtree that contains both this node and that node.- Parameters:
that
- another node- Returns:
- the least common ancestor of this & that
-
rightMostLeaf
public Node rightMostLeaf()
Finds the last node on the thread that has a larger depth than this node. Note that if this node is a leaf node then 'this' is returned.- Returns:
- the last node on the thread that is in the subtree of this node
-
predecessorOnThread
public Node predecessorOnThread()
Finds the predecessor of this node on the thread. It uses the parent node as starting point of the search. (Hence, this method cannot be invoked on the root)- Returns:
- the node i with i.thread == this
-
markTree
public void markTree(boolean setMark)
Sets or clears a mark on a subtree rooted at this node- Parameters:
setMark
- whether to set or clear the mark
-
computePotentials
void computePotentials()
Recomputes the potential & depth values in the subtree rooted at this node.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-