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