net.datastructures
Class AdjacencyListGraph<V,E>

java.lang.Object
  net.datastructures.AdjacencyListGraph<V,E>

All Implemented Interfaces:

Graph<V,E>

public class AdjacencyListGraph<V,E>
extends Object
implements Graph<V,E>

An realization of a graph according to adjacency list structure.

Author:

Roberto Tamassia, Eric Zamore

Nested Class Summary

protected class	AdjacencyListGraph.MyEdge<E> Implementation of an edge for an undirected adjacency list graph.
protected static class	AdjacencyListGraph.MyPosition<T> Implementation of a decorable position by means of a hash table.
protected class	AdjacencyListGraph.MyVertex<V> Implementation of a vertex for an undirected adjacency list graph.

Field Summary

protected NodePositionList<Edge<E>>	EList
protected NodePositionList<Vertex<V>>	VList

Constructor Summary

AdjacencyListGraph()
Default constructor that creates an empty graph

Method Summary

boolean	areAdjacent(Vertex<V> u, Vertex<V> v) Test whether two vertices are adjacent
protected AdjacencyListGraph.MyEdge<E>	checkEdge(Edge<E> e) Determines whether a given edge is valid.
protected AdjacencyListGraph.MyPosition	checkPosition(Position p) Determines whether a given position is valid.
protected AdjacencyListGraph.MyVertex<V>	checkVertex(Vertex<V> v) Determines whether a given vertex is valid.
int	degree(Vertex<V> v) Return the degree of a given vertex
Iterable<Edge<E>>	edges() Return an iterator over the edges of the graph
Vertex<V>[]	endVertices(Edge<E> e) Return the endvertices of a edge in an array of length 2
Iterable<Edge<E>>	incidentEdges(Vertex<V> v) Return an iterator over the edges incident on a vertex
Edge<E>	insertEdge(Vertex<V> v, Vertex<V> w, E o) Insert and return a new edge with a given element between two vertices
Vertex<V>	insertVertex(V o) Insert and return a new vertex with a given element
int	numEdges() Returns the number of edges of the graph
int	numVertices() Returns the number of vertices of the graph
Vertex<V>	opposite(Vertex<V> v, Edge<E> e) Return the other endvertex of an incident edge
E	removeEdge(Edge<E> e) Remove an edge and return its element
V	removeVertex(Vertex<V> v) Remove a vertex and all its incident edges and return the element stored at the removed vertex
E	replace(Edge<E> p, E o) Replaces the element of a given edge with a new element and returns the old element
Object	replace(Position p, Object o) Replace the element a given position (vertex or edge) with a new element and return the old element
V	replace(Vertex<V> p, V o) Replaces the element of a given vertex with a new element and returns the old element
String	toString() Returns a string representation of the vertex and edge lists, separated by a newline.
Iterable<Vertex<V>>	vertices() Return an iterator over the vertices of the graph

Methods inherited from class java.lang.Object

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

Field Detail

VList

protected NodePositionList<Vertex<V>> VList

EList

protected NodePositionList<Edge<E>> EList

Constructor Detail

AdjacencyListGraph

public AdjacencyListGraph()

Default constructor that creates an empty graph

Method Detail

vertices

public Iterable<Vertex<V>> vertices()

Return an iterator over the vertices of the graph

Specified by:

vertices in interface Graph<V,E>

edges

public Iterable<Edge<E>> edges()

Return an iterator over the edges of the graph

Specified by:

edges in interface Graph<V,E>

replace

public Object replace(Position p,
                      Object o)
               throws InvalidPositionException

Replace the element a given position (vertex or edge) with a new element and return the old element

Throws:

InvalidPositionException

incidentEdges

public Iterable<Edge<E>> incidentEdges(Vertex<V> v)
                                throws InvalidPositionException

Return an iterator over the edges incident on a vertex

Specified by:

incidentEdges in interface Graph<V,E>

Throws:

InvalidPositionException

endVertices

public Vertex<V>[] endVertices(Edge<E> e)
                        throws InvalidPositionException

Return the endvertices of a edge in an array of length 2

Specified by:

endVertices in interface Graph<V,E>

Throws:

InvalidPositionException

opposite

public Vertex<V> opposite(Vertex<V> v,
                          Edge<E> e)
                   throws InvalidPositionException

Return the other endvertex of an incident edge

Specified by:

opposite in interface Graph<V,E>

Throws:

InvalidPositionException

areAdjacent

public boolean areAdjacent(Vertex<V> u,
                           Vertex<V> v)
                    throws InvalidPositionException

Test whether two vertices are adjacent

Specified by:

areAdjacent in interface Graph<V,E>

Throws:

InvalidPositionException

insertVertex

public Vertex<V> insertVertex(V o)

Insert and return a new vertex with a given element

Specified by:

insertVertex in interface Graph<V,E>

insertEdge

public Edge<E> insertEdge(Vertex<V> v,
                          Vertex<V> w,
                          E o)
                   throws InvalidPositionException

Insert and return a new edge with a given element between two vertices

Specified by:

insertEdge in interface Graph<V,E>

Throws:

InvalidPositionException

removeVertex

public V removeVertex(Vertex<V> v)
               throws InvalidPositionException

Remove a vertex and all its incident edges and return the element stored at the removed vertex

Specified by:

removeVertex in interface Graph<V,E>

Throws:

InvalidPositionException

removeEdge

public E removeEdge(Edge<E> e)
             throws InvalidPositionException

Remove an edge and return its element

Specified by:

removeEdge in interface Graph<V,E>

Throws:

InvalidPositionException

degree

public int degree(Vertex<V> v)

Return the degree of a given vertex

checkPosition

protected AdjacencyListGraph.MyPosition checkPosition(Position p)
                                               throws InvalidPositionException

Determines whether a given position is valid.

Throws:

InvalidPositionException

checkVertex

protected AdjacencyListGraph.MyVertex<V> checkVertex(Vertex<V> v)
                                              throws InvalidPositionException

Determines whether a given vertex is valid.

Throws:

InvalidPositionException

checkEdge

protected AdjacencyListGraph.MyEdge<E> checkEdge(Edge<E> e)
                                          throws InvalidPositionException

Determines whether a given edge is valid.

Throws:

InvalidPositionException

toString

public String toString()

Returns a string representation of the vertex and edge lists, separated by a newline.

Overrides:

toString in class Object

numVertices

public int numVertices()

Description copied from interface: Graph

Returns the number of vertices of the graph

Specified by:

numVertices in interface Graph<V,E>

numEdges

public int numEdges()

Description copied from interface: Graph

Returns the number of edges of the graph

Specified by:

numEdges in interface Graph<V,E>

replace

public V replace(Vertex<V> p,
                 V o)
          throws InvalidPositionException

Description copied from interface: Graph

Replaces the element of a given vertex with a new element and returns the old element

Specified by:

replace in interface Graph<V,E>

Throws:

InvalidPositionException

replace

public E replace(Edge<E> p,
                 E o)
          throws InvalidPositionException

Description copied from interface: Graph

Replaces the element of a given edge with a new element and returns the old element

Specified by:

replace in interface Graph<V,E>

Throws:

InvalidPositionException