/**************************** FloydTest.java **********************************/

import AlgoTools.IO;

/** testet den Floyd-Algorithmus                                              */

public class FloydTest {

  final static double INF = Double.MAX_VALUE;       // Konstante unendlich
 
  private static void printMatrix(double[][]m){     // druckt Kostenmatrix
    for (int i=0; i < m.length; i++) {              // fuer jede Zeile
      for (int j=0; j < m[i].length; j++)           // fuer jede Spalte
        if (m[i][j]==INF) IO.print("      ");       // falls unendlich: INF
                     else IO.print(m[i][j],6,1);    // sonst: Kantenkosten
      IO.println();
    } IO.println();
  } 

  private static void printPath(int[][]P,int i,int j){// druckt Knotenfolge
    if (i==j) IO.print(i); else {                   // erster Knoten des Weges
      printPath(P, i, P[i][j]);                     // Anfangsfolge des Weges 
      IO.print("-" + j);                            // letzter Knoten des Weges
    }
  }

  private static void printPathMatrix(int[][]P,double[][]D){// druckt Wegematrix
    for (int i=0; i < P.length; i++){
      for (int j=0; j < P[i].length; j++){
        if (D[i][j]==INF) IO.print("???     ");    // falls kein Weg existiert
        else {                                     // falls es Weg gibt
          printPath(P,i,j);                        // drucke Knotenfolge
          IO.print("    ");                        // Abstand zum naechsten Weg
        }
      } IO.println();
    } IO.println();
  }

  public static void main (String[]argv) {         // Hauptprogramm
    final int N = 4;                               // Konstante
    double[][]C = {{0.0,  8.0,  2.0,  INF },       // Kostenmatrix
                   {INF,  0.0,  INF,  4.0 },
                   {INF,  1.0,  0.0,  6.0 },
                   {INF,  2.0,  INF,  0.0 }};
    double[][]D = new double[N][N];                // errechnete Distanzkosten
    int   [][]P = new int   [N][N];                // vorletzter Knoten auf Weg

    IO.println("Gegebene Kostenmatrix:");
    printMatrix(C);                                // drucke Kostenmatrix
    Floyd.floyd(N,C,D,P);                          // berechne kuerzeste Wege
    IO.println("Errechnete Distanzmatrix:");
    printMatrix(D);                                // drucke Kostenmatrix
    IO.println("Errechnete Wegematrix:");
    printPathMatrix(P,D);                          // drucke Wegematrix 
  } 
}