goldman.graph
Class AdjacencyMatrixRepresentation<V,E extends Edge<V>>

java.lang.Object
  extended by goldman.graph.AdjacencyMatrixRepresentation<V,E>
All Implemented Interfaces:
GraphRepresentation<V,E>, Iterable<V>

public class AdjacencyMatrixRepresentation<V,E extends Edge<V>>
extends Object
implements GraphRepresentation<V,E>

The AdjacencyMatrixRepresentation class implements the adjacency matrix representation of a graph.


Field Summary
static int DEFAULT_INITIAL_CAPACITY
           
 
Constructor Summary
AdjacencyMatrixRepresentation(boolean isDirected)
           
 
Method Summary
 void addEdge(E edge)
          Adds the given edge to this graph.
protected  void addEdge(int sourceID, int destID, E edge)
           
 boolean addVertex(V vertex)
          It adds the given vertex unless it is already in the graph
 boolean containsEdge(V source, V dest)
          Returns true if and only if there is an edge in the graph from the source vertex to the destination vertex.
 boolean containsVertex(V vertex)
          Returns true if and only if the give vertex is in the graph.
 Iterator<E> edgesFrom(V source)
          Returns an iterator over the outgoing edges from source.
 Iterator<E> edgesTo(V dest)
          Returns an iterator over the incoming edges from dest.
 E getEdge(V source, V dest)
          Returns an edge in the graph from source to dest, or null if there is no such edge.
 boolean isDirected()
          Returns true if and only if this graph representation is being used to support a directed graph.
 NonMutatingIterator<V> iterator()
          Returns a non-mutating iterator over the vertices of the graph.
 int numVertices()
          Returns the number of vertices in this graph.
 boolean removeEdge(E edge)
          Returns true when the given edge is successfully removed, and false, if the edge did not exist.
 boolean removeVertex(V vertex)
          Removing a vertex implicitly removes all of its incident edges.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_INITIAL_CAPACITY

public static final int DEFAULT_INITIAL_CAPACITY
See Also:
Constant Field Values
Constructor Detail

AdjacencyMatrixRepresentation

public AdjacencyMatrixRepresentation(boolean isDirected)
Method Detail

isDirected

public boolean isDirected()
Description copied from interface: GraphRepresentation
Returns true if and only if this graph representation is being used to support a directed graph.

Specified by:
isDirected in interface GraphRepresentation<V,E extends Edge<V>>
Returns:
true if and only if this graph representation is being used to support a directed graph.

numVertices

public int numVertices()
Description copied from interface: GraphRepresentation
Returns the number of vertices in this graph.

Specified by:
numVertices in interface GraphRepresentation<V,E extends Edge<V>>
Returns:
the number of vertices in this graph.

containsVertex

public boolean containsVertex(V vertex)
Description copied from interface: GraphRepresentation
Returns true if and only if the give vertex is in the graph.

Specified by:
containsVertex in interface GraphRepresentation<V,E extends Edge<V>>
Returns:
true if and only if the given vertex is in this graph.

containsEdge

public boolean containsEdge(V source,
                            V dest)
Description copied from interface: GraphRepresentation
Returns true if and only if there is an edge in the graph from the source vertex to the destination vertex.

Specified by:
containsEdge in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
source - the source vertex
dest - the destination vertex
Returns:
true if and only if there is an edge in the graph from the source vertex to the destination vertex.

getEdge

public E getEdge(V source,
                 V dest)
Description copied from interface: GraphRepresentation
Returns an edge in the graph from source to dest, or null if there is no such edge.

Specified by:
getEdge in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
source - the source vertex
dest - the destination vertex
Returns:
an edge in the graph from the source vertex to the destination vertex, or null if there is no such edge. If the graph is undirected, the edge e returned may have e.source = dest and e.dest = source.

iterator

public NonMutatingIterator<V> iterator()
Description copied from interface: GraphRepresentation
Returns a non-mutating iterator over the vertices of the graph. A non-mutating iterator is returned to ensure that the application program can only remove a vertex from a graph using the removeVertex method.

Specified by:
iterator in interface GraphRepresentation<V,E extends Edge<V>>
Specified by:
iterator in interface Iterable<V>
Returns:
a non-mutating iterator over the vertices of the graph

addVertex

public boolean addVertex(V vertex)
It adds the given vertex unless it is already in the graph

Specified by:
addVertex in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
vertex - the vertex to add to this graph
Returns:
true if and only if the vertex is added to the graph

addEdge

protected void addEdge(int sourceID,
                       int destID,
                       E edge)
Parameters:
sourceID - the id associated with the source vertex
destID - the id associated with the destination vertex
edge - the edge to add
REQUIRES: the ids provided for the source and destination vertices are based upon the source and destination vertices of the provided edge

addEdge

public void addEdge(E edge)
Description copied from interface: GraphRepresentation
Adds the given edge to this graph.

Specified by:
addEdge in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
edge - the edge to add to this graph
REQUIRES: if the graph is not a multigraph, there must not already be an edge between the two vertices.

removeVertex

public boolean removeVertex(V vertex)
Removing a vertex implicitly removes all of its incident edges.

Specified by:
removeVertex in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
vertex - the vertex to be removed
Returns:
true if and only if the vertex existed and was removed.

removeEdge

public boolean removeEdge(E edge)
Description copied from interface: GraphRepresentation
Returns true when the given edge is successfully removed, and false, if the edge did not exist.

Specified by:
removeEdge in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
edge - the edge to be removed from this graph
Returns:
true when the edge is successfully removed, and false, if the edge did not exist.

edgesFrom

public Iterator<E> edgesFrom(V source)
Description copied from interface: GraphRepresentation
Returns an iterator over the outgoing edges from source. Observe that for an undirected graph, the iterator is over all edges incident to source.

Specified by:
edgesFrom in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
source - the source vertex
Returns:
an iterator over the outgoing edges from source
Throws:
IllegalArgumentException - source is not in the graph

edgesTo

public Iterator<E> edgesTo(V dest)
Description copied from interface: GraphRepresentation
Returns an iterator over the incoming edges from dest. This method throws an UnsupportedOperationException when the graph representations does not support this capability.

Specified by:
edgesTo in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
dest - the destination vertex
Returns:
an iterator over the incoming edges to dest
Throws:
IllegalArgumentException - dest is not in the graph