![to]( "to")
本文介绍了增强图库中边缘的随机访问（或其他快速访问）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想运行蒙特卡洛边缘交换，即随机选取图中两个现有边，然后（如果符合某些条件）交换其端点。
我现在使用 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 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 （如上 gen_int ）。在那个版本中， std :: advance 占用了计算时间的大部分。
如果我可以获得边（g）的随机访问迭代器，运行速度会更快，类似于随机访问顶点。
但是，我也会接受其他方法。应该有办法做到这一点，因为在在图形工具中的功能，运行速度比我的代码快得多。
不，你不能随机访问邻接列表：
以下是洗牌边缘的不同方法的基准：
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:
这篇关于增强图库中边缘的随机访问（或其他快速访问）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！