#include <iostream.h>
#include <fstream.h>    // File i/o.

const int VERTICES = 32;
const int n        = 32;
const double LARGE = 10000.0;
const int m        = n*(n-1)/2;

  int main( )
{
  int i, j, k, M[n][n], P[n][m], iflag;
  int path_row, path_col, temp;
  double C[n][n], A[n][n];
  ifstream inFile;           // Input file stream variable.
  ofstream outFile;

  inFile.open("edges32.dat");
  outFile.open("spd32.dat");

  // Fill the 2D array with data from the file.

    for (int i = 0; i < VERTICES; i++) {
        for (int j = 0; j < VERTICES; j++){
            inFile >> C[i][j];
	    M[i][j] = -1;
            if(C[i][j] < 1)
                C[i][j] = LARGE;
        }
    } // for

    for (int i=0; i < VERTICES; i++){
        for (int j=0; j < m; j++){
            P[i][j] = 0;
	}
    }	

    // Close input file

    inFile.close();

   // Floyd-Warshall algorithm for all pairs shortest path.
   // Takes an nxn matrix C of edge costs and produces
   // an nxn matrix A of lengths of shortest paths.
   
  
      for (i=0; i < VERTICES; i++)
        for (j=0; j < VERTICES; j++)
          A[i][j] = C[i][j];

      for (i=0; i < VERTICES; i++)
        A[i][i] = 0;              // no self loop

      for (k=0; k < VERTICES; k++)
        for (i=0; i < VERTICES; i++)
          for (j=0; j < VERTICES; j++)
            
            if (A[i][k]+A[k][j] < A[i][j])
            {
              A[i][j] = A[i][k] + A[k][j];
              M[i][j] = k;
            }

    // Fill the 2D array with data from the file.
  
   outFile << endl << endl;

   outFile << "shortest path dist:   " << endl;
   for (int i = 1; i <= VERTICES; i++) {
       if (i < 9) outFile << i << "   ";
       else outFile << i << "  ";
       }  
   outFile << ":= " << endl;  

   for (int i = 0; i < VERTICES; i++) {
        outFile << i+1 << "  ";
        for (int j = 0; j < VERTICES; j++){
            outFile << A[i][j] << " ";
            cout << A[i][j] << " ";
        } // end for
        outFile << endl;
        cout << endl;
    } // end for
   
   outFile << ";";
   outFile << endl << endl;

   outFile << "predecessor matrix:   " << endl;
   for (int i = 1; i <= VERTICES; i++) {
       if (i < 9) outFile << i << "  ";
       else outFile << i << " " ;
       }
   outFile << ":= " << endl;  

   for (int i = 0; i < VERTICES; i++) {
        outFile << i+1 << " ";
        for (int j = 0; j < VERTICES; j++){
            outFile << M[i][j] << " ";
            cout << M[i][j] << "  ";
        } // end for
        outFile << endl;
        cout << endl;
    } // end for
   
   outFile << ";";
   outFile << endl << endl;    

    // Construct node path incidence matrix
    // rows with n*(n-1)/2 - n columns
    
    path_col = 0;
    for (i=0; i < VERTICES; i++){   
      for (j=i+1; j < VERTICES; j++){

         P[i][path_col] = 1;  // first node in path
         P[j][path_col] = 1;  // final node in path

         iflag = 0;

	 path_row = M[i][j];

         while (iflag < 1) {
            if (path_row > 0) {
                P[path_row][path_col] = 1; // intermediate node in path
                temp = path_row;
                path_row = M[temp][j];     // setup next M lookup
            }
            else if (path_row < 0) { 
                iflag = 1;
            } 

         } // end while

         path_col++;

       } // end for j
    }  // end for i
    
   outFile << endl << endl;
   outFile << "path matrix:   " << endl;
         
   for (int j = 0; j < m; j++) {
        outFile << " " ;
        for (int i = 0; i < VERTICES; i++){
            outFile << P[i][j] << " ";
        } // end for
        outFile << endl;
    } // end for
   
    outFile.close();   

}