1.1 --- a/src/test/dijkstra_heap_test.cc Fri Mar 04 17:18:25 2005 +0000
1.2 +++ b/src/test/dijkstra_heap_test.cc Fri Mar 04 17:20:11 2005 +0000
1.3 @@ -31,49 +31,81 @@
1.4 #include <math.h>
1.5
1.6 #include <lemon/smart_graph.h>
1.7 +
1.8 +#include <lemon/graph_writer.h>
1.9 +#include <lemon/map_utils.h>
1.10 +
1.11 +
1.12 #include <lemon/dimacs.h>
1.13 #include <lemon/dijkstra.h>
1.14 #include <lemon/time_measure.h>
1.15 +#include <lemon/graph_utils.h>
1.16 +
1.17 #include <lemon/bin_heap.h>
1.18 #include <lemon/fib_heap.h>
1.19 +#include <lemon/radix_heap.h>
1.20
1.21 using namespace lemon;
1.22
1.23 -int main(int, char **) {
1.24 +typedef ListGraph Graph;
1.25 +
1.26 +typedef Graph::Edge Edge;
1.27 +typedef Graph::Node Node;
1.28 +typedef Graph::EdgeIt EdgeIt;
1.29 +typedef Graph::NodeIt NodeIt;
1.30 +typedef Graph::EdgeMap<int> LengthMap;
1.31 +
1.32 +
1.33 +struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
1.34 + typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap;
1.35 +};
1.36 +
1.37 +struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
1.38 + typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap;
1.39 +};
1.40 +
1.41 +
1.42 +int main(int argc, const char* argv[]) {
1.43
1.44 - typedef SmartGraph Graph;
1.45
1.46 - typedef Graph::Edge Edge;
1.47 - typedef Graph::Node Node;
1.48 - typedef Graph::EdgeIt EdgeIt;
1.49 - typedef Graph::NodeIt NodeIt;
1.50 - typedef Graph::template EdgeMap<int> LengthMap;
1.51 + Graph graph;
1.52 + Node s, t;
1.53 + LengthMap cap(graph);
1.54 + readDimacs(std::cin, graph, cap, s, t);
1.55 + Timer ts;
1.56
1.57 - Graph G;
1.58 - Node s, t;
1.59 - LengthMap cap(G);
1.60 - readDimacsMaxFlow(std::cin, G, s, t, cap);
1.61 - Timer ts;
1.62 + GraphWriter<Graph> writer(std::cout, graph);
1.63 +
1.64 + IdMap<Graph, Node> nodeIdMap(graph);
1.65 + writer.addNodeMap("id", nodeIdMap);
1.66 +
1.67 + IdMap<Graph, Edge> edgeIdMap(graph);
1.68 + writer.addEdgeMap("id", edgeIdMap);
1.69 +
1.70 + writer.addEdgeMap("cap", cap);
1.71 +
1.72 + writer.run();
1.73
1.74 std::cout <<
1.75 "\n Testing dijkstra.h with binary heap implementation bin_heap.h,"
1.76 <<std::endl;
1.77 std::cout<<" on a graph with " <<
1.78 - G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.79 + countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
1.80 << std::endl<<std::endl;
1.81 -
1.82 +
1.83 +
1.84 Dijkstra<Graph, LengthMap>
1.85 - dijkstra_test(G, cap);
1.86 + dijkstra_test(graph, cap);
1.87 ts.reset();
1.88 - dijkstra_test.run(s);
1.89 + dijkstra_test.run(s);
1.90 std::cout << "elapsed time: " << ts << std::endl;
1.91 -
1.92 +
1.93 int error1=0;
1.94 int error2=0;
1.95
1.96 - for(EdgeIt e(G); e!=INVALID; ++e) {
1.97 - Node u=G.source(e);
1.98 - Node v=G.target(e);
1.99 + for(EdgeIt e(graph); e!=INVALID; ++e) {
1.100 + Node u=graph.source(e);
1.101 + Node v=graph.target(e);
1.102 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
1.103 if ( dijkstra_test.reached(u) ) {
1.104 std::cout<<"Error! dist(target)-dist(source)- edge_length= "
1.105 @@ -84,10 +116,10 @@
1.106 }
1.107
1.108 NodeIt v;
1.109 - for(NodeIt v(G); v!=INVALID; ++v) {
1.110 + for(NodeIt v(graph); v!=INVALID; ++v) {
1.111 if ( dijkstra_test.reached(v) ) {
1.112 Edge e=dijkstra_test.pred(v);
1.113 - Node u=G.source(e);
1.114 + Node u=graph.source(e);
1.115 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
1.116 std::cout<<"Error in a shortest path tree edge! Difference: "
1.117 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.118 @@ -108,11 +140,12 @@
1.119 "\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
1.120 <<std::endl;
1.121 std::cout<<" on a graph with " <<
1.122 - G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.123 + countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
1.124 << std::endl<<std::endl;
1.125
1.126 - Dijkstra<Graph, LengthMap, FibHeap>
1.127 - dijkstra_test2(G, cap);
1.128 +
1.129 + Dijkstra<Graph, LengthMap, FibTraits>
1.130 + dijkstra_test2(graph, cap);
1.131 ts.reset();
1.132 dijkstra_test2.run(s);
1.133 std::cout << "elapsed time: " << ts << std::endl;
1.134 @@ -120,9 +153,9 @@
1.135 error1=0;
1.136 error2=0;
1.137
1.138 - for(EdgeIt e(G); e!=INVALID; ++e) {
1.139 - Node u=G.source(e);
1.140 - Node v=G.target(e);
1.141 + for(EdgeIt e(graph); e!=INVALID; ++e) {
1.142 + Node u=graph.source(e);
1.143 + Node v=graph.target(e);
1.144 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
1.145 if ( dijkstra_test2.reached(u) ) {
1.146 std::cout<<"Error! dist(target)-dist(source)- edge_length= "
1.147 @@ -132,10 +165,10 @@
1.148 }
1.149 }
1.150
1.151 - for(NodeIt n(G); v!=INVALID; ++v) {
1.152 + for(NodeIt n(graph); v!=INVALID; ++v) {
1.153 if ( dijkstra_test2.reached(v) ) {
1.154 Edge e=dijkstra_test2.pred(v);
1.155 - Node u=G.source(e);
1.156 + Node u=graph.source(e);
1.157 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
1.158 std::cout<<"Error in a shortest path tree edge! Difference: "
1.159 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
1.160 @@ -149,6 +182,52 @@
1.161 std::cout << error1 << " non-tree and " << error2
1.162 << " shortest path tree edge is erroneous."<<std::endl;
1.163
1.164 + std::cout <<
1.165 + "\n\n Testing dijkstra.h with Radix heap implementation radix_heap.h,"
1.166 + <<std::endl;
1.167 + std::cout<<" on a graph with " <<
1.168 + countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
1.169 + << std::endl<<std::endl;
1.170 +
1.171 +
1.172 + Dijkstra<Graph, LengthMap, RadixTraits>
1.173 + dijkstra_test3(graph, cap);
1.174 + ts.reset();
1.175 + dijkstra_test3.run(s);
1.176 + std::cout << "elapsed time: " << ts << std::endl;
1.177 +
1.178 +
1.179 + error1=0;
1.180 + error2=0;
1.181 +
1.182 + for(EdgeIt e(graph); e!=INVALID; ++e) {
1.183 + Node u=graph.source(e);
1.184 + Node v=graph.target(e);
1.185 + if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] )
1.186 + if ( dijkstra_test3.reached(u) ) {
1.187 + std::cout<<"Error! dist(target)-dist(source)- edge_length= "
1.188 + <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
1.189 + - cap[e]<<std::endl;
1.190 + ++error1;
1.191 + }
1.192 + }
1.193 +
1.194 + for(NodeIt n(graph); v!=INVALID; ++v) {
1.195 + if ( dijkstra_test3.reached(v) ) {
1.196 + Edge e=dijkstra_test3.pred(v);
1.197 + Node u=graph.source(e);
1.198 + if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) {
1.199 + std::cout<<"Error in a shortest path tree edge! Difference: "
1.200 + <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
1.201 + - cap[e])<<std::endl;
1.202 + ++error2;
1.203 + }
1.204 + }
1.205 + }
1.206 +
1.207 +
1.208 + std::cout << error1 << " non-tree and " << error2
1.209 + << " shortest path tree edge is erroneous."<<std::endl;
1.210
1.211 return 0;
1.212 }