net.datastructures
Class AdjacencyListGraph

java.lang.Object
  net.datastructures.AdjacencyListGraph

All Implemented Interfaces:

Graph

public class AdjacencyListGraph

extends Object

implements Graph

An realization of a graph according to adjacency list structure.

Author:

Roberto Tamassia, Eric Zamore

Nested Class Summary

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

Field Summary

protected NodeList	E
protected NodeList	V

Constructor Summary

AdjacencyListGraph()
Default constructor that creates an empty graph

Method Summary

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

V

protected NodeList V

E

protected NodeList E

Constructor Detail

AdjacencyListGraph

public AdjacencyListGraph()

Default constructor that creates an empty graph

Method Detail

vertices

public Iterator vertices()

Return an iterator over the vertices of the graph

Specified by:

vertices in interface Graph

edges

public Iterator edges()

Return an iterator over the edges of the graph

Specified by:

edges in interface Graph

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

Specified by:

replace in interface Graph

Throws:

InvalidPositionException

incidentEdges

public Iterator incidentEdges(Vertex v)
                       throws InvalidPositionException

Return an iterator over the edges incident on a vertex

Specified by:

incidentEdges in interface Graph

Throws:

InvalidPositionException

endVertices

public Vertex[] endVertices(Edge e)
                     throws InvalidPositionException

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

Specified by:

endVertices in interface Graph

Throws:

InvalidPositionException

opposite

public Vertex opposite(Vertex v,
                       Edge e)
                throws InvalidPositionException

Return the other endvertex of an incident edge

Specified by:

opposite in interface Graph

Throws:

InvalidPositionException

areAdjacent

public boolean areAdjacent(Vertex u,
                           Vertex v)
                    throws InvalidPositionException

Test whether two vertices are adjacent

Specified by:

areAdjacent in interface Graph

Throws:

InvalidPositionException

insertVertex

public Vertex insertVertex(Object o)

Insert and return a new vertex with a given element

Specified by:

insertVertex in interface Graph

insertEdge

public Edge insertEdge(Vertex v,
                       Vertex w,
                       Object o)
                throws InvalidPositionException

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

Specified by:

insertEdge in interface Graph

Throws:

InvalidPositionException

removeVertex

public Object removeVertex(Vertex 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

Throws:

InvalidPositionException

removeEdge

public Object removeEdge(Edge e)
                  throws InvalidPositionException

Remove an edge and return its element

Specified by:

removeEdge in interface Graph

Throws:

InvalidPositionException

degree

public int degree(Vertex 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 checkVertex(Vertex v)
                                           throws InvalidPositionException

Determines whether a given vertex is valid.

Throws:

InvalidPositionException

checkEdge

protected AdjacencyListGraph.MyEdge checkEdge(Edge 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.