com.solarmetric.rd.graph
Class DepthFirstAnalysis

java.lang.Object
  |
  +--com.solarmetric.rd.graph.DepthFirstAnalysis

public class DepthFirstAnalysis

extends java.lang.Object

Performs a depth-first analysis of a given Graph, caching information about the graph's nodes and edges. See the DFS algorithm in the book 'Introduction to Algorithms' by Cormen, Leiserson, and Rivest.

Field Summary

static int	EDGE_BACK An edge (u, v) is a back edge if it creates a cycle back to an ancestor in the graph.
static int	EDGE_FORWARD An edge (u, v) is a forward edge if it is not a tree or back edge.
static int	EDGE_TREE An edge (u, v) is a tree edge if node v was first discovered by traversing the edge.

Constructor Summary

DepthFirstAnalysis(com.solarmetric.rd.graph.Graph graph)
Constructor.

Method Summary

int	getDiscoveryTime(java.lang.Object node) Return the logical time that the given node was first discovered in the graph walk, or -1 if the node is not part of the graph.
com.solarmetric.rd.graph.Edge[]	getEdges(int type) Return all edges of the given type.
int	getEdgeType(com.solarmetric.rd.graph.Edge edge) Return the type of the given edge, or -1 if the edge is not part of the graph.
int	getFinishedTime(java.lang.Object node) Return the logical time that the given node was finished in the graph walk, or -1 if the node is not part of the graph.
java.lang.Object[]	getSortedNodes() Return the nodes in topologically-sorted order.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

EDGE_TREE

public static final int EDGE_TREE

An edge (u, v) is a tree edge if node v was first discovered by traversing the edge.

See Also:

Constant Field Values

EDGE_BACK

public static final int EDGE_BACK

An edge (u, v) is a back edge if it creates a cycle back to an ancestor in the graph.

See Also:

Constant Field Values

EDGE_FORWARD

public static final int EDGE_FORWARD

An edge (u, v) is a forward edge if it is not a tree or back edge.

See Also:

Constant Field Values

Constructor Detail

DepthFirstAnalysis

public DepthFirstAnalysis(com.solarmetric.rd.graph.Graph graph)

Constructor. Performs the analysis on the given graph and caches the resulting information.

Method Detail

getSortedNodes

public java.lang.Object[] getSortedNodes()

Return the nodes in topologically-sorted order. This is often used to order dependencies. If each graph edge (u, v) represents a dependency of v on u, then this method will return the nodes in the order that they should be evaluated to satisfy all dependencies. Of course, if the graph is cyclic (has back edges), then no such ordering is possible, though this method will still return the correct order as if edges creating the cycles did not exist.

getDiscoveryTime

public int getDiscoveryTime(java.lang.Object node)

Return the logical time that the given node was first discovered in the graph walk, or -1 if the node is not part of the graph.

getFinishedTime

public int getFinishedTime(java.lang.Object node)

Return the logical time that the given node was finished in the graph walk, or -1 if the node is not part of the graph.

getEdgeType

public int getEdgeType(com.solarmetric.rd.graph.Edge edge)

Return the type of the given edge, or -1 if the edge is not part of the graph.

getEdges

public com.solarmetric.rd.graph.Edge[] getEdges(int type)

Return all edges of the given type. This method can be used to discover all edges that cause cycles in the graph by passing it the EDGE_BACK edge type.