gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Add a detailed test file for BellmanFord (#51)
0 2 1
default
3 files changed with 230 insertions and 0 deletions:
↑ Collapse diff ↑
Ignore white space 64 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2009
6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8
 *
9
 * Permission to use, modify and distribute this software is granted
10
 * provided that this copyright notice appears in all copies. For
11
 * precise terms see the accompanying LICENSE file.
12
 *
13
 * This software is provided "AS IS" with no warranty of any kind,
14
 * express or implied, and with no claim as to its suitability for any
15
 * purpose.
16
 *
17
 */
18

	
19
#include <lemon/concepts/digraph.h>
20
#include <lemon/smart_graph.h>
21
#include <lemon/list_graph.h>
22
#include <lemon/lgf_reader.h>
23
#include <lemon/bellman_ford.h>
24
#include <lemon/path.h>
25

	
26
#include "graph_test.h"
27
#include "test_tools.h"
28

	
29
using namespace lemon;
30

	
31
char test_lgf[] =
32
  "@nodes\n"
33
  "label\n"
34
  "0\n"
35
  "1\n"
36
  "2\n"
37
  "3\n"
38
  "4\n"
39
  "@arcs\n"
40
  "    length\n"
41
  "0 1 3\n"
42
  "1 2 -3\n"
43
  "1 2 -5\n"
44
  "1 3 -2\n"
45
  "0 2 -1\n"
46
  "1 2 -4\n"
47
  "0 3 2\n"
48
  "4 2 -5\n"
49
  "2 3 1\n"
50
  "@attributes\n"
51
  "source 0\n"
52
  "target 3\n";
53

	
54

	
55
void checkBellmanFordCompile()
56
{
57
  typedef int Value;
58
  typedef concepts::Digraph Digraph;
59
  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
60
  typedef BellmanFord<Digraph, LengthMap> BF;
61
  typedef Digraph::Node Node;
62
  typedef Digraph::Arc Arc;
63

	
64
  Digraph gr;
65
  Node s, t, n;
66
  Arc e;
67
  Value l;
68
  int k;
69
  bool b;
70
  BF::DistMap d(gr);
71
  BF::PredMap p(gr);
72
  LengthMap length;
73
  concepts::Path<Digraph> pp;
74

	
75
  {
76
    BF bf_test(gr,length);
77
    const BF& const_bf_test = bf_test;
78

	
79
    bf_test.run(s);
80
    bf_test.run(s,k);
81

	
82
    bf_test.init();
83
    bf_test.addSource(s);
84
    bf_test.addSource(s, 1);
85
    b = bf_test.processNextRound();
86
    b = bf_test.processNextWeakRound();
87

	
88
    bf_test.start();
89
    bf_test.checkedStart();
90
    bf_test.limitedStart(k);
91

	
92
    l  = const_bf_test.dist(t);
93
    e  = const_bf_test.predArc(t);
94
    s  = const_bf_test.predNode(t);
95
    b  = const_bf_test.reached(t);
96
    d  = const_bf_test.distMap();
97
    p  = const_bf_test.predMap();
98
    pp = const_bf_test.path(t);
99
    
100
    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
101
  }
102
  {
103
    BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
104
      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
105
      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
106
      ::Create bf_test(gr,length);
107

	
108
    LengthMap length_map;
109
    concepts::ReadWriteMap<Node,Arc> pred_map;
110
    concepts::ReadWriteMap<Node,Value> dist_map;
111
    
112
    bf_test
113
      .lengthMap(length_map)
114
      .predMap(pred_map)
115
      .distMap(dist_map);
116

	
117
    bf_test.run(s);
118
    bf_test.run(s,k);
119

	
120
    bf_test.init();
121
    bf_test.addSource(s);
122
    bf_test.addSource(s, 1);
123
    b = bf_test.processNextRound();
124
    b = bf_test.processNextWeakRound();
125

	
126
    bf_test.start();
127
    bf_test.checkedStart();
128
    bf_test.limitedStart(k);
129

	
130
    l  = bf_test.dist(t);
131
    e  = bf_test.predArc(t);
132
    s  = bf_test.predNode(t);
133
    b  = bf_test.reached(t);
134
    pp = bf_test.path(t);
135
  }
136
}
137

	
138
void checkBellmanFordFunctionCompile()
139
{
140
  typedef int Value;
141
  typedef concepts::Digraph Digraph;
142
  typedef Digraph::Arc Arc;
143
  typedef Digraph::Node Node;
144
  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
145

	
146
  Digraph g;
147
  bool b;
148
  bellmanFord(g,LengthMap()).run(Node());
149
  b = bellmanFord(g,LengthMap()).run(Node(),Node());
150
  bellmanFord(g,LengthMap())
151
    .predMap(concepts::ReadWriteMap<Node,Arc>())
152
    .distMap(concepts::ReadWriteMap<Node,Value>())
153
    .run(Node());
154
  b=bellmanFord(g,LengthMap())
155
    .predMap(concepts::ReadWriteMap<Node,Arc>())
156
    .distMap(concepts::ReadWriteMap<Node,Value>())
157
    .path(concepts::Path<Digraph>())
158
    .dist(Value())
159
    .run(Node(),Node());
160
}
161

	
162

	
163
template <typename Digraph, typename Value>
164
void checkBellmanFord() {
165
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
166
  typedef typename Digraph::template ArcMap<Value> LengthMap;
167

	
168
  Digraph gr;
169
  Node s, t;
170
  LengthMap length(gr);
171

	
172
  std::istringstream input(test_lgf);
173
  digraphReader(gr, input).
174
    arcMap("length", length).
175
    node("source", s).
176
    node("target", t).
177
    run();
178

	
179
  BellmanFord<Digraph, LengthMap>
180
    bf(gr, length);
181
  bf.run(s);
182
  Path<Digraph> p = bf.path(t);
183

	
184
  check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
185
  check(p.length() == 3, "path() found a wrong path.");
186
  check(checkPath(gr, p), "path() found a wrong path.");
187
  check(pathSource(gr, p) == s, "path() found a wrong path.");
188
  check(pathTarget(gr, p) == t, "path() found a wrong path.");
189
  
190
  ListPath<Digraph> path;
191
  Value dist;
192
  bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
193

	
194
  check(reached && dist == -1, "Bellman-Ford found a wrong path.");
195
  check(path.length() == 3, "path() found a wrong path.");
196
  check(checkPath(gr, path), "path() found a wrong path.");
197
  check(pathSource(gr, path) == s, "path() found a wrong path.");
198
  check(pathTarget(gr, path) == t, "path() found a wrong path.");
199

	
200
  for(ArcIt e(gr); e!=INVALID; ++e) {
201
    Node u=gr.source(e);
202
    Node v=gr.target(e);
203
    check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
204
          "Wrong output. dist(target)-dist(source)-arc_length=" <<
205
          bf.dist(v) - bf.dist(u) - length[e]);
206
  }
207

	
208
  for(NodeIt v(gr); v!=INVALID; ++v) {
209
    if (bf.reached(v)) {
210
      check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
211
      if (bf.predArc(v)!=INVALID ) {
212
        Arc e=bf.predArc(v);
213
        Node u=gr.source(e);
214
        check(u==bf.predNode(v),"Wrong tree.");
215
        check(bf.dist(v) - bf.dist(u) == length[e],
216
              "Wrong distance! Difference: " <<
217
              bf.dist(v) - bf.dist(u) - length[e]);
218
      }
219
    }
220
  }
221
}
222

	
223
int main() {
224
  checkBellmanFord<ListDigraph, int>();
225
  checkBellmanFord<SmartDigraph, double>();
226
  return 0;
227
}
Ignore white space 6 line context
1 1
INCLUDE_DIRECTORIES(
2 2
  ${PROJECT_SOURCE_DIR}
3 3
  ${PROJECT_BINARY_DIR}
4 4
)
5 5

	
6 6
LINK_DIRECTORIES(
7 7
  ${PROJECT_BINARY_DIR}/lemon
8 8
)
9 9

	
10 10
SET(TESTS
11 11
  adaptors_test
12
  bellman_ford_test
12 13
  bfs_test
13 14
  circulation_test
14 15
  connectivity_test
15 16
  counter_test
16 17
  dfs_test
17 18
  digraph_test
18 19
  dijkstra_test
19 20
  dim_test
20 21
  edge_set_test
21 22
  error_test
22 23
  euler_test
23 24
  gomory_hu_test
24 25
  graph_copy_test
25 26
  graph_test
26 27
  graph_utils_test
27 28
  hao_orlin_test
28 29
  heap_test
29 30
  kruskal_test
30 31
  maps_test
31 32
  matching_test
32 33
  min_cost_arborescence_test
33 34
  min_cost_flow_test
34 35
  path_test
35 36
  preflow_test
36 37
  radix_sort_test
37 38
  random_test
38 39
  suurballe_test
39 40
  time_measure_test
40 41
  unionfind_test
41 42
)
42 43

	
43 44
IF(LEMON_HAVE_LP)
Ignore white space 6 line context
1 1
EXTRA_DIST += \
2 2
	test/CMakeLists.txt
