COIN-OR::LEMON - Graph Library

Changeset 1206:9c398137c2cb in lemon-0.x


Ignore:
Timestamp:
03/09/05 15:10:21 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1625
Message:

Increase test
Changing test graph

Location:
src/test
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/test/Makefile.am

    r1094 r1206  
    88        sym_graph_test.h \
    99        map_test.h \
    10         graph_utils_test.h
     10        graph_utils_test.h \
     11        heap_test.h
    1112
    1213check_PROGRAMS = \
     
    2930        unionfind_test \
    3031        undir_graph_test \
    31         xy_test
     32        xy_test \
     33        heap_test
    3234
    3335TESTS = $(check_PROGRAMS)
     
    5355xy_test_SOURCES = xy_test.cc
    5456undir_graph_test_SOURCES = undir_graph_test.cc
    55 
     57heap_test_SOURCES = heap_test.cc
  • src/test/heap_test.cc

    r1187 r1206  
    77#include <lemon/concept_check.h>
    88
     9#include <lemon/smart_graph.h>
     10
     11#include <lemon/graph_reader.h>
     12
    913#include <lemon/bin_heap.h>
    1014#include <lemon/fib_heap.h>
    1115#include <lemon/radix_heap.h>
    1216
    13 #include <lemon/dimacs.h>
     17#include "test_tools.h"
    1418
    15 #include "test_tools.h"
    1619#include "heap_test.h"
    17 #include "map_test.h"
    1820
    1921
     
    3234      Prio prio;
    3335
     36      ignore_unused_variable_warning(item);
     37      ignore_unused_variable_warning(prio);
     38
    3439      typedef typename _Heap::state_enum state_enum;
    3540      state_enum state;
     41
     42      ignore_unused_variable_warning(state);
    3643     
    3744      _Heap heap1 = _Heap(map);
     45
     46      ignore_unused_variable_warning(heap1);
    3847     
    3948      heap.push(item, prio);
     
    8190  Node start;
    8291
    83   std::ifstream input("preflow_graph.dim");
    84   readDimacs(input, graph, length, start); 
     92  /// \todo create own test graph
     93  std::ifstream input("dijkstra_test.lemon");
     94  readGraph(input, graph, length, start); 
    8595 
    8696  {
     
    8999    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
    90100    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
    91     heapSortTest<IntHeap>(20);
     101    heapSortTest<IntHeap>(100);
     102    heapIncreaseTest<IntHeap>(100);
    92103   
    93104    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
     
    100111    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
    101112    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
    102     heapSortTest<IntHeap>(20);
     113    heapSortTest<IntHeap>(100);
     114    heapIncreaseTest<IntHeap>(100);
    103115
    104116    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
     
    111123    typedef RadixHeap<Item, ItemIntMap> IntHeap;
    112124    checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
    113     heapSortTest<IntHeap>(20);
     125    heapSortTest<IntHeap>(100);
     126    heapIncreaseTest<IntHeap>(100);
    114127
    115128    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
  • src/test/heap_test.h

    r1187 r1206  
    11// -+- c++ -+-
     2
    23#include <vector>
    34#include <algorithm>
    4 
    5 #include <lemon/bin_heap.h>
    6 #include <lemon/fib_heap.h>
    7 #include <lemon/radix_heap.h>
    85
    96#include <lemon/dijkstra.h>
     
    4340}
    4441
     42template <typename _Heap>
     43void heapIncreaseTest(int n) {
     44  typedef _Heap Heap;
     45  IntIntMap map(n, -1);
     46
     47  Heap heap(map);
     48 
     49  std::vector<int> v(n);
     50
     51  for (int i = 0; i < n; ++i) {
     52    v[i] = rand() % 1000;
     53    heap.push(i, v[i]);
     54  }
     55  for (int i = 0; i < n; ++i) {
     56    v[i] += rand() % 1000;
     57    heap.increase(i, v[i]);
     58  }
     59  std::sort(v.begin(), v.end());
     60  for (int i = 0; i < n; ++i) {
     61    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
     62    heap.pop();
     63  }
     64}
     65
     66
     67
    4568template <typename _Traits, typename _Heap>
    4669struct DefHeapTraits : public _Traits {
     
    77100
    78101  for(NodeIt v(graph); v!=INVALID; ++v) {
    79     if ( dijkstra.reached(v) ) {
     102    if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) {
    80103      Edge e=dijkstra.pred(v);
    81104      Node u=graph.source(e);
Note: See TracChangeset for help on using the changeset viewer.