public class ListGraph implements UndirectedGraph{ private int numVertices; // Number of vertices in the graph private int numEdges; // Number of edges in the graph private static final boolean DEBUG = false; // 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; } /** * 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); while(test.hasNext()) { System.out.println(test.next()); } } /** * New class for creating a iterator for a vertex * Incidence container. */ private class AdjacentVerticesIterator implements VertexIterator { int pos = -1; int vertex; Integer[] elementArray; AdjacentVerticesIterator(int v) { vertex = v; elementArray = adjacentVertices[vertex].toArray(new Integer[0]); } public boolean hasNext() { return pos < adjacentVertices[vertex].size(); } public int next() { pos++; if (pos >= adjacentVertices[vertex].size()) { throw new NoSuchElementException("This iterator has no more elements."); } return elementArray[pos]; } } /** * Returns true iff 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) { //om två v, w finns i min iterator så return true annars false. int i; VertexIterator it = adjacentVertices(v); while(it.hasNext()) { if(it.next() == w) { return true; } } return false; } /** * 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 true iff v is adjacent to w. * @throws IllegalArgumentException if v or w are out of range. */ public int edgeCost(int v, int w) throws IllegalArgumentException { return 0; } /** * 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) { Edge edge = new Edge(v,w); adjacentVertices[edge.v].add(edge.w); adjacentVertices[edge.w].add(edge.v); } /** * 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) { } /** * 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"); } adjacentVertices[v].remove(w); adjacentVertices[w].remove(v); } /** * Returns a string representation of this graph. * * @return a String representation of this graph. */ public String toString() { HashSet<Edge> uniqueEdgesSet = new HashSet<Edge>(); //för varje vertex börja på 0 o iterera över o skapa en kant o softa StringBuilder sb = new StringBuilder(); sb.append("Vertices: " + numVertices + " " + "Edges ["); for(int i=0; i<numVertices; i++) { //Skapa en array med all integers och skapa edge. Integer[] elementArray = adjacentVertices[i].toArray(new Integer[0]); for(int j=0;j<elementArray.length; j++) { if(i <= elementArray[j]) { sb.append("(" + i + "," + elementArray[j] + ")"); } } } sb.append(" ]"); return sb.toString(); }