3 3

	
4 4
noinst_HEADERS += \
5 5
	test/graph_test.h \
6 6
	test/test_tools.h
7 7

	
8 8
check_PROGRAMS += \
9 9
	test/adaptors_test \
10
	test/bellman_ford_test \
10 11
	test/bfs_test \
11 12
	test/circulation_test \
12 13
	test/connectivity_test \
13 14
	test/counter_test \
14 15
	test/dfs_test \
15 16
	test/digraph_test \
16 17
	test/dijkstra_test \
17 18
	test/dim_test \
18 19
	test/edge_set_test \
19 20
	test/error_test \
20 21
	test/euler_test \
21 22
	test/gomory_hu_test \
22 23
	test/graph_copy_test \
23 24
	test/graph_test \
24 25
	test/graph_utils_test \
25 26
	test/hao_orlin_test \
26 27
	test/heap_test \
27 28
	test/kruskal_test \
28 29
	test/maps_test \
29 30
	test/matching_test \
30 31
	test/min_cost_arborescence_test \
31 32
	test/min_cost_flow_test \
32 33
	test/path_test \
33 34
	test/preflow_test \
34 35
	test/radix_sort_test \
35 36
	test/random_test \
36 37
	test/suurballe_test \
37 38
	test/test_tools_fail \
