320 lines
11 KiB
Java
320 lines
11 KiB
Java
package graph;
|
|
|
|
/**
|
|
* Created with xgiovio.macbookair.
|
|
* User: xgiovio
|
|
* Date: 19/05/14
|
|
* Time: 16:30
|
|
*/
|
|
|
|
import exceptions.InvalidPositionException;
|
|
import map.HashTableMap;
|
|
import position.NodePositionList;
|
|
import position.Position;
|
|
import position.PositionList;
|
|
|
|
import java.util.Iterator;
|
|
|
|
/**
|
|
* An realization of a graph according to adjacency list structure.
|
|
*
|
|
* @author Roberto Tamassia, Eric Zamore
|
|
*/
|
|
|
|
public class AdjacencyListGraph<V,E> implements Graph<V,E> {
|
|
|
|
protected NodePositionList<Vertex<V>> VList; // container for vertices
|
|
protected NodePositionList<Edge<E>> EList; // container for edges
|
|
|
|
// Default constructor that creates an empty graph
|
|
public AdjacencyListGraph() {
|
|
VList = new NodePositionList<Vertex<V>>();
|
|
EList = new NodePositionList<Edge<E>>();
|
|
}
|
|
|
|
// Return an iterator over the vertices of the graph
|
|
public Iterable<Vertex<V>> vertices() {
|
|
return VList;
|
|
}
|
|
|
|
// Return an iterator over the edges of the graph
|
|
public Iterable<Edge<E>> edges() {
|
|
return EList;
|
|
}
|
|
|
|
// Replace the element a given position (vertex or edge) with a new element and return the old element
|
|
public Object replace(Position p, Object o)
|
|
throws InvalidPositionException {
|
|
MyPosition pp = checkPosition(p);
|
|
Object temp = p.element();
|
|
pp.setElement(o);
|
|
return temp;
|
|
}
|
|
|
|
// Return an iterator over the edges incident on a vertex
|
|
public Iterable<Edge<E>> incidentEdges(Vertex<V> v)
|
|
throws InvalidPositionException {
|
|
MyVertex<V> vv = checkVertex(v);
|
|
return vv.incidentEdges();
|
|
|
|
}
|
|
|
|
// Return the endvertices of a edge in an array of length 2
|
|
public Vertex<V>[] endVertices(Edge<E> e)
|
|
throws InvalidPositionException {
|
|
MyEdge<E> ee = checkEdge(e);
|
|
return ee.endVertices();
|
|
}
|
|
|
|
// Return the other endvertex of an incident edge
|
|
public Vertex<V> opposite(Vertex<V> v, Edge<E> e) throws InvalidPositionException {
|
|
checkVertex(v);
|
|
MyEdge<E> ee = checkEdge(e);
|
|
Vertex<V>[] endv = ee.endVertices();
|
|
if (v == endv[0])
|
|
return endv[1];
|
|
else if (v == endv[1])
|
|
return endv[0];
|
|
else
|
|
throw new InvalidPositionException("No such vertex exists");
|
|
}
|
|
|
|
// Test whether two vertices are adjacent
|
|
public boolean areAdjacent(Vertex<V> u, Vertex<V> v) throws InvalidPositionException {
|
|
// search the incidence list of the vertex with smaller degree
|
|
Iterable<Edge<E>> iterToSearch;
|
|
if (degree(u) < degree(v)) {
|
|
iterToSearch = incidentEdges(u);
|
|
}
|
|
else {
|
|
iterToSearch = incidentEdges(v);
|
|
}
|
|
for (Edge<E> e: iterToSearch ) {
|
|
Vertex<V>[] endV = endVertices(e);
|
|
// if there exists an edge whose endpoints are u and v
|
|
if ((endV[0] == u && endV[1] == v) || (endV[0] == v && endV[1] == u))
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// Insert and return a new vertex with a given element
|
|
public Vertex<V> insertVertex(V o) {
|
|
MyVertex<V> vv = new MyVertex<V>(o);
|
|
VList.addLast(vv);
|
|
Position<Vertex<V>> p = VList.last();
|
|
vv.setLocation(p);
|
|
return vv;
|
|
}
|
|
|
|
// Insert and return a new edge with a given element between two vertices
|
|
public Edge<E> insertEdge(Vertex<V> v, Vertex<V> w, E o) throws InvalidPositionException {
|
|
MyVertex<V> vv = checkVertex(v);
|
|
MyVertex<V> ww = checkVertex(w);
|
|
MyEdge<E> ee = new MyEdge<E>(v, w, o);
|
|
Position<Edge<E>> pv = vv.insertIncidence(ee);
|
|
Position<Edge<E>> pw = ww.insertIncidence(ee);
|
|
ee.setIncidences(pv, pw);
|
|
EList.addLast(ee);
|
|
Position<Edge<E>> pe = EList.last();
|
|
ee.setLocation(pe);
|
|
return ee;
|
|
}
|
|
|
|
// Remove a vertex and all its incident edges and return the element stored at the removed vertex
|
|
public V removeVertex(Vertex<V> v)
|
|
throws InvalidPositionException {
|
|
MyVertex<V> vv = checkVertex(v);
|
|
Iterator<Edge<E>> inc = incidentEdges(v).iterator();
|
|
while (inc.hasNext()) {
|
|
MyEdge<E> e = (MyEdge<E>) inc.next();
|
|
if (e.location() != null) // if the edge has not been marked invalid
|
|
removeEdge(e);
|
|
}
|
|
VList.remove(vv.location());
|
|
return v.element();
|
|
}
|
|
|
|
// Remove an edge and return its element
|
|
public E removeEdge(Edge<E> e)
|
|
throws InvalidPositionException {
|
|
MyEdge<E> ee = checkEdge(e);
|
|
MyVertex<V>[] endv = ee.endVertices();
|
|
Position<Edge<E>>[] inc = ee.incidences();
|
|
endv[0].removeIncidence(inc[0]);
|
|
endv[1].removeIncidence(inc[1]);
|
|
EList.remove(ee.location());
|
|
ee.setLocation(null); // invalidating this edge
|
|
return e.element();
|
|
}
|
|
|
|
// Auxiliary methods
|
|
|
|
// Return the degree of a given vertex
|
|
public int degree(Vertex<V> v) {
|
|
MyVertex<V> vv = checkVertex(v);
|
|
return vv.degree();
|
|
}
|
|
|
|
// Determines whether a given position is valid.
|
|
protected MyPosition checkPosition(Position p)
|
|
throws InvalidPositionException {
|
|
if (p == null || !(p instanceof MyPosition))
|
|
throw new InvalidPositionException("Position is invalid");
|
|
return (MyPosition) p;
|
|
}
|
|
|
|
// Determines whether a given vertex is valid.
|
|
protected MyVertex<V> checkVertex(Vertex<V> v)
|
|
throws InvalidPositionException {
|
|
if (v == null || !(v instanceof MyVertex))
|
|
throw new InvalidPositionException("Vertex is invalid");
|
|
return (MyVertex<V>) v;
|
|
}
|
|
|
|
// Determines whether a given edge is valid.
|
|
protected MyEdge<E> checkEdge(Edge<E> e)
|
|
throws InvalidPositionException {
|
|
if (e == null || !(e instanceof MyEdge))
|
|
throw new InvalidPositionException("Edge is invalid");
|
|
return (MyEdge<E>) e;
|
|
}
|
|
|
|
// Implementation of a decorable position by means of a hash table.
|
|
protected static class MyPosition<T> extends HashTableMap<Object,Object> implements DecorablePosition<T> {
|
|
// The element stored at this position.
|
|
protected T elem;
|
|
// Returns the element stored at this position.
|
|
public T element() {
|
|
return elem;
|
|
}
|
|
// Sets the element stored at this position.
|
|
public void setElement(T o) {
|
|
elem = o;
|
|
}
|
|
}
|
|
|
|
// Returns a string representation of the vertex and edge lists, separated by a newline.
|
|
public String toString() {
|
|
return VList.toString() + "\n" + EList.toString();
|
|
}
|
|
|
|
public int numVertices() {
|
|
return VList.size();
|
|
}
|
|
|
|
public int numEdges() {
|
|
return EList.size();
|
|
}
|
|
|
|
public V replace(Vertex<V> p, V o) throws InvalidPositionException {
|
|
V temp = p.element();
|
|
MyVertex<V> vv = checkVertex(p);
|
|
vv.setElement(o);
|
|
return temp;
|
|
}
|
|
|
|
public E replace(Edge<E> p, E o) throws InvalidPositionException {
|
|
E temp = p.element();
|
|
MyEdge<E> ee = checkEdge(p);
|
|
ee.setElement(o);
|
|
return temp;
|
|
}
|
|
|
|
//Implementation of a vertex for an undirected adjacency list
|
|
//graph. Each vertex stores its incidence container and position
|
|
//in the vertex container of the graph.
|
|
protected class MyVertex<V> extends MyPosition<V> implements Vertex<V> {
|
|
// Incidence container of the vertex.
|
|
protected PositionList<Edge<E>> incEdges;
|
|
// Position of the vertex in the vertex container of the graph.
|
|
protected Position<Vertex<V>> loc;
|
|
// Constructs the vertex with the given element.
|
|
MyVertex(V o) {
|
|
elem = o;
|
|
incEdges = new NodePositionList<Edge<E>>();
|
|
}
|
|
// Return the degree of a given vertex
|
|
public int degree() {
|
|
return incEdges.size();
|
|
}
|
|
// Returns the incident edges on this vertex.
|
|
public Iterable<Edge<E>> incidentEdges() {
|
|
return incEdges;
|
|
}
|
|
// Inserts an edge into the incidence container of this vertex.
|
|
public Position<Edge<E>> insertIncidence(Edge<E> e) {
|
|
incEdges.addLast(e);
|
|
return incEdges.last();
|
|
}
|
|
//Removes an edge from the incidence container of this vertex.
|
|
public void removeIncidence(Position<Edge<E>> p) {
|
|
incEdges.remove(p);
|
|
}
|
|
// Returns the position of this vertex in the vertex container of the graph.
|
|
public Position<Vertex<V>> location() {
|
|
return loc;
|
|
}
|
|
// Sets the position of this vertex in the vertex container of the graph.
|
|
public void setLocation(Position<Vertex<V>> p) {
|
|
loc = p;
|
|
}
|
|
// Returns a string representation of the element stored at this vertex.
|
|
public String toString() {
|
|
return elem.toString();
|
|
}
|
|
}
|
|
|
|
// Implementation of an edge for an undirected adjacency list
|
|
// graph. Each edge stores its endpoints (end vertices), its
|
|
// positions within the incidence containers of its endpoints, and
|
|
// position in the edge container of the graph.
|
|
protected class MyEdge<E> extends MyPosition<E> implements Edge<E> {
|
|
|
|
// The end vertices of the edge.
|
|
protected MyVertex<V>[] endVertices;
|
|
// The positions of the entries for the edge in the incidence containers of the end vertices.
|
|
protected Position<Edge<E>>[] Inc;
|
|
// The position of the edge in the edge container of the graph.
|
|
protected Position<Edge<E>> loc;
|
|
|
|
// Constructs an edge with the given endpoints and elements.
|
|
MyEdge (Vertex<V> v, Vertex<V> w, E o) {
|
|
elem = o;
|
|
endVertices = (MyVertex<V>[]) new MyVertex[2];
|
|
endVertices[0] = (MyVertex<V>)v;
|
|
endVertices[1] = (MyVertex<V>)w;
|
|
Inc = (Position<Edge<E>>[]) new Position[2];
|
|
}
|
|
|
|
// Returns the end vertices of the edge. There are always two elements in the returned array.
|
|
public MyVertex<V>[] endVertices() {
|
|
return endVertices;
|
|
}
|
|
|
|
// Returns the positions of the edge in the incidence containers
|
|
// of its end vertices. The returned array always contains two
|
|
// elements.
|
|
public Position<Edge<E>>[] incidences() {
|
|
return Inc;
|
|
}
|
|
// Sets the positions of the edge in the incidence containers of its end vertices.
|
|
public void setIncidences(Position<Edge<E>> pv, Position<Edge<E>> pw) {
|
|
Inc[0] = pv;
|
|
Inc[1] = pw;
|
|
}
|
|
// Returns the position of the edge in the edge container of the graph.
|
|
public Position<Edge<E>> location() {
|
|
return loc;
|
|
}
|
|
// Sets the position of the edge in the edge container of the graph.
|
|
public void setLocation(Position<Edge<E>> p) {
|
|
loc = p;
|
|
}
|
|
// Returns a string representation of the edge via a tuple of vertices.
|
|
public String toString() {
|
|
return element() + "(" + endVertices[0].toString() +
|
|
"," + endVertices[1].toString() + ")";
|
|
}
|
|
}
|
|
} |