COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/heap_test.cc @ 257:8d76a7bf9961

Last change on this file since 257:8d76a7bf9961 was 257:8d76a7bf9961, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Rename Def* to Set* in Bfs, Dfs, Dijkstra (ticket #134)

File size: 4.4 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#include <iostream>
20#include <fstream>
21#include <string>
22#include <vector>
23
24#include <lemon/concept_check.h>
25#include <lemon/concepts/heap.h>
26
27#include <lemon/smart_graph.h>
28
29#include <lemon/lgf_reader.h>
30#include <lemon/dijkstra.h>
31#include <lemon/maps.h>
32
33#include <lemon/bin_heap.h>
34
35#include "test_tools.h"
36
37using namespace lemon;
38using namespace lemon::concepts;
39
40typedef ListDigraph Digraph;
41DIGRAPH_TYPEDEFS(Digraph);
42
43char test_lgf[] =
44  "@nodes\n"
45  "label\n"
46  "0\n"
47  "1\n"
48  "2\n"
49  "3\n"
50  "4\n"
51  "5\n"
52  "6\n"
53  "7\n"
54  "8\n"
55  "9\n"
56  "@arcs\n"
57  "                label   capacity\n"
58  "0       5       0       94\n"
59  "3       9       1       11\n"
60  "8       7       2       83\n"
61  "1       2       3       94\n"
62  "5       7       4       35\n"
63  "7       4       5       84\n"
64  "9       5       6       38\n"
65  "0       4       7       96\n"
66  "6       7       8       6\n"
67  "3       1       9       27\n"
68  "5       2       10      77\n"
69  "5       6       11      69\n"
70  "6       5       12      41\n"
71  "4       6       13      70\n"
72  "3       2       14      45\n"
73  "7       9       15      93\n"
74  "5       9       16      50\n"
75  "9       0       17      94\n"
76  "9       6       18      67\n"
77  "0       9       19      86\n"
78  "@attributes\n"
79  "source 3\n";
80
81int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
82int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
83
84int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
85
86template <typename Heap>
87void heapSortTest() {
88  RangeMap<int> map(test_len, -1);
89
90  Heap heap(map);
91
92  std::vector<int> v(test_len);
93
94  for (int i = 0; i < test_len; ++i) {
95    v[i] = test_seq[i];
96    heap.push(i, v[i]);
97  }
98  std::sort(v.begin(), v.end());
99  for (int i = 0; i < test_len; ++i) {
100    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
101    heap.pop();
102  }
103}
104
105template <typename Heap>
106void heapIncreaseTest() {
107  RangeMap<int> map(test_len, -1);
108
109  Heap heap(map);
110
111  std::vector<int> v(test_len);
112
113  for (int i = 0; i < test_len; ++i) {
114    v[i] = test_seq[i];
115    heap.push(i, v[i]);
116  }
117  for (int i = 0; i < test_len; ++i) {
118    v[i] += test_inc[i];
119    heap.increase(i, v[i]);
120  }
121  std::sort(v.begin(), v.end());
122  for (int i = 0; i < test_len; ++i) {
123    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
124    heap.pop();
125  }
126}
127
128
129
130template <typename Heap>
131void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
132                      Node source) {
133
134  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
135    Create dijkstra(digraph, length);
136
137  dijkstra.run(source);
138
139  for(ArcIt a(digraph); a != INVALID; ++a) {
140    Node s = digraph.source(a);
141    Node t = digraph.target(a);
142    if (dijkstra.reached(s)) {
143      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
144             "Error in a shortest path tree!");
145    }
146  }
147
148  for(NodeIt n(digraph); n != INVALID; ++n) {
149    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
150      Arc a = dijkstra.predArc(n);
151      Node s = digraph.source(a);
152      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
153             "Error in a shortest path tree!");
154    }
155  }
156
157}
158
159int main() {
160
161  typedef int Item;
162  typedef int Prio;
163  typedef RangeMap<int> ItemIntMap;
164
165  Digraph digraph;
166  IntArcMap length(digraph);
167  Node source;
168
169  std::istringstream input(test_lgf);
170  digraphReader(input, digraph).
171    arcMap("capacity", length).
172    node("source", source).
173    run();
174
175  {
176    typedef BinHeap<Prio, ItemIntMap> IntHeap;
177    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
178    heapSortTest<IntHeap>();
179    heapIncreaseTest<IntHeap>();
180
181    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
182    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
183    dijkstraHeapTest<NodeHeap>(digraph, length, source);
184  }
185
186  return 0;
187}
Note: See TracBrowser for help on using the repository browser.