Случайный доступ (или в противном случае быстрый доступ) ребер в библиотеке ускорителя

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); 
    }; 
} 

Для графиков с границами> 250 тыс., Это оказывается довольно медленным; каждое использование random_edge занимает от 1 до 10 миллисекунд. В предыдущей версии, которая занимала одинаково долгое время, я использовал std::advance по адресу edges(g).first (с 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