package algs44;
import stdlib.*;
import algs13.Stack;
/* ***********************************************************************
 *  Compilation:  javac FloydWarshall.java
 *  Execution:    java FloydWarshall V E
 *  Dependencies: AdjMatrixEdgeWeightedDigraph.java
 *
 *  Floyd-Warshall all-pairs shortest path algorithm.
 *
 *  % java FloydWarshall 100 500
 *
 *  Should check for negative cycles during triple loop; otherwise
 *  intermediate numbers can get exponentially large.
 *  Reference: "The Floyd-Warshall algorithm on graphs with negative cycles"
 *  by Stefan Hougardy
 *
 *************************************************************************/

public class XFloydWarshall {
  private double[][] distTo;        // distTo[v][w] = length of    shortest v->w path
  private DirectedEdge[][] edgeTo;  // edgeTo[v][w] = last edge on shortest v->w path

  public XFloydWarshall(EdgeWeightedDigraph G) {
    int V = G.V();
    distTo = new double[V][V];
    edgeTo = new DirectedEdge[V][V];

    // initialize distances to infinity
    for (int v = 0; v < V; v++) {
      for (int w = 0; w < V; w++) {
        distTo[v][w] = Double.POSITIVE_INFINITY;
      }
    }

    // initialize distances using edge-weighted digraph's
    for (int v = 0; v < G.V(); v++) {
      for (DirectedEdge e : G.adj(v)) {
        distTo[e.from()][e.to()] = e.weight();
        edgeTo[e.from()][e.to()] = e;
      }
      // in case of self-loops
      if (distTo[v][v] >= 0.0) {
        distTo[v][v] = 0.0;
        edgeTo[v][v] = null;
      }
    }

    // Floyd-Warshall updates
    for (int i = 0; i < V; i++) {
      // compute shortest paths using only 0, 1, ..., i as intermediate vertices
      for (int v = 0; v < V; v++) {
        if (edgeTo[v][i] == null) continue;    // optimization
        for (int w = 0; w < V; w++) {
          if (distTo[v][w] > distTo[v][i] + distTo[i][w]) {
            distTo[v][w] = distTo[v][i] + distTo[i][w];
            edgeTo[v][w] = edgeTo[i][w];
          }
        }
        if (distTo[v][v] < 0.0) return;  // negative cycle
      }
    }
  }

  // is there a negative cycle?
  public boolean hasNegativeCycle() {
    for (int v = 0; v < distTo.length; v++)
      if (distTo[v][v] < 0.0) return true;
    return false;
  }

  // negative cycle
  public Iterable<DirectedEdge> negativeCycle() {
    for (int v = 0; v < distTo.length; v++) {
      // negative cycle in v's predecessor graph
      if (distTo[v][v] < 0.0) {
        int V = edgeTo.length;
        EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
        for (int w = 0; w < V; w++)
          if (edgeTo[v][w] != null)
            spt.addEdge(edgeTo[v][w]);
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
        assert finder.hasCycle();
        return finder.cycle();
      }
    }
    return null;
  }

  // is there a path from v to w?
  public boolean hasPath(int v, int w) {
    return distTo[v][w] < Double.POSITIVE_INFINITY;
  }


  // return length of shortest path from v to w
  public double dist(int v, int w) {
    return distTo[v][w];
  }

  // return view of shortest path from v to w, null if no such path
  public Iterable<DirectedEdge> path(int v, int w) {
    if (!hasPath(v, w) || hasNegativeCycle()) return null;
    Stack<DirectedEdge> path = new Stack<>();
    for (DirectedEdge e = edgeTo[v][w]; e != null; e = edgeTo[v][e.from()]) {
      path.push(e);
    }
    return path;
  }

  // check optimality conditions
  private boolean check(EdgeWeightedDigraph G, int s) {

    // no negative cycle
    if (!hasNegativeCycle()) {
      for (int v = 0; v < G.V(); v++) {
        for (DirectedEdge e : G.adj(v)) {
          int w = e.to();
          for (int i = 0; i < G.V(); i++) {
            if (distTo[i][w] > distTo[i][v] + e.weight()) {
              System.err.println("edge " + e + " is eligible");
              return false;
            }
          }
        }
      }
    }
    return true;
  }



  public static void main(String[] args) {

    // random graph with V vertices and E edges, parallel edges allowed
    int V = Integer.parseInt(args[0]);
    int E = Integer.parseInt(args[1]);
    EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
    for (int i = 0; i < E; i++) {
      int v = (int) (V * Math.random());
      int w = (int) (V * Math.random());
      double weight = Math.round(100 * (Math.random() - 0.15)) / 100.0;
      if (v == w) G.addEdge(new DirectedEdge(v, w, Math.abs(weight)));
      else        G.addEdge(new DirectedEdge(v, w, weight));
    }

    StdOut.println(G);

    // run Floyd-Warshall algorithm
    XFloydWarshall spt = new XFloydWarshall(G);

    // print all-pairs shortest path distances
    StdOut.format("     ");
    for (int v = 0; v < G.V(); v++) {
      StdOut.format("%6d ", v);
    }
    StdOut.println();
    for (int v = 0; v < G.V(); v++) {
      StdOut.format("%3d: ", v);
      for (int w = 0; w < G.V(); w++) {
        if (spt.hasPath(v, w)) StdOut.format("%6.2f ", spt.dist(v, w));
        else                   StdOut.format("   Inf ");
      }
      StdOut.println();
    }

    // print negative cycle
    if (spt.hasNegativeCycle()) {
      StdOut.println("Negative cost cycle:");
      for (DirectedEdge e : spt.negativeCycle())
        StdOut.println(e);
      StdOut.println();
    }

    // print all-pairs shortest paths
    else {
      for (int v = 0; v < G.V(); v++) {
        for (int w = 0; w < G.V(); w++) {
          if (spt.hasPath(v, w)) {
            StdOut.format("%d to %d (%5.2f)  ", v, w, spt.dist(v, w));
            for (DirectedEdge e : spt.path(v, w))
              StdOut.print(e + "  ");
            StdOut.println();
          }
          else {
            StdOut.format("%d to %d          no path\n", v, w);
          }
        }
      }
    }

  }

}