c++ - 随机访问(或以其他方式快速访问)boost 图形库中的边

Question

我想运行蒙特卡洛边交换，即随机均匀地选取图中的两条现有边，然后(如果满足某些条件)交换它们的端点。

我目前正在使用 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) 获得随机访问迭代器，事情会运行得更快，类似于对顶点的随机访问 here .

但是，我也愿意接受其他方法。应该有一些方法可以做到这一点，因为在 random_rewire 中有一个蒙特卡罗边缘交换的实现。图形工具中的函数，运行速度比我的代码快得多。

Answer 1

不，你不能随机访问邻接列表:

• Reason for not allowing random access to the vector of edges in adjacency lists

下面是不同洗牌方法的基准:

• How to efficiently shuffle edges in a graph