edu.byu.ece.graph
Class BasicGraph

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

public class BasicGraph
extends AbstractGraph
implements java.lang.Cloneable

Data structure for representing a simple directed graph.

This class contains the state associated with edges and nodes. The edges are represented within NodeEdgeMap objects and all connectivity information is obtained by querying these Map objects.

The actual objects used for edges and nodes can be specified by an application-specific graph data structure.

See Also:
Serialized Form

Field Summary
protected  java.util.HashSet _nodes
          The Set of Node objects contained within the graph.
protected  NodeEdgeMap _nodeSinkMap
          A Map between graph "node" objects (which are implementation specific) and Collection objects (value).
protected  NodeEdgeMap _nodeSourceMap
          A Map between graph "node" objects (which are implementation specific) and Collection objects (value).
 
Constructor Summary
BasicGraph()
          Create an empty graph with no nodes or edges.
BasicGraph(BasicGraph graph)
          Create new graph that is a copy of the graph passed in as a parameter.
BasicGraph(java.util.Collection nodes)
          Create an empty graph initialized with the nodes passed in as a Collection but with no edges.
BasicGraph(int nodeCount)
          Create an empty graph with no nodes or edges.
 
Method Summary
 boolean addEdge(Edge edge)
          Adds the given Edge from the graph
 void addNode(java.lang.Object node)
          Add a node object.
 void addNodes(java.util.Collection nodes)
          Add a collection of node objects.
 java.lang.Object clone()
          Clone the BasicGraph object.
 boolean containsNode(java.lang.Object o)
          Determines if the given object is contained as a node within the graph.
 Edge getEdge(java.lang.Object source, java.lang.Object sink)
          Returns the first edge found that corresponds to the given source and sink objects.
 java.util.Collection<? extends Edge> getEdges()
          Return a Collection of all edges in the graph.
 java.util.Collection<? extends Edge> getEdges(java.lang.Object source, java.lang.Object sink)
          Returns a collection of edges found that correspond to the given source and sink objects.
 java.util.Collection getInputEdges(java.lang.Object node)
          Return all links in which the specified node Object is the "sink".
 java.util.Collection getNodes()
          Return all the node objects in the graph.
 java.util.Collection getNodesWithNoInputEdges()
           
 java.util.Collection getNodesWithNoOutputEdges()
           
 java.util.Collection getOutputEdges(java.lang.Object node)
          Return all links in which the specified node Object is the "source".
 java.util.Collection getSinkNodes()
          Returns a Collection of nodes which have no predecessors.
 java.util.Collection getSourceNodes()
          Returns a Collection of nodes which have no predecessors.
 BasicGraph getSubGraph(java.util.Collection nodeCollection)
          Creates a sub-graph of the given graph from a sub-set of nodes in the graph.
 BasicGraph getSubGraph2(java.util.Collection nodes)
           
 DirectedGraph invert()
           
 boolean removeEdge(Edge edge)
          Removes the given Edge from the graph
 void removeEdges(java.util.Collection edges)
           
 void removeNode(java.lang.Object node)
          Removes the given node Object from the graph Also removes ALL Edges in the graph that refer to this node
 void removeNode(java.lang.Object node, boolean removeAllEdges)
          Removes the given node Object from the graph
static java.util.List topologicalSort(AbstractEdifGraph graph)
          Performs a topological sort on the given acyclic AbstractEdifGraph.
 
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
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

_nodeSourceMap

protected NodeEdgeMap _nodeSourceMap
A Map between graph "node" objects (which are implementation specific) and Collection objects (value). The Collection objects contain Edge objects. The Collection of Edge objects associated with a given node object are those in which the given node is the "source" of the Edge.


_nodeSinkMap

protected NodeEdgeMap _nodeSinkMap
A Map between graph "node" objects (which are implementation specific) and Collection objects (value). The Collection objects contain Edge objects. The Collection of Edge objects associated with a given node object are those in which the given node is the "sink" of the Edge.


_nodes

protected java.util.HashSet _nodes
The Set of Node objects contained within the graph.

Constructor Detail

BasicGraph

public BasicGraph()
Create an empty graph with no nodes or edges.


BasicGraph

