Forgotten functions in the graph adaptor extenders.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 #include <lemon/dijkstra.h>
24 class IntIntMap : public std::vector<int> {
26 typedef std::vector<int> Parent;
28 IntIntMap() : Parent() {}
29 IntIntMap(int n) : Parent(n) {}
30 IntIntMap(int n, int v) : Parent(n, v) {}
32 void set(int key, int value) {
33 Parent::operator[](key) = value;
38 template <typename _Heap>
39 void heapSortTest(int n) {
45 std::vector<int> v(n);
47 for (int i = 0; i < n; ++i) {
51 std::sort(v.begin(), v.end());
52 for (int i = 0; i < n; ++i) {
53 check(v[i] == heap.prio() ,"Wrong order in heap sort.");
58 template <typename _Heap>
59 void heapIncreaseTest(int n) {
65 std::vector<int> v(n);
67 for (int i = 0; i < n; ++i) {
71 for (int i = 0; i < n; ++i) {
72 v[i] += rand() % 1000;
73 heap.increase(i, v[i]);
75 std::sort(v.begin(), v.end());
76 for (int i = 0; i < n; ++i) {
77 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
84 template <typename _Graph, typename _LengthMap, typename _Heap>
85 void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
86 typename _Graph::Node& start) {
90 typedef _LengthMap LengthMap;
92 typedef typename Graph::Node Node;
93 typedef typename Graph::Edge Edge;
94 typedef typename Graph::NodeIt NodeIt;
95 typedef typename Graph::EdgeIt EdgeIt;
97 typename Dijkstra<Graph, LengthMap>::template DefStandardHeap<Heap>::
98 Create dijkstra(graph, length);
102 for(EdgeIt e(graph); e!=INVALID; ++e) {
103 Node u=graph.source(e);
104 Node v=graph.target(e);
105 if (dijkstra.reached(u)) {
106 check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
107 "Error in a shortest path tree edge!");
111 for(NodeIt v(graph); v!=INVALID; ++v) {
112 if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) {
113 Edge e=dijkstra.predEdge(v);
114 Node u=graph.source(e);
115 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
116 "Error in a shortest path tree edge!");