edu.byu.ece.graph.dfs
Class BasicDepthFirstSearchTree

java.lang.Object
  extended by edu.byu.ece.graph.AbstractGraph
      extended by edu.byu.ece.graph.dfs.BasicDepthFirstSearchTree
All Implemented Interfaces:
DepthFirstTree, DirectedGraph, java.io.Serializable, java.lang.Comparable

public class BasicDepthFirstSearchTree
extends AbstractGraph
implements DepthFirstTree, java.lang.Comparable

Represents a single depth-first tree within a depth first search.

This class contains its own state and does not inherit any state from its super classes.

This tree is created from a root node from an DirectedGraph object. Upon construction, this class will evaluate the topology of the graph at a particular "root" node and create a new graph with the same nodes but edges representing the traversal of the depth-first search.

All of the edges in the original circuit are classified in this search as follows:

Since:
Created on Jun 3, 2005
Author:
Michael Wirthlin
See Also:
Serialized Form

Field Summary
protected  NodeEdgeMap _backEdges
          The back edges of this graph.
protected  NodeEdgeMap _crossEdges
          The cross edges of this graph.
(package private)  java.util.ArrayList _finished
          An ordered List of the finish times of the depth first search.
protected  NodeEdgeMap _forwardEdges
          The forward edges of this graph.
(package private)  boolean _invert
           
(package private)  java.util.ArrayList _nodes
           
protected  DepthFirstSearchForest _parent
          The parent "forest" of DFSTree objects.
protected  java.lang.Object _root
          The root of the DFSTree.
protected  NodeEdgeMap _successorEdges
          The successor edges of this graph.
static boolean DEBUG
           
 
Constructor Summary
BasicDepthFirstSearchTree(DepthFirstSearchForest parent, DirectedGraph graph, java.lang.Object node)
          Create a BasicDepthFirstSearchTree with the given DepthFirstSearchForest as the parent of the Tree and the given node as the root.
BasicDepthFirstSearchTree(DepthFirstSearchForest parent, DirectedGraph graph, java.lang.Object node, boolean invertDirection)
          Create a BasicDepthFirstSearchTree with the given DepthFirstSearchForest as the parent of the Tree and the given node as the root.
 
