edu.byu.ece.graph.dfs
Class SCCDepthFirstSearch

java.lang.Object
  extended by edu.byu.ece.graph.dfs.DepthFirstSearchForest
      extended by edu.byu.ece.graph.dfs.SCCDepthFirstSearch
All Implemented Interfaces:
DirectedGraph, GraphForest, java.io.Serializable

public class SCCDepthFirstSearch
extends DepthFirstSearchForest

A depth first search that is composed of strongly connected component (SCC) trees.

Author:
Mike Wirthlin
See Also:
Serialized Form

Field Summary
(package private)  java.util.Collection _singleNodes
           
(package private)  boolean localDEBUG
           
 
Fields inherited from class edu.byu.ece.graph.dfs.DepthFirstSearchForest
_graph, _trees, DEBUG
 
Constructor Summary
SCCDepthFirstSearch(DepthFirstSearchForest firstDFS)
          Deprecated. Use SCCDepthFirstSearch(DirectedGraph)
SCCDepthFirstSearch(DirectedGraph graph)
           
SCCDepthFirstSearch(DirectedGraph graph, java.util.List nodesInOrder)
           
 
Method Summary
 void _init(DirectedGraph graph, java.util.List nodesInOrder)
           
protected  void _search(java.util.List cellsInorder)
          This method performs the top-level depth first search on directed graph.
 boolean containsNode(java.lang.Object node)
          Search all the DepthFirstTree objects in the current DepthFirstSearch object for the given node and return true if found.
 java.util.Collection getSingleNodes()
           
 java.util.List<DepthFirstTree> getTopologicallySortedTreeList()
          Return a List of the DFS trees in topologically sorted order.
 void printSCCs()
           
 
Methods inherited from class edu.byu.ece.graph.dfs.DepthFirstSearchForest
_getSortedTreeList, getAncestors, getAscendingTreeList, getDescendents, getDescendingTreeList, getEdge, getEdges, getFinishList, getGraph, getInputEdges, getNodes, getOutputEdges, getPredecessors, getReveresedFinishList, getSubGraph, getSuccessors, getTrees, invert, removeSingleNodeTrees
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

localDEBUG

boolean localDEBUG

_singleNodes

java.util.Collection _singleNodes
Constructor Detail

SCCDepthFirstSearch

public SCCDepthFirstSearch(DirectedGraph graph)

SCCDepthFirstSearch

public SCCDepthFirstSearch(DirectedGraph graph,
                           java.util.List nodesInOrder)

SCCDepthFirstSearch

@Deprecated
public SCCDepthFirstSearch(DepthFirstSearchForest firstDFS)
Deprecated. Use SCCDepthFirstSearch(DirectedGraph)

Parameters:
firstDFS -
Method Detail

_init

public void _init(DirectedGraph graph,
                  java.util.List nodesInOrder)

containsNode

public boolean containsNode(java.lang.Object node)
Description copied from class: DepthFirstSearchForest
Search all the DepthFirstTree objects in the current DepthFirstSearch object for the given node and return true if found.

Specified by:
containsNode in interface DirectedGraph
Overrides:
containsNode in class DepthFirstSearchForest
Parameters:
node - The given node
Returns:
true if the DepthFirstSearch object contains the node in any of the DepthFirstTree objects. Otherwise, false.

getTopologicallySortedTreeList

public java.util.List<DepthFirstTree> getTopologicallySortedTreeList()
Return a List of the DFS trees in topologically sorted order.

Returns:
List of topologically-sorted trees.

_search

protected void _search(java.util.List cellsInorder)
Description copied from class: DepthFirstSearchForest
This method performs the top-level depth first search on directed graph. The order in which the graph Nodes are visited is determined by the List parameter. This method will sequentially visit each Node in the list and call the recursive _visit method. The _visit method will visit all "successor" Nodes of the chosen Node (excluding feedback). When visit is completed, this method will choose the next unvisited item in the list. Each call to _visit from this method will create a new spanning tree in the depth first search.

Overrides:
_search in class DepthFirstSearchForest
Parameters:
cellsInorder - A List of the nodes which will be traverse in the order given. Any necessary sorting should be done by the caller.

getSingleNodes

public java.util.Collection getSingleNodes()

printSCCs

public void printSCCs()