test/bellman_ford_test.cc
changeset 942 633956ca9421
parent 844 a6eb9698c321
child 880 b89e46862dc2
equal deleted inserted replaced
5:83631935e9b7 6:a036fbc8fea7
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    95     b  = const_bf_test.reached(t);
    95     b  = const_bf_test.reached(t);
    96     d  = const_bf_test.distMap();
    96     d  = const_bf_test.distMap();
    97     p  = const_bf_test.predMap();
    97     p  = const_bf_test.predMap();
    98     pp = const_bf_test.path(t);
    98     pp = const_bf_test.path(t);
    99     pp = const_bf_test.negativeCycle();
    99     pp = const_bf_test.negativeCycle();
   100     
   100 
   101     for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
   101     for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
   102   }
   102   }
   103   {
   103   {
   104     BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
   104     BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
   105       ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
   105       ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
   108       ::Create bf_test(gr,length);
   108       ::Create bf_test(gr,length);
   109 
   109 
   110     LengthMap length_map;
   110     LengthMap length_map;
   111     concepts::ReadWriteMap<Node,Arc> pred_map;
   111     concepts::ReadWriteMap<Node,Arc> pred_map;
   112     concepts::ReadWriteMap<Node,Value> dist_map;
   112     concepts::ReadWriteMap<Node,Value> dist_map;
   113     
   113 
   114     bf_test
   114     bf_test
   115       .lengthMap(length_map)
   115       .lengthMap(length_map)
   116       .predMap(pred_map)
   116       .predMap(pred_map)
   117       .distMap(dist_map);
   117       .distMap(dist_map);
   118 
   118 
   187   check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
   187   check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
   188   check(p.length() == 3, "path() found a wrong path.");
   188   check(p.length() == 3, "path() found a wrong path.");
   189   check(checkPath(gr, p), "path() found a wrong path.");
   189   check(checkPath(gr, p), "path() found a wrong path.");
   190   check(pathSource(gr, p) == s, "path() found a wrong path.");
   190   check(pathSource(gr, p) == s, "path() found a wrong path.");
   191   check(pathTarget(gr, p) == t, "path() found a wrong path.");
   191   check(pathTarget(gr, p) == t, "path() found a wrong path.");
   192   
   192 
   193   ListPath<Digraph> path;
   193   ListPath<Digraph> path;
   194   Value dist;
   194   Value dist;
   195   bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
   195   bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
   196 
   196 
   197   check(reached && dist == -1, "Bellman-Ford found a wrong path.");
   197   check(reached && dist == -1, "Bellman-Ford found a wrong path.");
   226 void checkBellmanFordNegativeCycle() {
   226 void checkBellmanFordNegativeCycle() {
   227   DIGRAPH_TYPEDEFS(SmartDigraph);
   227   DIGRAPH_TYPEDEFS(SmartDigraph);
   228 
   228 
   229   SmartDigraph gr;
   229   SmartDigraph gr;
   230   IntArcMap length(gr);
   230   IntArcMap length(gr);
   231   
   231 
   232   Node n1 = gr.addNode();
   232   Node n1 = gr.addNode();
   233   Node n2 = gr.addNode();
   233   Node n2 = gr.addNode();
   234   Node n3 = gr.addNode();
   234   Node n3 = gr.addNode();
   235   Node n4 = gr.addNode();
   235   Node n4 = gr.addNode();
   236   
   236 
   237   Arc a1 = gr.addArc(n1, n2);
   237   Arc a1 = gr.addArc(n1, n2);
   238   Arc a2 = gr.addArc(n2, n2);
   238   Arc a2 = gr.addArc(n2, n2);
   239   
   239 
   240   length[a1] = 2;
   240   length[a1] = 2;
   241   length[a2] = -1;
   241   length[a2] = -1;
   242   
   242 
   243   {
   243   {
   244     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   244     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   245     bf.run(n1);
   245     bf.run(n1);
   246     StaticPath<SmartDigraph> p = bf.negativeCycle();
   246     StaticPath<SmartDigraph> p = bf.negativeCycle();
   247     check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
   247     check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
   248           "Wrong negative cycle.");
   248           "Wrong negative cycle.");
   249   }
   249   }
   250  
   250 
   251   length[a2] = 0;
   251   length[a2] = 0;
   252   
   252 
   253   {
   253   {
   254     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   254     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   255     bf.run(n1);
   255     bf.run(n1);
   256     check(bf.negativeCycle().empty(),
   256     check(bf.negativeCycle().empty(),
   257           "Negative cycle should not be found.");
   257           "Negative cycle should not be found.");
   258   }
   258   }
   259   
   259 
   260   length[gr.addArc(n1, n3)] = 5;
   260   length[gr.addArc(n1, n3)] = 5;
   261   length[gr.addArc(n4, n3)] = 1;
   261   length[gr.addArc(n4, n3)] = 1;
   262   length[gr.addArc(n2, n4)] = 2;
   262   length[gr.addArc(n2, n4)] = 2;
   263   length[gr.addArc(n3, n2)] = -4;
   263   length[gr.addArc(n3, n2)] = -4;
   264   
   264 
   265   {
   265   {
   266     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   266     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
   267     bf.init();
   267     bf.init();
   268     bf.addSource(n1);
   268     bf.addSource(n1);
   269     for (int i = 0; i < 4; ++i) {
   269     for (int i = 0; i < 4; ++i) {