public class ListGraph implements UndirectedGraph{ private int numVertices; // Number of vertices in the graph private int numEdges; // Number of edges in the graph // 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> /** * Constructs a graph with v vertices and v edges * */ public ListGraph(int v) { adjacentVertices = new HashSet[v]; Random randomizer = new Random(); numVertices = v; numEdges = v; //Creates a vector with hashset elements int i; for(i = 0; i<numVertices; i++) { adjacentVertices[i] = new HashSet<Integer>(); } for(i = 0; i < numVertices; ) { int a = randomizer.nextInt(v); int b = randomizer.nextInt(v); new Edge(a,b); if(!adjacentVertices[a].contains(b)) { adjacentVertices[a].add(new Integer(b)); adjacentVertices[b].add(new Integer(a)); i++; } } } private static class Edge { private int v; // v <= w 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; }