随机访问（或以其他方式快速访问）boost 图形库中的边

Question

我想运行 Monte Carlo边交换，即随机均匀地选择图中的两条现有边，然后（如果满足某些条件）交换它们的端点。

我目前正在使用 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> 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);
  };
}

对于边超过 250k 的图，结果证明这相当慢；每次使用 random_edge 大约需要 1 到 10 毫秒。在运行花费同样长的先前版本中，我在 edges(g).first 上使用了 std::advance（如上所述使用 gen_int）。在那个版本中，std::advance 占据了大部分计算时间。

我假设如果我能为 edges(g) 获得随机访问迭代器，事情会运行快得多，类似于对顶点的随机访问。

但是，我也愿意接受其他方法。应该有一些方法可以做到这一点，因为在 graph-tool 的 random_rewire 函数中有一个 Monte Carlo 边缘交换的实现，运行s 比我的代码快得多。

Answer 1

不，您不能随机访问邻接列表：

这里是不同洗牌方法的基准：

随机访问（或以其他方式快速访问）boost 图形库中的边

Random access (or otherwise fast access) of edges in boost graph library

c++

boost

graph

random-access

graph-tool