Произвольный доступ (или иной быстрый доступ) к ребрам в библиотеке графов повышения

Я хочу запустить обмен ребрами по методу Монте-Карло, т. Е. Выбрать два существующих ребра в графе равномерно случайным образом, а затем (если выполняются некоторые условия) поменять местами их конечные точки.

В настоящее время я использую 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);
  };
}

Для графов с >250 тыс. ребер это оказывается довольно медленным; каждое использование random_edge занимает от 1 до 10 миллисекунд. В предыдущей версии, запуск которой занимал столько же времени, я использовал std::advance на edges(g).first (с gen_int, как указано выше). В этой версии std::advance занимало львиную долю времени вычислений.

Я предполагаю, что все работало бы намного быстрее, если бы я мог получить итератор произвольного доступа для edges(g), аналогичный произвольному доступу к вершинам здесь.

Однако я был бы открыт и для других подходов. Должен быть какой-то способ сделать это, потому что в random_rewire в графическом инструменте, который работает намного быстрее, чем мой код.