Unionfind changes induced some bugs here. Also some augmentations made.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
24 #include <lemon/concept_check.h>
25 #include <lemon/concept/heap.h>
27 #include <lemon/smart_graph.h>
29 #include <lemon/graph_reader.h>
31 #include <lemon/bin_heap.h>
32 #include <lemon/fib_heap.h>
33 #include <lemon/radix_heap.h>
34 #include <lemon/linear_heap.h>
36 #include "test_tools.h"
38 #include "heap_test.h"
40 #include <lemon/time_measure.h>
42 using namespace lemon;
43 using namespace lemon::concept;
50 typedef IntIntMap ItemIntMap;
52 typedef ListGraph Graph;
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;
61 LengthMap length(graph);
64 /// \todo create own test graph
67 if( getenv("srcdir") )
68 f_name = std::string(getenv("srcdir"));
70 f_name += "/dijkstra_test.lgf";
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).
80 std::cerr << "Checking Bin Heap" << std::endl;
82 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
83 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
84 heapSortTest<IntHeap>(100);
85 heapIncreaseTest<IntHeap>(100);
87 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
88 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
90 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
91 std::cout << timer << std::endl;
94 std::cerr << "Checking Fib Heap" << std::endl;
96 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
97 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
98 heapSortTest<IntHeap>(100);
99 heapIncreaseTest<IntHeap>(100);
101 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
102 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
104 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
105 std::cout << timer << std::endl;
108 std::cerr << "Checking Radix Heap" << std::endl;
110 typedef RadixHeap<Item, ItemIntMap> IntHeap;
111 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
112 heapSortTest<IntHeap>(100);
113 heapIncreaseTest<IntHeap>(100);
115 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
116 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
118 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
119 std::cout << timer << std::endl;
123 std::cerr << "Checking Linear Heap" << std::endl;
125 typedef LinearHeap<Item, ItemIntMap> IntHeap;
126 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
127 heapSortTest<IntHeap>(100);
128 heapIncreaseTest<IntHeap>(100);
130 typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
131 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
133 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
134 std::cout << timer << std::endl;
137 std::cout << __FILE__ ": All tests passed.\n";