1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 #include <boost/config.hpp>
10 #include <iostream>
11 #include <vector>
12 #include <boost/graph/random.hpp>
13 #ifndef BOOST_NO_CXX11_HDR_RANDOM
14 #include <random>
15 namespace random_ns = std;
16 #else
17 #include <boost/random/mersenne_twister.hpp>
18 namespace random_ns = boost;
19 #endif
20 #include <algorithm>
21 #include <boost/pending/fibonacci_heap.hpp>
22 #include <boost/graph/graph_utility.hpp>
23 #include <boost/pending/indirect_cmp.hpp>
24
25 using namespace boost;
26
main()27 int main()
28 {
29 typedef indirect_cmp< float*, std::less< float > > ICmp;
30 int i;
31 random_ns::mt19937 gen;
32 for (int N = 2; N < 200; ++N)
33 {
34 uniform_int<> distrib(0, N - 1);
35 boost::variate_generator< random_ns::mt19937&, uniform_int<> > rand_gen(
36 gen, distrib);
37 for (int t = 0; t < 10; ++t)
38 {
39 std::vector< float > v, w(N);
40
41 ICmp cmp(&w[0], std::less< float >());
42 fibonacci_heap< int, ICmp > Q(N, cmp);
43
44 for (int c = 0; c < w.size(); ++c)
45 w[c] = c;
46 #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
47 std::random_shuffle(w.begin(), w.end());
48 #else
49 std::shuffle(w.begin(), w.end(), gen);
50 #endif
51
52 for (i = 0; i < N; ++i)
53 Q.push(i);
54
55 for (i = 0; i < N; ++i)
56 {
57 int u = rand_gen();
58 float r = rand_gen();
59 r /= 2.0;
60 w[u] = w[u] - r;
61 Q.update(u);
62 }
63
64 for (i = 0; i < N; ++i)
65 {
66 v.push_back(w[Q.top()]);
67 Q.pop();
68 }
69 std::sort(w.begin(), w.end());
70
71 if (!std::equal(v.begin(), v.end(), w.begin()))
72 {
73 std::cout << std::endl << "heap sorted: ";
74 std::copy(v.begin(), v.end(),
75 std::ostream_iterator< float >(std::cout, " "));
76 std::cout << std::endl << "correct: ";
77 std::copy(w.begin(), w.end(),
78 std::ostream_iterator< float >(std::cout, " "));
79 std::cout << std::endl;
80 return -1;
81 }
82 }
83 }
84 std::cout << "fibonacci heap passed test" << std::endl;
85 return 0;
86 }
87