Sorry for the previous commit, it was not ready yet, but that damned up arrow... So in this new revision string-double and double-string conversion is corrected to a more C++ way.
6 #include <lemon/dijkstra.h>
8 class IntIntMap : public std::vector<int> {
10 typedef std::vector<int> Parent;
12 IntIntMap() : Parent() {}
13 IntIntMap(int n) : Parent(n) {}
14 IntIntMap(int n, int v) : Parent(n, v) {}
16 void set(int key, int value) {
17 Parent::operator[](key) = value;
22 template <typename _Heap>
23 void heapSortTest(int n) {
29 std::vector<int> v(n);
31 for (int i = 0; i < n; ++i) {
35 std::sort(v.begin(), v.end());
36 for (int i = 0; i < n; ++i) {
37 check(v[i] == heap.prio() ,"Wrong order in heap sort.");
42 template <typename _Heap>
43 void heapIncreaseTest(int n) {
49 std::vector<int> v(n);
51 for (int i = 0; i < n; ++i) {
55 for (int i = 0; i < n; ++i) {
56 v[i] += rand() % 1000;
57 heap.increase(i, v[i]);
59 std::sort(v.begin(), v.end());
60 for (int i = 0; i < n; ++i) {
61 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
68 template <typename _Traits, typename _Heap>
69 struct DefHeapTraits : public _Traits {
73 template <typename _Graph, typename _LengthMap, typename _Heap>
74 void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
75 typename _Graph::Node& start) {
79 typedef _LengthMap LengthMap;
81 typedef typename Graph::Node Node;
82 typedef typename Graph::Edge Edge;
83 typedef typename Graph::NodeIt NodeIt;
84 typedef typename Graph::EdgeIt EdgeIt;
86 Dijkstra<Graph, LengthMap,
87 DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
88 dijkstra(graph, length);
92 for(EdgeIt e(graph); e!=INVALID; ++e) {
93 Node u=graph.source(e);
94 Node v=graph.target(e);
95 if (dijkstra.reached(u)) {
96 check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
97 "Error in a shortest path tree edge!");
101 for(NodeIt v(graph); v!=INVALID; ++v) {
102 if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {
103 Edge e=dijkstra.pred(v);
104 Node u=graph.source(e);
105 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
106 "Error in a shortest path tree edge!");