Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.openjpa.lib.graph
Class DepthFirstAnalysis

    java.lang.Object
      org.apache.openjpa.lib.graph.DepthFirstAnalysis

    public class DepthFirstAnalysis

extends 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. The algorithm has been modified to group sibling nodes without connections together during the topological sort.

Since:
  1.0.0
Author:
  Abe White

Constructor Summary
`DepthFirstAnalysis(Graph graph)` Constructor.

Method Summary
`Collection<Edge>` | `getEdges(int type)` Return all edges of the given type.
`int` | `getFinishedTime(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.
`List<Object>` | `getSortedNodes()` Return the nodes in topologically-sorted order.
`boolean` | `hasNoCycles()` Test, if the analysis didn't find cycles.
`void` | `setNodeComparator(Comparator<Object> comp)` Set the comparator that should be used for ordering groups of nodes with the same dependencies.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### DepthFirstAnalysis

    public DepthFirstAnalysis(Graph graph)

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

Method Detail

### setNodeComparator

    public void setNodeComparator(Comparator<Object> comp)

  Set the comparator that should be used for ordering groups of nodes with the same dependencies.

### getSortedNodes

    public List<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.

### getEdges

    public Collection<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.TYPE_BACK` or `Edge.TYPE_FORWARD` edge type.

### getFinishedTime

    public int getFinishedTime(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.

### hasNoCycles

    public boolean hasNoCycles()

  Test, if the analysis didn't find cycles.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2006-2013 Apache Software Foundation. All Rights Reserved.