package algorithms.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import datastructures.graph.AbstractGraph;
import datastructures.graph.Edge;
import datastructures.graph.UndirectedGraph;
import datastructures.graph.Vertex;

public class BellmanFordShortestPath {
  private AbstractGraph<String> graph = null;
  private Map<Vertex<String>, Vertex<String>> parentVerticesMap = null;
  private Map<Vertex<String>, Integer> distancesMap = null;
  private Vertex<String> sourceVertex = null;

  public BellmanFordShortestPath() {
    graph = new UndirectedGraph<String>();
    parentVerticesMap = new HashMap<Vertex<String>, Vertex<String>>();
    distancesMap = new HashMap<Vertex<String>, Integer>();
  }

  public void constructGraph(String[] input) {
    for (String line : input) {
      String[] values = line.split(" ");
      String action = values[0];
      Vertex<String> sourceVertex = null, destVertex = null;
      switch (action) {
      case "vertex":
        Vertex<String> vertex = graph.createVertex(values[1]);
        if (vertex != null) {
          System.out.println("Created Vertex with label: " + values[1]);
        } else {
          System.out.println("Vertex creation failed for label: " + values[1]);
        }
        break;
      case "edge":
        sourceVertex = graph.getVertex(values[1]);
        destVertex = graph.getVertex(values[2]);
        if (graph.addEdge(sourceVertex, destVertex, Integer.parseInt(values[3]))) {
          System.out.println("Edge created between: " + values[1] + " and " + values[2] + " with weight: " + values[3]);
        } else {
          System.out.println("Either of the vertices dont exist");
        }
        break;
      }
    }
  }

  public void computeShortestPath(String label) {
    Vertex<String> sourceVertex = graph.getVertex(label);
    if (sourceVertex == null) {
      return;
    }

    this.sourceVertex = sourceVertex;
    distancesMap = new HashMap<Vertex<String>, Integer>();
    parentVerticesMap = new HashMap<Vertex<String>, Vertex<String>>();
    distancesMap.put(sourceVertex, 0);

    Set<Edge<String>> edges = graph.edgesSet();
    for (int i = 0; i < graph.numVertices() - 1; i++) {
      relaxAllEdges(edges, false);
    }

    // Detect Negative Weight Cycle
    relaxAllEdges(edges, true);
  }

  public Integer getShortestDistanceTo(String label) {
    Vertex<String> vertex = graph.getVertex(label);
    if (vertex == null || distancesMap.get(vertex) == null) {
      return Integer.MAX_VALUE;
    } else {
      return distancesMap.get(vertex);
    }
  }

  public List<String> getShortestPathTo(String label) {
    Vertex<String> vertex = graph.getVertex(label);
    if (vertex == null) {
      return new ArrayList<String>();
    }

    List<String> minimumPath = new ArrayList<String>();
    getShortestPath(vertex, this.sourceVertex, minimumPath);

    return minimumPath;
  }

  private void getShortestPath(Vertex<String> vertex, Vertex<String> sourceVertex, List<String> minimumPath) {
    if (vertex == null) {
      minimumPath.clear();
    } else if (vertex.equals(sourceVertex)) {
      minimumPath.add(sourceVertex.label);
    } else {
      minimumPath.add(vertex.label);
      getShortestPath(parentVerticesMap.get(vertex), sourceVertex, minimumPath);
    }
  }

  private void relaxAllEdges(Set<Edge<String>> edges, boolean detectNegativeCycle) {
    for (Edge<String> edge : edges) {
      relaxEdge(edge, detectNegativeCycle);
    }
  }

  private void relaxEdge(Edge<String> edge, boolean detectNegativeCycle) {
    Vertex<String> sourceVertex = edge.sourceVertex;
    Vertex<String> destVertex = edge.destVertex;
    int sourceDistance = distancesMap.getOrDefault(sourceVertex, Integer.MAX_VALUE);
    int destDistance = distancesMap.getOrDefault(destVertex, Integer.MAX_VALUE);
    int distance = (sourceDistance == Integer.MAX_VALUE) ? Integer.MAX_VALUE : (sourceDistance + edge.weight);
    if (destDistance > distance) {
      if (detectNegativeCycle) {
        System.out.println("Negative Weight Cycle");
      }
      distancesMap.put(destVertex, distance);
      parentVerticesMap.put(destVertex, sourceVertex);
    }
  }
}

@@ -44,24 +44,49 @@
 .ArrayList;%0A
+import java.util.Arrays;%0A
 import java.
@@ -95,24 +95,24 @@
 il.HashMap;%0A
-
 import java.
@@ -588,16 +588,71 @@
  = null;
+%0A  private boolean containsNegativeWeightCycle = false;
 %0A%0A  publ
@@ -2054,24 +2054,65 @@
 urceVertex;%0A
+    containsNegativeWeightCycle = false;%0A
     distance
@@ -2535,32 +2535,110 @@
 String label) %7B%0A
+    if (containsNegativeWeightCycle) %7B%0A      return Integer.MIN_VALUE;%0A    %7D%0A%0A
     Vertex%3CStrin
@@ -3005,24 +3005,133 @@
 %3E();%0A    %7D%0A%0A
+    if (containsNegativeWeightCycle) %7B%0A      return Arrays.asList(new String%5B%5D %7B %22negative_cycle%22 %7D);%0A    %7D%0A%0A
     List%3CStr
@@ -4372,36 +4372,24 @@
     
-System.out.println(%22
+contains
 Negative
  Wei
@@ -4388,23 +4388,26 @@
 tive
- 
 Weight
- 
 Cycle
-%22)
+ = true
 ;%0A  

Handle NegativeWeightCycles in BellmanFordShortestPath