Overview | Package | Class | Tree | Deprecated | Index | Help
| SolarMetric Kodo JDO 2.5.0 Reverse Schema Tool
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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.

Overview | Package | Class | Tree | Deprecated | Index | Help
| SolarMetric Kodo JDO 2.5.0 Reverse Schema Tool
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright 2001,2002,2003 SolarMetric, Inc. All Rights Reserved.