package DataStructures.Graphs;

import java.util.*;

class BellmanFord
/*Implementation of Bellman ford to detect negative cycles. Graph accepts inputs in form of edges which have
start vertex, end vertes and weights. Vertices should be labelled with a number between 0 and total number of vertices-1,both inclusive*/
{
  int vertex, edge;
  private Edge edges[];
  private int index = 0;

  BellmanFord(int v, int e) {
    vertex = v;
    edge = e;
    edges = new Edge[e];
  }

  class Edge {
    int u, v;
    int w;
    /**
     * @param u Source Vertex
     * @param v End vertex
     * @param c Weight
     */
    public Edge(int a, int b, int c) {
      u = a;
      v = b;
      w = c;
    }
  }
  /**
   * @param p[] Parent array which shows updates in edges
   * @param i Current vertex under consideration
   */
  void printPath(int p[], int i) {
    if (p[i] == -1) // Found the path back to parent
    return;
    printPath(p, p[i]);
    System.out.print(i + " ");
  }

  public static void main(String args[]) {
    BellmanFord obj = new BellmanFord(0, 0); // Dummy object to call nonstatic variables
    obj.go();
  }

  public void
      go() // Interactive run for understanding the class first time. Assumes source vertex is 0 and
        // shows distaance to all vertices
      {
    Scanner sc = new Scanner(System.in); // Grab scanner object for user input
    int i, v, e, u, ve, w, j, neg = 0;
    System.out.println("Enter no. of vertices and edges please");
    v = sc.nextInt();
    e = sc.nextInt();
    Edge arr[] = new Edge[e]; // Array of edges
    System.out.println("Input edges");
    for (i = 0; i < e; i++) {
      u = sc.nextInt();
      ve = sc.nextInt();
      w = sc.nextInt();
      arr[i] = new Edge(u, ve, w);
    }
    int dist[] =
        new int
            [v]; // Distance array for holding the finalized shortest path distance between source
    // and all vertices
    int p[] = new int[v]; // Parent array for holding the paths
    for (i = 0; i < v; i++) dist[i] = Integer.MAX_VALUE; // Initializing distance values
    dist[0] = 0;
    p[0] = -1;
    for (i = 0; i < v - 1; i++) {
      for (j = 0; j < e; j++) {
        if ((int) dist[arr[j].u] != Integer.MAX_VALUE
            && dist[arr[j].v] > dist[arr[j].u] + arr[j].w) {
          dist[arr[j].v] = dist[arr[j].u] + arr[j].w; // Update
          p[arr[j].v] = arr[j].u;
        }
      }
    }
    // Final cycle for negative checking
    for (j = 0; j < e; j++)
      if ((int) dist[arr[j].u] != Integer.MAX_VALUE && dist[arr[j].v] > dist[arr[j].u] + arr[j].w) {
        neg = 1;
        System.out.println("Negative cycle");
        break;
      }
    if (neg == 0) // Go ahead and show results of computaion
    {
      System.out.println("Distances are: ");
      for (i = 0; i < v; i++) System.out.println(i + " " + dist[i]);
      System.out.println("Path followed:");
      for (i = 0; i < v; i++) {
        System.out.print("0 ");
        printPath(p, i);
        System.out.println();
      }
    }
    sc.close();
  }
  /**
   * @param source Starting vertex
   * @param end Ending vertex
   * @param Edge Array of edges
   */
  public void show(
      int source,
      int end,
      Edge arr[]) // Just shows results of computation, if graph is passed to it. The graph should
        // be created by using addEdge() method and passed by calling getEdgeArray() method
      {
    int i, j, v = vertex, e = edge, neg = 0;
    double dist[] =
        new double
            [v]; // Distance array for holding the finalized shortest path distance between source
    // and all vertices
    int p[] = new int[v]; // Parent array for holding the paths
    for (i = 0; i < v; i++) dist[i] = Integer.MAX_VALUE; // Initializing distance values
    dist[source] = 0;
    p[source] = -1;
    for (i = 0; i < v - 1; i++) {
      for (j = 0; j < e; j++) {
        if ((int) dist[arr[j].u] != Integer.MAX_VALUE
            && dist[arr[j].v] > dist[arr[j].u] + arr[j].w) {
          dist[arr[j].v] = dist[arr[j].u] + arr[j].w; // Update
          p[arr[j].v] = arr[j].u;
        }
      }
    }
    // Final cycle for negative checking
    for (j = 0; j < e; j++)
      if ((int) dist[arr[j].u] != Integer.MAX_VALUE && dist[arr[j].v] > dist[arr[j].u] + arr[j].w) {
        neg = 1;
        System.out.println("Negative cycle");
        break;
      }
    if (neg == 0) // Go ahead and show results of computaion
    {
      System.out.println("Distance is: " + dist[end]);
      System.out.println("Path followed:");
      System.out.print(source + " ");
      printPath(p, end);
      System.out.println();
    }
  }
  /**
   * @param x Source Vertex
   * @param y End vertex
   * @param z Weight
   */
  public void addEdge(int x, int y, int z) // Adds unidirectionl Edge
      {
    edges[index++] = new Edge(x, y, z);
  }

  public Edge[] getEdgeArray() {
    return edges;
  }
}