public BasicGraph(int nodeCount)
Create an empty graph with no nodes or edges. Provide internal capacity for the number of nodes specified in the node count parameter.


BasicGraph

public BasicGraph(java.util.Collection nodes)
Create an empty graph initialized with the nodes passed in as a Collection but with no edges.


BasicGraph

public BasicGraph(BasicGraph graph)
Create new graph that is a copy of the graph passed in as a parameter.

Method Detail

addNode

public void addNode(java.lang.Object node)
Add a node object.


addNodes

public void addNodes(java.util.Collection nodes)
Add a collection of node objects.


addEdge

public boolean addEdge(Edge edge)
Adds the given Edge from the graph

Parameters:
edge - The Edge object to add
Returns:
true if the edge was successfully added (If any of the internal maps changed)

clone

public java.lang.Object clone()
Clone the BasicGraph object.

Overrides:
clone in class java.lang.Object

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.

getEdge

public Edge getEdge(java.lang.Object source,
                    java.lang.Object sink)
Returns the first edge found that corresponds to the given source and sink objects. Returns null if no edge is found.

TODO: What if there are multiple edges for the same source and sink?

Specified by:
getEdge in interface DirectedGraph

getEdges

public java.util.Collection<? extends Edge> getEdges(java.lang.Object source,
                                                     java.lang.Object sink)
Returns a collection of edges found that correspond to the given source and sink objects. Returns empty Collection if no edges are found.


getEdges

public java.util.Collection<? extends 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

getInputEdges

public java.util.Collection getInputEdges(java.lang.Object node)
Return all links in which the specified node Object is the "sink".

Specified by:
getInputEdges in interface DirectedGraph
See Also:
DirectedGraph.getInputEdges(Object)

getNodes

public java.util.Collection getNodes()
Return all the node objects in the graph.

Specified by:
getNodes in interface DirectedGraph

getNodesWithNoInputEdges

public java.util.Collection getNodesWithNoInputEdges()
Returns:
A Collection of Nodes that have no incoming Edges (input Nodes)

getNodesWithNoOutputEdges

public java.util.Collection getNodesWithNoOutputEdges()
Returns:
A Collection of Nodes that have no outgoing Edges (output Nodes)

getOutputEdges

public java.util.Collection getOutputEdges(java.lang.Object node)
Return all links in which the specified node Object is the "source".

Specified by:
getOutputEdges in interface DirectedGraph

getSinkNodes

public java.util.Collection getSinkNodes()
Returns a Collection of nodes which have no predecessors.

Returns:

getSourceNodes

public java.util.Collection getSourceNodes()
Returns a Collection of nodes which have no predecessors.

Returns:

getSubGraph

public BasicGraph getSubGraph(java.util.Collection nodeCollection)
Creates a sub-graph of the given graph from a sub-set of nodes in the graph. The resulting graph contains a sub-set of nodes and only those edges that connect nodes in the sub-graph.

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.

getSubGraph2

public BasicGraph getSubGraph2(java.util.Collection nodes)

invert

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

removeEdges

public void removeEdges(java.util.Collection edges)

removeEdge

public boolean removeEdge(Edge edge)
Removes the given Edge from the graph

Parameters:
edge - The Edge object to remove
Returns:
true if the edge was successfully removed (If any of the internal maps changed)

removeNode

public void removeNode(java.lang.Object node)
Removes the given node Object from the graph Also removes ALL Edges in the graph that refer to this node

Parameters:
node - The node Object to remove

removeNode

public void removeNode(java.lang.Object node,
                       boolean removeAllEdges)
Removes the given node Object from the graph

Parameters:
node - The node Object to remove
removeAllEdges - If true, removes ALL Edges that refer to this node, not just the ones mapped from this node (the easy-to-get-to Edges). In other words, true removes ALL references to this node, while false may leave some Edges that refer to this node.

topologicalSort

public static java.util.List topologicalSort(AbstractEdifGraph graph)
Performs a topological sort on the given acyclic AbstractEdifGraph. The sorted node Objects are returned in an ordered List.

Parameters:
graph - The acyclic AbstractEdifGraph to sort
Returns:
A sorted List of the node Objects of the graph
Throws:
EdifRuntimeException - In the case of a cyclic graph