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;
 }
}