Bugfix, thanks to Janos.
2 * src/test/dijkstra_heap_test.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 //Tests dijsktra.h with two heap implementations:
18 //the default binary heap of bin_heap.h, and the
19 //Fibonacci heap of fib_heap.h.
21 //The input is a graph in standard dimacs format from the standard input (like
22 //in /lemon_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both
23 //heaps, checking two postconditions:
25 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have
26 //dist(v)-dist(u)=length(e)
28 // - if all edges e=uv with u reachable from the root have
29 //dist(v)-dist(u)>=length(e)
33 #include <lemon/smart_graph.h>
35 #include <lemon/graph_writer.h>
36 #include <lemon/map_utils.h>
39 #include <lemon/dimacs.h>
40 #include <lemon/dijkstra.h>
41 #include <lemon/time_measure.h>
42 #include <lemon/graph_utils.h>
44 #include <lemon/bin_heap.h>
45 #include <lemon/fib_heap.h>
46 #include <lemon/radix_heap.h>
48 using namespace lemon;
50 typedef ListGraph Graph;
52 typedef Graph::Edge Edge;
53 typedef Graph::Node Node;
54 typedef Graph::EdgeIt EdgeIt;
55 typedef Graph::NodeIt NodeIt;
56 typedef Graph::EdgeMap<int> LengthMap;
59 struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
60 typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap;
63 struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
64 typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap;
68 int main(int argc, const char* argv[]) {
74 readDimacs(std::cin, graph, cap, s, t);
77 GraphWriter<Graph> writer(std::cout, graph);
79 IdMap<Graph, Node> nodeIdMap(graph);
80 writer.addNodeMap("id", nodeIdMap);
82 IdMap<Graph, Edge> edgeIdMap(graph);
83 writer.addEdgeMap("id", edgeIdMap);
85 writer.addEdgeMap("cap", cap);
90 "\n Testing dijkstra.h with binary heap implementation bin_heap.h,"
92 std::cout<<" on a graph with " <<
93 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
94 << std::endl<<std::endl;
97 Dijkstra<Graph, LengthMap>
98 dijkstra_test(graph, cap);
100 dijkstra_test.run(s);
101 std::cout << "elapsed time: " << ts << std::endl;
106 for(EdgeIt e(graph); e!=INVALID; ++e) {
107 Node u=graph.source(e);
108 Node v=graph.target(e);
109 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
110 if ( dijkstra_test.reached(u) ) {
111 std::cout<<"Error! dist(target)-dist(source)- edge_length= "
112 <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
119 for(NodeIt v(graph); v!=INVALID; ++v) {
120 if ( dijkstra_test.reached(v) ) {
121 Edge e=dijkstra_test.pred(v);
123 Node u=graph.source(e);
124 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
125 std::cout<<"Error in a shortest path tree edge! Difference: "
126 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
127 - cap[e])<<std::endl;
136 std::cout << error1 << " non-tree and " << error2
137 << " shortest path tree edge is erroneous."<<std::endl;
142 "\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
144 std::cout<<" on a graph with " <<
145 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
146 << std::endl<<std::endl;
149 Dijkstra<Graph, LengthMap, FibTraits>
150 dijkstra_test2(graph, cap);
152 dijkstra_test2.run(s);
153 std::cout << "elapsed time: " << ts << std::endl;
158 for(EdgeIt e(graph); e!=INVALID; ++e) {
159 Node u=graph.source(e);
160 Node v=graph.target(e);
161 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
162 if ( dijkstra_test2.reached(u) ) {
163 std::cout<<"Error! dist(target)-dist(source)- edge_length= "
164 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
170 for(NodeIt n(graph); v!=INVALID; ++v) {
171 if ( dijkstra_test2.reached(v) ) {
172 Edge e=dijkstra_test2.pred(v);
174 Node u=graph.source(e);
175 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
176 std::cout<<"Error in a shortest path tree edge! Difference: "
177 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
178 - cap[e])<<std::endl;
186 std::cout << error1 << " non-tree and " << error2
187 << " shortest path tree edge is erroneous."<<std::endl;
190 "\n\n Testing dijkstra.h with Radix heap implementation radix_heap.h,"
192 std::cout<<" on a graph with " <<
193 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
194 << std::endl<<std::endl;
197 Dijkstra<Graph, LengthMap, RadixTraits>
198 dijkstra_test3(graph, cap);
200 dijkstra_test3.run(s);
201 std::cout << "elapsed time: " << ts << std::endl;
207 for(EdgeIt e(graph); e!=INVALID; ++e) {
208 Node u=graph.source(e);
209 Node v=graph.target(e);
210 if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] )
211 if ( dijkstra_test3.reached(u) ) {
212 std::cout<<"Error! dist(target)-dist(source)- edge_length= "
213 <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
219 for(NodeIt n(graph); v!=INVALID; ++v) {
220 if ( dijkstra_test3.reached(v) ) {
221 Edge e=dijkstra_test3.pred(v);
223 Node u=graph.source(e);
224 if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) {
225 std::cout<<"Error in a shortest path tree edge! Difference: "
226 <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
227 - cap[e])<<std::endl;
235 std::cout << error1 << " non-tree and " << error2
236 << " shortest path tree edge is erroneous."<<std::endl;