//////////////////////////////////////////////////////////////////////
// 
//  common.h  --  some common definitions for graphs and matrices
//
//////////////////////////////////////////////////////////////////////

#ifndef __COMMON_H__
#define __COMMON_H__

//Common definitons for graphs and matrices

#include <limits.h>

const int INFTY = INT_MAX;     //we depend on our special infinity
                               //being greater than any int weight

#endif // __COMMON_H_

///////////////////////////////////////////////////////////////////////////
//
//  matrix.h  --  implementation of matrix. Skip it, go to graph.h .
//
///////////////////////////////////////////////////////////////////////////

#ifndef __MATRIX_H__
#define __MATRIX_H__

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <stdlib.h>

extern const int INFTY;  //infinity for adj matrix of weighted graphs
 
//matrix of integers, initialized to variable size n x n
//on initialization an n^2 array of int is created.
//to enable [][] adressing, an array of int* is created,
//pointing to the first element of each row.
 
struct matrix {
  int size_;
  int* mat;     //n^2 array to keep the values
  int** rows;    //array of ptr to staring elts of rows
  
  int size() const { return size_; }

  matrix( );                            //construct an empty matrix
  matrix( int );                        //allocate n x n matrix
  matrix( char * filename );            //read a matrix from a file
  ~matrix() { delete[] mat; delete[] rows; } 
                                            
  int* operator [](int i) const { return rows[i]; }   
  int at( int i, int j )  { return rows[i][j]; }    

  matrix& operator= ( const matrix& other );

  matrix( const matrix& );             //copy constructor
  friend void print_matrix( const matrix& , int );
}; 

void check_size( const matrix& , const matrix& , char* error_message);
void print_matrix( const matrix& x, int wid = 4 );
void matrix_mult( matrix& c, matrix& a, matrix& b );

matrix::matrix( ) : 
  size_(0),
  mat( NULL ),
  rows( NULL ) {}
   
//allocates a matrix n x n to store values, and indexes into the
//rows
matrix::matrix( int n ) : 
  size_(n),
  mat( new int[ n*n ]),
  rows( new int*[ n ]) { 
    for( int i=0; i < n; i++ ) rows[i] = &(mat[ i*n ]);
}

// read matrix from a file - used only for testing
// expected file format: n x11 x12 ... xnn 

matrix::matrix( char* filename ){
  if( ! filename ) 
    { cout << "Filename needed for matrix source.\n"; exit(-1); }
  ifstream infile( filename );
  if( !infile ) 
    { cout << "Failed to open file.\n"; exit(-1); }

  int n;
  infile >> n;
  size_ = n;
  mat = new int[ n * n ];
  rows = new int*[ n ];

  for( int i=0; i < n; i++ ) rows[i] = &(mat[ i*n ]);

  for( int i=0; i<n; i++ )    
    for( int j=0; j<n; j++ ) infile >> mat[ i*n+j ];

  infile.close();
}

matrix& matrix::operator= ( const matrix& other ){
  if ( this == &other ){ return *this; }  //guard against self-assignment
  if ( this->size_ == other.size_ ){ 
    for( int i=0; i<size_*size_; i++ ) 
      mat[i] = other.mat[i];              //copy contents   
  }
  else {                                  //re-allocation required  
    delete mat;
    delete[] rows;
    int n = size_ = other.size_;
    mat = new int[ n*n ];
    rows = new int*[ n ]; 
    for( int i=0; i < n; i++ ) rows[i] = &(mat[ i*n ]);
    for( int i=0; i<n*n; i++ )    
        mat[ i ] = other.mat[ i ];
  }
  return *this;
}

matrix::matrix( const matrix& other ) :
  size_( other.size_ ),
  mat( new int[ size_* size_ ]),
  rows( new int*[ size_ ]) 
{ 
    int n = size_;
    for( int i=0; i < n; i++ ) rows[i] = &(mat[ i*n ]);
    for( int i=0; i<n; i++ )    
      for( int j=0; j<n; j++ ) 
        mat[ i*n+j ] = other.mat[ i*n+j ];
}

void print_matrix( const matrix& x, int wid ){
  int n = x.size();
  for( int i=0; i< x.size() ; i++){
    for( int j=0; j< x.size() ; j++) { 
     if ( x.mat[ i*n+j ] != INFTY ) cout << setw(wid) << x.mat[i*n+j] ;
     else cout << setw(wid) << right << "INF";
    }
    cout << '\n';
  }
  cout << "\n";
}