Method Summary
protected  void _visitNonrecursive(java.lang.Object node, DirectedGraph ic)
          Perform a non-recursive depth-first visit of nodes in a DirectedGraph.
 void addNode(java.lang.Object node)
           
 int compareTo(java.lang.Object o)
           
 boolean containsNode(java.lang.Object o)
          Determines if the given object is contained as a node within the graph.
 java.util.Collection getAllEdges()
           
 java.util.Collection<Edge> getBackEdges()
          Returns all of the back edges of this Map.
 java.util.Collection getCrossEdges()
          Return all cross edges from the tree.
 java.util.Map<java.lang.Object,java.lang.Integer> getDepthMap()
           
 Edge getEdge(java.lang.Object source, java.lang.Object sink)
          Return the Edge associated with the given source,sink pair.
 java.util.Collection<Edge> getEdges()
          Return a Collection of all edges in the graph.
 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.
 java.util.Collection getInputEdges(java.lang.Object node)
          Return a Collection of Edge objects that are "inputs" to the given node (i.e.
 Edge getLongestBackEdge()
          Identifies the back edge that has the longest distance.
 java.util.Collection getNodes()
          Return a Collection of all nodes in the graph.
 java.util.Collection getOutputEdges(java.lang.Object node)
          Return a Collection of Edge objects that are "outputs" to the given node (i.e.
 DepthFirstSearchForest getParent()
          Get the parent depth-first search graph.
 java.lang.Object getRoot()
          Get the root node of the tree
 DirectedGraph getSubGraph(java.util.Collection nodes)
          Return a new DirectedGraph object that is a sub-graph of this graph.
 java.util.Collection getSuccessorEdges()
          Return all successor edges from the tree.
 java.util.List getTopologicalSort()
          Provide a new List of nodes that appear in a reverse order of the finish list.
 DirectedGraph invert()
           
 void print(java.io.PrintStream out)
           
 void printEdges(java.util.Map edges, java.io.PrintStream out)
          Print all the edges (source node -> sink node) in the given map to the given PrintStream object.
 void printEdges(java.util.Map edges, java.io.PrintStream out, java.util.Map depthMap)
          Print all the edges in the map, along with the depth of the edge.
static java.util.List reverseList(java.util.List list)
          Create a new List that is a reverse of the List provided as a parameter.
 void trimToSize()
          Trims the capacity of the finished list to its current size.
 
Methods inherited from class edu.byu.ece.graph.AbstractGraph
_getAncestorsOrDescendents, _getAncestorsOrDescendents, getAncestors, getAncestors, getDescendents, getDescendents, getPredecessors, getSuccessors, toDotty, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface edu.byu.ece.graph.DirectedGraph
getAncestors, getDescendents, getPredecessors, getSuccessors
 

Field Detail

DEBUG

public static boolean DEBUG

_backEdges

protected NodeEdgeMap _backEdges
The back edges of this graph.


_crossEdges

protected NodeEdgeMap _crossEdges
The cross edges of this graph.


_forwardEdges

protected NodeEdgeMap _forwardEdges
The forward edges of this graph.


_parent

protected DepthFirstSearchForest _parent
The parent "forest" of DFSTree objects.


_root

protected java.lang.Object _root
The root of the DFSTree.


_successorEdges

protected NodeEdgeMap _successorEdges
The successor edges of this graph.


_finished

java.util.ArrayList _finished
An ordered List of the finish times of the depth first search.


_invert

boolean _invert

_nodes

java.util.ArrayList _nodes
Constructor Detail

BasicDepthFirstSearchTree

public BasicDepthFirstSearchTree(DepthFirstSearchForest parent,
                                 DirectedGraph graph,
                                 java.lang.Object node,
                                 boolean invertDirection)
Create a BasicDepthFirstSearchTree with the given DepthFirstSearchForest as the parent of the Tree and the given node as the root. The DirectedGraph is used to fill the Tree, which can be inverted or not, as specified by invertDirection.

Parameters:
parent - The DepthFirstSearchForest to which this BasicDepthFirstSearchTree belongs
graph -
node - The root node
invertDirection - Specifies whether the Tree should be inverted or not.

BasicDepthFirstSearchTree

public BasicDepthFirstSearchTree(DepthFirstSearchForest parent,
                                 DirectedGraph graph,
                                 java.lang.Object node)
Create a BasicDepthFirstSearchTree with the given DepthFirstSearchForest as the parent of the Tree and the given node as the root. The Tree is created without being inverted.

Parameters:
parent - The DepthFirstSearchForest to which this BasicDepthFirstSearchTree belongs
graph - A DirectedGraph
node - The root node
Method Detail

addNode

public void addNode(java.lang.Object node)

compareTo

public int compareTo(java.lang.Object o)
Specified by:
compareTo in interface java.lang.Comparable

containsNode

public boolean containsNode(java.lang.Object o)
Description copied from interface: DirectedGraph
Determines if the given object is contained as a node within the graph.

Specified by:
containsNode in interface DirectedGraph
Parameters:
o - Object to test for graph inclusion.
Returns:
true if the node is contained within the graph and false if the node is not contained within the graph.

getAllEdges

public java.util.Collection getAllEdges()

getBackEdges

public java.util.Collection<Edge> getBackEdges()
Returns all of the back edges of this Map. This is, all the edges that lead to a predecessor node in the depth first tree (a feedback edge). The returned Collection is guaranteed not to be null.

Implements DepthFirstTree.getBackEdges().

Specified by:
getBackEdges in interface DepthFirstTree
Returns:
A Collection of the Edges in this map. If the Map is empty, this method will return an empty but non-null Collection.

getCrossEdges

public java.util.Collection getCrossEdges()
Description copied from interface: DepthFirstTree
Return all cross edges from the tree.

Specified by:
getCrossEdges in interface DepthFirstTree

getDepthMap

public java.util.Map<java.lang.Object,java.lang.Integer> getDepthMap()
Returns:
A Map between each node in the depth-first tree and an Integer the depth of the node. The depth is calculated as the shortest path from a root node. The depth of the root is zero.

getEdge

public Edge getEdge(java.lang.Object source,
                    java.lang.Object sink)
Description copied from interface: DirectedGraph
Return the Edge associated with the given source,sink pair. If there is no edge, return null.

TODO: What if there is more than one edge?

Specified by:
getEdge in interface DirectedGraph

getEdges

public java.util.Collection<Edge> getEdges()
Description copied from interface: DirectedGraph
Return a Collection of all edges in the graph. The objects in this collection are of type Edge.

Specified by:
getEdges in interface DirectedGraph

getFinishList

public java.util.List getFinishList()
Description copied from interface: DepthFirstTree
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.

Specified by:
getFinishList in interface DepthFirstTree

getForwardEdges

public java.util.Collection getForwardEdges()
Description copied from interface: DepthFirstTree
Return all forward edges from the tree.

Specified by:
getForwardEdges in interface DepthFirstTree
Returns:
A Collection of all the forward edges in the Tree. A forward edge is one that leads to a successor (but not direct successor) in the depth first traversal. Implements DepthFirstTree.getForwardEdges().

getInputEdges

public java.util.Collection getInputEdges(java.lang.Object node)
Description copied from interface: DirectedGraph
Return a Collection of Edge objects that are "inputs" to the given node (i.e. edge goes into the node). The given node is considered the "sink" of the edge. This method will return an empty Collection if there are no input edges.

Specified by:
getInputEdges in interface DirectedGraph

getLongestBackEdge

public Edge getLongestBackEdge()
Identifies the back edge that has the longest distance. The distance of a back edge is defined as the depth (see getDepthMap()) of the source of the edge minus the depth of the sink of the edge.

This method will return null if there are no back edges in the graph.

Returns:
the back edge that has the longest distance, or null if there are no back edges in the graph.

getNodes

public java.util.Collection getNodes()
Description copied from interface: DirectedGraph
Return a Collection of all nodes in the graph. The class type of the objects in the Collection are not specified.

Specified by:
getNodes in interface DirectedGraph

getOutputEdges

public java.util.Collection getOutputEdges(java.lang.Object node)
Description copied from interface: DirectedGraph
Return a Collection of Edge objects that are "outputs" to the given node (i.e. edge goes out of the node). The given node is considered the "source" of the edge. This method will return an empty Collection if there are no output edges.

Specified by:
getOutputEdges in interface DirectedGraph
Returns:
the Edge objects that go out of the given node. To preserve the acyclic nature of this graph and to insure that the source and sink of all edges are within the graph, this method will return only the forward and successor edges of the depth first search.

getParent

public DepthFirstSearchForest getParent()
Description copied from interface: DepthFirstTree
Get the parent depth-first search graph.

Specified by:
getParent in interface DepthFirstTree

getRoot

public java.lang.Object getRoot()
Description copied from interface: DepthFirstTree
Get the root node of the tree

Specified by:
getRoot in interface DepthFirstTree

getSubGraph

public DirectedGraph getSubGraph(java.util.Collection nodes)
Description copied from interface: DirectedGraph
Return a new DirectedGraph object that is a sub-graph of this graph. The sub-graph is based on the Collection of nodes passed in as a parameter.

Specified by:
getSubGraph in interface DirectedGraph
Returns:
a new DirectedGraph object that is a sub-graph of this graph. The sub-graph is based on the Collection of nodes passed in as a parameter.

getSuccessorEdges

public java.util.Collection getSuccessorEdges()
Description copied from interface: DepthFirstTree
Return all successor edges from the tree.

Specified by:
getSuccessorEdges in interface DepthFirstTree

getTopologicalSort

public java.util.List getTopologicalSort()
Provide a new List of nodes that appear in a reverse order of the finish list.

Specified by:
getTopologicalSort in interface DepthFirstTree
Returns:
The list of nodes.

invert

public DirectedGraph invert()
Specified by:
invert in interface DirectedGraph

reverseList

public static java.util.List reverseList(java.util.List list)
Create a new List that is a reverse of the List provided as a parameter.

Returns:
The reversed list.

printEdges

public void printEdges(java.util.Map edges,
                       java.io.PrintStream out)
Print all the edges (source node -> sink node) in the given map to the given PrintStream object.

Parameters:
edges - Map from source to destination nodes.
out - PrintStream used to print the nodes.
See Also:
printEdges(Map, PrintStream, Map)

printEdges

public void printEdges(java.util.Map edges,
                       java.io.PrintStream out,
                       java.util.Map depthMap)
Print all the edges in the map, along with the depth of the edge.

Parameters:
edges - Map from source to destination nodes.
out - Map from source to destination nodes.
depthMap -
See Also:
printEdges(Map, PrintStream)

print

public void print(java.io.PrintStream out)

trimToSize

public void trimToSize()
Trims the capacity of the finished list to its current size.

See Also:
ArrayList#trimToSize()}.

_visitNonrecursive

protected void _visitNonrecursive(java.lang.Object node,
                                  DirectedGraph ic)
Perform a non-recursive depth-first visit of nodes in a DirectedGraph. This method uses an internal stack to manage the traversal through the circuit instead of recursion. Although the algorithm implementation is less readable than a traditional recursive algorithm, it leads to significantly lower memory requirements (the recursive version would kill the JVM stack for large designs).

Parameters:
node - The root node
ic - The DirectedGraph to get the output edges