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 java.lang.Object
implements Graph<V,E>

An realization of a graph according to adjacency list structure.

Author:

Roberto Tamassia, Eric Zamore

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
int	degree(Vertex<V> v) Return the degree of a given vertex
java.lang.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
java.lang.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
<T> T	replace(Position<T> p, T 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
java.lang.String	toString() Returns a string representation of the vertex and edge lists, separated by a newline.
java.lang.Iterable<Vertex<V>>	vertices() Return an iterator over the vertices of the graph

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

AdjacencyListGraph

public AdjacencyListGraph()

Default constructor that creates an empty graph

Method Detail

vertices

public java.lang.Iterable<Vertex<V>> vertices()

Return an iterator over the vertices of the graph

Specified by:

vertices in interface Graph<V,E>

edges

public java.lang.Iterable<Edge<E>> edges()

Return an iterator over the edges of the graph

Specified by:

edges in interface Graph<V,E>

replace

public <T> T replace(Position<T> p,
                     T 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 java.lang.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

toString

public java.lang.String toString()

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

Overrides:

toString in class java.lang.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