byucc.jhdl.synth.graph
Class Graph

java.lang.Object
  byucc.jhdl.synth.graph.NamedObject
      byucc.jhdl.synth.graph.Graph

All Implemented Interfaces:

Nameable

Direct Known Subclasses:

ControlFlowGraph, DAG

public class Graph

extends NamedObject

Basic object for representing graphs. It is intended that users will extend this class for implementing any user-specific graph annotations or features.

Author:

Mike Wirthlin and Carl Worth

Field Summary

protected int	printNum To help printing a graph multiple times, during debugging an algorithm that modifies the graph regularly,etc
protected VertexVector	vertexVector This vector contains all vertices in the graph.

Fields inherited from class byucc.jhdl.synth.graph.NamedObject

name

Constructor Summary

Graph()
Default constructor.

Graph(java.lang.String name)
Construct a named graph.

Method Summary

Edge	addEdge(Edge edge) Adds an Edge to the graph using an existing Edge object.
Edge	addEdge(Vertex tail, Vertex head) Adds an Edge to the graph (tailVertex -> headVertex).
Vertex	addVertex(java.lang.String name) Adds a named vertex to the graph.
Vertex	addVertex(Vertex v)
Edge	getEdge(Vertex tail, Vertex head) Get the edge going from tail to head, (or null if no edge goes from tail to edge).
EdgeIterator	getEdges() Get a GenericIterator of all the edges in the graph.
static java.io.PrintWriter	getPrintWriter(java.lang.String fileName)
IndexedVertexIterator	getVertices() Get a list of all the vertices in the graph.
boolean	hasEdge(Edge edge) Does this graph contain the given edge
boolean	hasEdge(Vertex tail, Vertex head) Does this graph contain an edge from tail -> head
boolean	hasVertex(Vertex vertex) Does this graph contain the given vertex
void	mergeVertices(Vertex A, Vertex B) Merge two vertices.
protected Edge	newEdge(Vertex tail, Vertex head) This method will create the appropriate vertex for the graph.
protected Vertex	newVertex(java.lang.String name) This method will create the appropriate vertex for the graph.
void	printGraph() Every call of printGraph wld print a new graph with the name incremented each time
static void	printGraph(Graph g) static method that cld used from outside to print a Graph
static void	printGraph(Graph g, java.lang.String fname) a filename can be specified where the output shd go
void	printGraph(java.lang.String outputName)
static void	removeEdge(Edge edge) Removes an Edge from the graph using an existing Edge object.
void	removeEdge(Vertex tail, Vertex head) Removes an Edge from the graph.
void	removeVertex(Vertex vertex) Removes a Vertex from the graph, as well as all edges associated with the Vertex.
void	resetVisited() Reset the visited flag for all vertices in the graph.
void	setEdgeProperty(Edge e, java.lang.String key, java.lang.String value)
void	setVertexProperty(Vertex v, java.lang.String key, java.lang.String value)
java.lang.StringBuffer	toDot() Create a representation of this graph in the IBM dotty file format.
java.lang.StringBuffer	toDot(java.lang.StringBuffer s) Create a representation of this graph in the IBM dotty file format.
java.lang.String	toString() Get a String representation of this graph.

Methods inherited from class byucc.jhdl.synth.graph.NamedObject

getName, setName

Methods inherited from class java.lang.Object

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

Field Detail

vertexVector

protected VertexVector vertexVector

This vector contains all vertices in the graph. Note that the edge information is not explicity described in this class. Instead, the edge information is represented in the individual vertices. See @see Vertex to find out how edges are represented. WARNING: This object is not private so that objects that extend Graph can loop through the actual vector. However, you should *NEVER* reassign vertexVector directly. If you do, then all current VectorIterators that are pointing at vertexVector will continue to point at the old Vector rather than the new one. This includes the private Graph member vertices! In other words, the graph will be entirely broken. If you spend days trying to hunt down bugs because you didn't heed this warning, don't come whining to me, because I warned you.

printNum

protected int printNum

To help printing a graph multiple times, during debugging an algorithm that modifies the graph regularly,etc

Constructor Detail

Graph

public Graph()

Default constructor. Builds an unnamed, empty Graph (i.e. a Graph with no vertices or edges).

Graph

public Graph(java.lang.String name)

Construct a named graph. Builds a new empty Graph with the given name. (i.e. a Graph with no vertices or edges).

Parameters:

name - the name for the graph

Method Detail

addVertex

public final Vertex addVertex(java.lang.String name)

Adds a named vertex to the graph. The type of vertex that is created is determined by the protected method newVertex.

Parameters:

name - The name for the new vertex

Returns:

The new vertex added to the graph

addVertex

public final Vertex addVertex(Vertex v)

mergeVertices

public void mergeVertices(Vertex A,
                          Vertex B)

Merge two vertices.

This merge is implemented by copying all input and output edges from vertex B to vertex A. That is, all edges of the form ?->B will be replaced with ?->A and all edges B->? will be replaced with A->?. (Actually, if any of these new edges already exist on A they will not be duplicated.) Then vertex B will be removed from the graph.

Parameters:

A - one of the vertices to be merged, this vertex will still be in the graph after the merge.

B - another vertex to be merged, this vertex will be removed from the graph after the merge.

newVertex

protected Vertex newVertex(java.lang.String name)

This method will create the appropriate vertex for the graph. Users should create their own newVertex() method for subclasses that need to build a Vertex that is not a Vertex.

Returns:

A new vertex of type Vertex

removeVertex

public void removeVertex(Vertex vertex)

Removes a Vertex from the graph, as well as all edges associated with the Vertex.

Parameters:

vertex - The Vertex to remove from the graph.

addEdge

