JaCoP.constraints.netflow.simplex
Class Node

java.lang.Object
  JaCoP.constraints.netflow.simplex.Node

public final class Node
extends java.lang.Object

A node (vertex) in the network.

Version:

3.1

Author:

Robin Steiger and Radoslaw Szymanek

Field Summary

Arc[]	adjacencyList adjacency list (recorded when degree reaches 2)
Arc	artificial connects this node to the root
int	balance balance of the last feasible flow
int	degree number of connected arcs
int	deltaBalance change in balance for the next flow computation
int	depth
int	initialBalance for debug only
java.lang.String	name a label, great for debugging
Node	parent
int	potential the potential (or dual variable) of the network simplex
Node	thread
Arc	toParent

Constructor Summary

Node(java.lang.String name, int balance)

Method Summary

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 node
Node	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()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

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

degree

public int degree

number of connected arcs

adjacencyList

public Arc[] adjacencyList

adjacency list (recorded when degree reaches 2)

Constructor Detail

Node

public Node(java.lang.String name,
            int balance)

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

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object