text: /**
   * @file testCaseBellmanFord.cxx    another test case for Bellman Ford
   * @brief 
   * 
   *   A test case
   *
   * @author George Heineman
   * @date 6/15/08
   */
  
  #include <cassert>
  #include <iostream>
  
  #include "singleSourceShortest.h"
  
  /**
   * A test case for Bellman Ford.  
   * Note there are two versions of the code, which requires you to modify
   * it to see both graphs. Figure 6-17 is generated by using both versions
   * of the code.
   */
  int main () {
    int n = 5;
    Graph g (n,true);
  
    // in this arrangement, four edges found in first pass, one in second
    if (1) {
      g.addEdge (0, 1, 2); 
      g.addEdge (1, 3, 4); 
      g.addEdge (1, 4, 5); 
      g.addEdge (4, 3, -2); 
      g.addEdge (3, 2, 6); 
      g.addEdge (2, 4, -3); 
    }
    // in this arrangement, two edges found in first pass, two in second
    if (0) {
      g.addEdge (0, 4, 2); 
      g.addEdge (4, 3, 4); 
      g.addEdge (4, 1, 5); 
      g.addEdge (1, 3, -2); 
      g.addEdge (3, 2, 6); 
      g.addEdge (2, 1, -3); 
    }
  
    vector<int> dist(n);
    vector<int> pred(n);
  
    singleSourceShortest(g, 0, dist, pred);
  
    for (int i = 0; i < n; i++) {
      cout << i << ". " << dist[i] << " " << pred[i] << "\n";
    }
  
    n = 4;
    Graph g2 (n, true);
    g2.addEdge (0,1,4);
    g2.addEdge (0,2,3);
    g2.addEdge (2,1,1);
    g2.addEdge (3,0,5);
    g2.addEdge (3,1,10);
    g2.addEdge (3,2,7);
  
    vector<int> dist2(n);
    vector<int> pred2(n);
  
    singleSourceShortest(g2, 0, dist2, pred2);
  
    assert (dist2[0] == 0);
    assert (dist2[1] == 4);
    assert (dist2[2] == 3);
    assert (dist2[3] == numeric_limits<int>::max());
  
    // try another one
    singleSourceShortest(g2, 3, dist2, pred2);
  
    assert (dist2[0] == 5);
    assert (dist2[1] == 8);
    assert (dist2[2] == 7);
    assert (dist2[3] == 0);
  
    // detect negative cycle
    n = 3;
    Graph g3 (n, true);
    g3.addEdge (0,1,-3);
    g3.addEdge (1,2,-2);
    g3.addEdge (2,0,-1);
  
    vector<int> dist3(n);
    vector<int> pred3(n);
  
    try {
      singleSourceShortest(g3, 0, dist3, pred3);
      assert (0 == 1);  // FAILURE CASE
    } catch (...) {
      cout << "caught proper exception\n";
    }
  }
  