// ----------------------------------------------------------------------------
//
// All pairs shortes path problem (Thread Pool Version).
// 
// In:  N x N matrix W such that
//       W(i,j) = weight of edge from i to j (or infinity, if none)
//
// Out: N x N matrix W such that
//      W(i,j) = length of shortest path from i to j (or infinity, if none)
//
// (c) Wolfgang Schreiner, 2005.
//
// ----------------------------------------------------------------------------

import java.util.*;
import java.util.concurrent.*;

public class PathThreadPool
{
  final static int N = 768;       // matrix dimension
  final static int L = 10;         // N = 2^L
  final static int D = 1;         // matrix density in percent
  final static int MAX = 100;     // maximum edge weight
  final static int INF = N*MAX+1; // infinity, N*MAX < INF, 2*INF must be in range

  // print result flag
  final static boolean flag = false;  

  // number of threads
  static int T;

  // thread pool
  static ExecutorService pool;

  // ----------------------------------------------------------------------------
  //
  // initialize W
  //
  // ----------------------------------------------------------------------------
  static void init(float[][] W) 
  {
    Random r = new Random(3142);

    for (int i = 0; i < N; i++)       /* initialize by random numbers */
    {        
      for (int j = 0; j < N; j++) 
      {
	if (r.nextInt(100/D) == 0)
	  W[i][j] = r.nextInt(MAX);   /* weight of edge between i and j */
	else
	  W[i][j] = INF;              /* no edge between i and j */
      }
    }
    for (int i = 0; i < N; i++)       /* initialize diagonale */
      W[i][i] = 0;

  }

  // ----------------------------------------------------------------------------
  // 
  // print W
  // 
  // ----------------------------------------------------------------------------
  static void print(float[][] W) 
  {
    int n = 0;
    for (int i = 0; i < N; i++) 
    {
      for (int j = 0; j < N; j++) 
      {
	if (W[i][j] == INF) 
	{
	  if (flag) System.out.print(" ");
	}
	else 
	{
	  n++;
	  if (flag) System.out.print(".");
	}
      }
      if (flag) System.out.println();
    }
    System.out.println("*** " + n + " paths ***");
  }

  // input/output data for threads
  static float[][] A0;
  static float[][] B0;

  static class SquareThread implements Callable<Integer>
  {
    private int i; // index of row

    // --------------------------------------------------------------------------
    // 
    // Create thread in charge of filling B[i]
    //
    // -------------------------------------------------------------------------
    public SquareThread(int i)
    {
      this.i = i;
    }

    // --------------------------------------------------------------------------
    // 
    // square A to B filling rows begin..(end-1) of B.
    // 
    // --------------------------------------------------------------------------
    public Integer call() throws Exception
    {
      for (int j = 0; j < N; j++) 
      {
        float m = A0[i][j];
        for (int k = 0; k < N; k++) 
          m = Math.min(m, A0[i][k] + A0[k][j]);
        B0[i][j] = m;
      }
      return 0;
    }
  }

  // ----------------------------------------------------------------------------
  // 
  // square A to B
  // 
  // ----------------------------------------------------------------------------
  static void square(float[][] A, float[][] B) 
  {
    A0 = A;
    B0 = B;

    Vector<Future<Integer>> result = new Vector<Future<Integer>>(N);

    for (int i = 0; i < N; i++) 
    {
      result.add(pool.submit(new SquareThread(i)));
    }

    try
    {
      for (int i = 0; i < T; i++) 
      {
        int value = result.get(i).get();
      }
    }
    catch(InterruptedException e) 
    { }
    catch(ExecutionException e) 
    { }
  }

  // ----------------------------------------------------------------------------
  // 
  // copy A to B
  // 
  // ----------------------------------------------------------------------------
  static void copy(float[][] A, float[][] B) 
  {
    for (int i = 0; i < N; i++) 
      for (int j = 0; j < N; j++) 
	B[i][j] = A[i][j];            
  }

  // ----------------------------------------------------------------------------
  // 
  // compute all pairs shortest paths
  //
  // ----------------------------------------------------------------------------
  static void path(float[][] W) 
  {
    float[][] V = new float[N][N];

    int t = 0;
    for (int s = 0; s < L-1 ; s++) {   
      if (t == 0)
	square(W, V);             /* V = W^2 */
      else
	square(V, W);             /* W = V^2 */
      t = 1 - t;
    }
    if (t == 1) copy(V, W);       /* W = V */
  }

  // ----------------------------------------------------------------------------
  //
  // main program
  //
  // ----------------------------------------------------------------------------
  public static void main(String[] args) 
  {
    if (args.length != 1)
    {
      System.out.println("Usage: PathThread <number of threads>");
      return;
    }
    try
    {
      T = Integer.parseInt(args[0]);
    }
    catch(NumberFormatException e)
    {
      System.out.println("Invalid argument (number expected): " + args[0]);
      return;
    } 

    float[][] W = new float[N][N];

    pool = Executors.newFixedThreadPool(T);
    init(W);  /* initialize matrix */
    print(W); /* print input */
    path(W);  /* compute all shortest pathes */
    print(W); /* print result */
    pool.shutdown();
  }
}