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

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

Я сейчас пользуюсь 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 миллисекунд. В предыдущей версии, для запуска которой требовалось столько же времени, я использовал std::advance на edges(g).first (с gen_int как указано выше). В этой версии std::advance занимал львиную долю времени вычислений.

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

Однако я был бы открыт и для других подходов. Там должен быть какой-то способ сделать это, потому что есть реализация краевых свопов Монте-Карло в random_rewire функция в Graph-Tool, которая работает намного быстрее, чем мой код.