38 39
	test/test_tools_pass \
39 40
	test/time_measure_test \
40 41
	test/unionfind_test
41 42

	
42 43
test_test_tools_pass_DEPENDENCIES = demo
43 44

	
44 45
if HAVE_LP
45 46
check_PROGRAMS += test/lp_test
46 47
endif HAVE_LP
47 48
if HAVE_MIP
48 49
check_PROGRAMS += test/mip_test
49 50
endif HAVE_MIP
50 51

	
51 52
TESTS += $(check_PROGRAMS)
52 53
XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
53 54

	
54 55
test_adaptors_test_SOURCES = test/adaptors_test.cc
56
test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
55 57
test_bfs_test_SOURCES = test/bfs_test.cc
56 58
test_circulation_test_SOURCES = test/circulation_test.cc
57 59
test_counter_test_SOURCES = test/counter_test.cc
58 60
test_connectivity_test_SOURCES = test/connectivity_test.cc
59 61
test_dfs_test_SOURCES = test/dfs_test.cc
60 62
test_digraph_test_SOURCES = test/digraph_test.cc
61 63
test_dijkstra_test_SOURCES = test/dijkstra_test.cc
62 64
test_dim_test_SOURCES = test/dim_test.cc
63 65
test_edge_set_test_SOURCES = test/edge_set_test.cc
64 66
test_error_test_SOURCES = test/error_test.cc
65 67
test_euler_test_SOURCES = test/euler_test.cc
66 68
test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
67 69
test_graph_copy_test_SOURCES = test/graph_copy_test.cc
68 70
test_graph_test_SOURCES = test/graph_test.cc
69 71
test_graph_utils_test_SOURCES = test/graph_utils_test.cc
70 72
test_heap_test_SOURCES = test/heap_test.cc
71 73
test_kruskal_test_SOURCES = test/kruskal_test.cc
72 74
test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
73 75
test_lp_test_SOURCES = test/lp_test.cc
74 76
test_maps_test_SOURCES = test/maps_test.cc
75 77
test_mip_test_SOURCES = test/mip_test.cc
76 78
test_matching_test_SOURCES = test/matching_test.cc
77 79
test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
78 80
test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
79 81
test_path_test_SOURCES = test/path_test.cc
80 82
test_preflow_test_SOURCES = test/preflow_test.cc
81 83
test_radix_sort_test_SOURCES = test/radix_sort_test.cc
82 84
test_suurballe_test_SOURCES = test/suurballe_test.cc
83 85
test_random_test_SOURCES = test/random_test.cc
84 86
test_test_tools_fail_SOURCES = test/test_tools_fail.cc
85 87
test_test_tools_pass_SOURCES = test/test_tools_pass.cc
86 88
test_time_measure_test_SOURCES = test/time_measure_test.cc
0 comments (0 inline)