29 //dist(v)-dist(u)>=length(e) |
29 //dist(v)-dist(u)>=length(e) |
30 #include <iostream> |
30 #include <iostream> |
31 #include <math.h> |
31 #include <math.h> |
32 |
32 |
33 #include <lemon/smart_graph.h> |
33 #include <lemon/smart_graph.h> |
|
34 |
|
35 #include <lemon/graph_writer.h> |
|
36 #include <lemon/map_utils.h> |
|
37 |
|
38 |
34 #include <lemon/dimacs.h> |
39 #include <lemon/dimacs.h> |
35 #include <lemon/dijkstra.h> |
40 #include <lemon/dijkstra.h> |
36 #include <lemon/time_measure.h> |
41 #include <lemon/time_measure.h> |
|
42 #include <lemon/graph_utils.h> |
|
43 |
37 #include <lemon/bin_heap.h> |
44 #include <lemon/bin_heap.h> |
38 #include <lemon/fib_heap.h> |
45 #include <lemon/fib_heap.h> |
|
46 #include <lemon/radix_heap.h> |
39 |
47 |
40 using namespace lemon; |
48 using namespace lemon; |
41 |
49 |
42 int main(int, char **) { |
50 typedef ListGraph Graph; |
43 |
51 |
44 typedef SmartGraph Graph; |
52 typedef Graph::Edge Edge; |
45 |
53 typedef Graph::Node Node; |
46 typedef Graph::Edge Edge; |
54 typedef Graph::EdgeIt EdgeIt; |
47 typedef Graph::Node Node; |
55 typedef Graph::NodeIt NodeIt; |
48 typedef Graph::EdgeIt EdgeIt; |
56 typedef Graph::EdgeMap<int> LengthMap; |
49 typedef Graph::NodeIt NodeIt; |
57 |
50 typedef Graph::template EdgeMap<int> LengthMap; |
58 |
51 |
59 struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> { |
52 Graph G; |
60 typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap; |
|
61 }; |
|
62 |
|
63 struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> { |
|
64 typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap; |
|
65 }; |
|
66 |
|
67 |
|
68 int main(int argc, const char* argv[]) { |
|
69 |
|
70 |
|
71 Graph graph; |
53 Node s, t; |
72 Node s, t; |
54 LengthMap cap(G); |
73 LengthMap cap(graph); |
55 readDimacsMaxFlow(std::cin, G, s, t, cap); |
74 readDimacs(std::cin, graph, cap, s, t); |
56 Timer ts; |
75 Timer ts; |
|
76 |
|
77 GraphWriter<Graph> writer(std::cout, graph); |
|
78 |
|
79 IdMap<Graph, Node> nodeIdMap(graph); |
|
80 writer.addNodeMap("id", nodeIdMap); |
|
81 |
|
82 IdMap<Graph, Edge> edgeIdMap(graph); |
|
83 writer.addEdgeMap("id", edgeIdMap); |
|
84 |
|
85 writer.addEdgeMap("cap", cap); |
|
86 |
|
87 writer.run(); |
57 |
88 |
58 std::cout << |
89 std::cout << |
59 "\n Testing dijkstra.h with binary heap implementation bin_heap.h," |
90 "\n Testing dijkstra.h with binary heap implementation bin_heap.h," |
60 <<std::endl; |
91 <<std::endl; |
61 std::cout<<" on a graph with " << |
92 std::cout<<" on a graph with " << |
62 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
93 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..." |
63 << std::endl<<std::endl; |
94 << std::endl<<std::endl; |
64 |
95 |
|
96 |
65 Dijkstra<Graph, LengthMap> |
97 Dijkstra<Graph, LengthMap> |
66 dijkstra_test(G, cap); |
98 dijkstra_test(graph, cap); |
67 ts.reset(); |
99 ts.reset(); |
68 dijkstra_test.run(s); |
100 dijkstra_test.run(s); |
69 std::cout << "elapsed time: " << ts << std::endl; |
101 std::cout << "elapsed time: " << ts << std::endl; |
70 |
102 |
71 int error1=0; |
103 int error1=0; |
72 int error2=0; |
104 int error2=0; |
73 |
105 |
74 for(EdgeIt e(G); e!=INVALID; ++e) { |
106 for(EdgeIt e(graph); e!=INVALID; ++e) { |
75 Node u=G.source(e); |
107 Node u=graph.source(e); |
76 Node v=G.target(e); |
108 Node v=graph.target(e); |
77 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) |
109 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) |
78 if ( dijkstra_test.reached(u) ) { |
110 if ( dijkstra_test.reached(u) ) { |
79 std::cout<<"Error! dist(target)-dist(source)- edge_length= " |
111 std::cout<<"Error! dist(target)-dist(source)- edge_length= " |
80 <<dijkstra_test.dist(v) - dijkstra_test.dist(u) |
112 <<dijkstra_test.dist(v) - dijkstra_test.dist(u) |
81 - cap[e]<<std::endl; |
113 - cap[e]<<std::endl; |
82 ++error1; |
114 ++error1; |
83 } |
115 } |
84 } |
116 } |
85 |
117 |
86 NodeIt v; |
118 NodeIt v; |
87 for(NodeIt v(G); v!=INVALID; ++v) { |
119 for(NodeIt v(graph); v!=INVALID; ++v) { |
88 if ( dijkstra_test.reached(v) ) { |
120 if ( dijkstra_test.reached(v) ) { |
89 Edge e=dijkstra_test.pred(v); |
121 Edge e=dijkstra_test.pred(v); |
90 Node u=G.source(e); |
122 Node u=graph.source(e); |
91 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) { |
123 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) { |
92 std::cout<<"Error in a shortest path tree edge! Difference: " |
124 std::cout<<"Error in a shortest path tree edge! Difference: " |
93 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) |
125 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) |
94 - cap[e])<<std::endl; |
126 - cap[e])<<std::endl; |
95 ++error2; |
127 ++error2; |
106 |
138 |
107 std::cout << |
139 std::cout << |
108 "\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h," |
140 "\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h," |
109 <<std::endl; |
141 <<std::endl; |
110 std::cout<<" on a graph with " << |
142 std::cout<<" on a graph with " << |
111 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
143 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..." |
112 << std::endl<<std::endl; |
144 << std::endl<<std::endl; |
113 |
145 |
114 Dijkstra<Graph, LengthMap, FibHeap> |
146 |
115 dijkstra_test2(G, cap); |
147 Dijkstra<Graph, LengthMap, FibTraits> |
|
148 dijkstra_test2(graph, cap); |
116 ts.reset(); |
149 ts.reset(); |
117 dijkstra_test2.run(s); |
150 dijkstra_test2.run(s); |
118 std::cout << "elapsed time: " << ts << std::endl; |
151 std::cout << "elapsed time: " << ts << std::endl; |
119 |
152 |
120 error1=0; |
153 error1=0; |
121 error2=0; |
154 error2=0; |
122 |
155 |
123 for(EdgeIt e(G); e!=INVALID; ++e) { |
156 for(EdgeIt e(graph); e!=INVALID; ++e) { |
124 Node u=G.source(e); |
157 Node u=graph.source(e); |
125 Node v=G.target(e); |
158 Node v=graph.target(e); |
126 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) |
159 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) |
127 if ( dijkstra_test2.reached(u) ) { |
160 if ( dijkstra_test2.reached(u) ) { |
128 std::cout<<"Error! dist(target)-dist(source)- edge_length= " |
161 std::cout<<"Error! dist(target)-dist(source)- edge_length= " |
129 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u) |
162 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u) |
130 - cap[e]<<std::endl; |
163 - cap[e]<<std::endl; |
131 ++error1; |
164 ++error1; |
132 } |
165 } |
133 } |
166 } |
134 |
167 |
135 for(NodeIt n(G); v!=INVALID; ++v) { |
168 for(NodeIt n(graph); v!=INVALID; ++v) { |
136 if ( dijkstra_test2.reached(v) ) { |
169 if ( dijkstra_test2.reached(v) ) { |
137 Edge e=dijkstra_test2.pred(v); |
170 Edge e=dijkstra_test2.pred(v); |
138 Node u=G.source(e); |
171 Node u=graph.source(e); |
139 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) { |
172 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) { |
140 std::cout<<"Error in a shortest path tree edge! Difference: " |
173 std::cout<<"Error in a shortest path tree edge! Difference: " |
141 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u) |
174 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u) |
142 - cap[e])<<std::endl; |
175 - cap[e])<<std::endl; |
143 ++error2; |
176 ++error2; |
147 |
180 |
148 |
181 |
149 std::cout << error1 << " non-tree and " << error2 |
182 std::cout << error1 << " non-tree and " << error2 |
150 << " shortest path tree edge is erroneous."<<std::endl; |
183 << " shortest path tree edge is erroneous."<<std::endl; |
151 |
184 |
|
185 std::cout << |
|
186 "\n\n Testing dijkstra.h with Radix heap implementation radix_heap.h," |
|
187 <<std::endl; |
|
188 std::cout<<" on a graph with " << |
|
189 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..." |
|
190 << std::endl<<std::endl; |
|
191 |
|
192 |
|
193 Dijkstra<Graph, LengthMap, RadixTraits> |
|
194 dijkstra_test3(graph, cap); |
|
195 ts.reset(); |
|
196 dijkstra_test3.run(s); |
|
197 std::cout << "elapsed time: " << ts << std::endl; |
|
198 |
|
199 |
|
200 error1=0; |
|
201 error2=0; |
|
202 |
|
203 for(EdgeIt e(graph); e!=INVALID; ++e) { |
|
204 Node u=graph.source(e); |
|
205 Node v=graph.target(e); |
|
206 if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] ) |
|
207 if ( dijkstra_test3.reached(u) ) { |
|
208 std::cout<<"Error! dist(target)-dist(source)- edge_length= " |
|
209 <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u) |
|
210 - cap[e]<<std::endl; |
|
211 ++error1; |
|
212 } |
|
213 } |
|
214 |
|
215 for(NodeIt n(graph); v!=INVALID; ++v) { |
|
216 if ( dijkstra_test3.reached(v) ) { |
|
217 Edge e=dijkstra_test3.pred(v); |
|
218 Node u=graph.source(e); |
|
219 if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) { |
|
220 std::cout<<"Error in a shortest path tree edge! Difference: " |
|
221 <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u) |
|
222 - cap[e])<<std::endl; |
|
223 ++error2; |
|
224 } |
|
225 } |
|
226 } |
|
227 |
|
228 |
|
229 std::cout << error1 << " non-tree and " << error2 |
|
230 << " shortest path tree edge is erroneous."<<std::endl; |
152 |
231 |
153 return 0; |
232 return 0; |
154 } |
233 } |