GeezerVison is showing github.com — boost_graph/example/cycle_ratio_example.cpp at develop · stdgraph/boost_graph

Expand file tree

cycle_ratio_example.cpp

Copy path

More file actions

Latest commit

History

81 lines (73 loc) · 2.77 KB

cycle_ratio_example.cpp

Copy path

File metadata and controls

81 lines (73 loc) · 2.77 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

// 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;

using grap_real_t

= adjacency_list< listS, listS, directedS, property< vertex_index_t, int >,

property< edge_weight_t, double, property< edge_weight2_t, double > > >;

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

using ccReal_t

= std::vector< graph_traits< grap_real_t >::edge_descriptor >;

ccReal_t cc; /// critical cycle

grap_real_t tgr;

auto vim = get(vertex_index, tgr);

auto ew1 = get(edge_weight, tgr);

auto 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 (auto const & edge : cc)

{

cr.first += ew1[edge];

cr.second += ew2[edge];

std::cout << "(" << vim[source(edge, tgr)] << ","

<< vim[target(edge, tgr)] << ") ";

}

cout << endl;

assert(std::abs(cr.first / cr.second - min_cr) < epsilon * 2);

return EXIT_SUCCESS;

}