]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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; | |
92f5a8d4 | 80 | assert(std::abs(cr.first / cr.second - min_cr) < epsilon * 2); |
7c673cae FG |
81 | return EXIT_SUCCESS; |
82 | } | |
83 |