COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/heap_test.cc @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 3.7 KB
RevLine 
[1956]1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2553]5 * Copyright (C) 2003-2008
[1956]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 */
[1187]18
19#include <iostream>
20#include <fstream>
[1215]21#include <string>
[1187]22#include <vector>
23
24#include <lemon/concept_check.h>
[2260]25#include <lemon/concepts/heap.h>
[1187]26
[1206]27#include <lemon/smart_graph.h>
28
29#include <lemon/graph_reader.h>
30
[1187]31#include <lemon/bin_heap.h>
32#include <lemon/fib_heap.h>
33#include <lemon/radix_heap.h>
[2038]34#include <lemon/bucket_heap.h>
[1187]35
[1206]36#include "test_tools.h"
[1187]37
38#include "heap_test.h"
39
[1728]40#include <lemon/time_measure.h>
[1187]41
42using namespace lemon;
[2260]43using namespace lemon::concepts;
[1187]44
45
46int main() {
47
48  typedef int Item;
49  typedef int Prio;
50  typedef IntIntMap ItemIntMap;
51
52  typedef ListGraph Graph;
53
54  typedef Graph::Edge Edge;
55  typedef Graph::Node Node;
56  typedef Graph::EdgeIt EdgeIt;
57  typedef Graph::NodeIt NodeIt;
58  typedef Graph::EdgeMap<int> LengthMap;
59
60  Graph graph;
61  LengthMap length(graph);
62  Node start;
63
[1206]64  /// \todo create own test graph
[1215]65
66  std::string f_name;
67  if( getenv("srcdir") )
68    f_name = std::string(getenv("srcdir"));
69  else f_name = ".";
[2108]70  f_name += "/test/dijkstra_test.lgf";
[1215]71 
72  std::ifstream input(f_name.c_str());
73  check(input, "Input file '" << f_name << "' not found.");
[1744]74  GraphReader<Graph>(input, graph).
[1845]75    readEdgeMap("capacity", length).
[1744]76    readNode("source", start).
77    run(); 
[1187]78 
79  {
80    std::cerr << "Checking Bin Heap" << std::endl;
81
[2269]82    typedef BinHeap<Prio, ItemIntMap> IntHeap;
83    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
[1206]84    heapSortTest<IntHeap>(100);
85    heapIncreaseTest<IntHeap>(100);
[1187]86   
[2269]87    typedef FibHeap<Prio, Graph::NodeMap<int> > NodeHeap;
88    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
[1728]89    Timer timer;
[1187]90    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
[1728]91    std::cout << timer << std::endl;
[1187]92  }
93  {
94    std::cerr << "Checking Fib Heap" << std::endl;
95
[2269]96    typedef FibHeap<Prio, ItemIntMap> IntHeap;
97    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
[1206]98    heapSortTest<IntHeap>(100);
99    heapIncreaseTest<IntHeap>(100);
[1187]100
[2269]101    typedef FibHeap<Prio, Graph::NodeMap<int> > NodeHeap;
102    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
[1728]103    Timer timer;
[1187]104    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
[1728]105    std::cout << timer << std::endl;
[1187]106  }
107  {
108    std::cerr << "Checking Radix Heap" << std::endl;
109
[2269]110    typedef RadixHeap<ItemIntMap> IntHeap;
111    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
[1206]112    heapSortTest<IntHeap>(100);
113    heapIncreaseTest<IntHeap>(100);
[1187]114
[2269]115    typedef RadixHeap<Graph::NodeMap<int> > NodeHeap;
116    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
[1728]117    Timer timer;
[1187]118    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
[1728]119    std::cout << timer << std::endl;
120  }
121
122  {
[2038]123    std::cerr << "Checking Bucket Heap" << std::endl;
[1728]124
[2269]125    typedef BucketHeap<ItemIntMap> IntHeap;
126    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
[1728]127    heapSortTest<IntHeap>(100);
128    heapIncreaseTest<IntHeap>(100);
129
[2269]130    typedef BucketHeap<Graph::NodeMap<int> > NodeHeap;
131    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
[1728]132    Timer timer;
133    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
134    std::cout << timer << std::endl;
[1187]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.