edu.byu.ece.graph.dfs
Interface DepthFirstTree

All Superinterfaces:
DirectedGraph, java.io.Serializable
All Known Implementing Classes:
BasicDepthFirstSearchTree

public interface DepthFirstTree
extends DirectedGraph

A graph that represents a single tree from a depth first search. This tree is created from a root node from a DirectedGraph object. As this interface extends DirectedGraph, all graph methods are available and this tree responds like a conventional graph. The edges in the graph are all classified into one of the following categories:

By definition, the tree is acyclic and the traditional graph methods (getInputEdges, getOutputEdges, getSuccessors, etc.) will only use the successor and forward edges. The cross edges are not considered part of this graph as they lead to nodes that do not belong in the graph. The back edges are also not included within the graph as they would make the tree acyclic. These edges, however, are available through accessor methods in the interface.


Method Summary
 java.util.Collection getBackEdges()
          Return the back edges from the tree.
 java.util.Collection getCrossEdges()
          Return all cross edges from the tree.
 java.util.List getFinishList()
          Return a sorted list of nodes in the tree based on their depth-first search finish time.
 java.util.Collection getForwardEdges()
          Return all forward edges from the tree.
 DepthFirstSearchForest getParent()
          Get the parent depth-first search graph.
 java.lang.Object getRoot()
          Get the root node of the tree
 java.util.Collection getSuccessorEdges()
          Return all successor edges from the tree.
 java.util.List getTopologicalSort()
          Return a topological sort of the given depth first traversal.
 
Methods inherited from interface edu.byu.ece.graph.DirectedGraph
containsNode, getAncestors, getDescendents, getEdge, getEdges, getInputEdges, getNodes, getOutputEdges, getPredecessors, getSubGraph, getSuccessors, invert
 

Method Detail

getBackEdges

java.util.Collection getBackEdges()
Return the back edges from the tree.


getForwardEdges

java.util.Collection getForwardEdges()
Return all forward edges from the tree.


getCrossEdges

java.util.Collection getCrossEdges()
Return all cross edges from the tree.


getSuccessorEdges

java.util.Collection getSuccessorEdges()
Return all successor edges from the tree.


getFinishList

java.util.List getFinishList()
Return a sorted list of nodes in the tree based on their depth-first search finish time. The nodes that finish first are at the top of this list.


getParent

DepthFirstSearchForest getParent()
Get the parent depth-first search graph.


getRoot

java.lang.Object getRoot()
Get the root node of the tree


getTopologicalSort

java.util.List getTopologicalSort()
Return a topological sort of the given depth first traversal. This is simply the reverse of the finish list.

Returns:
A topological sort of the given depth first traversal. This is simply the reverse of the finish list.