cycle_ratio_example.cpp 2.9 KB

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