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.

Constructor Summary

Constructors

Constructor and Description
AdjacencyListGraph() Default constructor that creates an empty graph

Method Summary

Modifier and Type	Method and Description
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
java.lang.Object	replace(Position p, java.lang.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
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

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

degree

public int degree(Vertex<V> v)

Return the degree of a given vertex

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>

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

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

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

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>

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>

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>

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

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

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

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

replace

public java.lang.Object replace(Position p,
                                java.lang.Object o)
                         throws InvalidPositionException

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

Throws:

InvalidPositionException

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

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

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>