COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/heap_test.cc @ 1206:9c398137c2cb

Last change on this file since 1206:9c398137c2cb was 1206:9c398137c2cb, checked in by Balazs Dezso, 16 years ago

Increase test
Changing test graph

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