byucc.jhdl.synth.graph
Class Vertex

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

All Implemented Interfaces:

Nameable

Direct Known Subclasses:

CFVertex, DFVertex

public class Vertex

extends NamedObject

Represents a vertex in a graph. This data structure contains a list of all edges which leave this vertex and all edges which enter this vertex. Users may want to subclass this object to provide a Vertex with properites (i.e. distance, etc.).

Author:

Mike Wirthlin and Carl Worth

Field Summary

protected EdgeVector	inEdgeVector This object contains a list of all Edges in which this Vertex object is the head (or "sink" of the edge).
protected EdgeVector	outEdgeVector This object contains a list of all Edges in which this Vertex object is the tail (or "source" of the edge).
protected Graph	parent The Graph object to which this vertex belongs.
protected int	visited A flag used for marking vertices as they are traversed.

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

name

Constructor Summary

Vertex(Graph g)
Construct a new unnamed Vertex belonging to the given graph.

Vertex(Graph g, java.lang.String name)
Construct a new named Vertex belonging to the given graph.

Method Summary

protected Edge	findEdgeTo(Vertex head) Find the edge going from this vertex to the vertex head.
EdgeIterator	getInEdges() Get a GenericIterator of all inEdges to this Vertex.
EdgeIterator	getOutEdges() Get a GenericIterator of all outEdges from this Vertex.
Graph	getParent() Get the Graph to which this Vertex belongs.
Vertex	getSingleHead() Get the vertex which is the head of the single output edge to this vertex.
Vertex	getSingleTail() Get the vertex which is the tail of the single input edge to this vertex.
int	getVisited()
int	inDegree() Get the in-degree of this vertex.
boolean	isAdjacent(Vertex tail) Is this Vertex adjacent to the given Vertex.
boolean	isVisited() Has this vertex been visited?
int	outDegree() Get the out-degree of this vertex.
void	resetVisit() Clear the visited attribute on this vertex, (subsequent calls to isVisited will return false.
void	setProperty(java.lang.String key, java.lang.String value)
java.lang.String	toDot()
java.lang.String	toString() Generate a String representation of this object.
protected java.lang.String	vertexDotLabels()
protected java.lang.String	vertexDotProperties()
void	visit() Mark this node as visited, (subsequent calls to isVisited will return true.)
void	visit(int i)

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

parent

protected Graph parent

The Graph object to which this vertex belongs.

outEdgeVector

protected EdgeVector outEdgeVector

This object contains a list of all Edges in which this Vertex object is the tail (or "source" of the edge). It is called 'outEdges' since it contains all edges leaving or going 'out' of the vertex.

inEdgeVector

protected EdgeVector inEdgeVector

This object contains a list of all Edges in which this Vertex object is the head (or "sink" of the edge). It is called 'inEdges' since it contains all edges arriving or going 'in' the vertex.

visited

protected int visited

A flag used for marking vertices as they are traversed.

Constructor Detail

Vertex

public Vertex(Graph g)

Construct a new unnamed Vertex belonging to the given graph.

Parameters:

g - The graph to which this vertex belongs.

Vertex

public Vertex(Graph g,
              java.lang.String name)

Construct a new named Vertex belonging to the given graph.

Parameters:

g - The graph to which this vertex belongs.

name - The name for this vertex.

Method Detail

getParent

public Graph getParent()

Get the Graph to which this Vertex belongs.

Returns:

Provides the parent graph of this Vertex

isVisited

public boolean isVisited()

Has this vertex been visited?

Returns:

true if visit() has been called since resetVisit, false otherwise

resetVisit

public void resetVisit()

Clear the visited attribute on this vertex, (subsequent calls to isVisited will return false.

visit

public void visit()

Mark this node as visited, (subsequent calls to isVisited will return true.)

visit

public void visit(int i)

getVisited

public int getVisited()

isAdjacent

public boolean isAdjacent(Vertex tail)

Is this Vertex adjacent to the given Vertex. Note: This method uses the following definition of adjacency which applies to directed graphs: If a Vertex head is the head of an edge from the Vertex tail, then head.isAdjacent(tail) will return true.

Parameters:

tail - The vertex to be tested for adjacency.

Returns:

true if this vertex is adjacent to tail

findEdgeTo

protected Edge findEdgeTo(Vertex head)

Find the edge going from this vertex to the vertex head.

Parameters:

head - the vertex that is the head of the desired edge

Returns:

the edge that goes from this vertex to head.

See Also:

Graph.getEdge(byucc.jhdl.synth.graph.Vertex, byucc.jhdl.synth.graph.Vertex)

getOutEdges

public EdgeIterator getOutEdges()

Get a GenericIterator of all outEdges from this Vertex. This method provides a list of all edges leaving this vertex, (edges that have this vertex as their tail). The EdgeIterator returned contains its own pointer into the list of Edges so it is safe to use in nested loops with other EdgeIterator objects.

Returns:

an EdgeIterator containing all edges leaving this vertex.

outDegree

public int outDegree()

Get the out-degree of this vertex. This is the number of edges going out from this vertx, (the number of edges in which this vertex is the tail).

Returns:

the out-degree of this vertex

getInEdges

public EdgeIterator getInEdges()

Get a GenericIterator of all inEdges to this Vertex. This method provides a list of all edges entering this vertex, (edges that have this vertex as their head). The EdgeIterator returned contains its own pointer into the list of Edges so it is safe to use in nested loops with other EdgeIterator objects.

Returns:

an EdgeIterator containing all edges entering this vertex.

inDegree

public int inDegree()

Get the in-degree of this vertex. This is the number of edges coming in to this vertx, (the number of edges in which this vertex is the head).

Returns:

the in-degree of this vertex

getSingleTail

public Vertex getSingleTail()

Get the vertex which is the tail of the single input edge to this vertex. Throws an AmbiguousGetException if this vertex does not have exactly one input edge.

Returns:

the vertex that is the tail of the single input edge.

getSingleHead

public Vertex getSingleHead()

Get the vertex which is the head of the single output edge to this vertex. Throws an AmbiguousGetException if this vertex does not have exactly one output edge.

Returns:

the vertex that is the head of the single output edge.

setProperty

public void setProperty(java.lang.String key,
                        java.lang.String value)

vertexDotProperties

protected java.lang.String vertexDotProperties()

vertexDotLabels

protected java.lang.String vertexDotLabels()

toDot

public final java.lang.String toDot()

toString

public java.lang.String toString()

Generate a String representation of this object. For now it just returns a String version of toDot().

Overrides:

toString in class NamedObject

Returns:

a String representing this vertex.