|
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 } |