COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/heap_test.cc @ 2125:2f2cbe4e78a8

Last change on this file since 2125:2f2cbe4e78a8 was 2108:f2c532541730, checked in by Akos Ladanyi, 18 years ago

Single makefile.

File size: 3.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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/concept/heap.h>
26
27#include <lemon/smart_graph.h>
28
29#include <lemon/graph_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::concept;
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
64  /// \todo create own test graph
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  GraphReader<Graph>(input, graph).
75    readEdgeMap("capacity", length).
76    readNode("source", start).
77    run(); 
78 
79  {
80    std::cerr << "Checking Bin Heap" << std::endl;
81
82    typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
83    checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
84    heapSortTest<IntHeap>(100);
85    heapIncreaseTest<IntHeap>(100);
86   
87    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
88    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
89    Timer timer;
90    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
91    std::cout << timer << std::endl;
92  }
93  {
94    std::cerr << "Checking Fib Heap" << std::endl;
95
96    typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
97    checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
98    heapSortTest<IntHeap>(100);
99    heapIncreaseTest<IntHeap>(100);
100
101    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
102    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
103    Timer timer;
104    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
105    std::cout << timer << std::endl;
106  }
107  {
108    std::cerr << "Checking Radix Heap" << std::endl;
109
110    typedef RadixHeap<Item, ItemIntMap> IntHeap;
111    checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
112    heapSortTest<IntHeap>(100);
113    heapIncreaseTest<IntHeap>(100);
114
115    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
116    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
117    Timer timer;
118    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
119    std::cout << timer << std::endl;
120  }
121
122  {
123    std::cerr << "Checking Bucket Heap" << std::endl;
124
125    typedef BucketHeap<Item, ItemIntMap> IntHeap;
126    checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
127    heapSortTest<IntHeap>(100);
128    heapIncreaseTest<IntHeap>(100);
129
130    typedef BucketHeap<Node, Graph::NodeMap<int> > NodeHeap;
131    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
132    Timer timer;
133    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, 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.