//size checker for matrices involved in operation requiring 
//matrices of the same size 

inline void check_size( const matrix& a, const matrix& b, char* error_message){
  if( a.size() != b.size() ){
    cout << "\nERROR: matrices of different sizes in " 
	 << error_message << "\n";
    exit(-1); 
  }  
}

//multiplication -- not used. Better not multiply infinities!
void matrix_mult( matrix& c, matrix& a, matrix& b ){
  int n = c.size();
  check_size( a, b , "mult" );
  check_size( a, c , "mult" );
  for( int i=0; i<n; i++ )    
    for( int j=0; j<n; j++ ) 
      for( int k=0; k<n; k++ )    
	c[i][j] += a[i][k] * b[k][j]; 
}


#endif // __MATRIX_H__

//////////////////////////////////////////////////////////////////////
// 
//  graph.h   --   graph class represented by its adjacency matrix
//
//////////////////////////////////////////////////////////////////////

#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <string>
#include <stdlib.h>
#include <fstream.h>

#include "common.h"
#include "matrix.h"   //for adj matrix

// Basic routines for a graph stored as an adjacency matrix

// this file uses no STL types or algorithms
// all algs that use STL are in graph_alg.h

// vertices are numbered 0 .. N-1  where n is the total number of 
// vertices in the graph

typedef int vertex;

// I assume that the graph is read from a file where it is represented
// by an edge list. Consequently, the size of the graph is not known
// at class declaration time, so all arrays have will have to be allocated
// by new once the number of vertices is read from the file and attached
// to corresponding pointers in the class. Later they have to be deleted 
// via delete[] .

// unweighted graph -- adj matrix contains 1's and zeros, 1's on the
// diagonal (a vertex is assumed to be connected to itself) 

// ************************** UNWEIGHTED GRAPH *************************

class graph {
protected:
  matrix*  adj;           //ptr to adjacency matrix
  string*  v_name;        //ptr to array of vertex names
  int      num_v;         //number of vertices
public:
  graph();                //needed for inheritance
  graph( char* filename );
  ~graph()                         { delete adj; delete[] v_name; } 
  bool are_connected( const vertex& x, const vertex& y ) const;
  int size(){ return num_v; }
  matrix& adj_matrix()             { return *adj; }
  string name( const vertex& v )   { return v_name[v]; }
private:
  graph( const graph & ){};   //we don't want anyone to call c.c.
};

// weighted graph -- adj matrix contains weights, has 0s on the diagonal
// (the cost of staying at a vertex is 0)
// adj matrix entries corresponding to missing edges are INFTY == INT_MAX
// (hence weight == INT_MAX is prohibited)

// weighted graph needs to override the file-reading constructor
// and are_connected. Notice that the same "bits of storage" are
// used in a different way.

class weighted_graph : public graph {
public:  
  weighted_graph( char* filename );
  bool are_connected( const vertex& x, const vertex& y ) const;
};

graph::graph() : num_v(0), adj(NULL), v_name(NULL) {}

//expected format of a graph data file: 
  // COMMENT LINE (discarded) 
  // num_v 
  // v1  name_of_v1   num_neighbors_of_v1   v11 v12 v13 ...
  // v1  name_of_v2   num_neighbors_of_v2   v21 v22 v23 ...
  // ...
  
// Note: by treating newlines differently from spaces in the file
//       I could eliminate the need for  num_neighbors_of_v  .
//       However, just using  filename >> var  is easier.
//       For the same reason the names are supposed to be 
//       one word (with _ for spaces). Recall that  
//       filename >> var  scans the input chars until next whitespace
//       (space, tab or newline). 

