sofya.graphs
Class Graph

java.lang.Object
  sofya.graphs.Graph

Direct Known Subclasses:

CFG

public abstract class Graph
extends java.lang.Object

Class to represent a basic graph, constructed of a set of nodes connected by directed edges. Any specialized graph should be built by deriving from this class.

Version:

09/16/2004

Author:

Alex Kinneer

Field Summary

protected java.util.List	edges The collection of edges in the graph.
static int	MATCH_INCOMING For use with getEdges(Node,int,Edge[]), specifies that incoming edges to the node will be matched.
static int	MATCH_OUTGOING For use with getEdges(Node,int,Edge[]), specifies that outgoing edges from the node will be matched.
protected java.util.List	nodes The collection of nodes in the graph.

Constructor Summary

Graph()

Method Summary

protected void	addEdge(Edge e) Adds an edge to the graph.
protected void	addNode(Node n) Inserts a node into the graph.
protected void	clear() Clears the graph, such that it has no nodes or edges.
Edge	getEdge(Node sourceNode, Node sinkNode) Gets an edge in the graph.
int	getEdgeCount() Gets the total number of edges contained in the graph.
Edge[]	getEdges(Edge[] a) Gets all of the edges in the graph, in the order in which they were added to the graph.
Edge[]	getEdges(Node n, int matchType, Edge[] a) Gets either all the edges which originate on a given node or which are incident on a node.
Edge[]	getEdges(Node sourceNode, Node sinkNode, Edge[] a) Gets all edges which have the given source and sink nodes.
Node	getNode(int nodeID) Gets a node by index.
int	getNodeCount() Gets the total number of nodes contained in the graph.
Node	getRootNode() Gets the 'root' node of the graph, which is defined to be the node with ID 1.
protected void	removeEdge(Edge e) Removes an edge from the graph.
protected void	removeNode(Node n) Removes a node from the graph.
java.lang.String	toString() Returns string representation of the graph, which is a list of the edges that constitute the graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

nodes

protected java.util.List nodes

The collection of nodes in the graph.

edges

protected java.util.List edges

The collection of edges in the graph.

MATCH_OUTGOING

public static final int MATCH_OUTGOING

For use with getEdges(Node,int,Edge[]), specifies that outgoing edges from the node will be matched.

See Also:

Constant Field Values

MATCH_INCOMING

public static final int MATCH_INCOMING

For use with getEdges(Node,int,Edge[]), specifies that incoming edges to the node will be matched.

See Also:

Constant Field Values

Constructor Detail

Graph

public Graph()

Method Detail

addNode

protected void addNode(Node n)

Inserts a node into the graph.

Parameters:

n - Node to be inserted into the graph.

getNode

public Node getNode(int nodeID)

Gets a node by index. Nodes should be accessed using start-from-one numbering.

Parameters:

nodeID - ID of the node to be retrieved, where the first node in the graph is indexed as 1 (one).

Returns:

The node in the graph with the given ID (index).

getRootNode

public Node getRootNode()

Gets the 'root' node of the graph, which is defined to be the node with ID 1. This is a convenience method only, the semantics of the method are not strictly enforced and it is perfectly possible for a graph to be constructed where this definition of a root node is meaningless or even misleading.

Returns:

The 'root' node of the graph.

removeNode

protected void removeNode(Node n)

Removes a node from the graph.

Parameters:

n - Node to be removed from the graph.

addEdge

protected void addEdge(Edge e)

Adds an edge to the graph.

Parameters:

e - Edge to be added to the graph.

removeEdge

protected void removeEdge(Edge e)

Removes an edge from the graph.

Parameters:

e - Edge to be removed from the graph.

getEdge

public Edge getEdge(Node sourceNode,
                    Node sinkNode)

Gets an edge in the graph. This method will match only the first edge which is found to have the given source and sink nodes. Note that edges are searched in the order in which they were added to the graph.

Parameters:

sourceNode - Source node of the edge to be matched.

sinkNode - Sink node of the edge to be matched.

Returns:

The edge in the control flow graph with the specified source node and sink node, if any.

Throws:

java.util.NoSuchElementException - If a matching edge cannot be found in the graph.

getEdges

public Edge[] getEdges(Edge[] a)

Gets all of the edges in the graph, in the order in which they were added to the graph.

Parameters:

a - Array which will be used to determine the runtime type of the array returned by this method.

Returns:

The complete set of edges in the graph, in order of addition.

getEdges

public Edge[] getEdges(Node sourceNode,
                       Node sinkNode,
                       Edge[] a)

Gets all edges which have the given source and sink nodes.

Special explanatory note regarding CFGs: Under some circumstances, it is possible for switch statements and finally-block returns to have multiple edges which point to the same successor node (e.g. multiple cases point to the same block or multiple exceptions return to the same location after handling). The getEdge(Node,Node) method will only return the first matching edge, which may be insufficient.

Parameters:

sourceNode - Source node of matching edges.

sinkNode - Sink node of matching edges.

a - Array which will be used to determine the runtime type of the array returned by this method.

Returns:

The set of edges in the graph with the specified source node and sink node, if any.

Throws:

java.util.NoSuchElementException - If no matching edges can be found in the graph.

getEdges

public Edge[] getEdges(Node n,
                       int matchType,
                       Edge[] a)

Gets either all the edges which originate on a given node or which are incident on a node.

Parameters:

n - Node for which associated edges will be returned.

matchType - Constant indicating whether edges which start on the node or which end on the node are to be returned. Acceptable values are MATCH_OUTGOING and MATCH_INCOMING.

a - Array which will be used to determine the runtime type of the array returned by this method.

Returns:

Either the set of edges in the graph which start on the given node or the set of edges which end on the node.

Throws:

java.util.NoSuchElementException - If no matching edges can be found in the graph.

getNodeCount

public int getNodeCount()

Gets the total number of nodes contained in the graph.

Returns:

The number of nodes in the graph.

getEdgeCount

public int getEdgeCount()

Gets the total number of edges contained in the graph.

Returns:

The number of edges in the graph.

clear

protected void clear()

Clears the graph, such that it has no nodes or edges.

toString

public java.lang.String toString()

Returns string representation of the graph, which is a list of the edges that constitute the graph.

Overrides:

toString in class java.lang.Object

Returns:

List of edges that constitute this graph.

See Also:

Edge.toString()