1.1 --- a/src/test/dijkstra_heap_test.cc Sat Apr 09 19:36:46 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,239 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/test/dijkstra_heap_test.cc - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -//Tests dijsktra.h with two heap implementations:
1.21 -//the default binary heap of bin_heap.h, and the
1.22 -//Fibonacci heap of fib_heap.h.
1.23 -
1.24 -//The input is a graph in standard dimacs format from the standard input (like
1.25 -//in /lemon_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both
1.26 -//heaps, checking two postconditions:
1.27 -
1.28 -//- if the edges e=uv of the shortest path tree reported by dijkstra.h have
1.29 -//dist(v)-dist(u)=length(e)
1.30 -
1.31 -// - if all edges e=uv with u reachable from the root have
1.32 -//dist(v)-dist(u)>=length(e)
1.33 -#include <iostream>
1.34 -#include <math.h>
1.35 -
1.36 -#include <lemon/smart_graph.h>
1.37 -
1.38 -#include <lemon/graph_writer.h>
1.39 -#include <lemon/map_utils.h>
1.40 -
1.41 -
1.42 -#include <lemon/dimacs.h>
1.43 -#include <lemon/dijkstra.h>
1.44 -#include <lemon/time_measure.h>
1.45 -#include <lemon/graph_utils.h>
1.46 -
1.47 -#include <lemon/bin_heap.h>
1.48 -#include <lemon/fib_heap.h>
1.49 -#include <lemon/radix_heap.h>
1.50 -
1.51 -using namespace lemon;
1.52 -
1.53 -typedef ListGraph Graph;
1.54 -
1.55 -typedef Graph::Edge Edge;
1.56 -typedef Graph::Node Node;
1.57 -typedef Graph::EdgeIt EdgeIt;
1.58 -typedef Graph::NodeIt NodeIt;
1.59 -typedef Graph::EdgeMap<int> LengthMap;
1.60 -
1.61 -
1.62 -struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
1.63 - typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap;
1.64 -};
1.65 -
1.66 -struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
1.67 - typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap;
1.68 -};
1.69 -
1.70 -
1.71 -int main(int argc, const char* argv[]) {
1.72 -
1.73 -
1.74 - Graph graph;
1.75 - Node s, t;
1.76 - LengthMap cap(graph);
1.77 - readDimacs(std::cin, graph, cap, s, t);
1.78 - Timer ts;
1.79 -
1.80 - GraphWriter<Graph> writer(std::cout, graph);
1.81 -
1.82 - IdMap<Graph, Node> nodeIdMap(graph);
1.83 - writer.addNodeMap("id", nodeIdMap);
1.84 -
1.85 - IdMap<Graph, Edge> edgeIdMap(graph);
1.86 - writer.addEdgeMap("id", edgeIdMap);
1.87 -
1.88 - writer.addEdgeMap("cap", cap);
1.89 -
1.90 - writer.run();
1.91 -
1.92 - std::cout <<
1.93 - "\n Testing dijkstra.h with binary heap implementation bin_heap.h,"
1.94 - <<std::endl;
1.95 - std::cout<<" on a graph with " <<
1.96 - countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
1.97 - << std::endl<<std::endl;
1.98 -
1.99 -
1.100 - Dijkstra<Graph, LengthMap>
1.101 - dijkstra_test(graph, cap);
1.102 - ts.reset();
1.103 - dijkstra_test.run(s);
1.104 - std::cout << "elapsed time: " << ts << std::endl;
1.105 -
1.106 - int error1=0;
1.107 - int error2=0;
1.108 -
1.109 - for(EdgeIt e(graph); e!=INVALID; ++e) {
1.110 - Node u=graph.source(e);
1.111 - Node v=graph.target(e);
1.112 - if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
1.113 - if ( dijkstra_test.reached(u) ) {
1.114 - std::cout<<"Error! dist(target)-dist(source)- edge_length= "
1.115 - <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.116 - - cap[e]<<std::endl;
1.117 - ++error1;
1.118 - }
1.119 - }
1.120 -
1.121 - NodeIt v;
1.122 - for(NodeIt v(graph); v!=INVALID; ++v) {
1.123 - if ( dijkstra_test.reached(v) ) {
1.124 - Edge e=dijkstra_test.pred(v);
1.125 - if(e!=INVALID) {
1.126 - Node u=graph.source(e);
1.127 - if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
1.128 - std::cout<<"Error in a shortest path tree edge! Difference: "
1.129 - <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.130 - - cap[e])<<std::endl;
1.131 - ++error2;
1.132 - }
1.133 - }
1.134 - }
1.135 - }
1.136 -
1.137 -
1.138 -
1.139 - std::cout << error1 << " non-tree and " << error2
1.140 - << " shortest path tree edge is erroneous."<<std::endl;
1.141 -
1.142 -
1.143 -
1.144 - std::cout <<
1.145 - "\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
1.146 - <<std::endl;
1.147 - std::cout<<" on a graph with " <<
1.148 - countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
1.149 - << std::endl<<std::endl;
1.150 -
1.151 -
1.152 - Dijkstra<Graph, LengthMap, FibTraits>
1.153 - dijkstra_test2(graph, cap);
1.154 - ts.reset();
1.155 - dijkstra_test2.run(s);
1.156 - std::cout << "elapsed time: " << ts << std::endl;
1.157 -
1.158 - error1=0;
1.159 - error2=0;
1.160 -
1.161 - for(EdgeIt e(graph); e!=INVALID; ++e) {
1.162 - Node u=graph.source(e);
1.163 - Node v=graph.target(e);
1.164 - if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
1.165 - if ( dijkstra_test2.reached(u) ) {
1.166 - std::cout<<"Error! dist(target)-dist(source)- edge_length= "
1.167 - <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
1.168 - - cap[e]<<std::endl;
1.169 - ++error1;
1.170 - }
1.171 - }
1.172 -
1.173 - for(NodeIt n(graph); v!=INVALID; ++v) {
1.174 - if ( dijkstra_test2.reached(v) ) {
1.175 - Edge e=dijkstra_test2.pred(v);
1.176 - if(e!=INVALID) {
1.177 - Node u=graph.source(e);
1.178 - if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
1.179 - std::cout<<"Error in a shortest path tree edge! Difference: "
1.180 - <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
1.181 - - cap[e])<<std::endl;
1.182 - ++error2;
1.183 - }
1.184 - }
1.185 - }
1.186 - }
1.187 -
1.188 -
1.189 - std::cout << error1 << " non-tree and " << error2
1.190 - << " shortest path tree edge is erroneous."<<std::endl;
1.191 -
1.192 - std::cout <<
1.193 - "\n\n Testing dijkstra.h with Radix heap implementation radix_heap.h,"
1.194 - <<std::endl;
1.195 - std::cout<<" on a graph with " <<
1.196 - countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
1.197 - << std::endl<<std::endl;
1.198 -
1.199 -
1.200 - Dijkstra<Graph, LengthMap, RadixTraits>
1.201 - dijkstra_test3(graph, cap);
1.202 - ts.reset();
1.203 - dijkstra_test3.run(s);
1.204 - std::cout << "elapsed time: " << ts << std::endl;
1.205 -
1.206 -
1.207 - error1=0;
1.208 - error2=0;
1.209 -
1.210 - for(EdgeIt e(graph); e!=INVALID; ++e) {
1.211 - Node u=graph.source(e);
1.212 - Node v=graph.target(e);
1.213 - if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] )
1.214 - if ( dijkstra_test3.reached(u) ) {
1.215 - std::cout<<"Error! dist(target)-dist(source)- edge_length= "
1.216 - <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
1.217 - - cap[e]<<std::endl;
1.218 - ++error1;
1.219 - }
1.220 - }
1.221 -
1.222 - for(NodeIt n(graph); v!=INVALID; ++v) {
1.223 - if ( dijkstra_test3.reached(v) ) {
1.224 - Edge e=dijkstra_test3.pred(v);
1.225 - if(e!=INVALID) {
1.226 - Node u=graph.source(e);
1.227 - if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) {
1.228 - std::cout<<"Error in a shortest path tree edge! Difference: "
1.229 - <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
1.230 - - cap[e])<<std::endl;
1.231 - ++error2;
1.232 - }
1.233 - }
1.234 - }
1.235 - }
1.236 -
1.237 -
1.238 - std::cout << error1 << " non-tree and " << error2
1.239 - << " shortest path tree edge is erroneous."<<std::endl;
1.240 -
1.241 - return 0;
1.242 -}