edu.byu.ece.graph.dfs
Class DepthFirstSearchForest

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

public class DepthFirstSearchForest
extends java.lang.Object
implements GraphForest

This class performs a depth-first search on a DirectedGraph. A depth first search is represented as a Collection of DepthFirstTrees.

TODO: all of the graph operations need to be defined.

See Also:
Serialized Form

Field Summary
protected  DirectedGraph _graph
           
protected  java.util.List<DepthFirstTree> _trees
           
protected static boolean DEBUG
           
 
Constructor Summary
DepthFirstSearchForest()
          Create an empty search.
DepthFirstSearchForest(DirectedGraph graph)
          Create a depth-first search with the nodes contained in the given DirectedGraph
DepthFirstSearchForest(DirectedGraph graph, java.util.List nodesInOrder)
          Create a depth-first search with the nodes contained in the given DirectedGraph
DepthFirstSearchForest(DirectedGraph graph, java.lang.Object root)
           
 
Method Summary
protected  java.util.List _getSortedTreeList(boolean ascending)
          Return a List of the DFS trees in sorted order where the trees are sorted on a basis of size.
protected  void _search(java.util.List nodesInorder)
          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 getAncestors(java.lang.Object node)
          Return a Collection of node objects in the graph that are ancestors of the node passed in as a parameter.
 java.util.List getAscendingTreeList()
           
 java.util.Collection getDescendents(java.lang.Object node)
          Return a Collection of node objects in the graph that are descendants of the node passed in as a parameter.
 java.util.List getDescendingTreeList()
           
 Edge getEdge(java.lang.Object source, java.lang.Object sink)
          Return the Edge associated with the given source,sink pair.
 java.util.Collection getEdges()
          Return a Collection of all edges in the graph.
 java.util.List getFinishList()
           
 DirectedGraph getGraph()
           
 java.util.Collection getInputEdges(java.lang.Object node)
          Return a Collection of Edge objects that are "inputs" to the given node (i.e.
 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.
 java.util.Collection getPredecessors(java.lang.Object node)
          Return a Collection of node objects in the graph that are direct predecessors of the node passed in as a parameter.
 java.util.List getReveresedFinishList()
           
 DirectedGraph getSubGraph(java.util.Collection nodes)
          Return a new DirectedGraph object that is a sub-graph of this graph.
 java.util.Collection getSuccessors(java.lang.Object node)
          Return a Collection of node objects in the graph that are direct successors of the node passed in as a parameter.
 java.util.Collection<DepthFirstTree> getTrees()
          Return the trees that compose this forest.
 DirectedGraph invert()
           
 void removeSingleNodeTrees()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

_graph

protected DirectedGraph _graph

_trees

protected java.util.List<DepthFirstTree> _trees

DEBUG

protected static boolean DEBUG
Constructor Detail

DepthFirstSearchForest

public DepthFirstSearchForest()
Create an empty search.


DepthFirstSearchForest

public DepthFirstSearchForest(DirectedGraph graph)
Create a depth-first search with the nodes contained in the given DirectedGraph

Parameters:
graph - DirectedGraph containing nodes to be added to the search

DepthFirstSearchForest

public DepthFirstSearchForest(DirectedGraph graph,
                              java.util.List nodesInOrder)
Create a depth-first search with the nodes contained in the given DirectedGraph

Parameters:
graph - DirectedGraph containing nodes to be added to the search
nodesInOrder - A List of the nodes in order

DepthFirstSearchForest

public DepthFirstSearchForest(DirectedGraph graph,
                              java.lang.Object root)
Method Detail

containsNode

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

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

getAscendingTreeList

public java.util.List getAscendingTreeList()
Returns:
List of trees in ascending order (DepthFirstTree)

getDescendingTreeList

public java.util.List getDescendingTreeList()
Returns:
List of trees in descending order

getEdges

public java.util.Collection 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()

getGraph

public DirectedGraph getGraph()

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

getReveresedFinishList

public java.util.List getReveresedFinishList()

getTrees

public java.util.Collection<DepthFirstTree> getTrees()
Description copied from interface: GraphForest
Return the trees that compose this forest. Each object in this collection is an DirectedGraph object.

Specified by:
getTrees in interface GraphForest
Returns:

removeSingleNodeTrees

public void removeSingleNodeTrees()

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

getSuccessors

public java.util.Collection getSuccessors(java.lang.Object node)
Description copied from interface: DirectedGraph
Return a Collection of node objects in the graph that are direct successors of the node passed in as a parameter. The Collection should be empty if there are no successors.

Specified by:
getSuccessors in interface DirectedGraph

getPredecessors

public java.util.Collection getPredecessors(java.lang.Object node)
Description copied from interface: DirectedGraph
Return a Collection of node objects in the graph that are direct predecessors of the node passed in as a parameter. The Collection should be empty if there are no predecessors.

Specified by:
getPredecessors in interface DirectedGraph

getDescendents

public java.util.Collection getDescendents(java.lang.Object node)
Description copied from interface: DirectedGraph
Return a Collection of node objects in the graph that are descendants of the node passed in as a parameter. Descendants are all nodes that are reachable from the node. The Collection should be empty if there are no Descendants.

This is the same as "reachableNodes" in ptolemy.graph.

Specified by:
getDescendents in interface DirectedGraph

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.

getAncestors

public java.util.Collection getAncestors(java.lang.Object node)
Description copied from interface: DirectedGraph
Return a Collection of node objects in the graph that are ancestors of the node passed in as a parameter. Ancestors are all nodes that can reach the node. The Collection should be empty if there are no ancestors.

This is the same as "backwardReachableNodes" in ptolemy.graph.

Specified by:
getAncestors in interface DirectedGraph

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

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

invert

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

_getSortedTreeList

protected java.util.List _getSortedTreeList(boolean ascending)
Return a List of the DFS trees in sorted order where the trees are sorted on a basis of size.

Parameters:
ascending - If true, sort the trees in ascending order. If false, sort the trees in descending order.
Returns:
List of sorted trees.

_search

protected void _search(java.util.List nodesInorder)
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.

Parameters:
nodesInorder - A List of the nodes which will be traverse in the order given. Any necessary sorting should be done by the caller.