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
gen_rand_graph(TG & g,size_t nV,size_t nE)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
main(int argc,char * argv[])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 }
86