/*----------------------------------------------------------------------
//  parpath - parallel all-pairs shortest path algorithm
//            Written by Mike Patterson for CS133, Winter 96
//            Revised for consistency by Richard Meyer
//            Adapted for Parsec v. 1.0 on 9-8-97 by Monnica Terwilliger
//
// This parallel version performs row striping on the initial
// paths (A) matrix.
//
// For each iteration, k:
//
// the kth process passes its row values to all other
// processes, which use it to check each of their row values
// in the min() function listed above.
//
// Takes the following command line parameters:
//  -input  file, where file is the name of a file with the format:
//     N                                // size of graph
//     blank line
//     NxN matrix, N elements per line  // -1 if no edge from i to j
//                                      //  0  if i == j
//                                      // >0 otherwise
//  -output file, where file is the name of the output file.
//
//  Example: apsp.seq -input allpairs.input -output allpairs.out
//  Note: compile with -lm
//
//--------------------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAXSIZE 64

message Init {ename nodes[MAXSIZE];};
message Row  {int row[MAXSIZE]; int node;};

entity Node(int, int, int, int, ename);

/*----------------------------------------------------------------------
// Min just returns the minimum of value1 and value2
//--------------------------------------------------------------------*/
int Min(int value1, int value2)
{
  if (value1 < value2)
    return(value1);
  return(value2);
}

/*----------------------------------------------------------------------
// MaxIntSize
//
// Returns the number of characters val takes when printed.
//--------------------------------------------------------------------*/
int MaxIntSize(int val)
{
  int size = 1;     /* even '0' takes one space */

  if (val < 0) {
    val = abs(val);
    size++;         /* for the minus sign */
  }

  while (val > 9) {
    val = val / 10;
    size++;
  }

  return(size);
}

/*----------------------------------------------------------------------
// PrintMatrix
//
// Prints the matrix to the output file.
//--------------------------------------------------------------------*/
int PrintMatrix(FILE* file, int matrix [MAXSIZE][MAXSIZE], int size)
{
  int  i, j;
  int  maxval;
  int  padding;
  char formatstring[10];

  maxval = 0;
  for (i = 0; i < size; i++)
    for (j = 0; j < size; j++)
      if (abs(maxval) < abs(matrix[i][j]))
        maxval = matrix[i][j];

  padding = MaxIntSize(maxval) + 1;

  /* This next line creates something like "%4d" for the print
     stmt below, replacing the 4 with the padding value */

  sprintf(formatstring, " %%%dd", padding);

  for (i = 0; i < size; i++) {
    for (j = 0; j < size; j++)
      fprintf(file, formatstring, matrix[i][j]);
    fprintf(file, "\n");
  }
  fprintf(file, "\n");
  fclose(file);
}

/*----------------------------------------------------------------------
// ReadFile
//
// Reads in the digraph.
//--------------------------------------------------------------------*/
int ReadFile(FILE* file, int* size, int graph[MAXSIZE][MAXSIZE])
{
  int i, j;

  assert(file != NULL);

  fscanf(file, "%d", size);

  for (i = 0; i < (*size); i++)
    for (j = 0; j < (*size); j++)
      fscanf(file, "%d", &graph[i][j]);

  fclose(file);
  return(1);
}

/*----------------------------------------------------------------------
// ParseArgs
//
// Parses the command line arguments.
//--------------------------------------------------------------------*/
int ParseArgs(int argc, char* argv[], FILE** inf, FILE** outf)
{
  int i;

  for (i = 0; i < argc; i++)
    if (strcmp(argv[i], "-input") == 0) {
      if (++i < argc) {
        if ((*inf = fopen(argv[i], "r")) == 0) {
          printf("Can't open input file.\n");
          return (0);
        }
      }
      else {
        printf("Not enough arguments.");
        printf("USAGE: %s -input infile -output outfile\n", argv[0]);
        return (0);
      }
    }
    else if (strcmp(argv[i], "-output") == 0) {
      if (++i < argc) {
        if ((*outf = fopen(argv[i], "w")) == 0) {
          printf("Can't open output file.\n");
          return (0);
        }
      }
      else {
        printf("Not enough arguments.");
        printf("USAGE: %s -input infile -output outfile\n", argv[0]);
        return (0);
      }
    }

  return(1);
}

/*----------------------------------------------------------------------
// FillInMatrix
//
// Used to place a row vector into the matrix.
//--------------------------------------------------------------------*/
int FillInMatrix(
 int matrix[MAXSIZE][MAXSIZE],
 int size,
 int row,
 int const vector[MAXSIZE])
{
  int j;

  for (j = 0; j < size; j++)
    matrix[row][j] = vector[j];
}

/*----------------------------------------------------------------------
// Driver entity
//
// Reads the input, creates the node entities, collects and prints
// the results.
//--------------------------------------------------------------------*/

entity driver (int argc, char **argv)
{
  int   size;                        /* size of digraph                */
  int   i;                           /* generic counters and indices   */
  int   processors;
  int   block_size;
  int   graph[MAXSIZE][MAXSIZE];
  FILE* in_file;
  FILE* out_file;

  ename nodes[MAXSIZE];

  message Init init;
  message Row row;

  if (!ParseArgs(argc, argv, &in_file, &out_file))
    pc_exit(1);

  if (!ReadFile(in_file, &size, graph)) {
    printf("program terminating\n");
    pc_exit(1);
  }

  processors = pc_num_nodes();
  block_size = size / processors;
  if (size % processors)
    block_size++;

  for (i = 0; i < processors; i++) {
    nodes[i] = new Node(i, size, block_size, processors, self) at i;
  }

  for (i = 0; i < processors; i++)
    send Init{nodes} to nodes[i];

  for (i = 0; i < size; i++)
    send Row{graph[i], i} to nodes[i/block_size];

  for (i = 0; i < size; i++)
    receive (Row row)
      FillInMatrix(graph, size, row.node, row.row);

  PrintMatrix(out_file, graph, size);

  pc_exit(1);
}

/*----------------------------------------------------------------------
// entity Node
//
// Calculates the shortest path for a row.
//--------------------------------------------------------------------*/
entity Node (int mynode, int size, int block_size, int processors, ename spokesperson)
{
  int i, j, k;
  int my_block_size, my_base;
  ename nodes[MAXSIZE];
  ename myid;
  int   graph[MAXSIZE][MAXSIZE];

  message Init init;
  message Row row;

  my_block_size = Min(block_size, (size - (mynode * block_size)));
  my_base = block_size * mynode;

  receive (Init init)
      for (i = 0; i < processors; i++)
        nodes[i] = init.nodes[i];

  for (i = 0; i < my_block_size; i++)
    receive (Row row) {
      FillInMatrix(graph, size, row.node, row.row);
    }

  for (k = 0; k < size; k++) {
    if (mynode == (k/block_size)) {
      for (i = 0; i < processors; i++)
        send Row{graph[k], k} to nodes[i];
    }

    receive (Row row) when (row.node == k); /* do nothing */

    for (i = my_base; i < (my_base + my_block_size); i++) {
      if (graph[i][k] < 1) continue;
      for (j = 0; j < size; j++) {
        if (row.row[j] < 1)
          continue;
        if (graph[i][j] < 0)
          graph[i][j] = graph[i][k] + row.row[j];
        else
          graph[i][j] = Min(graph[i][j], (graph[i][k] + row.row[j]));
      }
    }
  }

  for (i = my_base; i < (my_base + my_block_size); i++)
    send Row{graph[i], i} to spokesperson;
}