public final Edge addEdge(Vertex tail,
                          Vertex head)

Adds an Edge to the graph (tailVertex -> headVertex). Note that both the head and tail of the Edge must be created before creating the Edge. This method uses newEdge to create an edge of the appropriate type for this graph.

Parameters:

tail - The vertex corresponding to the tail of the Edge (i.e. the source of the edge)

head - The vertex corresponding to the head of the Edge (i.e. the sink of the edge)

Returns:

The new edge created in the graph

See Also:

newEdge(byucc.jhdl.synth.graph.Vertex, byucc.jhdl.synth.graph.Vertex)

addEdge

public Edge addEdge(Edge edge)

Adds an Edge to the graph using an existing Edge object.

Parameters:

edge - A valid edge object with tail and head Vertex objects that already exist in the graph.

Returns:

The edge created in the graph, (the same edge that was passed in).

removeEdge

public final void removeEdge(Vertex tail,
                             Vertex head)

Removes an Edge from the graph. (tail -> head)

Parameters:

tail - The vertex corresponding to the tail of the edge to remove.

head - The vertex corresponding to the head of the edge to remove.

removeEdge

public static final void removeEdge(Edge edge)

Removes an Edge from the graph using an existing Edge object.

Parameters:

edge - The edge to be removed. A valid Edge object with tail and head Vertex objects that exist in the graph.

newEdge

protected Edge newEdge(Vertex tail,
                       Vertex head)

This method will create the appropriate vertex for the graph. Users should create their own newVertex() method for subclasses that need to build a Vertex that is not a Vertex.

Parameters:

tail - The vertex corresponding to the tail of the Edge (i.e. the source of the edge)

head - The vertex corresponding to the head of the Edge (i.e. the sink of the edge)

Returns:

A new vertex of type Vertex

getEdge

public Edge getEdge(Vertex tail,
                    Vertex head)

Get the edge going from tail to head, (or null if no edge goes from tail to edge). This is the method to call if you need the exact edge that is in the graph, (ie. you need some property associated with that edge such as a weight). If all you need is an edge that goes from tail to head you can safely call new Edge(tail, head). The equals() method for Edge is overloaded so that your new Edge will still be determined equal to an edge from tail to head in the graph.

Parameters:

tail - The vertex at the tail of the desired edge

head - The vertex at the head of the desired edge

Returns:

the edge in the graph from tail -> head if it exists, null otherwise.

getEdges

public EdgeIterator getEdges()

Get a GenericIterator of all the edges in the graph. The EdgeIterator object returned by this method implements GenericIterator so you can use all of the GenericIterator methods to traverse the list. You will notice that GenericIterator is like Enumeration with the addition that you can move backwards. Also, the EdgeIterator object returned by this method contains its own pointer to the current element so you can safely use this object in a nested loop with other EdgeIterator objects, (but never nested with itself!).

Returns:

an EdgeIterator containing all the edges in the graph.

getVertices

public IndexedVertexIterator getVertices()

Get a list of all the vertices in the graph. The IndexedVertexIterator object returned by this method implements GenericIterator so you can use all of the GenericIterator methods to traverse the list. You will notice that GenericIterator is like Enumeration with the addition that you can move backwards. Also, the IndexedVertexIterator object returned by this method contains its own pointer to the current element so you can safely use this object in a nested loop with other IndexedVertexIterator objects, (but never nested with itself!).

Returns:

an IndexedVertexIterator containing all the vertices in the graph.

hasEdge

public boolean hasEdge(Vertex tail,
                       Vertex head)

Does this graph contain an edge from tail -> head

Parameters:

tail - the tail of the edge to look for.

head - the head of the edge to look for.

Returns:

true if there is an edge from tail to head in this graph, false otherwise.

hasEdge

public boolean hasEdge(Edge edge)

Does this graph contain the given edge

Parameters:

edge - the edge to look for.

Returns:

true if the given edge is in this graph. Note that the Edge object passed in need not be the same reference as the Edge object in the graph. This method will return true is there is an Edge from edge.getTail() to edge.getHead()

hasVertex

public boolean hasVertex(Vertex vertex)

Does this graph contain the given vertex

Parameters:

vertex - the vertex to look for

Returns:

true if vertex is found in this grpah, false otherwise.

resetVisited

public void resetVisited()

Reset the visited flag for all vertices in the graph. This method calls resetVisit fpr every vertex in the graph.

See Also:

Vertex.resetVisit()

toString

public java.lang.String toString()

Get a String representation of this graph. Currently just returns a String version of toDot.

Overrides:

toString in class NamedObject

Returns:

a String describing the contents of this graph.

See Also:

toDot()

toDot

public final java.lang.StringBuffer toDot()

Create a representation of this graph in the IBM dotty file format.

Returns:

a new StringBuffer containing the dotty representation of this graph

toDot

public final java.lang.StringBuffer toDot(java.lang.StringBuffer s)

Create a representation of this graph in the IBM dotty file format. Append this data onto the provided StringBuffer.

Parameters:

s - The StringBuffer onto which data should be appended

setVertexProperty

public void setVertexProperty(Vertex v,
                              java.lang.String key,
                              java.lang.String value)

setEdgeProperty

public void setEdgeProperty(Edge e,
                            java.lang.String key,
                            java.lang.String value)

printGraph

public void printGraph()

Every call of printGraph wld print a new graph with the name incremented each time

printGraph

public void printGraph(java.lang.String outputName)

printGraph

public static void printGraph(Graph g)

static method that cld used from outside to print a Graph

printGraph

public static void printGraph(Graph g,
                              java.lang.String fname)

a filename can be specified where the output shd go

getPrintWriter

public static java.io.PrintWriter getPrintWriter(java.lang.String fileName)