support.graph
Interface AdjacencyMatrixGraph

All Known Implementing Classes:

MyGraph

public interface AdjacencyMatrixGraph

Field Summary

static Object	FROMVERTEX
static int	MAX_VERTICES
static Object	POSITION
static Object	TOVERTEX
static Object	VERTEX_NUMBER

Method Summary

boolean	areAdjacent(CS16Vertex v1, CS16Vertex v2) Returns true if there exists an Edge that connects Vertex v1 and Vertex v2.
void	clear() Clears all the vertics and edges from the graph.
CS16Edge	connectingEdge(CS16Vertex v1, CS16Vertex v2) Returns the edge that connects the two vertices.
Iterator<CS16Edge>	edges() Returns an iterator holding all the Edge's of the graph.
CS16Vertex[]	endVertices(CS16Edge e) Returns the two Vertex's that the Edge e is incident upon.
Iterator<CS16Edge>	incidentEdges(CS16Vertex v) Returns an EdgeIterator over all the Edge's that are connected to this Vertex.
CS16Edge	insertEdge(CS16Vertex v1, CS16Vertex v2, Object edgeElement) Inserts a new Edge into your Graph.
CS16Vertex	insertVertex(Object vertElement) Inserts a new Vertex into your Graph.
CS16Vertex	opposite(CS16Vertex v, CS16Edge e) Returns the Vertex that is on the other side of Edge e opposite of Vertex v.
Object	removeEdge(CS16Edge e) Removes an Edge from your Graph.
Object	removeVertex(CS16Vertex v) Removes a Vertex from your graph.
Iterator<CS16Vertex>	vertices() Returns an iterator holding all the Vertex's of the graph.

Field Detail

MAX_VERTICES

static final int MAX_VERTICES

See Also:

Constant Field Values

VERTEX_NUMBER

static final Object VERTEX_NUMBER

POSITION

static final Object POSITION

TOVERTEX

static final Object TOVERTEX

FROMVERTEX

static final Object FROMVERTEX

Method Detail

insertVertex

CS16Vertex insertVertex(Object vertElement)

Inserts a new Vertex into your Graph. You will want to first generate a unique number for your vertex that falls within the range of your adjacency array. You will then have to add the Vertex to your sequence of vertices. Finally, set a reference to its Position in the sequence. You may want to use a decorator for this purpose. You will not have to worry about the case where *more* than MAX_VERTICES vertices are in your graph. Your code should, however, be able to hold MAX_VERTICES vertices at any time. This must run in O(n^2) time. It is possible, though difficult, to get this to run in O(1) time.

Parameters:

vertElement - The element of the inserted Vertex.

Returns:

the newly inserted Vertex.

insertEdge

CS16Edge insertEdge(CS16Vertex v1,
                    CS16Vertex v2,
                    Object edgeElement)

Inserts a new Edge into your Graph. You need to update your adjacency matrix to reflect this new added Edge. Finally, the Edge needs to be added the edge sequence. Just as with insertVertex(.), the Edge will need a reference to its position in this sequence. This must run in O(1) time.

Parameters:

v1 - The first vertex of the edge connection.

v2 - The second vertex of the edge connection.

edgeElement - The element of the newly inserted edge.

Returns:

the newly inserted Edge.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

removeVertex

Object removeVertex(CS16Vertex v)
                    throws InvalidVertexException

Removes a Vertex from your graph. You will first have to remove all edges that are connected to this Vertex. (perhaps you can use other methods you will eventually write to make this easier?) Finally, remove the Vertex from the vertex sequence. This must run in O(n^2) time. It is possible, though difficult, to get this to run in O(1) time.

Parameters:

v - The Vertex to remove.

Returns:

The object of the removed Vertex.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

removeEdge

Object removeEdge(CS16Edge e)
                  throws InvalidEdgeException

Removes an Edge from your Graph. You will want to remove all references to it from your adjacency matrix. Don't forget to remove it from the edge sequence. This must run in O(1) time.

