COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/heap_test.cc @ 184:716b220697a0

Last change on this file since 184:716b220697a0 was 171:02f4d5d9bfd7, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Improve and redesign test programs + unify their output (ticket #25)

  • Move graph related utilities form test_tools.h to graph_test.h.
  • Move the contents of graph_utils_test.h to graph_utils_test.cc.
  • Rename map_test.h -> graph_maps_test.h.
  • Rename digraph_test.h -> graph_test.h.
  • Many improvements in the following files:
    • digraph_test.cc
    • graph_test.cc
    • graph_test.h
    • graph_maps_test.h
    • graph_utils_test.cc
    • bfs_test.cc
    • dfs_test.cc
    • counter_test.cc
  • Test programs print messages only if it really seems necessary.
  • Remove \file commands form .cc test files.
File size: 3.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <iostream>
20#include <fstream>
21#include <string>
22#include <vector>
23
24#include <lemon/concept_check.h>
25#include <lemon/concepts/heap.h>
26
27#include <lemon/list_graph.h>
28
29#include <lemon/digraph_reader.h>
30
31#include <lemon/bin_heap.h>
32#include <lemon/fib_heap.h>
33#include <lemon/radix_heap.h>
34#include <lemon/bucket_heap.h>
35
36#include "test_tools.h"
37
38#include "heap_test.h"
39
40#include <lemon/time_measure.h>
41
42using namespace lemon;
43using namespace lemon::concepts;
44
45int main() {
46
47  typedef int Item;
48  typedef int Prio;
49  typedef IntIntMap ItemIntMap;
50
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).
76    run(); 
77 
78  {
79    std::cout << "Checking Bin Heap" << std::endl;
80
81    typedef BinHeap<Prio, ItemIntMap> IntHeap;
82    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
83    heapSortTest<IntHeap>(100);
84    heapIncreaseTest<IntHeap>(100);
85   
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;
134  }
135
136  return 0;
137}
Note: See TracBrowser for help on using the repository browser.