edu.byu.ece.graph
Class BasicGraph

java.lang.Object
  edu.byu.ece.graph.AbstractGraph
      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