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< listS, listS, directedS,
  22     property< vertex_index_t, int >,
  23     property< edge_weight_t, double, property< edge_weight2_t, double > > >
  24     grap_real_t;
  25
  26 template < typename TG > void gen_rand_graph(TG& g, size_t nV, size_t nE)
  27 {
  28     g.clear();
  29     mt19937 rng;
  30     rng.seed(0 /*uint32_t(time(0))*/);  // Reproducable seed.
  31     boost::generate_random_graph(g, nV, nE, rng, true, true);
  32     boost::uniform_real<> ur(-1, 10);
  33     boost::variate_generator< boost::mt19937&, boost::uniform_real<> > ew1rg(
  34         rng, ur);
  35     randomize_property< edge_weight_t >(g, ew1rg);
  36     boost::uniform_int< size_t > uint(1, 5);
  37     boost::variate_generator< boost::mt19937&, boost::uniform_int< size_t > >
  38         ew2rg(rng, uint);
  39     randomize_property< edge_weight2_t >(g, ew2rg);
  40 }
  41
  42 int main(int argc, char* argv[])
  43 {
  44     using std::cout;
  45     using std::endl;
  46     const double epsilon = 0.0000001;
  47     double min_cr, max_cr; /// Minimum and maximum cycle ratio
  48     typedef std::vector< graph_traits< grap_real_t >::edge_descriptor >
  49         ccReal_t;
  50     ccReal_t cc; /// critical cycle
  51
  52     grap_real_t tgr;
  53     property_map< grap_real_t, vertex_index_t >::type vim
  54         = get(vertex_index, tgr);
  55     property_map< grap_real_t, edge_weight_t >::type ew1
  56         = get(edge_weight, tgr);
  57     property_map< grap_real_t, edge_weight2_t >::type ew2
  58         = get(edge_weight2, tgr);
  59
  60     gen_rand_graph(tgr, 1000, 30000);
  61     cout << "Vertices number: " << num_vertices(tgr) << endl;
  62     cout << "Edges number: " << num_edges(tgr) << endl;
  63     int i = 0;
  64     graph_traits< grap_real_t >::vertex_iterator vi, vi_end;
  65     for (boost::tie(vi, vi_end) = vertices(tgr); vi != vi_end; vi++)
  66     {
  67         vim[*vi] = i++; /// Initialize vertex index property
  68     }
  69     max_cr = maximum_cycle_ratio(tgr, vim, ew1, ew2);
  70     cout << "Maximum cycle ratio is " << max_cr << endl;
  71     min_cr = minimum_cycle_ratio(tgr, vim, ew1, ew2, &cc);
  72     cout << "Minimum cycle ratio is " << min_cr << endl;
  73     std::pair< double, double > cr(.0, .0);
  74     cout << "Critical cycle:\n";
  75     for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
  76     {
  77         cr.first += ew1[*itr];
  78         cr.second += ew2[*itr];
  79         std::cout << "(" << vim[source(*itr, tgr)] << ","
  80                   << vim[target(*itr, tgr)] << ") ";
  81     }
  82     cout << endl;
  83     assert(std::abs(cr.first / cr.second - min_cr) < epsilon * 2);
  84     return EXIT_SUCCESS;
  85 }