graph::graph( char* filename ){
  if( ! filename ) 
    { cout << "Filename needed for graph source.\n"; exit(-1); }
  ifstream infile( filename );
  if( !infile ) 
    { cout << "Failed to open file.\n"; exit(-1); }
  
  //discard the first line
  string dummy; getline( infile, dummy );

  infile >> num_v;
 
  adj    = (matrix*) new matrix(num_v);     //create adj matrix
  v_name = new string[num_v];               //create vertex names array
  
  for( int i=0; i<num_v; i++ )           //zero out adj matrix
    for( int j=i+1; j<num_v; j++ ) (*adj)[i][j] = (*adj)[j][i] = 0; 

  for( int j=0; j<num_v; j++ ) (*adj)[j][j] = 1; 
                                   //by convention, we consider any vertex
                                   //to be connected to itself
  
  int num_neighb, aux;
  vertex this_vertex, other_vertex;
  
  for( int i=0; i<num_v; i++ ){       //vertices may be listed in any order,
    infile >> this_vertex;            //but all are expected to be mentioned
    infile >> v_name[this_vertex] >> num_neighb;
    for( int j=0; j<num_neighb; j++ ){
      infile >> aux;
      (*adj)[this_vertex][aux] = 1;
    }
  }
}

// check if edge x --> y exists in the graph
bool graph::are_connected( const vertex& x, const vertex& y) const {
  return (*adj)[ x ][ y ] != 0 ;    //undefined for empty graph
}  

// ************************** WEIGHTED GRAPH *************************

//expected format of a graph data file: 
  // COMMENT LINE (discarded) 
  // num_v 
  // v1  name_of_v1   num_neighbors_of_v1   v11 weight v12 weight v13 ...
  // v1  name_of_v2   num_neighbors_of_v2   v21 weight v22 weight v23 ...
  // ...

weighted_graph::weighted_graph( char* filename ){
  if( ! filename ) 
    { cout << "Filename needed for graph source.\n"; exit(-1); }
  ifstream infile( filename );
  if( !infile ) 
    { cout << "Failed to open file.\n"; exit(-1); }

  //discard the first line
  string dummy; getline( infile, dummy );
  
  infile >> num_v;
 
  adj    = (matrix*) new matrix(num_v);     //create adj matrix
  v_name = new string[num_v];               //create vertex names array
  
  for( int i=0; i<num_v; i++ )              //INFTY out adj matrix
    for( int j=i+1; j<num_v; j++ ) (*adj)[i][j] = (*adj)[j][i] = INFTY; 

  for( int j=0; j<num_v; j++ ) (*adj)[j][j] = 0; 
                                   //by convention, cost to itseflf is 0
  
  int num_neighb, aux, weight;
  vertex this_vertex, other_vertex;
  
  for( int i=0; i<num_v; i++ ){       //vertices may be listed in any order,
    infile >> this_vertex;            //but all are expected to be mentioned
    infile >> v_name[this_vertex] >> num_neighb;
    for( int j=0; j<num_neighb; j++ ){
      infile >> aux >> weight;
      (*adj)[this_vertex][aux] = weight;
    }
  }
}

// check if edge x --> y exists in the graph
bool weighted_graph::are_connected( const vertex& x, const vertex& y) const {
  return (*adj)[ x ][ y ] != INFTY ;    //undefined for empty graph
}  


 
#endif // __GRAPH_H__


//////////////////////////////////////////////////////////////////////
// 
//  matrix-alg.h  --  Graph algorithms using the adjacency matrix
//
//////////////////////////////////////////////////////////////////////

#ifndef __MATRIX_ALG_H__
#define __MATRIX_ALG_H__

#include "common.h"
#include "matrix.h"

void floyd           ( matrix& c, const matrix& a);
void warshall        ( matrix& c, const matrix& a);
void floyd_with_predecessors ( matrix& , matrix&, const matrix& a );
void print_shortest_path( int source, int target,  const matrix& pred );

inline int min( int x, int y ){ return  x>y ? y : x; }

//fill in c with the reachability matrix. A is assumed to be
//a properly formed adjacency matrix n x n  for an unweighted graph

void warshall( matrix& c, const matrix& a){
  int n = a.size();

  c = a;                                       //overloaded !  
  for( int k=0; k<n; k++ ) 
    for( int i=0; i<n; i++ )    
      for( int j=0; j<n; j++ ) 
        c[i][j] |= c[i][k] & c[k][j] ; 
}

// fill c with the weights of minimum weight paths for a weighted graph

