edu.byu.ece.graph
Class AbstractGraph

java.lang.Object
  extended by edu.byu.ece.graph.AbstractGraph
All Implemented Interfaces:
DirectedGraph, java.io.Serializable
Direct Known Subclasses:
BasicDepthFirstSearchTree, BasicGraph

public abstract class AbstractGraph
extends java.lang.Object
implements DirectedGraph

An abstract implementation of a directed graph that contains default methods for basic topology traversal operations.

This class has no state and provides a default implementation for the following methods: getSuccessors(java.lang.Object), getPredecessors(java.lang.Object), getAncestors(Object), getAncestors(Collection), getDescendents(Object), and getDescendents(Collection).

These methods all rely on the following two unimplemented methods to operate correctly: DirectedGraph.getInputEdges(Object) and DirectedGraph.getOutputEdges(Object).

This class also provides a default toString and toDotty method.

Author:
wirthlin
See Also:
Serialized Form

Constructor Summary
AbstractGraph()
           
 
Method Summary
protected  java.util.List _getAncestorsOrDescendents(java.util.Collection nodes, boolean predecessors)
          This helper method will provide an ordered list of all the ancestors or Descendants.
protected  java.util.List _getAncestorsOrDescendents(java.lang.Object node, boolean predecessors)
          Provides the ancestors or descendants of a single Node.
 java.util.Collection getAncestors(java.util.Collection nodes)
           
 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.Collection getDescendents(java.util.Collection nodes)
           
 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.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.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.
 void toDotty(java.lang.String filename)
          Uses the AbstractGraphToDotty.graphToDotty method to create a Dotty version of this graph.
 java.lang.String 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
containsNode, getEdge, getEdges, getInputEdges, getNodes, getOutputEdges, getSubGraph, invert
 

Constructor Detail

AbstractGraph

public AbstractGraph()
Method Detail

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
Returns:
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.

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
Returns:
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.

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
Returns:
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.

getAncestors

public java.util.Collection getAncestors(java.util.Collection nodes)
Returns:
a Collection of node objects in the graph that are ancestors of each of the nodes passed in as a parameter. Ancestors are all nodes that can reach any of the nodes in the Collection. The Collection should be empty if there are no ancestors. Note: this method is not part of the DirectedGraph interface.

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
Returns:
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.

getDescendents

public java.util.Collection getDescendents(java.util.Collection nodes)
Returns:
a Collection of node objects in the graph that are descendants of any of the Nodes in the Collection passed in as a parameter. Descendants are all nodes that are reachable from any node in the Collection. The Collection should be empty if there are no Descendants. Note: this method is not part of the DirectedGraph interface.

toDotty

public void toDotty(java.lang.String filename)
Uses the AbstractGraphToDotty.graphToDotty method to create a Dotty version of this graph.


toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

_getAncestorsOrDescendents

protected java.util.List _getAncestorsOrDescendents(java.util.Collection nodes,
                                                    boolean predecessors)
This helper method will provide an ordered list of all the ancestors or Descendants.

The algorithm for finding ancestors and descendants is the same and this algorithm will differentiate between them based on the boolean flag.

TODO: We need to review this method and make sure that it returns nodes in a topological order. It is not clear whether any other ordering makes sense.

Parameters:
nodes -
predecessors -
Returns:

_getAncestorsOrDescendents

protected java.util.List _getAncestorsOrDescendents(java.lang.Object node,
                                                    boolean predecessors)
Provides the ancestors or descendants of a single Node.