Parameters:

e - The Edge to remove.

Returns:

The object of the removed Edge.

Throws:

InvalidEdgeException - Thrown when the Edge is not valid.

connectingEdge

CS16Edge connectingEdge(CS16Vertex v1,
                        CS16Vertex v2)
                        throws InvalidVertexException,
                               NoSuchEdgeException

Returns the edge that connects the two vertices. You will want to consult your adjacency matrix to see if they are connected. If so, return that edge, otherwise throw a NoSuchEdgeException. This must run in O(1) time.

Parameters:

v1 - The first vertex that may be connected.

v2 - The second vertex that may be connected.

Returns:

The edge that connects the first and second vertices.

Throws:

InvalidVertexException - Thrown when either vertex is invalid.

NoSuchEdgeException - Thrown when no edge connects the vertices.

incidentEdges

Iterator<CS16Edge> incidentEdges(CS16Vertex v)
                                 throws InvalidVertexException

Returns an EdgeIterator over all the Edge's that are connected to this Vertex. The only current implementation of the EdgeIterator interface is the EdgeIteratorAdapter. You will also need to use an ObjectIterator as an intermediary. A good implementation of the ObjectIterator is the ArrayObjectIterator. This takes in an array and a length and returns an ObjectIterator. This must run in O(n) time;

Parameters:

v - The vertex to find the incident edges on.

Returns:

an EdgeIterator holding the incident edges on v.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

opposite

CS16Vertex opposite(CS16Vertex v,
                    CS16Edge e)
                    throws InvalidVertexException,
                           InvalidEdgeException,
                           NoSuchVertexException

Returns the Vertex that is on the other side of Edge e opposite of Vertex v. Consulting the adjacency matrix may result in a running time that is too high. An alternate way of finding the other Vertex may get this method running in the correct time. If the edge is not incident on v, then throw a NoSuchVertexException. This must run in O(1) time.

Parameters:

v - The first vertex on Edge e.

e - The edge connecting Vertex v and the uknown opposite Vertex.

Returns:

The opposite Vertex of v across Edge e.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

InvalidEdgeException - Thrown when the Edge is not valid.

NoSuchVertexException - Thrown when Edge e is not incident on v.

endVertices

CS16Vertex[] endVertices(CS16Edge e)
                         throws InvalidEdgeException

Returns the two Vertex's that the Edge e is incident upon. Again, checking the adjacency matrix may be too costly for this method. A more savvy (and decorable) approach may be in order. This must run in O(1) time.

Parameters:

e - The edge to find the connecting Vertex's on.

Returns:

An array of Vertex's holding the two connecting vertices.

Throws:

InvalidEdgeException - Thrown when the Edge e is not valid.

areAdjacent

boolean areAdjacent(CS16Vertex v1,
                    CS16Vertex v2)
                    throws InvalidVertexException

Returns true if there exists an Edge that connects Vertex v1 and Vertex v2. This must run in O(1) time.

Parameters:

v1 - The first Vertex to test adjacency.

v2 - The second Vertex to test adjacency.

Returns:

true if the vertices are adjacent.

Throws:

InvalidVertexException - Thrown if either vertex is invalid.

edges

Iterator<CS16Edge> edges()

Returns an iterator holding all the Edge's of the graph. There may be some methods in the Sequence ADT to make this method easier.

Returns:

an EdgeIterator containing the Edge's of the Graph.

See Also:

This must run in O(m) time.

vertices

Iterator<CS16Vertex> vertices()

Returns an iterator holding all the Vertex's of the graph. There may be some methods in the Sequence ADT to make this method easier.

Returns:

a VertexIterator containing the Vertex's of the Graph.

See Also:

This must run in O(n) time.

clear

void clear()

Clears all the vertics and edges from the graph. You will want to also clear the adjacency matrix. Remember the power of Java's garbage collection mechanism. If you re-instantiate something, the instance of what that Object used to be dissappears. This must run in O(1) time.