增强图库中边缘的随机访问(或其他快速访问) [英] Random access (or otherwise fast access) of edges in boost graph library
问题描述
我想运行蒙特卡洛边缘交换,即随机选取图中两个现有边,然后(如果符合某些条件)交换其端点。
我现在使用 boost :: random_edge
来随机统一选择边缘。
#include< boost / graph / adjacency_list.hpp>
#include< boost / graph / erdos_renyi_generator.hpp>
#include< boost / random / mersenne_twister.hpp>
#include< boost / random / variate_generator.hpp>
#include< boost / graph / random.hpp>
#include< boost / random / linear_congruential.hpp>
int main(int argc,char * argv []){
typedef boost :: adjacency_list< boost :: setS,boost :: vecS,boost :: undirectedS>图形;
typedef boost :: erdos_renyi_iterator< boost :: minstd_rand,Graph>耳根;
typedef boost :: uniform_int<> UniformIntDistr;
typedef boost :: variate_generator< boost :: mt19937&,UniformIntDistr> IntRNG;
//制作随机图
int n = 17000;
boost :: graph_traits< Graph> :: edges_size_type m = 250000;
boost :: minstd_rand gen;
图g(ERGen(gen,n,m),ERGen(),n);
//使随机数发生器
boost :: mt19937 rng;
UniformIntDistr dis(0,num_edges(g)-1);
IntRNG gen_int(rng,dis);
//随机统一选择两条边(一百万次)
Graph :: edge_descriptor e1;
Graph :: edge_descriptor e2;
for(int i = 0; i <1000000; i ++){
Graph :: edge_descriptor e1 = boost :: random_edge(g,gen_int);
Graph :: edge_descriptor e2 = boost :: random_edge(g,gen_int);
};
}
对于边缘大于250k的图形来说,每使用 random_edge
大约需要1到10毫秒。在以前的版本中运行时间相当长,我在边缘(g).first
上使用 std :: advance
(如上 std :: advance
占用了计算时间的大部分。
如果我可以获得边(g)
的随机访问迭代器,运行速度会更快,类似于随机访问顶点此处。
但是,我也会接受其他方法。应该有办法做到这一点,因为在 random_rewire 在图形工具中的功能,运行速度比我的代码快得多。
不,你不能随机访问邻接列表:
以下是洗牌边缘的不同方法的基准:
I want to run Monte Carlo edge swaps, i.e., picking two existing edges in a graph uniformly at random and then (if some conditions are met) swap their end points.
I am currently using boost::random_edge
for selecting edges uniformly at random.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/graph/random.hpp>
#include <boost/random/linear_congruential.hpp>
int main(int argc, char* argv[]) {
typedef boost::adjacency_list<boost::setS,boost::vecS,boost::undirectedS> Graph;
typedef boost::erdos_renyi_iterator<boost::minstd_rand, Graph> ERGen;
typedef boost::uniform_int<> UniformIntDistr;
typedef boost::variate_generator<boost::mt19937&, UniformIntDistr> IntRNG;
// make random graph
int n = 17000;
boost::graph_traits<Graph>::edges_size_type m = 250000;
boost::minstd_rand gen;
Graph g(ERGen(gen, n, m), ERGen(), n);
// make random number generator
boost::mt19937 rng;
UniformIntDistr dis(0, num_edges(g)-1);
IntRNG gen_int(rng, dis);
// select two edges uniformly at random (a million times)
Graph::edge_descriptor e1;
Graph::edge_descriptor e2;
for (int i=0; i<1000000;i++) {
Graph::edge_descriptor e1 = boost::random_edge(g, gen_int);
Graph::edge_descriptor e2 = boost::random_edge(g, gen_int);
};
}
For graphs with >250k edges, this turns out to be rather slow; each use of random_edge
takes around 1 to 10 milliseconds. In a previous version that took equally long to run, I used std::advance
on edges(g).first
(with gen_int
as above). In that version, std::advance
took up the lion share of the computation time.
I assume that things would run much faster if I could get a random access iterator for edges(g)
, similar to the random access to vertices here.
However, I'd be open to other approaches too. There should be some way to do this, because there is an implementation of Monte Carlo edge swaps in the random_rewire function in graph-tool, which runs much faster than my code.
No you can't have random access for adjacency-lists:
Here's a benchmark of different approaches to shuffle edges:
这篇关于增强图库中边缘的随机访问(或其他快速访问)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!