import java.util.*;/** * An undirected graph with a fixed number of vertices implemented using * adjacency lists. Space complexity is O(V + E) where V is the number * of vertices and E the number of edges. * * @author Josef Nilsen * @version 2006-03-21 */public class ListGraph implements UndirectedGraph{ private int numVertices; // Number of vertices in the graph private int numEdges; // Number of edges in the graph private final static int NO_COST = -1; // an edge with no cost // All vertices adjacent to v are stored in adjacentVertices[v]. // No set is allocated if there are no adjacent vertices. private Set<Integer>[] adjacentVertices; // HashSet<Integer>[] // Edge costs are stored in a hash map. The key is an // Edge(v, w)-object and the cost is an Integer object. private Map<Edge, Integer> edgeCosts; // HashMap<Edge, Integer> public ListGraph(int size) { if(size > 0) { numVertices = size; adjacentVertices = new HashSet[size]; edgeCosts = new HashMap<Edge, Integer>(); for(int i=0; i<size; i++) { adjacentVertices[i] = new HashSet(); } } } private static class Edge { private int v; private int w; Edge(int v, int w) { if (v <= w) { this.v = v; this.w = w; } else { this.v = w; this.w = v; } } public boolean equals(Object o) { if (o == null) return false; Edge e = (Edge) o; return (v == e.v && w == e.w); } public int hashCode() { return v<<16 + w; } } /** * Returns the number of vertices in this graph. * Time complexity: O(1). * * @return the number of vertices in this graph. */ public int numVertices() { return numVertices; } /** * Returns the number of edges in this graph. * Time complexity: O(1). * * @return the number of edges in this graph. */ public int numEdges() { return numEdges; } /** * Returns the degree of vertex v. * Time complexity: O(1). * * @param v vertex. * @return the degree of vertex v. * @throws IllegalArgumentException if v is out of range. */ public int degree(int v) throws IllegalArgumentException { if (v < 0 || v >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v + "."); } return adjacentVertices[v].size(); } /** * Returns an iterator of vertices adjacent to v. * Time complexity for iterating over all vertices: O(n), * where n is the number of adjacent vertices. * * @param v vertex. * @return an iterator of vertices adjacent to v. * @throws IllegalArgumentException if v is out of range. */ public VertexIterator adjacentVertices(int v) throws IllegalArgumentException { if (v < 0 || v >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v); } return new AdjacentVerticesIterator(v); } private class AdjacentVerticesIterator implements VertexIterator { private Iterator<Integer> setIterator; public AdjacentVerticesIterator(int v) { setIterator = adjacentVertices[v].iterator(); } public boolean hasNext() { return setIterator.hasNext(); } public int next() throws NoSuchElementException { return setIterator.next(); } } /** * Returns true if v is adjacent to w. * Time complexity: O(1). * * @param v vertex. * @param w vertex. * @return true iff v is adjacent to w. * @throws IllegalArgumentException if v or w are out of range. */ public boolean areAdjacent(int v, int w) throws IllegalArgumentException { if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v + ", w = " + w + "."); } boolean adjacent = false; if (adjacentVertices[v].contains(w) || adjacentVertices[w].contains(v)) { adjacent = true; } return adjacent; } /** * Returns the edge cost if v is adjacent to w and an edge cost * has been assigned, -1 otherwise. Time complexity: O(1). * * @param v vertex. * @param w vertex. * @return the edge cost (I'm assuming the boolean return-type was for the previous method). * @throws IllegalArgumentException if v or w are out of range. */ public int edgeCost(int v, int w) throws IllegalArgumentException { if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v + ", w = " + w + "."); } int edgeCost = -1; if (adjacentVertices[v].contains(w) || adjacentVertices[w].contains(v)) { if(edgeCosts.get(new Edge(v,w)) != null) { edgeCost = edgeCosts.get(new Edge(v,w)); } } return edgeCost; } /** * Inserts an undirected edge between vertex positions v and w. * (No edge cost is assigned.) Time complexity: O(1). * * @param v vertex position. * @param w vertex position. * @throws IllegalArgumentException if v or w are out of range. */ public void addEdge(int v, int w) throws IllegalArgumentException { if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v + ", w = " + w + "."); } if (!adjacentVertices[v].contains(w) || !adjacentVertices[w].contains(v)) { adjacentVertices[v].add(w); adjacentVertices[w].add(v); edgeCosts.put(new Edge(v,w),NO_COST); numEdges++; } } /** * Inserts an undirected edge with edge cost c between v and w. * Time complexity: O(1). * * @param c edge cost, c >= 0. * @param v vertex. * @param w vertex. * @throws IllegalArgumentException if v or w are out of range. * @throws IllegalArgumentException if c < 0. */ public void addEdge(int v, int w, int c) throws IllegalArgumentException { if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v + ", w = " + w + "."); } if (!adjacentVertices[v].contains(w) || !adjacentVertices[w].contains(v)) { adjacentVertices[v].add(w); adjacentVertices[w].add(v); edgeCosts.put(new Edge(v,w),c); numEdges++; } } /** * Removes the edge between v and w. * Time complexity: O(1). * * @param v vertex. * @param w vertex. * @throws IllegalArgumentException if v or w are out of range. */ public void removeEdge(int v, int w) throws IllegalArgumentException { if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) { throw new IllegalArgumentException( "Out of range: v = " + v + ", w = " + w + "."); } if (adjacentVertices[v].contains(w) || adjacentVertices[w].contains(v)) { adjacentVertices[v].remove(w); adjacentVertices[w].remove(v); edgeCosts.remove(new Edge(v,w)); numEdges--; } } /** * Returns a string representation of this graph. * * @return a String representation of this graph. */ public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Vertices: " + numVertices + " " + "Edges: {"); Iterator<Integer> it = null; for (int i = 0; i < numVertices; i++) { it = adjacentVertices[i].iterator(); while (it.hasNext()) { int w = it.next(); int c = -2; if (edgeCosts.get(new Edge(w,i)) != null) { c = edgeCosts.get(new Edge(w,i)); } else { c = NO_COST; } if (sb.lastIndexOf("(" + w + "," + i + "), ") == -1 && c == NO_COST) { sb.append("(" + i + "," + w + "), "); } else if (sb.lastIndexOf("(" + w + "," + i + "," + c + "), ") == -1 && c >= 0) { sb.append("(" + i + "," + w + "," + c + "), "); } } } if (numEdges > 0) { sb.setLength(sb.length() - 2); } sb.append("}"); return sb.toString(); }}