ceph/src/boost/libs/graph/example/fibonacci_heap.cpp

   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
  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 }