Small bugs in the documentation.
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;
31 IntIntMap() : Parent() {}
32 IntIntMap(int n) : Parent(n) {}
33 IntIntMap(int n, int v) : Parent(n, v) {}
35 void set(int key, int value) {
36 Parent::operator[](key) = value;
41 template <typename _Heap>
42 void heapSortTest(int n) {
48 std::vector<int> v(n);
50 for (int i = 0; i < n; ++i) {
54 std::sort(v.begin(), v.end());
55 for (int i = 0; i < n; ++i) {
56 check(v[i] == heap.prio() ,"Wrong order in heap sort.");
61 template <typename _Heap>
62 void heapIncreaseTest(int n) {
68 std::vector<int> v(n);
70 for (int i = 0; i < n; ++i) {
74 for (int i = 0; i < n; ++i) {
76 heap.increase(i, v[i]);
78 std::sort(v.begin(), v.end());
79 for (int i = 0; i < n; ++i) {
80 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
87 template <typename _Graph, typename _LengthMap, typename _Heap>
88 void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
89 typename _Graph::Node& start) {
93 typedef _LengthMap LengthMap;
95 typedef typename Graph::Node Node;
96 typedef typename Graph::Edge Edge;
97 typedef typename Graph::NodeIt NodeIt;
98 typedef typename Graph::EdgeIt EdgeIt;
100 typename Dijkstra<Graph, LengthMap>::template DefStandardHeap<Heap>::
101 Create dijkstra(graph, length);
105 for(EdgeIt e(graph); e!=INVALID; ++e) {
106 Node u=graph.source(e);
107 Node v=graph.target(e);
108 if (dijkstra.reached(u)) {
109 check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
110 "Error in a shortest path tree edge!");
114 for(NodeIt v(graph); v!=INVALID; ++v) {
115 if ( dijkstra.reached(v) && dijkstra.predEdge(v) != INVALID ) {
116 Edge e=dijkstra.predEdge(v);
117 Node u=graph.source(e);
118 check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
119 "Error in a shortest path tree edge!");