Classes
class	IntegerIterator
class	MinMaxDistance
Public Member Functions
void	addEdge (DoubleLinkedDAGNode from, DoubleLinkedDAGNode to)
int	addNode (DoubleLinkedDAGNode node)
Object	clone ()
int	computeMaxDistance (DoubleLinkedDAGNode fromNode, DoubleLinkedDAGNode toNode)
int	computeMaxPathLen ()
int	computeMinDistance (DoubleLinkedDAGNode fromNode, DoubleLinkedDAGNode toNode)
GraphMatrix	computeTransitiveClosure (boolean computeMinMaxDist)
boolean	correctTransitiveClosure (GraphMatrix transClosure, boolean checkMinMaxDist)
	DoubleLinkedDAG ()
	DoubleLinkedDAG (DoubleLinkedDAG dag)
List	findCycle ()
Iterator	getAncestorIterator (DoubleLinkedDAGNode node, GraphMatrix transitiveClosure)
Iterator	getDescendantIterator (DoubleLinkedDAGNode node, GraphMatrix transitiveClosure)
final DoubleLinkedDAGNode	getNode (int index)
ArrayList	getNodes ()
int	getNumEdges ()
int	getNumNodes ()
boolean	hasEdge (DoubleLinkedDAGNode from, DoubleLinkedDAGNode to)
boolean	hasNode (int id)
boolean	hasNode (DoubleLinkedDAGNode node)
boolean	isAncestor (DoubleLinkedDAGNode possAnc, DoubleLinkedDAGNode possDesc)
boolean	isAncestor (DoubleLinkedDAGNode possAnc, DoubleLinkedDAGNode possDesc, GraphMatrix transitiveClosure)
Iterator	iterator ()
void	removeEdge (DoubleLinkedDAGNode from, DoubleLinkedDAGNode to)
String	toString ()
String	toString (GraphMatrix graphMatrix)
String	toStringShort ()
void	updateTransClosureForNewEdge (GraphMatrix transClosure, DoubleLinkedDAGNode fromNode, DoubleLinkedDAGNode toNode, boolean computeMinDistance)
void	visitChildrenPreOrder (DoubleLinkedDAGNode node, DoubleLinkedDAGVisitor visitor, boolean visitOnlyOnce)
void	visitChildrenPreOrder_Recursive (DoubleLinkedDAGNode node, DoubleLinkedDAGVisitor visitor, boolean visitOnlyOnce)
void	visitRoots (DoubleLinkedDAGVisitor visitor, boolean visitOnlyOnce)
Protected Member Functions
int	computeMaxPathLen_Recursive (DoubleLinkedDAGNode root)
DoubleLinkedDAGNode	findCycle_Recursive (DoubleLinkedDAGNode n, ArrayList foundCycle)
void	transClosureRecursion (GraphMatrix closure, DoubleLinkedDAGNode n, DoubleLinkedDAGNode descendant, boolean computeMinMaxDist, int distance)
Protected Attributes
int[]	nodeMarks
ArrayList	nodes = new ArrayList()
BitSet	nodesVisited
int	numEdges = 0
Static Protected Attributes
static int	MARK_BEING_VISITED = 1
static int	MARK_DONE_VISITED = 2
static int	MARK_NOT_VISITED = 0

Detailed Description

Definition at line 28 of file DoubleLinkedDAG.java.

Constructor & Destructor Documentation

utils.DoubleLinkedDAG.DoubleLinkedDAG ( ) [inline]

Definition at line 76 of file DoubleLinkedDAG.java.

utils.DoubleLinkedDAG.DoubleLinkedDAG ( DoubleLinkedDAG dag ) [inline]

Definition at line 82 of file DoubleLinkedDAG.java.

Member Function Documentation

void utils.DoubleLinkedDAG.addEdge	(	DoubleLinkedDAGNode	from,
		DoubleLinkedDAGNode	to
	)		`[inline]`

Adds a new edge to the DAG.

Precondition: both nodes must already exist in the DAG, but there must not be an edge from "from" to "to".

Definition at line 145 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.addNode ( DoubleLinkedDAGNode node ) [inline]

Add the node to the DAG and automaticall assigns an integer ID to the node.

Returns the node ID.

Definition at line 108 of file DoubleLinkedDAG.java.

Object utils.DoubleLinkedDAG.clone ( ) [inline]

Definition at line 98 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.computeMaxDistance	(	DoubleLinkedDAGNode	fromNode,
		DoubleLinkedDAGNode	toNode
	)		`[inline]`

Definition at line 557 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.computeMaxPathLen ( ) [inline]

Definition at line 352 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.computeMaxPathLen_Recursive ( DoubleLinkedDAGNode root ) [inline, protected]

Definition at line 333 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.computeMinDistance	(	DoubleLinkedDAGNode	fromNode,
		DoubleLinkedDAGNode	toNode
	)		`[inline]`

Definition at line 521 of file DoubleLinkedDAG.java.

GraphMatrix utils.DoubleLinkedDAG.computeTransitiveClosure ( boolean computeMinMaxDist ) [inline]

