Benchmark of different BFS implementations

bfs_benchmark.cpp

#include <benchmark/benchmark.h>
#include <algorithm>
 
#include <iostream>
#include <vector>
#include <random>
#include <list>
#include <array>
#include <queue>  
#include <deque>
using namespace std;

class Graph{
  public:
    int size;
    int id;
    int visited;

    vector<int> *adj_list;  
  
  Graph(int n){
    size=n;
    adj_list = new vector<int>[size];
  }

  void addEdge(int i, int j){
    adj_list[i].push_back(j);
    adj_list[j].push_back(i);
  }

  int getSize(){
    return size;
  }

  // Generates a random graph of size "size"
  // The p is the probabiliy that there exists an edge between two vertices i and j
  // Furthermore, we ensure that the graph is connected by connecting every node i to i+1 (without losing any generality)
  Graph(int n, double p){
    size=n;
    adj_list = new vector<int>[size];

      //step 0: setup random number generator
      std::mt19937 rng;
      std::array<int, 624> seed_data;
      std::random_device r;
      std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
      std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
      rng.seed(seq);
      std::uniform_real_distribution<> dis(0, 1);

      //step 1: make sure the graph is connected
      for(int i=0;i<size-1;i++){
        addEdge(i, i+1);
      }
      
      //step 2: randomly generate edges
      for(int i=0;i<size;i++){
          for(int j=0;j<size;j++){
              if(i!=j){
                  double prob = dis(rng);
                  if(prob<p){
                    addEdge(i, j);
                  }
              }
          }
      }
  }

};

//list is basically a linked-list
int bfs_list(Graph* g){
  int sig=0;
  vector<bool> visited(g->getSize(), false);
  list<int> q; 
  auto init = rand()%g->getSize();
  q.push_back(init);
  visited[init]=true;
  while(!q.empty()){
    auto u = q.front(); 
    sig += u;
    q.pop_front();
    for(auto v: g->adj_list[u]){
      if(!visited[v]){
        visited[v]=true;
        q.push_back(v);
      }
    }
  }
  return sig;
}

//queue by default uses dequeue as its internal container
int bfs_queue(Graph* g){
  int sig=0;
  vector<bool> visited(g->getSize(), false);
  queue<int> q; 
  auto init = rand()%g->getSize();
  q.push(init);
  visited[init]=true;
  while(!q.empty()){
    auto u = q.front(); 
    sig += u;
    q.pop();
    for(auto v: g->adj_list[u]){
      if(!visited[v]){
        visited[v]=true;
        q.push(v);
      }
    }
  }
  return sig;
}

int bfs_vector(Graph* g){
  int sig=0;
  vector<bool> visited(g->getSize(), false);
  vector<int> q; 
  q.reserve(10);
  auto init = rand()%g->getSize();
  q.push_back(init);
  visited[init]=true;
  while(!q.empty()){
    auto u = q.front(); 
    sig += u;
    q.erase(q.begin()); // expensive operation for vector
    for(auto v: g->adj_list[u]){
      if(!visited[v]){
        visited[v]=true;
        q.push_back(v);
      }
    }
  }
  return sig;
}


int bfs_vector_no_order(Graph* g){
  int sig=0;
  vector<bool> visited(g->getSize(), false);
  vector<int> q; 
  q.reserve(50);
  auto init = rand()%g->getSize();
  q.push_back(init);
  visited[init]=true;
  while(!q.empty()){
    auto u = q.front(); 
    sig += u;
    
    //q.erase(q.begin());  // O(1) pop for vector, if we don't care about the ordering
    swap(q[0], q.back());
      q.pop_back();
    for(auto v: g->adj_list[u]){
      if(!visited[v]){
        visited[v]=true;
        q.push_back(v);
      }
    }
  }
  return sig;
}

int bfs_deque(Graph* g){
  int sig=0;
  vector<bool> visited(g->getSize(), false);
  deque<int> q; 
  auto init = rand()%g->getSize();
  q.push_back(init);
  visited[init]=true;
  while(!q.empty()){
    auto u = q.front(); 
    sig += u;
    q.pop_front();
    for(auto v: g->adj_list[u]){
      if(!visited[v]){
        visited[v]=true;
        q.push_back(v);
      }
    }
  }
  return sig;
}


const int graph_size = 500;
const float probability = 0.05;
Graph* g;
static void BM_Graph_Constructor(benchmark::State& state) {
  int ret=0;
  while (state.KeepRunning()){
    g = new Graph(graph_size, probability);
    ret += g->getSize();
  }
  //cout << ret << endl ;
}

static void BM_BFS_List(benchmark::State& state) {
  int ret=0;
  //Graph* g = new Graph(graph_size, probability);  
  while (state.KeepRunning()){
    ret += bfs_list(g);
  }
  //delete g;
  //cout << ret << endl ;
}
 
static void BM_BFS_queue(benchmark::State& state) {
  int ret=0;
  //Graph* g = new Graph(graph_size, probability);
  while (state.KeepRunning()){
    ret += bfs_queue(g);
  }
  //delete g;
  //cout << ret << endl ;
}

static void BM_BFS_vector(benchmark::State& state) {
  int ret=0;
  //Graph* g = new Graph(graph_size, probability);
  while (state.KeepRunning()){
    ret += bfs_vector(g);
  }
  //delete g;
  //cout << ret << endl ;
}

static void BM_BFS_vector_no_order(benchmark::State& state) {
  int ret=0;
  //Graph* g = new Graph(graph_size, probability);
  while (state.KeepRunning()){
    ret += bfs_vector_no_order(g);
  }
  //delete g;
  //cout << ret << endl ;
}

static void BM_BFS_deque(benchmark::State& state) {
  int ret=0;
  //Graph* g = new Graph(graph_size, probability);
  while (state.KeepRunning()){
    ret += bfs_deque(g);
  }
  //delete g;
  //cout << ret << endl ;
}
BENCHMARK(BM_Graph_Constructor);
BENCHMARK(BM_BFS_List);
BENCHMARK(BM_BFS_queue);
BENCHMARK(BM_BFS_vector);
BENCHMARK(BM_BFS_vector_no_order);
BENCHMARK(BM_BFS_deque);
BENCHMARK_MAIN()