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

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

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

The AdjacencyListRepresentation class implements the adjacency list representation of a graph.


Constructor Summary
AdjacencyListRepresentation(boolean isDirected, boolean storeIncomingEdges)
          Observe that no parameter is needed to indicate whether the graph allows multi-edges, since the underlying representation of an adjacency list is not affected by this choice.
 
Method Summary
 void addEdge(E edge)
          Adds the given edge to this graph.
 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)
          Returns true if and only if the given vertex existed and was removed.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AdjacencyListRepresentation

public AdjacencyListRepresentation(boolean isDirected,
                                   boolean storeIncomingEdges)
Observe that no parameter is needed to indicate whether the graph allows multi-edges, since the underlying representation of an adjacency list is not affected by this choice. The differences in the implementation for a graph and a multigraph are handled by the GraphRepresentation class

Parameters:
isDirected - which is true when the graph is a directed graph
storeIncomingEdges - which is true when the incoming edges should be maintained
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 no such edge exists.

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:
an 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

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

removeVertex

public boolean removeVertex(V vertex)
Description copied from interface: GraphRepresentation
Returns true if and only if the given vertex existed and was removed.

Specified by:
removeVertex in interface GraphRepresentation<V,E extends Edge<V>>
Parameters:
vertex - the vertex to remove
Returns:
true if the vertex was in the graph, and false otherwise.

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 the given vertex

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 from the given vertex
Throws:
UnsupportedOperationException - the graph is directed and the constructor parameter specified not to maintain the inedges