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

   1 // Copyright (C) 2006-2009 Dmitry Bufistov and Andrey Parfenov
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <cassert>
   8 #include <ctime>
   9 #include <boost/random/mersenne_twister.hpp>
  10 #include <boost/random/uniform_real.hpp>
  11 #include <boost/graph/adjacency_list.hpp>
  12 #include <boost/graph/random.hpp>
  13 #include <boost/graph/howard_cycle_ratio.hpp>
  14
  15 /**
  16  * @author Dmitry Bufistov
  17  * @author Andrey Parfenov
  18  */
  19
  20 using namespace boost;
  21 typedef adjacency_list<
  22     listS, listS, directedS,
  23     property<vertex_index_t, int>,
  24     property<
  25         edge_weight_t, double, property<edge_weight2_t, double>
  26     >
  27 > grap_real_t;
  28
  29 template <typename TG>
  30 void gen_rand_graph(TG &g, size_t nV, size_t nE)
  31 {
  32     g.clear();
  33     mt19937 rng;
  34     rng.seed(uint32_t(time(0)));
  35     boost::generate_random_graph(g, nV, nE, rng, true, true);
  36     boost::uniform_real<> ur(-1,10);
  37     boost::variate_generator<boost::mt19937&, boost::uniform_real<> >   ew1rg(rng, ur);
  38     randomize_property<edge_weight_t>(g, ew1rg);
  39     boost::uniform_int<size_t> uint(1,5);
  40     boost::variate_generator<boost::mt19937&, boost::uniform_int<size_t> >      ew2rg(rng, uint);
  41     randomize_property<edge_weight2_t>(g, ew2rg);
  42 }
  43
  44 int main(int argc, char* argv[])
  45 {
  46     using std::cout;
  47     using std::endl;
  48     const double epsilon = 0.0000001;
  49     double min_cr, max_cr; ///Minimum and maximum cycle ratio
  50     typedef std::vector<graph_traits<grap_real_t>::edge_descriptor> ccReal_t;
  51     ccReal_t cc; ///critical cycle
  52
  53     grap_real_t tgr;
  54     property_map<grap_real_t, vertex_index_t>::type vim = get(vertex_index, tgr);
  55     property_map<grap_real_t, edge_weight_t>::type ew1 = get(edge_weight, tgr);
  56     property_map<grap_real_t, edge_weight2_t>::type ew2 = get(edge_weight2, tgr);
  57
  58     gen_rand_graph(tgr, 1000, 30000);
  59     cout << "Vertices number: " << num_vertices(tgr) << endl;
  60     cout << "Edges number: " << num_edges(tgr) << endl;
  61     int i = 0;
  62     graph_traits<grap_real_t>::vertex_iterator vi, vi_end;
  63     for (boost::tie(vi, vi_end) = vertices(tgr); vi != vi_end; vi++) {
  64         vim[*vi] = i++; ///Initialize vertex index property
  65     }
  66     max_cr = maximum_cycle_ratio(tgr, vim, ew1, ew2);
  67     cout << "Maximum cycle ratio is " << max_cr << endl;
  68     min_cr = minimum_cycle_ratio(tgr, vim, ew1, ew2, &cc);
  69     cout << "Minimum cycle ratio is " << min_cr << endl;
  70     std::pair<double, double> cr(.0,.0);
  71     cout << "Critical cycle:\n";
  72     for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
  73     {
  74         cr.first += ew1[*itr];
  75         cr.second += ew2[*itr];
  76         std::cout << "(" << vim[source(*itr, tgr)] << "," <<
  77             vim[target(*itr, tgr)] << ") ";
  78     }
  79     cout << endl;
  80     assert(std::abs(cr.first / cr.second - min_cr) < epsilon * 2);
  81     return EXIT_SUCCESS;
  82 }
  83