COIN-OR::LEMON - Graph Library

Changeset 203:215bfc30b14f in lemon-1.2


Ignore:
Timestamp:
07/11/08 15:01:49 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Cleaning of heap test and bug fix in heap concept check (ticket #100)

  • The dijkstra heap test's digraph is inlined into the source file
  • The random sequences are fixed
  • The content of the header is moved to the source file
  • Only the binary heap is checked
Files:
1 deleted
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/heap.h

    r113 r203  
    182182          Item item;
    183183          Prio prio;
    184           State state;
    185184          item=Item();
    186185          prio=Prio();
    187186          ignore_unused_variable_warning(item);
    188187          ignore_unused_variable_warning(prio);
    189           ignore_unused_variable_warning(state);
    190188
    191189          OwnItem own_item;
     
    204202         
    205203          int s = heap.size();
     204          ignore_unused_variable_warning(s);
    206205          bool e = heap.empty();
     206          ignore_unused_variable_warning(e);
    207207
    208208          prio = heap.prio();
     
    228228          heap.clear();
    229229
    230           state = heap.state(item);
    231           heap.state(item, state);
    232           state = heap.state(own_item);
     230          own_state = heap.state(own_item);
    233231          heap.state(own_item, own_state);
    234232
    235           state = _Heap::PRE_HEAP;
    236           state = _Heap::IN_HEAP;
    237           state = _Heap::POST_HEAP;
    238233          own_state = _Heap::PRE_HEAP;
    239234          own_state = _Heap::IN_HEAP;
  • test/CMakeLists.txt

    r200 r203  
    1414  graph_test
    1515  graph_utils_test
     16  heap_test
    1617  kruskal_test
    1718  maps_test
  • test/Makefile.am

    r200 r203  
    44noinst_HEADERS += \
    55        test/graph_test.h \
    6         test/heap_test.h \
    76        test/graph_maps_test.h \
    87        test/test_tools.h
     
    1918        test/graph_test \
    2019        test/graph_utils_test \
     20        test/heap_test \
    2121        test/kruskal_test \
    2222        test/maps_test \
     
    4141test_graph_test_SOURCES = test/graph_test.cc
    4242test_graph_utils_test_SOURCES = test/graph_utils_test.cc
    43 # test_heap_test_SOURCES = test/heap_test.cc
     43test_heap_test_SOURCES = test/heap_test.cc
    4444test_kruskal_test_SOURCES = test/kruskal_test.cc
    4545test_maps_test_SOURCES = test/maps_test.cc
  • test/heap_test.cc

    r171 r203  
    2525#include <lemon/concepts/heap.h>
    2626
    27 #include <lemon/list_graph.h>
     27#include <lemon/smart_graph.h>
    2828
    29 #include <lemon/digraph_reader.h>
     29#include <lemon/lgf_reader.h>
     30#include <lemon/dijkstra.h>
     31#include <lemon/maps.h>
    3032
    3133#include <lemon/bin_heap.h>
    32 #include <lemon/fib_heap.h>
    33 #include <lemon/radix_heap.h>
    34 #include <lemon/bucket_heap.h>
    3534
    3635#include "test_tools.h"
    3736
    38 #include "heap_test.h"
    39 
    40 #include <lemon/time_measure.h>
    41 
    4237using namespace lemon;
    4338using 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 DefStandardHeap<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}
    44158
    45159int main() {
     
    47161  typedef int Item;
    48162  typedef int Prio;
    49   typedef IntIntMap ItemIntMap;
     163  typedef RangeMap<int> ItemIntMap;
     164 
     165  Digraph digraph;
     166  IntArcMap length(digraph);
     167  Node source;
    50168
    51   typedef ListDigraph Digraph;
    52 
    53   typedef Digraph::Arc Arc;
    54   typedef Digraph::Node Node;
    55   typedef Digraph::ArcIt ArcIt;
    56   typedef Digraph::NodeIt NodeIt;
    57   typedef Digraph::ArcMap<int> LengthMap;
    58 
    59   Digraph digraph;
    60   LengthMap length(digraph);
    61   Node start;
    62 
    63   /// \todo create own test digraph
    64 
    65   std::string f_name;
    66   if( getenv("srcdir") )
    67     f_name = std::string(getenv("srcdir"));
    68   else f_name = ".";
    69   f_name += "/test/dijkstra_test.lgf";
    70  
    71   std::ifstream input(f_name.c_str());
    72   check(input, "Input file '" << f_name << "' not found.");
    73   DigraphReader<Digraph>(input, digraph).
    74     readArcMap("capacity", length).
    75     readNode("source", start).
     169  std::istringstream input(test_lgf);
     170  digraphReader(input, digraph).
     171    arcMap("capacity", length).
     172    node("source", source).
    76173    run(); 
    77174 
    78175  {
    79     std::cout << "Checking Bin Heap" << std::endl;
    80 
    81176    typedef BinHeap<Prio, ItemIntMap> IntHeap;
    82177    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    83     heapSortTest<IntHeap>(100);
    84     heapIncreaseTest<IntHeap>(100);
     178    heapSortTest<IntHeap>();
     179    heapIncreaseTest<IntHeap>();
    85180   
    86     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
    87     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    88     Timer timer;
    89     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    90     std::cout << timer << std::endl;
    91   }
    92   {
    93     std::cout << "Checking Fib Heap" << std::endl;
    94 
    95     typedef FibHeap<Prio, ItemIntMap> IntHeap;
    96     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    97     heapSortTest<IntHeap>(100);
    98     heapIncreaseTest<IntHeap>(100);
    99 
    100     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
    101     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    102     Timer timer;
    103     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    104     std::cout << timer << std::endl;
    105   }
    106   {
    107     std::cout << "Checking Radix Heap" << std::endl;
    108 
    109     typedef RadixHeap<ItemIntMap> IntHeap;
    110     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    111     heapSortTest<IntHeap>(100);
    112     heapIncreaseTest<IntHeap>(100);
    113 
    114     typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
    115     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    116     Timer timer;
    117     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    118     std::cout << timer << std::endl;
    119   }
    120 
    121   {
    122     std::cout << "Checking Bucket Heap" << std::endl;
    123 
    124     typedef BucketHeap<ItemIntMap> IntHeap;
    125     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    126     heapSortTest<IntHeap>(100);
    127     heapIncreaseTest<IntHeap>(100);
    128 
    129     typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
    130     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    131     Timer timer;
    132     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    133     std::cout << timer << std::endl;
     181    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
     182    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     183    dijkstraHeapTest<NodeHeap>(digraph, length, source);
    134184  }
    135185
Note: See TracChangeset for help on using the changeset viewer.