Tons of todos have been removed.
8 #include <lemon/concept_check.h>
9 #include <lemon/concept/heap.h>
11 #include <lemon/smart_graph.h>
13 #include <lemon/graph_reader.h>
15 #include <lemon/bin_heap.h>
16 #include <lemon/fib_heap.h>
17 #include <lemon/radix_heap.h>
18 #include <lemon/linear_heap.h>
20 #include "test_tools.h"
22 #include "heap_test.h"
24 #include <lemon/time_measure.h>
26 using namespace lemon;
27 using namespace lemon::concept;
34 typedef IntIntMap ItemIntMap;
36 typedef ListGraph Graph;
38 typedef Graph::Edge Edge;
39 typedef Graph::Node Node;
40 typedef Graph::EdgeIt EdgeIt;
41 typedef Graph::NodeIt NodeIt;
42 typedef Graph::EdgeMap<int> LengthMap;
45 LengthMap length(graph);
48 /// \todo create own test graph
51 if( getenv("srcdir") )
52 f_name = std::string(getenv("srcdir"));
54 f_name += "/dijkstra_test.lgf";
56 std::ifstream input(f_name.c_str());
57 check(input, "Input file '" << f_name << "' not found.");
58 GraphReader<Graph>(input, graph).
59 readEdgeMap("length", length).
60 readNode("source", start).
64 std::cerr << "Checking Bin Heap" << std::endl;
66 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
67 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
68 heapSortTest<IntHeap>(100);
69 heapIncreaseTest<IntHeap>(100);
71 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
72 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
74 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
75 std::cout << timer << std::endl;
78 std::cerr << "Checking Fib Heap" << std::endl;
80 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
81 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
82 heapSortTest<IntHeap>(100);
83 heapIncreaseTest<IntHeap>(100);
85 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
86 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
88 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
89 std::cout << timer << std::endl;
92 std::cerr << "Checking Radix Heap" << std::endl;
94 typedef RadixHeap<Item, ItemIntMap> IntHeap;
95 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
96 heapSortTest<IntHeap>(100);
97 heapIncreaseTest<IntHeap>(100);
99 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
100 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
102 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
103 std::cout << timer << std::endl;
107 std::cerr << "Checking Linear Heap" << std::endl;
109 typedef LinearHeap<Item, ItemIntMap> IntHeap;
110 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
111 heapSortTest<IntHeap>(100);
112 heapIncreaseTest<IntHeap>(100);
114 typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
115 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
117 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
118 std::cout << timer << std::endl;
121 std::cout << __FILE__ ": All tests passed.\n";