1 /* -*- C++ -*- |
1 /* -*- C++ -*- |
2 * src/test/dijkstra_heap_test.cc - Part of HUGOlib, a generic C++ optimization library |
2 * src/test/dijkstra_heap_test.cc - Part of LEMON, a generic C++ optimization library |
3 * |
3 * |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
6 * |
6 * |
7 * Permission to use, modify and distribute this software is granted |
7 * Permission to use, modify and distribute this software is granted |
17 //Tests dijsktra.h with two heap implementations: |
17 //Tests dijsktra.h with two heap implementations: |
18 //the default binary heap of bin_heap.h, and the |
18 //the default binary heap of bin_heap.h, and the |
19 //Fibonacci heap of fib_heap.h. |
19 //Fibonacci heap of fib_heap.h. |
20 |
20 |
21 //The input is a graph in standard dimacs format from the standard input (like |
21 //The input is a graph in standard dimacs format from the standard input (like |
22 //in /hugo_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both |
22 //in /lemon_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both |
23 //heaps, checking two postconditions: |
23 //heaps, checking two postconditions: |
24 |
24 |
25 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have |
25 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have |
26 //dist(v)-dist(u)=length(e) |
26 //dist(v)-dist(u)=length(e) |
27 |
27 |
28 // - if all edges e=uv with u reachable from the root have |
28 // - if all edges e=uv with u reachable from the root have |
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 <hugo/smart_graph.h> |
33 #include <lemon/smart_graph.h> |
34 #include <hugo/dimacs.h> |
34 #include <lemon/dimacs.h> |
35 #include <hugo/dijkstra.h> |
35 #include <lemon/dijkstra.h> |
36 #include <hugo/time_measure.h> |
36 #include <lemon/time_measure.h> |
37 #include <hugo/bin_heap.h> |
37 #include <lemon/bin_heap.h> |
38 #include <hugo/fib_heap.h> |
38 #include <lemon/fib_heap.h> |
39 |
39 |
40 using namespace hugo; |
40 using namespace lemon; |
41 |
41 |
42 int main(int, char **) { |
42 int main(int, char **) { |
43 |
43 |
44 typedef SmartGraph Graph; |
44 typedef SmartGraph Graph; |
45 |
45 |