COIN-OR::LEMON - Graph Library

source: lemon/test/heap_test.cc @ 119:82a2639a05bb

Last change on this file since 119:82a2639a05bb was 100:4f754b4cf82b, checked in by Alpar Juttner <alpar@…>, 17 years ago

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

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
45
46int main() {
47
48  typedef int Item;
49  typedef int Prio;
50  typedef IntIntMap ItemIntMap;
51
52  typedef ListDigraph Digraph;
53
54  typedef Digraph::Arc Arc;
55  typedef Digraph::Node Node;
56  typedef Digraph::ArcIt ArcIt;
57  typedef Digraph::NodeIt NodeIt;
58  typedef Digraph::ArcMap<int> LengthMap;
59
60  Digraph digraph;
61  LengthMap length(digraph);
62  Node start;
63
64  /// \todo create own test digraph
65
66  std::string f_name;
67  if( getenv("srcdir") )
68    f_name = std::string(getenv("srcdir"));
69  else f_name = ".";
70  f_name += "/test/dijkstra_test.lgf";
71 
72  std::ifstream input(f_name.c_str());
73  check(input, "Input file '" << f_name << "' not found.");
74  DigraphReader<Digraph>(input, digraph).
75    readArcMap("capacity", length).
76    readNode("source", start).
77    run(); 
78 
79  {
80    std::cerr << "Checking Bin Heap" << std::endl;
81
82    typedef BinHeap<Prio, ItemIntMap> IntHeap;
83    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
84    heapSortTest<IntHeap>(100);
85    heapIncreaseTest<IntHeap>(100);
86   
87    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
88    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
89    Timer timer;
90    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
91    std::cout << timer << std::endl;
92  }
93  {
94    std::cerr << "Checking Fib Heap" << std::endl;
95
96    typedef FibHeap<Prio, ItemIntMap> IntHeap;
97    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
98    heapSortTest<IntHeap>(100);
99    heapIncreaseTest<IntHeap>(100);
100
101    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
102    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
103    Timer timer;
104    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
105    std::cout << timer << std::endl;
106  }
107  {
108    std::cerr << "Checking Radix Heap" << std::endl;
109
110    typedef RadixHeap<ItemIntMap> IntHeap;
111    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
112    heapSortTest<IntHeap>(100);
113    heapIncreaseTest<IntHeap>(100);
114
115    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
116    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
117    Timer timer;
118    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
119    std::cout << timer << std::endl;
120  }
121
122  {
123    std::cerr << "Checking Bucket Heap" << std::endl;
124
125    typedef BucketHeap<ItemIntMap> IntHeap;
126    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
127    heapSortTest<IntHeap>(100);
128    heapIncreaseTest<IntHeap>(100);
129
130    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
131    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
132    Timer timer;
133    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
134    std::cout << timer << std::endl;
135  }
136
137  std::cout << __FILE__ ": All tests passed.\n";
138
139  return 0;
140}
Note: See TracBrowser for help on using the repository browser.