/**
 Initiate
    distance - stores the distance of the shortest path from source to each vertex.
    predecessor - for each vertex, predecessor stores its previous vertex on the path from the source to it.
 For the object distance, define each property for the corresponding vertex as Infinity, except for the source,
 which should be zero.  For the object predecessor, set the property for every vertex as null.

 Cycle
    Repeatedly check all the edges to see if the stored distance (total weight from the source to a target vertex)
 for side u of the edge plus the edge's weight w is smaller than the distance of another vertex u.
 If it is true, set the distance of v as the distance of u plus w; and set predecessor of v as u.
 The process repeats with vertices.length times to guarantee the shortest result.

 Check
    Do one more time and throw an error if there exists a negative-weight cycle.
 The negative cycle is a problem because it prevents the algorithm from finding the correct answer.
 */
export const graph = {
  vertices: [ 'A', 'B', 'C', 'D', 'E' ],
  edges: [
    { u: 'A', v: 'B', w: 4 },
    { u: 'A', v: 'C', w: 2 },
    { u: 'B', v: 'C', w: 3 },
    { u: 'B', v: 'D', w: 2 },
    { u: 'B', v: 'E', w: 3 },
    { u: 'C', v: 'B', w: 1 },
    { u: 'C', v: 'D', w: 4 },
    { u: 'C', v: 'E', w: 5 },
    { u: 'E', v: 'D', w: -5 }
  ],
  positions: {
    A: { x: 60, y: 180 },
    B: { x: 240, y: 60 },
    C: { x: 240, y: 300 },
    D: { x: 420, y: 60 },
    E: { x: 420, y: 300 }
  }
};

export const bellmanFord = ({ vertices, edges }, source) => {
  const distance = vertices.reduce((r, i) => ({ [i]: Infinity, ...r }), { [source]: 0 });
  const predecessor = vertices.reduce((r, i) => ({ [i]: null, ...r }), {});

  vertices.forEach(() => {
    edges.forEach(({ u, v, w }) => {
      if (distance[v] > distance[u] + w) {
        distance[v] = distance[u] + w;
        predecessor[v] = u;
      }
    });
  });

  // check for negative-weight cycles
  for (let { u, v, w } of edges) {
    if (distance[v] > distance[u] + w) throw 'Graph contains a negative-weight cycle';
  }

  return { distance, predecessor };
};