/**
 * Class implementing the Floyd-Warshall algorithm!
 * 
 * @author 
 * 
 * Other notes/comments:
 */

// import java.util.Arrays; // in case it's needed later...


public class FW {
  
  /**
   * the data member holding the graph: graph!
   */
  // first index == src (source), second index == dst (destination)
  // value == distance from src to dst, with -1 representing infinity
  private int[][] graph; // PLEASE USE graph[src][dst] form!
  
  public static int INF = -1; // INF is -1
  
  
  
  
  
  /**
   * constructor for a FW problem!
   * @param graph_input, the input graph as an adjacency matrix
   *        it should be in [src][dst] form, with each value the distance
   *        a value of -1 will represent infinity 
   */
  public FW(int[][] graph_input) {
    this.graph = graph_input;
  }
  
  
  /**
   * 
   * @param src
   * @param dst
   * @return
   */
  public int[] path(int src, int dst) {
    // TODO - for extra credit
    return null;
  }
  
  /**
   * minDistance should return the minimum distance that it takes
   * to traverse from src to dst in this.graph
   * @param src
   * @param dst
   * @return
   */
  public int minDistance(int src, int dst) {
    // TODO
    return 0;
  }
  
  /**
   * a method for showing a 2d array nicely...
   * @param A, the 2d array to be printed
   */
  public static void print2dArray(int[][] A) {
    int WIDTH = 4;
    for (int row = 0 ; row<A.length ; ++row) {
      for (int col=0 ; col<A[row].length ; ++col) {
        String s = "" + A[row][col];
        if (A[row][col] < 0) s = " INF";
        while (s.length() < WIDTH) 
          s = " "+s;
        System.out.print( s ); // let it go...
      }
      System.out.println();
    }
  }
  
  /**
   * a method for showing a 3d array "nicely"...
   * @param A, the 3d array to be printed
   */
  public static void print3dArray(int[][][] A) {
    for (int layer = 0 ; layer < A.length ; ++layer) {
      System.out.println("Layer " + layer + ":");
      print2dArray( A[layer] );
      System.out.println();
    }
    System.out.println();
  }
  
  

  /**
   * main, for smaller tests...
   */
  public static void main(String[] args) {
    /*
    int[][] graph = { {0,     1, INF}, 
                  {INF,   0,   1},
                  {  1, INF,   0}  };
    FW fw_problem = new FW(graph);
    fw_problem.run_fw();
    System.out.println("fw table:");
    print3dArray( fw_problem.fw );
    System.out.println("pv table:");
    print2dArray( fw_problem.pv );
    */
  }

}