graph
Class MyGraph

java.lang.Object
  graph.MyGraph

All Implemented Interfaces:

AdjacencyMatrixGraph

public class MyGraph
extends java.lang.Object
implements AdjacencyMatrixGraph

Field Summary

Fields inherited from interface support.graph.AdjacencyMatrixGraph

MAX_VERTICES

Constructor Summary

MyGraph()
Constructor for your Graph, where among other things, you will most likely want to instantiate your matrix array, and your NodeSequence's.

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 vertices and edges from the graph.
CS16Edge	connectingEdge(CS16Vertex v1, CS16Vertex v2) Returns the edge that connects the two vertices.
java.util.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.
java.util.Iterator<CS16Edge>	incidentEdges(CS16Vertex v) Returns an Iterator over all the Edges that are connected to this Vertex.
CS16Edge	insertEdge(CS16Vertex v1, CS16Vertex v2, java.lang.Object edgeElement) Inserts a new Edge into your Graph.
CS16Vertex	insertVertex(java.lang.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.
java.lang.Object	removeEdge(CS16Edge e) Removes an Edge from your Graph.
java.lang.Object	removeVertex(CS16Vertex v) Removes a Vertex from your graph.
java.util.Iterator<CS16Vertex>	vertices() Returns an iterator holding all the Vertex's of the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

MyGraph

public MyGraph()

Constructor for your Graph, where among other things, you will most likely want to instantiate your matrix array, and your NodeSequence's.

See Also:

NodeSequence

Method Detail

insertVertex

public CS16Vertex insertVertex(java.lang.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(n) time.

Specified by:

insertVertex in interface AdjacencyMatrixGraph

Parameters:

vertElement - The element of the inserted Vertex.

Returns:

Returns the newly inserted Vertex.

insertEdge

public CS16Edge insertEdge(CS16Vertex v1,
                           CS16Vertex v2,
                           java.lang.Object edgeElement)
                    throws InvalidVertexException

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.

Specified by:

insertEdge in interface AdjacencyMatrixGraph

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:

Returns the newly inserted Edge.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

removeVertex

public java.lang.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.

Specified by:

removeVertex in interface AdjacencyMatrixGraph

Parameters:

v - The Vertex to remove.

Returns:

The object of the removed Vertex.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

removeEdge

public java.lang.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.

Specified by:

removeEdge in interface AdjacencyMatrixGraph

Parameters:

e - The Edge to remove.

Returns:

The object of the removed Edge.

Throws:

InvalidEdgeException - Thrown when the Edge is not valid.

connectingEdge

public 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.

Specified by:

connectingEdge in interface AdjacencyMatrixGraph

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

public java.util.Iterator<CS16Edge> incidentEdges(CS16Vertex v)
                                           throws InvalidVertexException

Returns an Iterator over all the Edges that are connected to this Vertex.

Specified by:

incidentEdges in interface AdjacencyMatrixGraph

Parameters:

v - The vertex to find the incident edges on.

Returns:

Returns an EdgeIterator holding the incident edges on v.

Throws:

InvalidVertexException - Thrown when the Vertex is not valid.

See Also:

This must run in O(n) time;

opposite

public 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.

Specified by:

opposite in interface AdjacencyMatrixGraph

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 isnot valid.

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

endVertices

public 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.

Specified by:

endVertices in interface AdjacencyMatrixGraph

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

public 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.

Specified by:

areAdjacent in interface AdjacencyMatrixGraph

Parameters:

v1 - The first Vertex to test adjacency.

v2 - The second Vertex to test adjacency.

Returns:

Returns true if the vertices are adjacent.

Throws:

InvalidVertexException - Thrown if either vertex is invalid.

edges

public java.util.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.

Specified by:

edges in interface AdjacencyMatrixGraph

Returns:

Returns an EdgeIterator containing the Edge's of the Graph.

See Also:

This must run in O(m) time.

vertices

public java.util.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.

Specified by:

vertices in interface AdjacencyMatrixGraph

Returns:

Returns an VertexIterator containing the Vertex's of the Graph.

See Also:

This must run in O(n) time.

clear

public void clear()

Clears all the vertices 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 should run in O(1) time, but depending on what you do this could also very easily run in O(n) time. We wont grade this method on the time requirements.

Specified by:

clear in interface AdjacencyMatrixGraph