Definition at line 429 of file DoubleLinkedDAG.java.

boolean utils.DoubleLinkedDAG.correctTransitiveClosure	(	GraphMatrix	transClosure,
		boolean	checkMinMaxDist
	)		`[inline]`

Definition at line 470 of file DoubleLinkedDAG.java.

List utils.DoubleLinkedDAG.findCycle ( ) [inline]

Definition at line 710 of file DoubleLinkedDAG.java.

DoubleLinkedDAGNode utils.DoubleLinkedDAG.findCycle_Recursive	(	DoubleLinkedDAGNode	n,
		ArrayList	foundCycle
	)		`[inline, protected]`

Definition at line 661 of file DoubleLinkedDAG.java.

Iterator utils.DoubleLinkedDAG.getAncestorIterator	(	DoubleLinkedDAGNode	node,
		GraphMatrix	transitiveClosure
	)		`[inline]`

Definition at line 749 of file DoubleLinkedDAG.java.

Iterator utils.DoubleLinkedDAG.getDescendantIterator	(	DoubleLinkedDAGNode	node,
		GraphMatrix	transitiveClosure
	)		`[inline]`

Definition at line 758 of file DoubleLinkedDAG.java.

final DoubleLinkedDAGNode utils.DoubleLinkedDAG.getNode ( int index ) [inline]

Definition at line 265 of file DoubleLinkedDAG.java.

ArrayList utils.DoubleLinkedDAG.getNodes ( ) [inline]

Definition at line 173 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.getNumEdges ( ) [inline]

Definition at line 181 of file DoubleLinkedDAG.java.

int utils.DoubleLinkedDAG.getNumNodes ( ) [inline]

Definition at line 177 of file DoubleLinkedDAG.java.

boolean utils.DoubleLinkedDAG.hasEdge	(	DoubleLinkedDAGNode	from,
		DoubleLinkedDAGNode	to
	)		`[inline]`

Definition at line 157 of file DoubleLinkedDAG.java.

boolean utils.DoubleLinkedDAG.hasNode ( int id ) [inline]

Definition at line 118 of file DoubleLinkedDAG.java.

boolean utils.DoubleLinkedDAG.hasNode ( DoubleLinkedDAGNode node ) [inline]

Checks if node is in the DAG.

Compares the reference of node with the nodes added to this DAG. I.e., the method DoubleLinkedDAGNode.equals() is not used.

Definition at line 130 of file DoubleLinkedDAG.java.

boolean utils.DoubleLinkedDAG.isAncestor	(	DoubleLinkedDAGNode	possAnc,
		DoubleLinkedDAGNode	possDesc
	)		`[inline]`

Definition at line 618 of file DoubleLinkedDAG.java.

boolean utils.DoubleLinkedDAG.isAncestor	(	DoubleLinkedDAGNode	possAnc,
		DoubleLinkedDAGNode	possDesc,
		GraphMatrix	transitiveClosure
	)		`[inline]`

Definition at line 640 of file DoubleLinkedDAG.java.

Iterator utils.DoubleLinkedDAG.iterator ( ) [inline]

Definition at line 258 of file DoubleLinkedDAG.java.

void utils.DoubleLinkedDAG.removeEdge	(	DoubleLinkedDAGNode	from,
		DoubleLinkedDAGNode	to
	)		`[inline]`

Definition at line 164 of file DoubleLinkedDAG.java.

String utils.DoubleLinkedDAG.toString ( ) [inline]

Definition at line 185 of file DoubleLinkedDAG.java.

String utils.DoubleLinkedDAG.toString ( GraphMatrix graphMatrix ) [inline]

Definition at line 197 of file DoubleLinkedDAG.java.

String utils.DoubleLinkedDAG.toStringShort ( ) [inline]

Definition at line 244 of file DoubleLinkedDAG.java.

void utils.DoubleLinkedDAG.transClosureRecursion	(	GraphMatrix	closure,
		DoubleLinkedDAGNode	n,
		DoubleLinkedDAGNode	descendant,
		boolean	computeMinMaxDist,
		int	distance
	)		`[inline, protected]`

Definition at line 372 of file DoubleLinkedDAG.java.

void utils.DoubleLinkedDAG.updateTransClosureForNewEdge	(	GraphMatrix	transClosure,
		DoubleLinkedDAGNode	fromNode,
		DoubleLinkedDAGNode	toNode,
		boolean	computeMinDistance
	)		`[inline]`

Definition at line 591 of file DoubleLinkedDAG.java.

void utils.DoubleLinkedDAG.visitChildrenPreOrder	(	DoubleLinkedDAGNode	node,
		DoubleLinkedDAGVisitor	visitor,
		boolean	visitOnlyOnce
	)		`[inline]`

Definition at line 277 of file DoubleLinkedDAG.java.

void utils.DoubleLinkedDAG.visitChildrenPreOrder_Recursive	(	DoubleLinkedDAGNode	node,
		DoubleLinkedDAGVisitor	visitor,
		boolean	visitOnlyOnce
	)		`[inline]`