17 */ |
17 */ |
18 |
18 |
19 #include <lemon/concepts/digraph.h> |
19 #include <lemon/concepts/digraph.h> |
20 #include <lemon/smart_graph.h> |
20 #include <lemon/smart_graph.h> |
21 #include <lemon/list_graph.h> |
21 #include <lemon/list_graph.h> |
|
22 #include <lemon/lgf_reader.h> |
|
23 |
22 #include <lemon/dijkstra.h> |
24 #include <lemon/dijkstra.h> |
23 #include <lemon/path.h> |
25 #include <lemon/path.h> |
24 |
26 |
25 #include "graph_test.h" |
27 #include "graph_test.h" |
26 #include "test_tools.h" |
28 #include "test_tools.h" |
27 |
29 |
28 using namespace lemon; |
30 using namespace lemon; |
|
31 |
|
32 char test_lgf[] = |
|
33 "@nodes\n" |
|
34 "label\n" |
|
35 "0\n" |
|
36 "1\n" |
|
37 "2\n" |
|
38 "3\n" |
|
39 "4\n" |
|
40 "@arcs\n" |
|
41 " label length\n" |
|
42 "0 1 0 1\n" |
|
43 "1 2 1 1\n" |
|
44 "2 3 2 1\n" |
|
45 "0 3 4 5\n" |
|
46 "0 3 5 10\n" |
|
47 "0 3 6 7\n" |
|
48 "4 2 7 1\n" |
|
49 "@attributes\n" |
|
50 "source 0\n" |
|
51 "target 3\n"; |
29 |
52 |
30 void checkDijkstraCompile() |
53 void checkDijkstraCompile() |
31 { |
54 { |
32 typedef int VType; |
55 typedef int VType; |
33 typedef concepts::Digraph Digraph; |
56 typedef concepts::Digraph Digraph; |
82 typedef typename Digraph::template ArcMap<int> LengthMap; |
105 typedef typename Digraph::template ArcMap<int> LengthMap; |
83 |
106 |
84 Digraph G; |
107 Digraph G; |
85 Node s, t; |
108 Node s, t; |
86 LengthMap length(G); |
109 LengthMap length(G); |
87 PetStruct<Digraph> ps = addPetersen(G, 5); |
|
88 |
110 |
89 for(int i=0;i<5;i++) { |
111 std::istringstream input(test_lgf); |
90 length[ps.outcir[i]]=4; |
112 digraphReader(input, G). |
91 length[ps.incir[i]]=1; |
113 arcMap("length", length). |
92 length[ps.chords[i]]=10; |
114 node("source", s). |
93 } |
115 node("target", t). |
94 s=ps.outer[0]; |
116 run(); |
95 t=ps.inner[1]; |
|
96 |
117 |
97 Dijkstra<Digraph, LengthMap> |
118 Dijkstra<Digraph, LengthMap> |
98 dijkstra_test(G, length); |
119 dijkstra_test(G, length); |
99 dijkstra_test.run(s); |
120 dijkstra_test.run(s); |
100 |
121 |
101 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path."); |
122 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); |
102 |
123 |
103 Path<Digraph> p = dijkstra_test.path(t); |
124 Path<Digraph> p = dijkstra_test.path(t); |
104 check(p.length()==4,"getPath() found a wrong path."); |
125 check(p.length()==3,"getPath() found a wrong path."); |
105 check(checkPath(G, p),"path() found a wrong path."); |
126 check(checkPath(G, p),"path() found a wrong path."); |
106 check(pathSource(G, p) == s,"path() found a wrong path."); |
127 check(pathSource(G, p) == s,"path() found a wrong path."); |
107 check(pathTarget(G, p) == t,"path() found a wrong path."); |
128 check(pathTarget(G, p) == t,"path() found a wrong path."); |
108 |
129 |
109 for(ArcIt e(G); e!=INVALID; ++e) { |
130 for(ArcIt e(G); e!=INVALID; ++e) { |
113 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]), |
134 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]), |
114 "dist(target)-dist(source)-arc_length= " << |
135 "dist(target)-dist(source)-arc_length= " << |
115 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); |
136 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); |
116 } |
137 } |
117 |
138 |
118 for(NodeIt v(G); v!=INVALID; ++v){ |
139 for(NodeIt v(G); v!=INVALID; ++v) { |
119 check(dijkstra_test.reached(v),"Each node should be reached."); |
140 if (dijkstra_test.reached(v)) { |
120 if ( dijkstra_test.predArc(v)!=INVALID ) { |
141 check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree."); |
121 Arc e=dijkstra_test.predArc(v); |
142 if (dijkstra_test.predArc(v)!=INVALID ) { |
122 Node u=G.source(e); |
143 Arc e=dijkstra_test.predArc(v); |
123 check(u==dijkstra_test.predNode(v),"Wrong tree."); |
144 Node u=G.source(e); |
124 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], |
145 check(u==dijkstra_test.predNode(v),"Wrong tree."); |
125 "Wrong distance! Difference: " << |
146 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], |
126 std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e])); |
147 "Wrong distance! Difference: " << |
|
148 std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e])); |
|
149 } |
127 } |
150 } |
128 } |
151 } |
129 |
152 |
130 { |
153 { |
131 NullMap<Node,Arc> myPredMap; |
154 NullMap<Node,Arc> myPredMap; |