COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/heap_test.cc @ 1325:916ec8699dc3

Last change on this file since 1325:916ec8699dc3 was 1325:916ec8699dc3, checked in by Alpar Juttner, 15 years ago

An icc warning resolved.

File size: 3.4 KB
Line 
1// -*- c++ -*-
2
3#include <iostream>
4#include <fstream>
5#include <string>
6#include <vector>
7
8#include <lemon/concept_check.h>
9
10#include <lemon/smart_graph.h>
11
12#include <lemon/graph_reader.h>
13
14#include <lemon/bin_heap.h>
15#include <lemon/fib_heap.h>
16#include <lemon/radix_heap.h>
17
18#include "test_tools.h"
19
20#include "heap_test.h"
21
22
23using namespace lemon;
24
25template <typename Item, typename Prio, typename ItemIntMap>
26class HeapConcept {
27public: 
28
29  template <typename _Heap>
30  struct Constraints {
31  public:
32   
33    void constraints() {
34      Item item;
35      Prio prio;
36
37      ignore_unused_variable_warning(item);
38      ignore_unused_variable_warning(prio);
39
40      typedef typename _Heap::state_enum state_enum;
41      state_enum state;
42
43      ignore_unused_variable_warning(state);
44     
45      _Heap heap1 = _Heap(map);
46
47      ignore_unused_variable_warning(heap1);
48     
49      heap.push(item, prio);
50
51      prio = heap.prio();
52      item = heap.top();
53
54      heap.pop();
55
56      heap.set(item, prio);
57      heap.decrease(item, prio);
58      heap.increase(item, prio);
59      prio = heap[item];
60
61      heap.erase(item);
62
63      state = heap.state(item);
64
65      state = _Heap::PRE_HEAP;
66      state = _Heap::IN_HEAP;
67      state = _Heap::POST_HEAP;
68    }
69   
70    _Heap& heap;
71    ItemIntMap& map;
72
73    Constraints() : heap(0), map(0) {}
74  };
75};
76
77int main() {
78
79  typedef int Item;
80  typedef int Prio;
81  typedef IntIntMap ItemIntMap;
82
83  typedef ListGraph Graph;
84
85  typedef Graph::Edge Edge;
86  typedef Graph::Node Node;
87  typedef Graph::EdgeIt EdgeIt;
88  typedef Graph::NodeIt NodeIt;
89  typedef Graph::EdgeMap<int> LengthMap;
90
91  Graph graph;
92  LengthMap length(graph);
93  Node start;
94
95  /// \todo create own test graph
96
97  std::string f_name;
98  if( getenv("srcdir") )
99    f_name = std::string(getenv("srcdir"));
100  else f_name = ".";
101  f_name += "/dijkstra_test.lgf";
102 
103  std::ifstream input(f_name.c_str());
104  check(input, "Input file '" << f_name << "' not found.");
105  readGraph(input, graph, length, start); 
106 
107  {
108    std::cerr << "Checking Bin Heap" << std::endl;
109
110    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
111    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
112    heapSortTest<IntHeap>(100);
113    heapIncreaseTest<IntHeap>(100);
114   
115    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
116    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
117    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
118  }
119  {
120    std::cerr << "Checking Fib Heap" << std::endl;
121
122    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
123    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
124    heapSortTest<IntHeap>(100);
125    heapIncreaseTest<IntHeap>(100);
126
127    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
128    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
129    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
130  }
131  {
132    std::cerr << "Checking Radix Heap" << std::endl;
133
134    typedef RadixHeap<Item, ItemIntMap> IntHeap;
135    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
136    heapSortTest<IntHeap>(100);
137    heapIncreaseTest<IntHeap>(100);
138
139    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
140    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
141    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
142  }
143
144  std::cout << __FILE__ ": All tests passed.\n";
145
146  return 0;
147}
Note: See TracBrowser for help on using the repository browser.