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 which we used in class. Then generate the Wiener Index for Wiener.txt. Submit your .java program and the Index.

For this you have to download following Princeton code:(you have to modify BreadthFirstPaths.java with the help of following java code and run program with txt files) I want output which is shown as below.

BreadthFirstPaths.java,

Grapth.java,

GraphClient.java

tinyCG.txt

LO20.txt

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  sources) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v  q = new Queue(); for (int v = 0; v  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  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]  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 = V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } // throw an IllegalArgumentException unless {@code 0  vertices) { if (vertices == null) { throw new IllegalArgumentException("argument is null"); } int V = marked.length; for (int v : vertices) { if (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  
  % java BreadthFirstPaths tinyCG.txt  to (8): e to 1 (1): 8-1  to 2 (1): 0-2  to 3 (2): 6-2-3 8 to 4 (2) 8-2-4  to 5 (1): 0-5 % java BreadthFirstPathsLangeG.txt 0 to  (0):  to 1 (418): e-932942-474885-82707-879889-971961 # to 2 (323): e-460790-53378-594358-780059-287921-... 8 to 3 (168) 8-713461-75238-953125-568284-358485  to 4 (144): e-460790-53378-318931-440226-380102  to 5 (566): e-932942-474885-82787-879889-971961-... 8 to 6 (349): 8-932942-474885-82787-879889-971961