COIN-OR::LEMON - Graph Library

Changeset 699:75325dfccf38 in lemon-1.2 for test


Ignore:
Timestamp:
08/03/09 00:54:04 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add negativeCycle() function to BellmanFord? (#51)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/bellman_ford_test.cc

    r698 r699  
    221221}
    222222
     223void checkBellmanFordNegativeCycle() {
     224  DIGRAPH_TYPEDEFS(SmartDigraph);
     225
     226  SmartDigraph gr;
     227  IntArcMap length(gr);
     228 
     229  Node n1 = gr.addNode();
     230  Node n2 = gr.addNode();
     231  Node n3 = gr.addNode();
     232  Node n4 = gr.addNode();
     233 
     234  Arc a1 = gr.addArc(n1, n2);
     235  Arc a2 = gr.addArc(n2, n2);
     236 
     237  length[a1] = 2;
     238  length[a2] = -1;
     239 
     240  {
     241    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     242    bf.run(n1);
     243    StaticPath<SmartDigraph> p = bf.negativeCycle();
     244    check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
     245          "Wrong negative cycle.");
     246  }
     247 
     248  length[a2] = 0;
     249 
     250  {
     251    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     252    bf.run(n1);
     253    check(bf.negativeCycle().empty(),
     254          "Negative cycle should not be found.");
     255  }
     256 
     257  length[gr.addArc(n1, n3)] = 5;
     258  length[gr.addArc(n4, n3)] = 1;
     259  length[gr.addArc(n2, n4)] = 2;
     260  length[gr.addArc(n3, n2)] = -4;
     261 
     262  {
     263    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     264    bf.init();
     265    bf.addSource(n1);
     266    for (int i = 0; i < 4; ++i) {
     267      check(bf.negativeCycle().empty(),
     268            "Negative cycle should not be found.");
     269      bf.processNextRound();
     270    }
     271    StaticPath<SmartDigraph> p = bf.negativeCycle();
     272    check(p.length() == 3, "Wrong negative cycle.");
     273    check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
     274          "Wrong negative cycle.");
     275  }
     276}
     277
    223278int main() {
    224279  checkBellmanFord<ListDigraph, int>();
    225280  checkBellmanFord<SmartDigraph, double>();
     281  checkBellmanFordNegativeCycle();
    226282  return 0;
    227283}
Note: See TracChangeset for help on using the changeset viewer.