COIN-OR::LEMON - Graph Library

Changeset 838:4e3484a2e90c in lemon


Ignore:
Timestamp:
11/18/09 14:22:52 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
836:8ddb7deabab9 (diff), 837:1870cfd14fb6 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • test/bellman_ford_test.cc

    r828 r838  
    6666  Arc e;
    6767  Value l;
    68   int k;
     68  int k=3;
    6969  bool b;
    7070  BF::DistMap d(gr);
  • test/bellman_ford_test.cc

    r837 r838  
    9797    p  = const_bf_test.predMap();
    9898    pp = const_bf_test.path(t);
     99    pp = const_bf_test.negativeCycle();
    99100   
    100101    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
     
    133134    b  = bf_test.reached(t);
    134135    pp = bf_test.path(t);
     136    pp = bf_test.negativeCycle();
    135137  }
    136138}
     
    221223}
    222224
     225void checkBellmanFordNegativeCycle() {
     226  DIGRAPH_TYPEDEFS(SmartDigraph);
     227
     228  SmartDigraph gr;
     229  IntArcMap length(gr);
     230 
     231  Node n1 = gr.addNode();
     232  Node n2 = gr.addNode();
     233  Node n3 = gr.addNode();
     234  Node n4 = gr.addNode();
     235 
     236  Arc a1 = gr.addArc(n1, n2);
     237  Arc a2 = gr.addArc(n2, n2);
     238 
     239  length[a1] = 2;
     240  length[a2] = -1;
     241 
     242  {
     243    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     244    bf.run(n1);
     245    StaticPath<SmartDigraph> p = bf.negativeCycle();
     246    check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
     247          "Wrong negative cycle.");
     248  }
     249 
     250  length[a2] = 0;
     251 
     252  {
     253    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     254    bf.run(n1);
     255    check(bf.negativeCycle().empty(),
     256          "Negative cycle should not be found.");
     257  }
     258 
     259  length[gr.addArc(n1, n3)] = 5;
     260  length[gr.addArc(n4, n3)] = 1;
     261  length[gr.addArc(n2, n4)] = 2;
     262  length[gr.addArc(n3, n2)] = -4;
     263 
     264  {
     265    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     266    bf.init();
     267    bf.addSource(n1);
     268    for (int i = 0; i < 4; ++i) {
     269      check(bf.negativeCycle().empty(),
     270            "Negative cycle should not be found.");
     271      bf.processNextRound();
     272    }
     273    StaticPath<SmartDigraph> p = bf.negativeCycle();
     274    check(p.length() == 3, "Wrong negative cycle.");
     275    check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
     276          "Wrong negative cycle.");
     277  }
     278}
     279
    223280int main() {
    224281  checkBellmanFord<ListDigraph, int>();
    225282  checkBellmanFord<SmartDigraph, double>();
     283  checkBellmanFordNegativeCycle();
    226284  return 0;
    227285}
Note: See TracChangeset for help on using the changeset viewer.