Enhance ComputePaths.java so that it uses the specified number of threads. The idea is to split up the work among threads. For instance, when using 2 threads each thread should compute 2520/2 = 1260 graphs; using 3 threads, each thread should compute 2520/3 = 840 graphs; etc.

For instance, repeating the run from the previous question but specifying 2 threads, the output from the enhanced program looks like:

% java paths/ComputePaths 250 2 Ran Floyd-Warshall on Graph # 0: 68790 Ran Floyd-Warshall on Graph #1260: 93759 Ran Floyd-Warshall on Graph #1261: 93785 Ran Floyd-Warshall on Graph # 1: 65671 [...] Ran Floyd-Warshall on Graph #2519: 124981 All graphs computed in 23.964 seconds 

You should observe that using 2 threads your program goes faster. If not, you most likely have a bug. Make sure your program uses the number of threads that's specified.

Make "thread" class called Worker that's nested in class ComputePaths that implements the Runnable interface. Do not use the ExecutorService.

Hints:

• The "Ran Floyd-Warshall..." messages will appear out of order, which is fine
• Using an array of threads is a good idea
• Because 2520 is divisible by all integers up to and including 10, and because we won't run this code with more than 10 threads, it's absolutely trivial to divide up the work among the threads.
• The only method you have to modify in the ComputePaths class is compute().
• Your code should still work if one specifies 1 thread (and use only only thread).

Inside ComputePaths.java:

package paths;

public class ComputePaths {

public void compute(int graph_size, int num_threads) {

for (long i = 0; i < 2520; i++) {

new FloydWarshall(graph_size, i).floydWarshall();

}

}

public static void main(String[] args) {

if (args.length != 2) {

System.err.println("Usage: java ComputePaths <# threads>");

System.exit(1);

}

int graph_size = 0;

int num_threads = 0;

try {

graph_size = Integer.parseInt(args[0]);

num_threads = Integer.parseInt(args[1]);

if ((graph_size <= 0) || (num_threads < 1)) {

throw new NumberFormatException();

}

} catch (NumberFormatException e) {

System.err.println("Invalid command-line arguments");

System.exit(1);

}

double now = System.currentTimeMillis();

new ComputePaths().compute(graph_size, num_threads);

System.out.println("All graphs computed in " + (System.currentTimeMillis() - now) / 1000 + " seconds");

}

}

Inside FloydWarshall.java (Do not modify):

package paths;

import java.util.Arrays;

import java.util.Random;

public class FloydWarshall {

// graph represented by an adjacency matrix

private double[][] graph;

private long seed;

public FloydWarshall(int n, long seed) {

this.graph = new double[n][n];

this.seed = seed;

initGraph(seed);

}

private void initGraph(long seed) {

Random rng = new Random(seed);

for (int i = 0; i < graph.length; i++) {

for (int j = 0; j < graph.length; j++) {

if (rng.nextFloat() < 1.0 / (10 + 10 * seed)) {

graph[i][j] = Double.POSITIVE_INFINITY;

} else {

graph[i][j] = 1 + seed / 2520.0;

}

}

}

}

// average all-pairs shortest path

public void floydWarshall() {

double[][] distances;

int n = this.graph.length;

distances = Arrays.copyOf(this.graph, n);

for (int k = 0; k < n; k++) {

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);

}

}

}

double average_distance = 0;

for (int i=0; i < n; i++) {

for (int j=0; j < n; j++) {

average_distance += distances[i][j];

}

}

System.out.println("Ran Floyd-Warshall on Graph #" + String.format("%1$4s", this.seed) +": " + (int)average_distance);

}

}