edu.byu.ece.graph.dfs
Class DFSTree

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractList<E>
          extended by java.util.ArrayList
              extended by edu.byu.ece.graph.dfs.DFSTree
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, java.lang.Iterable, java.util.Collection, java.util.List, java.util.RandomAccess

public class DFSTree
extends java.util.ArrayList

This class represents a depth-first tree.

TODO: Change this class name to EdifCellDFSTree

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

Field Summary
(package private)  java.util.Collection _backEdges
          A collection of edges in the tree that go back inside of the tree (i.e.
(package private)  java.util.Map _depthMap
          The key to this map is a ECI.
(package private)  java.util.List _finished
          An ordered List of the finish times of the depth first search.
(package private)  java.util.Collection _forwardCrossEdges
           
(package private)  EdifCellInstance _root
          The root of the DFSTree.
static boolean DEBUG
           
 
Fields inherited from class java.util.AbstractList
modCount
 
Constructor Summary
DFSTree(EdifCellInstance eci)
           
DFSTree(int i)
           
 
Method Summary
protected  void _visitNonrecursive(EdifCellInstance eci1, boolean invertDirection, java.util.Collection otherTrees, EdifCellInstanceGraph ic)
          Perform a non-recursive depth-first visit of instances in an EdifCell.
 void addBackEdge(java.lang.Object o)
           
 java.util.Collection getBackEdges()
           
 int getInstanceDepth(EdifCellInstance eci)
           
 
Methods inherited from class java.util.ArrayList
add, add, addAll, addAll, clear, clone, contains, ensureCapacity, get, indexOf, isEmpty, lastIndexOf, remove, remove, removeRange, set, size, toArray, toArray, trimToSize
 
Methods inherited from class java.util.AbstractList
equals, hashCode, iterator, listIterator, listIterator, subList
 
Methods inherited from class java.util.AbstractCollection
containsAll, removeAll, retainAll, toString
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.List
containsAll, equals, hashCode, iterator, listIterator, listIterator, removeAll, retainAll, subList
 

Field Detail

DEBUG

public static boolean DEBUG

_forwardCrossEdges

java.util.Collection _forwardCrossEdges

_depthMap

java.util.Map _depthMap
The key to this map is a ECI. the Value is an Integer object that represents the depth in the tree of the node.


_finished

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


_backEdges

java.util.Collection _backEdges
A collection of edges in the tree that go back inside of the tree (i.e. feedback edges).


_root

EdifCellInstance _root
The root of the DFSTree.

Constructor Detail

DFSTree

public DFSTree(EdifCellInstance eci)

DFSTree

public DFSTree(int i)
Method Detail

getBackEdges

public java.util.Collection getBackEdges()

addBackEdge

public void addBackEdge(java.lang.Object o)

getInstanceDepth

public int getInstanceDepth(EdifCellInstance eci)

_visitNonrecursive

protected void _visitNonrecursive(EdifCellInstance eci1,
                                  boolean invertDirection,
                                  java.util.Collection otherTrees,
                                  EdifCellInstanceGraph ic)
Perform a non-recursive depth-first visit of instances in an EdifCell. This method uses an internal stack to manage the traversal through the circuit instead of recursion. This leads to significantly lower memory requirements (the recursive version would kill the JVM stack for large designs).

Parameters:
eci1 -
invertDirection -