The Wiener index of a vertex is the sum of the shortest path distances between v and all other vertices. The Wiener index of a graph G is the sum of the shortest path distances over all pairs of vertices. It's used by chemists (vertices = atoms, edges = bonds).

Modify BreadthFirstPaths.java to return the Wiener index of a graph. Find the shortest path distance for each pair of vertices, and sum all the paths. Start with tinyCG.txt, an easy graph, which you can do by hand to check your algorithm, or LO20.txt Then generate the Wiener Index for Wiener.txt. Submit your .java program and the Index.

Wiener.txt.

/** * The BreadthFirstPaths class represents a data type for finding * shortest paths (number of edges) from a source vertex * (or a set of source vertices) * to every other vertex in an undirected graph. * * This implementation uses breadth-first search. * The constructor takes time proportional to V + E, * where V is the number of vertices and E is the number of edges. * It uses extra space (not including the graph) proportional to V * * */ public class BreadthFirstPaths { private static final int INFINITY = Integer.MAX_VALUE; private boolean[] marked; // marked[v] = is there an s-v path private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path private int[] distTo; // distTo[v] = number of edges shortest s-v path /** * Computes the shortest path between the source vertex {@code s} * and every other vertex in the graph {@code G}. * @param G the graph * @param s the source vertex * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public BreadthFirstPaths(Graph G, int s) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; validateVertex(s); bfs(G, s); assert check(G, s); } /** * Computes the shortest path between any one of the source vertices in {@code sources} * and every other vertex in graph {@code G}. * @param G the graph * @param sources the source vertices * @throws IllegalArgumentException unless {@code 0 <= s < V} for each vertex * {@code s} in {@code sources} */ public BreadthFirstPaths(Graph G, Iterable sources) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; validateVertices(sources); bfs(G, sources); } // breadth-first search from a single source private void bfs(Graph G, int s) { Queue q = new Queue(); for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; distTo[s] = 0; marked[s] = true; q.enqueue(s); while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } // breadth-first search from multiple sources private void bfs(Graph G, Iterable sources) { Queue q = new Queue(); for (int s : sources) { marked[s] = true; distTo[s] = 0; q.enqueue(s); } while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } /** * Is there a path between the source vertex {@code s} (or sources) and vertex {@code v}? * @param v the vertex * @return {@code true} if there is a path, and {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean hasPathTo(int v) { validateVertex(v); return marked[v]; } /** * Returns the number of edges in a shortest path between the source vertex {@code s} * (or sources) and vertex {@code v}? * @param v the vertex * @return the number of edges in a shortest path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int distTo(int v) { validateVertex(v); return distTo[v]; } /** * Returns a shortest path between the source vertex {@code s} (or sources) * and {@code v}, or {@code null} if no such path. * @param v the vertex * @return the sequence of vertices on a shortest path, as an Iterable * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public Iterable pathTo(int v) { validateVertex(v); if (!hasPathTo(v)) return null; Stack path = new Stack(); int x; for (x = v; distTo[x] != 0; x = edgeTo[x]) path.push(x); path.push(x); return path; } // check optimality conditions for single source private boolean check(Graph G, int s) { // check that the distance of s = 0 if (distTo[s] != 0) { StdOut.println("distance of source " + s + " to itself = " + distTo[s]); return false; } // check that for each edge v-w dist[w] <= dist[v] + 1 // provided v is reachable from s for (int v = 0; v < G.V(); v++) { for (int w : G.adj(v)) { if (hasPathTo(v) != hasPathTo(w)) { StdOut.println("edge " + v + "-" + w); StdOut.println("hasPathTo(" + v + ") = " + hasPathTo(v)); StdOut.println("hasPathTo(" + w + ") = " + hasPathTo(w)); return false; } if (hasPathTo(v) && (distTo[w] > distTo[v] + 1)) { StdOut.println("edge " + v + "-" + w); StdOut.println("distTo[" + v + "] = " + distTo[v]); StdOut.println("distTo[" + w + "] = " + distTo[w]); return false; } } } // check that v = edgeTo[w] satisfies distTo[w] = distTo[v] + 1 // provided v is reachable from s for (int w = 0; w < G.V(); w++) { if (!hasPathTo(w) || w == s) continue; int v = edgeTo[w]; if (distTo[w] != distTo[v] + 1) { StdOut.println("shortest path edge " + v + "-" + w); StdOut.println("distTo[" + v + "] = " + distTo[v]); StdOut.println("distTo[" + w + "] = " + distTo[w]); return false; } } return true; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = marked.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertices(Iterable vertices) { if (vertices == null) { throw new IllegalArgumentException("argument is null"); } int V = marked.length; for (int v : vertices) { if (v < 0 || v >= V) { throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } } } /** * Unit tests the {@code BreadthFirstPaths} data type. * * @param args the command-line arguments */ public static void main(String[] args) { In in = new In(args[0]); Graph G = new Graph(in); // StdOut.println(G); int s = Integer.parseInt(args[1]); BreadthFirstPaths bfs = new BreadthFirstPaths(G, s); for (int v = 0; v < G.V(); v++) { if (bfs.hasPathTo(v)) { StdOut.printf("%d to %d (%d): ", s, v, bfs.distTo(v)); for (int x : bfs.pathTo(v)) { if (x == s) StdOut.print(x); else StdOut.print("-" + x); } StdOut.println(); } else { StdOut.printf("%d to %d (-): not connected ", s, v); } } } }

input file

tinyCG.txt

6 8 0 5 2 4 2 3 1 2 0 1 3 4 3 5 0 2

Run via cmd