Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/test/heap_test.cc
changeset 1214 39993ada11c7
parent 1187 04e5825000c5
child 1215 81b4731f8a6b
equal deleted inserted replaced
0:6cee3fc31101 1:81c61343a592 
     4 #include <fstream>
 
     4 #include <fstream>
 
     5 #include <vector>
 
     5 #include <vector>
 
     6 
     6 
     7 #include <lemon/concept_check.h>
 
     7 #include <lemon/concept_check.h>
 
     8 
     8 
       
     9 #include <lemon/smart_graph.h>
 
       
    10 
       
    11 #include <lemon/graph_reader.h>
 
       
    12 
     9 #include <lemon/bin_heap.h>
 
    13 #include <lemon/bin_heap.h>
 
    10 #include <lemon/fib_heap.h>
 
    14 #include <lemon/fib_heap.h>
 
    11 #include <lemon/radix_heap.h>
 
    15 #include <lemon/radix_heap.h>
 
    12 
    16 
    13 #include <lemon/dimacs.h>
 
    17 #include "test_tools.h"
 
    14 
    18 
    15 #include "test_tools.h"
 
       
    16 #include "heap_test.h"
 
    19 #include "heap_test.h"
 
    17 #include "map_test.h"
 
       
    18 
    20 
    19 
    21 
    20 using namespace lemon;
 
    22 using namespace lemon;
 
    21 
    23 
    22 template <typename Item, typename Prio, typename ItemIntMap>
 
    24 template <typename Item, typename Prio, typename ItemIntMap>
 
    29     
    31     
    30     void constraints() {
 
    32     void constraints() {
 
    31       Item item;
 
    33       Item item;
 
    32       Prio prio;
 
    34       Prio prio;
 
    33 
    35 
       
    36       ignore_unused_variable_warning(item);
 
       
    37       ignore_unused_variable_warning(prio);
 
       
    38 
    34       typedef typename _Heap::state_enum state_enum;
 
    39       typedef typename _Heap::state_enum state_enum;
 
    35       state_enum state;
 
    40       state_enum state;
 
       
    41 
       
    42       ignore_unused_variable_warning(state);
 
    36       
    43       
    37       _Heap heap1 = _Heap(map);
 
    44       _Heap heap1 = _Heap(map);
 
       
    45 
       
    46       ignore_unused_variable_warning(heap1);
 
    38       
    47       
    39       heap.push(item, prio);
 
    48       heap.push(item, prio);
 
    40 
    49 
    41       prio = heap.prio();
 
    50       prio = heap.prio();
 
    42       item = heap.top();
 
    51       item = heap.top();
 
    78 
    87 
    79   Graph graph;
 
    88   Graph graph;
 
    80   LengthMap length(graph);
 
    89   LengthMap length(graph);
 
    81   Node start;
 
    90   Node start;
 
    82 
    91 
    83   std::ifstream input("preflow_graph.dim");
 
    92   /// \todo create own test graph
 
    84   readDimacs(input, graph, length, start);  
    93   std::ifstream input("dijkstra_test.lemon");
 
       
    94   readGraph(input, graph, length, start);  
    85  
    95  
    86   {
 
    96   {
 
    87     std::cerr << "Checking Bin Heap" << std::endl;
 
    97     std::cerr << "Checking Bin Heap" << std::endl;
 
    88 
    98 
    89     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
 
    99     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
 
    90     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
 
   100     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
 
    91     heapSortTest<IntHeap>(20);
 
   101     heapSortTest<IntHeap>(100);
 
       
   102     heapIncreaseTest<IntHeap>(100);
 
    92     
   103     
    93     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
 
   104     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
 
    94     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
 
   105     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
 
    95     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
 
   106     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
 
    96   }
 
   107   }
 
    97   {
 
   108   {
 
    98     std::cerr << "Checking Fib Heap" << std::endl;
 
   109     std::cerr << "Checking Fib Heap" << std::endl;
 
    99 
   110 
   100     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
 
   111     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
 
   101     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
 
   112     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
 
   102     heapSortTest<IntHeap>(20);
 
   113     heapSortTest<IntHeap>(100);
 
       
   114     heapIncreaseTest<IntHeap>(100);
 
   103 
   115 
   104     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
 
   116     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
 
   105     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
 
   117     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
 
   106     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
 
   118     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
 
   107   }
 
   119   }
 
   108   {
 
   120   {
 
   109     std::cerr << "Checking Radix Heap" << std::endl;
 
   121     std::cerr << "Checking Radix Heap" << std::endl;
 
   110 
   122 
   111     typedef RadixHeap<Item, ItemIntMap> IntHeap;
 
   123     typedef RadixHeap<Item, ItemIntMap> IntHeap;
 
   112     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
 
   124     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
 
   113     heapSortTest<IntHeap>(20);
 
   125     heapSortTest<IntHeap>(100);
 
       
   126     heapIncreaseTest<IntHeap>(100);
 
   114 
   127 
   115     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
 
   128     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
 
   116     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
 
   129     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
 
   117     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
 
   130     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
 
   118   }
 
   131   }
lemon-0.x