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