1.1 --- a/test/bellman_ford_test.cc	Mon Aug 03 00:52:45 2009 +0200
     1.2 +++ b/test/bellman_ford_test.cc	Mon Aug 03 00:54:04 2009 +0200
     1.3 @@ -220,8 +220,64 @@
     1.4    }
     1.5  }
     1.6  
     1.7 +void checkBellmanFordNegativeCycle() {
     1.8 +  DIGRAPH_TYPEDEFS(SmartDigraph);
     1.9 +
    1.10 +  SmartDigraph gr;
    1.11 +  IntArcMap length(gr);
    1.12 +  
    1.13 +  Node n1 = gr.addNode();
    1.14 +  Node n2 = gr.addNode();
    1.15 +  Node n3 = gr.addNode();
    1.16 +  Node n4 = gr.addNode();
    1.17 +  
    1.18 +  Arc a1 = gr.addArc(n1, n2);
    1.19 +  Arc a2 = gr.addArc(n2, n2);
    1.20 +  
    1.21 +  length[a1] = 2;
    1.22 +  length[a2] = -1;
    1.23 +  
    1.24 +  {
    1.25 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
    1.26 +    bf.run(n1);
    1.27 +    StaticPath<SmartDigraph> p = bf.negativeCycle();
    1.28 +    check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
    1.29 +          "Wrong negative cycle.");
    1.30 +  }
    1.31 + 
    1.32 +  length[a2] = 0;
    1.33 +  
    1.34 +  {
    1.35 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
    1.36 +    bf.run(n1);
    1.37 +    check(bf.negativeCycle().empty(),
    1.38 +          "Negative cycle should not be found.");
    1.39 +  }
    1.40 +  
    1.41 +  length[gr.addArc(n1, n3)] = 5;
    1.42 +  length[gr.addArc(n4, n3)] = 1;
    1.43 +  length[gr.addArc(n2, n4)] = 2;
    1.44 +  length[gr.addArc(n3, n2)] = -4;
    1.45 +  
    1.46 +  {
    1.47 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
    1.48 +    bf.init();
    1.49 +    bf.addSource(n1);
    1.50 +    for (int i = 0; i < 4; ++i) {
    1.51 +      check(bf.negativeCycle().empty(),
    1.52 +            "Negative cycle should not be found.");
    1.53 +      bf.processNextRound();
    1.54 +    }
    1.55 +    StaticPath<SmartDigraph> p = bf.negativeCycle();
    1.56 +    check(p.length() == 3, "Wrong negative cycle.");
    1.57 +    check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
    1.58 +          "Wrong negative cycle.");
    1.59 +  }
    1.60 +}
    1.61 +
    1.62  int main() {
    1.63    checkBellmanFord<ListDigraph, int>();
    1.64    checkBellmanFord<SmartDigraph, double>();
    1.65 +  checkBellmanFordNegativeCycle();
    1.66    return 0;
    1.67  }