Benchmark BGL functions on list and matrix graph representations

adjacency.cpp

#include <fstream>
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/random.hpp>

using namespace std;
using namespace boost;

template<class Graph, class Generator>
Graph random_graph(int n, double p, Generator generator) {
  Graph g(n);
  bernoulli_distribution distribution(p);
  auto trial = bind(distribution, generator);
  for(int i = 0; i < n; ++i)
    for(int j = i + 1; j < n; ++j)
      if(trial()) add_edge(i, j, g);
  return g;
}

class timing {
  timespec c_start, c_end;
  clockid_t c_id;
public:
  timing(clockid_t id) : c_id(id) {}
  void start() {
    clock_gettime(c_id, &c_start);
  }
  void stop() {
    clock_gettime(c_id, &c_end);
  }
  time_t begin() const {
    return c_start.tv_sec * 1e9 + c_start.tv_nsec;
  }
  time_t end() const {
    return c_end.tv_sec * 1e9 + c_end.tv_nsec;
  }
  time_t elapsed() const {
    return end() - begin();
  }
};

template <class Graph>
void test(string name) {
  default_random_engine gen;
  ofstream file(name);
  timing t(CLOCK_PROCESS_CPUTIME_ID);
  for(int n = 100; n <= 1000; n += 100) {
    cerr << n << endl;
    for(int j = 0; j < 100; ++j) {
      auto g = random_graph<Graph>(n, 0.5, gen);
      for(int i = 0; i < 100; ++i) {
        auto v = random_vertex(g, gen);
        auto w = random_vertex(g, gen);
        t.start();
        auto e = edge(v, w, g).second;
        t.stop();
        file << n << ' ' << t.elapsed() << ' ' << e << endl;
      }
    }
  }
  file.close();
}

int main() {
  test<adjacency_list<vecS, vecS, undirectedS>>("vec.txt");
  test<adjacency_list<listS, vecS, undirectedS>>("list.txt");
  test<adjacency_list<slistS, vecS, undirectedS>>("slist.txt");
  test<adjacency_list<setS, vecS, undirectedS>>("set.txt");
  test<adjacency_list<multisetS, vecS, undirectedS>>("multiset.txt");
  test<adjacency_list<hash_setS, vecS, undirectedS>>("hashset.txt");
  test<adjacency_matrix<undirectedS>>("matrix.txt");
  return 0;
}