Add a detailed test file for BellmanFord (#51)
authorPeter Kovacs <kpeter@inf.elte.hu>
Mon, 03 Aug 2009 00:52:45 +0200
changeset 745f9746e45246e
parent 744 9496ed797f20
child 746 75325dfccf38
child 837 1870cfd14fb6
Add a detailed test file for BellmanFord (#51)
test/CMakeLists.txt
test/Makefile.am
test/bellman_ford_test.cc
     1.1 --- a/test/CMakeLists.txt	Sun Aug 02 13:24:46 2009 +0200
     1.2 +++ b/test/CMakeLists.txt	Mon Aug 03 00:52:45 2009 +0200
     1.3 @@ -9,6 +9,7 @@
     1.4  
     1.5  SET(TESTS
     1.6    adaptors_test
     1.7 +  bellman_ford_test
     1.8    bfs_test
     1.9    circulation_test
    1.10    connectivity_test
     2.1 --- a/test/Makefile.am	Sun Aug 02 13:24:46 2009 +0200
     2.2 +++ b/test/Makefile.am	Mon Aug 03 00:52:45 2009 +0200
     2.3 @@ -7,6 +7,7 @@
     2.4  
     2.5  check_PROGRAMS += \
     2.6  	test/adaptors_test \
     2.7 +	test/bellman_ford_test \
     2.8  	test/bfs_test \
     2.9  	test/circulation_test \
    2.10  	test/connectivity_test \
    2.11 @@ -52,6 +53,7 @@
    2.12  XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    2.13  
    2.14  test_adaptors_test_SOURCES = test/adaptors_test.cc
    2.15 +test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    2.16  test_bfs_test_SOURCES = test/bfs_test.cc
    2.17  test_circulation_test_SOURCES = test/circulation_test.cc
    2.18  test_counter_test_SOURCES = test/counter_test.cc
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/test/bellman_ford_test.cc	Mon Aug 03 00:52:45 2009 +0200
     3.3 @@ -0,0 +1,227 @@
     3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library.
     3.7 + *
     3.8 + * Copyright (C) 2003-2009
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22 +#include <lemon/concepts/digraph.h>
    3.23 +#include <lemon/smart_graph.h>
    3.24 +#include <lemon/list_graph.h>
    3.25 +#include <lemon/lgf_reader.h>
    3.26 +#include <lemon/bellman_ford.h>
    3.27 +#include <lemon/path.h>
    3.28 +
    3.29 +#include "graph_test.h"
    3.30 +#include "test_tools.h"
    3.31 +
    3.32 +using namespace lemon;
    3.33 +
    3.34 +char test_lgf[] =
    3.35 +  "@nodes\n"
    3.36 +  "label\n"
    3.37 +  "0\n"
    3.38 +  "1\n"
    3.39 +  "2\n"
    3.40 +  "3\n"
    3.41 +  "4\n"
    3.42 +  "@arcs\n"
    3.43 +  "    length\n"
    3.44 +  "0 1 3\n"
    3.45 +  "1 2 -3\n"
    3.46 +  "1 2 -5\n"
    3.47 +  "1 3 -2\n"
    3.48 +  "0 2 -1\n"
    3.49 +  "1 2 -4\n"
    3.50 +  "0 3 2\n"
    3.51 +  "4 2 -5\n"
    3.52 +  "2 3 1\n"
    3.53 +  "@attributes\n"
    3.54 +  "source 0\n"
    3.55 +  "target 3\n";
    3.56 +
    3.57 +
    3.58 +void checkBellmanFordCompile()
    3.59 +{
    3.60 +  typedef int Value;
    3.61 +  typedef concepts::Digraph Digraph;
    3.62 +  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
    3.63 +  typedef BellmanFord<Digraph, LengthMap> BF;
    3.64 +  typedef Digraph::Node Node;
    3.65 +  typedef Digraph::Arc Arc;
    3.66 +
    3.67 +  Digraph gr;
    3.68 +  Node s, t, n;
    3.69 +  Arc e;
    3.70 +  Value l;
    3.71 +  int k;
    3.72 +  bool b;
    3.73 +  BF::DistMap d(gr);
    3.74 +  BF::PredMap p(gr);
    3.75 +  LengthMap length;
    3.76 +  concepts::Path<Digraph> pp;
    3.77 +
    3.78 +  {
    3.79 +    BF bf_test(gr,length);
    3.80 +    const BF& const_bf_test = bf_test;
    3.81 +
    3.82 +    bf_test.run(s);
    3.83 +    bf_test.run(s,k);
    3.84 +
    3.85 +    bf_test.init();
    3.86 +    bf_test.addSource(s);
    3.87 +    bf_test.addSource(s, 1);
    3.88 +    b = bf_test.processNextRound();
    3.89 +    b = bf_test.processNextWeakRound();
    3.90 +
    3.91 +    bf_test.start();
    3.92 +    bf_test.checkedStart();
    3.93 +    bf_test.limitedStart(k);
    3.94 +
    3.95 +    l  = const_bf_test.dist(t);
    3.96 +    e  = const_bf_test.predArc(t);
    3.97 +    s  = const_bf_test.predNode(t);
    3.98 +    b  = const_bf_test.reached(t);
    3.99 +    d  = const_bf_test.distMap();
   3.100 +    p  = const_bf_test.predMap();
   3.101 +    pp = const_bf_test.path(t);
   3.102 +    
   3.103 +    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
   3.104 +  }
   3.105 +  {
   3.106 +    BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
   3.107 +      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
   3.108 +      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
   3.109 +      ::Create bf_test(gr,length);
   3.110 +
   3.111 +    LengthMap length_map;
   3.112 +    concepts::ReadWriteMap<Node,Arc> pred_map;
   3.113 +    concepts::ReadWriteMap<Node,Value> dist_map;
   3.114 +    
   3.115 +    bf_test
   3.116 +      .lengthMap(length_map)
   3.117 +      .predMap(pred_map)
   3.118 +      .distMap(dist_map);
   3.119 +
   3.120 +    bf_test.run(s);
   3.121 +    bf_test.run(s,k);
   3.122 +
   3.123 +    bf_test.init();
   3.124 +    bf_test.addSource(s);
   3.125 +    bf_test.addSource(s, 1);
   3.126 +    b = bf_test.processNextRound();
   3.127 +    b = bf_test.processNextWeakRound();
   3.128 +
   3.129 +    bf_test.start();
   3.130 +    bf_test.checkedStart();
   3.131 +    bf_test.limitedStart(k);
   3.132 +
   3.133 +    l  = bf_test.dist(t);
   3.134 +    e  = bf_test.predArc(t);
   3.135 +    s  = bf_test.predNode(t);
   3.136 +    b  = bf_test.reached(t);
   3.137 +    pp = bf_test.path(t);
   3.138 +  }
   3.139 +}
   3.140 +
   3.141 +void checkBellmanFordFunctionCompile()
   3.142 +{
   3.143 +  typedef int Value;
   3.144 +  typedef concepts::Digraph Digraph;
   3.145 +  typedef Digraph::Arc Arc;
   3.146 +  typedef Digraph::Node Node;
   3.147 +  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
   3.148 +
   3.149 +  Digraph g;
   3.150 +  bool b;
   3.151 +  bellmanFord(g,LengthMap()).run(Node());
   3.152 +  b = bellmanFord(g,LengthMap()).run(Node(),Node());
   3.153 +  bellmanFord(g,LengthMap())
   3.154 +    .predMap(concepts::ReadWriteMap<Node,Arc>())
   3.155 +    .distMap(concepts::ReadWriteMap<Node,Value>())
   3.156 +    .run(Node());
   3.157 +  b=bellmanFord(g,LengthMap())
   3.158 +    .predMap(concepts::ReadWriteMap<Node,Arc>())
   3.159 +    .distMap(concepts::ReadWriteMap<Node,Value>())
   3.160 +    .path(concepts::Path<Digraph>())
   3.161 +    .dist(Value())
   3.162 +    .run(Node(),Node());
   3.163 +}
   3.164 +
   3.165 +
   3.166 +template <typename Digraph, typename Value>
   3.167 +void checkBellmanFord() {
   3.168 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   3.169 +  typedef typename Digraph::template ArcMap<Value> LengthMap;
   3.170 +
   3.171 +  Digraph gr;
   3.172 +  Node s, t;
   3.173 +  LengthMap length(gr);
   3.174 +
   3.175 +  std::istringstream input(test_lgf);
   3.176 +  digraphReader(gr, input).
   3.177 +    arcMap("length", length).
   3.178 +    node("source", s).
   3.179 +    node("target", t).
   3.180 +    run();
   3.181 +
   3.182 +  BellmanFord<Digraph, LengthMap>
   3.183 +    bf(gr, length);
   3.184 +  bf.run(s);
   3.185 +  Path<Digraph> p = bf.path(t);
   3.186 +
   3.187 +  check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
   3.188 +  check(p.length() == 3, "path() found a wrong path.");
   3.189 +  check(checkPath(gr, p), "path() found a wrong path.");
   3.190 +  check(pathSource(gr, p) == s, "path() found a wrong path.");
   3.191 +  check(pathTarget(gr, p) == t, "path() found a wrong path.");
   3.192 +  
   3.193 +  ListPath<Digraph> path;
   3.194 +  Value dist;
   3.195 +  bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
   3.196 +
   3.197 +  check(reached && dist == -1, "Bellman-Ford found a wrong path.");
   3.198 +  check(path.length() == 3, "path() found a wrong path.");
   3.199 +  check(checkPath(gr, path), "path() found a wrong path.");
   3.200 +  check(pathSource(gr, path) == s, "path() found a wrong path.");
   3.201 +  check(pathTarget(gr, path) == t, "path() found a wrong path.");
   3.202 +
   3.203 +  for(ArcIt e(gr); e!=INVALID; ++e) {
   3.204 +    Node u=gr.source(e);
   3.205 +    Node v=gr.target(e);
   3.206 +    check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
   3.207 +          "Wrong output. dist(target)-dist(source)-arc_length=" <<
   3.208 +          bf.dist(v) - bf.dist(u) - length[e]);
   3.209 +  }
   3.210 +
   3.211 +  for(NodeIt v(gr); v!=INVALID; ++v) {
   3.212 +    if (bf.reached(v)) {
   3.213 +      check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
   3.214 +      if (bf.predArc(v)!=INVALID ) {
   3.215 +        Arc e=bf.predArc(v);
   3.216 +        Node u=gr.source(e);
   3.217 +        check(u==bf.predNode(v),"Wrong tree.");
   3.218 +        check(bf.dist(v) - bf.dist(u) == length[e],
   3.219 +              "Wrong distance! Difference: " <<
   3.220 +              bf.dist(v) - bf.dist(u) - length[e]);
   3.221 +      }
   3.222 +    }
   3.223 +  }
   3.224 +}
   3.225 +
   3.226 +int main() {
   3.227 +  checkBellmanFord<ListDigraph, int>();
   3.228 +  checkBellmanFord<SmartDigraph, double>();
   3.229 +  return 0;
   3.230 +}