void floyd ( matrix& c, const matrix& a){
  int n = a.size();
  int aux;

  c = a;                                       //overloaded !  
  for( int k=0; k<n; k++ ) 
    for( int i=0; i<n; i++ )    
      for( int j=0; j<n; j++ ) {
        if( c[i][k] == INFTY || c[k][j] == INFTY ) aux = INFTY;
	else aux = c[i][k] + c[k][j];
        c[i][j] = min( c[i][j], aux );
      }
}

// fill c with the weights of minimum weight paths for a weighted graph
// fill pred with the predecessors along those paths. Namely,
//   pred[i][j]  is a vertex, the (direct) predecessor of j on the 
// shortest path from i to j if no predecessor is known yet, or none 
// exists (no path i->..->j exists), the entry pred[i][j] is set to INFTY

void floyd_with_predecessors ( matrix& pred , matrix& c , const matrix& a ){
  int n = a.size();
  int aux;

  c = a;                                       //overloaded ! 
  
  //initialize the predecessor matrix
  pred = a;              	   //makes pred an  n x n  matrix
  for(int i=0; i<n; i++)
  	for(int j=0; j<n; j++){
  		if( a[i][j] != INFTY && i != j ) pred[i][j] = i;
  	    else pred[i][j] = INFTY;
    }

  for( int k=0; k<n; k++ ) 
    for( int i=0; i<n; i++ )    
      for( int j=0; j<n; j++ ) {
        if( c[i][k] == INFTY || c[k][j] == INFTY ) aux = INFTY;
	    else aux = c[i][k] + c[k][j];
        // c[i][j] = min( c[i][j], aux );
        if( c[i][j] > aux && aux != INFTY ) {     
                                //a better path is found, correct c and pred 
        	c[i][j] = aux;
        	pred[i][j] = pred[k][j];
        }	
      }
}

//print the shortest path source->..->target by looking at the predecessor 
// matrix pred (retrace from target to source)

void print_shortest_path( int source, int target,  const matrix& pred ){
    if ( source == target ) { cout << "Just stay there!\n"; return; }
    int v = pred[source][target]; 
    if( v == INFTY ) { cout << "No path exists, sorry.\n"; return; }
    
    cout << target; 
	while ( v != source ){
		cout << " <-- " << v ;
		v = pred[source][v];
	}
	cout <<  " <-- " << source ;
}


#endif // __MATRIX_ALG_H__

//////////////////////////////////////////////////////////////////////
// 
//  test-graph.cc  --   test all of the above
//
//////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <string>

#include "matrix.h"
#include "graph.h"
#include "matrix-alg.h"

main(){

  graph G( "gr0.dat" );
  print_matrix( G.adj_matrix() );
  matrix r; 
  warshall( r, G.adj_matrix() );
  cout << "Reachability matrix (warshall):\n";
  print_matrix( r );

  weighted_graph wg( "wgr0.dat" );
  print_matrix( wg.adj_matrix() );
  floyd( r, wg.adj_matrix() );
  cout << "Minimum path distances matrix (floyd):\n";
  print_matrix( r );
  
  matrix p;
  floyd_with_predecessors( p, r, wg.adj_matrix() );
  cout << "Minimum path distances matrix (floyd):\n";
  print_matrix( r );
  cout << "Predecessor matrix:\n";
  print_matrix( p );
  
  for( int i=0; i < wg.size() ; i++)
  	for( int j=0; j < wg.size() ; j++){ 
  		cout << "Shortest path from " << i << " to " << j << " :\n"; 
 		print_shortest_path( i, j, p );
 		if( r[i][j] != INFTY && r[i][j] != 0) 
                     cout << " , cost " << r[i][j] <<  "\n";
 		cout << endl;
 	}
 		
}  

//////////////////////////////////////////////////////////////////////
// 
//  sample data files,   gr0.dat,  wgr0.dat 
//
//////////////////////////////////////////////////////////////////////

NUM NAME NUM_NEIGHBORS { NEIGHBOR_ID }*  
6
0 zero 	3 	1 2 4	
1 one   2	4 3
2 two	1	1 
3 three 2	0 2  
4 four  1	3
5 five-unconnected  0

NUM NAME NUM_NEIGHBORS { NEIGHBOR_ID WEIGHT }*  
6
0 zero 	3 	1 3	2 8	4 -4	
1 one   2	4 7	3 1
2 two	1	1 4
3 three 2	0 2	2 -5  
4 four  1	3 6
5 five-unconnected  0