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); if(!adjacentVertices[a].contains(b)) { adjacentVertices[a].add(b); adjacentVertices[b].add(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; } /** * 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"); } int grad = adjacentVertices[v].size(); return grad; } /** * 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) { if(v < 0 || v >= numVertices) { throw new IllegalArgumentException("Out of range"); } return new AdjacentVerticesIterator(v); } /** * Testar iteratorn */ public void test(int v) { VertexIterator test = adjacentVertices(v); System.out.println(test.next()); } private class AdjacentVerticesIterator implements VertexIterator { int nextPos = 0; int vertex; AdjacentVerticesIterator(int v) { vertex = v; }// private void findNext() {// nextPos++;// while (nextPos < numVertices && adjacentVertices[vertex] == null)// nextPos++;// } public boolean hasNext() { return nextPos < adjacentVertices[vertex].size(); } public int next() { int pos = nextPos; if (pos >= adjacentVertices[vertex].size()) { throw new NoSuchElementException("This iterator has no more elements."); } pos++; return pos; //return the element at this position. but how ? } }