COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/heap_test.cc @ 1215:81b4731f8a6b

Last change on this file since 1215:81b4731f8a6b was 1215:81b4731f8a6b, checked in by Alpar Juttner, 15 years ago
  • '.lgf' could be the standard 'lemon graph format' extension.
  • heap_test is fixed in order that 'make discheck' work.
  • heap_test now checks whether the input file exists.
File size: 3.3 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};
74
75int main() {
76
77  typedef int Item;
78  typedef int Prio;
79  typedef IntIntMap ItemIntMap;
80
81  typedef ListGraph Graph;
82
83  typedef Graph::Edge Edge;
84  typedef Graph::Node Node;
85  typedef Graph::EdgeIt EdgeIt;
86  typedef Graph::NodeIt NodeIt;
87  typedef Graph::EdgeMap<int> LengthMap;
88
89  Graph graph;
90  LengthMap length(graph);
91  Node start;
92
93  /// \todo create own test graph
94
95  std::string f_name;
96  if( getenv("srcdir") )
97    f_name = std::string(getenv("srcdir"));
98  else f_name = ".";
99  f_name += "/dijkstra_test.lgf";
100 
101  std::ifstream input(f_name.c_str());
102  check(input, "Input file '" << f_name << "' not found.");
103  readGraph(input, graph, length, start); 
104 
105  {
106    std::cerr << "Checking Bin Heap" << std::endl;
107
108    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
109    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
110    heapSortTest<IntHeap>(100);
111    heapIncreaseTest<IntHeap>(100);
112   
113    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
114    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
115    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
116  }
117  {
118    std::cerr << "Checking Fib Heap" << std::endl;
119
120    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
121    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
122    heapSortTest<IntHeap>(100);
123    heapIncreaseTest<IntHeap>(100);
124
125    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
126    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
127    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
128  }
129  {
130    std::cerr << "Checking Radix Heap" << std::endl;
131
132    typedef RadixHeap<Item, ItemIntMap> IntHeap;
133    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
134    heapSortTest<IntHeap>(100);
135    heapIncreaseTest<IntHeap>(100);
136
137    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
138    checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
139    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
140  }
141
142  std::cout << __FILE__ ": All tests passed.\n";
143
144  return 0;
145}
Note: See TracBrowser for help on using the repository browser.