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;
    }