/*
**  floydWarshall.c
**
**  Implementazione dell'algoritmo di Floyd-Warshall per il calcolo
**  del cammino di costo minimo tra ogni coppia di vertici di un grafo G
**  con pesi assegnati agli spigoli e della chiusura transitiva di G.
**
**  FloydWarshall(G)
**    INPUT: Un grafo G orientato con funzione peso w:E(G) --> R
**    OUTPUT: La matrice D dei pesi dei cammini minimi per ciascuna
**            coppia di vertici in V(G), la matrice Pi dei predecessori
**            dei vertici di V(G) nei cammini minimi, la matrice di
**            adiacenza T del grafo chiusura transitiva di G
**    D(0) = W
**    per u = 1, 2, ..., n:
**      per v = 1, 2, ..., n:
**        se u=v o W(u,v) = infinito
**        allora Pi(0)(u,v) = null
**        altrimenti Pi(0)(u,v) = u
**      fine-ciclo
**    fine-ciclo
**    per k = 1, 2, ..., n:
**      per u = 1, 2, ..., n:
**        per v = 1, 2, ..., n:
**          T(k)(u,v) = T(k-1)(u,v) or (T(k-1)(u,k) and T(k-1)(k,v))
**          se D(k-1)(u,v) <= D(k-1)(u,k) + D(k-1)(k,v)
**          allora Pi(k)(u,v) = Pi(k-1)(u,v), D(k)(u,v) = D(k-1)(u,v)
**          altrimenti Pi(k)(u,v) = Pi(k-1)(k,v), D(k)(u,v) = D(k-1)(u,k) + D(k-1)(k,v)
**        fine-ciclo
**      fine-ciclo
**    fine-ciclo
**
**  #(@)20120430(liverani@mat.uniroma3.it)
*/

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "grafi.h"

/*
 *  Funzione che implementa l'algoritmo di Floyd-Warshall
 */

void floydWarshall(grafoPesato G, int ***D, int ***Pi, int ***T) {
  int i, j, k;
  /* inizializzazione di D, Pi */
  for (i=1; i<=G.n; i++)
    for (j=1; j<=G.n; j++) {
      D[0][i][j] = G.W[i][j];
      if (i==j || G.W[i][j]==INFINITO)
        Pi[0][i][j] = -1;
      else
        Pi[0][i][j] = i;
      if (i==j || G.W[i][j]<INFINITO)
        T[0][i][j] = 1;
      else
        T[0][i][j] = 0;
    }
  /* corpo dell'algoritmo */
  for (k=1; k<=G.n; k++) {
    for (i=1; i<=G.n; i++) {
      for (j=1; j<=G.n; j++) {
        T[k][i][j] = T[k-1][i][j] || (T[k-1][i][k] && T[k-1][k][j]);
        if (D[k-1][i][j] <= D[k-1][i][k] + D[k-1][k][j]) {
          Pi[k][i][j] = Pi[k-1][i][j];
          D[k][i][j] = D[k-1][i][j];
        } else {
          Pi[k][i][j] = Pi[k-1][k][j];
          D[k][i][j] = D[k-1][i][k] + D[k-1][k][j];
        }
      }
    }
  }
  return;
}

/*
 *  funzione principale
 */

int main(void) {
  grafoPesato G;
  int ***D, ***Pi, ***T, i, j;
  leggiGrafoPesato(&G);
  /* allocazione dinamica delle matrici D, Pi, T */
  D  = malloc((G.n+1)*sizeof(int *));
  Pi = malloc((G.n+1)*sizeof(int *));
  T  = malloc((G.n+1)*sizeof(int *));
  for (i=0; i<=G.n; i++) {
    D[i]  = malloc((G.n+1)*sizeof(int *));
    Pi[i] = malloc((G.n+1)*sizeof(int *));
    T[i]  = malloc((G.n+1)*sizeof(int *));
    for (j=0; j<=G.n; j++) {
      D[i][j]  = malloc((G.n+1)*sizeof(int));
      Pi[i][j] = malloc((G.n+1)*sizeof(int));
      T[i][j]  = malloc((G.n+1)*sizeof(int));
    }
  }
  /* esecuzione dell'algoritmo di Floyd-Warshall */
  floydWarshall(G, D, Pi, T);
  /* stampa dei risultati */
  printf("Matrice dei costi dei cammini minimi:\n");
  for (i=1; i<=G.n; i++) {
    for (j=1; j<=G.n; j++)
      if (D[G.n][i][j] < INFINITO)
        printf("%3d ", D[G.n][i][j]);
      else
        printf("INF ");
    printf("\n");
  }
  printf("\nMatrice dei cammini minimi:\n");
  for (i=1; i<=G.n; i++) {
    for (j=1; j<=G.n; j++)
      if (D[G.n][i][j] < INFINITO)
        printf("%3d ", Pi[G.n][i][j]);
      else
        printf("nil ");
    printf("\n");
  }
  printf("\nMatrice di adiacenza della chiusura transitiva di G:\n");
  for (i=1; i<=G.n; i++) {
    for (j=1; j<=G.n; j++)
      printf("%1d ", T[G.n][i][j]);
    printf("\n");
  }
  return(0);
}