Search code examples
c++boostgraphrandom-accessgraph-tool

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

I want to run Monte Carlo edge swaps, i.e., picking two existing edges in a graph uniformly at random and then (if some conditions are met) swap their end points.

I am currently using boost::random_edge for selecting edges uniformly at random.

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

For graphs with >250k edges, this turns out to be rather slow; each use of random_edge takes around 1 to 10 milliseconds. In a previous version that took equally long to run, I used std::advance on edges(g).first (with gen_int as above). In that version, std::advance took up the lion share of the computation time.

I assume that things would run much faster if I could get a random access iterator for edges(g), similar to the random access to vertices here.

However, I'd be open to other approaches too. There should be some way to do this, because there is an implementation of Monte Carlo edge swaps in the random_rewire function in graph-tool, which runs much faster than my code.

Solution

  • No you can't have random access for adjacency-lists:

    Here's a benchmark of different approaches to shuffle edges: