// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

// Test program for Floyd's all-pairs shortest paths algorithm.
// Use any of the files in this directory with a .gph extension.
// This version is for the Adjancency Matrix representation

#include <iostream>
using namespace std;

#include "book.h"

#include "grmat.h"

// Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
  int D[G->n()][G->n()];       // Store distances
  for (int i=0; i<G->n(); i++) // Initialize D with weights
    for (int j=0; j<G->n(); j++)
      D[i][j] = G->weight(i, j);
  for (int k=0; k<G->n(); k++) // Compute all k paths
    for (int i=0; i<G->n(); i++)
      for (int j=0; j<G->n(); j++)
        if (D[i][j] > (D[i][k] + D[k][j]))
          D[i][j] = D[i][k] + D[k][j];
  // Print the result
  for (int i=0; i<G->n(); i++) {
    for (int j=0; j<G->n(); j++)
      cout << D[i][j] << " ";
    cout << endl;
  }
}

// Test Floyd's all-pairs shortest paths algorithm
// Version for Adjancency Matrix representation
main(int argc, char** argv) {
  Graph* G;
  FILE *fid;

  if (argc != 2) {
    cout << "Usage: grfloydm <file>\n";
    exit(-1);
  }

  if ((fid = fopen(argv[1], "rt")) == NULL) {
    cout << "Unable to open file |" << argv[1] << "|\n";
    exit(-1);
  }

  G = createGraph<Graphm>(fid);
  if (G == NULL) {
    cout << "Unable to create graph\n";
    exit(-1);
  }

  Floyd(G);
  return 0;
}