Ticket #309: benchmark_graphs.cpp

#include <iostream>
#include <fstream>
#include <cstdlib>

#include <lemon/list_graph.h>
#include <lemon/smart_graph.h>
//#include <lemon/static_graph.h>
#include <lemon/dimacs.h>
#include <lemon/adaptors.h>
#include <lemon/random.h>
#include <lemon/time_measure.h>

using namespace std;
using namespace lemon;

template <typename Graph>
class NodeIterator1 {
  const Graph &_gr;
  int _cnt;
public:
  NodeIterator1(const Graph &gr) : _gr(gr), _cnt(0) {}
  void operator()() {
    for (typename Graph::NodeIt n(_gr); n != INVALID; ++n)
      ++_cnt;
  }
  int count() { return _cnt; }
};

template <typename Graph>
class NodeIterator2 {
  const Graph &_gr;
  int _cnt;
public:
  NodeIterator2(const Graph &gr) : _gr(gr), _cnt(0) {}
  void operator()() {
    typename Graph::Node n;
    for (_gr.first(n); n != INVALID; _gr.next(n))
      ++_cnt;
  }
  int count() { return _cnt; }
};

template <typename Graph>
class ArcIterator1 {
  const Graph &_gr;
  int _cnt;
public:
  ArcIterator1(const Graph &gr) : _gr(gr), _cnt(0) {}
  void operator()() {
    for (typename Graph::ArcIt e(_gr); e != INVALID; ++e)
      ++_cnt;
  }
  int count() { return _cnt; }
};

template <typename Graph>
class ArcIterator2 {
  const Graph &_gr;
  int _cnt;
public:
  ArcIterator2(const Graph &gr) : _gr(gr), _cnt(0) {}
  void operator()() {
    typename Graph::Arc e;
    for (_gr.first(e); e != INVALID; _gr.next(e))
      ++_cnt;
  }
  int count() { return _cnt; }
};

template <typename Graph>
class OutArcIterator {
  const Graph &_gr;
  int _cnt;
public:
  OutArcIterator(const Graph &gr) : _gr(gr), _cnt(0) {}
  void operator()() {
    for (typename Graph::NodeIt n(_gr); n != INVALID; ++n) {
      for (typename Graph::OutArcIt e(_gr, n); e != INVALID; ++e)
        ++_cnt;
    }
  }
  int count() { return _cnt; }
};

template <typename Graph>
class InArcIterator {
  const Graph &_gr;
  int _cnt;
public:
  InArcIterator(const Graph &gr) : _gr(gr), _cnt(0) {}
  void operator()() {
    for (typename Graph::NodeIt n(_gr); n != INVALID; ++n) {
      for (typename Graph::InArcIt e(_gr, n); e != INVALID; ++e)
        ++_cnt;
    }
  }
  int count() { return _cnt; }
};


const int K = 10;

template <typename GR>
void benchmarkGraph(const GR &gr, int n, int m) {
  Timer tni1, tni2, tai1, tai2, toai, tiai;
  NodeIterator1<GR> ni1(gr);
  NodeIterator2<GR> ni2(gr);
  ArcIterator1<GR> ai1(gr);
  ArcIterator2<GR> ai2(gr);
  OutArcIterator<GR> oai(gr);
  InArcIterator<GR> iai(gr);
  
  tni1.restart();
  for (int i=0; i!=K; ++i) ni1();
  tni1.stop();
  tni2.restart();
  for (int i=0; i!=K; ++i) ni2();
  tni2.stop();
  tai1.restart();
  for (int i=0; i!=K; ++i) ai1();
  tai1.stop();
  tai2.restart();
  for (int i=0; i!=K; ++i) ai2();
  tai2.stop();
  toai.restart();
  for (int i=0; i!=K; ++i) oai();
  toai.stop();
  tiai.restart();
  for (int i=0; i!=K; ++i) iai();
  tiai.stop();

  cout << "  NodeIt:    " << tni1.realTime() / K
       << "    \t"        << tni2.realTime() / K << endl;
  cout << "  ArcIt:     " << tai1.realTime() / K
       << "    \t"        << tai2.realTime() / K << endl;
  cout << "  OutArcIt:  " << toai.realTime() / K << endl;
  cout << "  InArcIt:   " << tiai.realTime() / K << endl;
  cout << endl;
  
  if (ni1.count() != K * n) exit(-1);
  if (ni2.count() != K * n) exit(-1);
  if (ai1.count() != K * m) exit(-1);
  if (ai2.count() != K * m) exit(-1);
  if (oai.count() != K * m) exit(-1);
  if (iai.count() != K * m) exit(-1);
}

int main(int argc, char *argv[])
{
  if (argc < 3) {
    cout << "Usage: " << argv[0] << " n m" << endl;
    return -1;
  }
  
  int n = atoi(argv[1]);
  int m = atoi(argv[2]);
  
  cout << "Benchmark tests on a random digraph (n = " << n
       << ", m = " << m << ")" << endl << endl;
  
  vector<pair<int, int> > arcs1;
  for (int j = 0; j != m; ++j) {
    arcs1.push_back(make_pair(rnd[n], rnd[n]));
  }
  vector<pair<int, int> > arcs2(arcs1);
  sort(arcs2.begin(), arcs2.end());

  // Building graphs
  cout << "ListDigraph - Building                  ";
  Timer tlgr1;
  ListDigraph lgr1;
  vector<ListDigraph::Node> lnodes1;
  for (int i = 0; i != n; ++i) {
    lnodes1.push_back(lgr1.addNode());
  }  
  for (int j = 0; j != m; ++j) {
    lgr1.addArc(lnodes1[arcs1[j].first], lnodes1[arcs1[j].second]);
  }
  tlgr1.stop();
  cout << tlgr1.realTime() << endl;
  
  cout << "ListDigraph (sorted arcs) - Building    ";
  Timer tlgr2;
  ListDigraph lgr2;
  vector<ListDigraph::Node> lnodes2;
  for (int i = 0; i != n; ++i) {
    lnodes2.push_back(lgr2.addNode());
  }  
  for (int j = 0; j != m; ++j) {
    lgr2.addArc(lnodes2[arcs2[j].first], lnodes2[arcs2[j].second]);
  }
  tlgr2.stop();
  cout << tlgr2.realTime() << endl;

  cout << "SmartDigraph - Building                 ";
  Timer tsgr1;
  SmartDigraph sgr1;
  vector<SmartDigraph::Node> snodes1;
  for (int i = 0; i != n; ++i) {
    snodes1.push_back(sgr1.addNode());
  }  
  for (int j = 0; j != m; ++j) {
    sgr1.addArc(snodes1[arcs1[j].first], snodes1[arcs1[j].second]);
  }
  tsgr1.stop();
  cout << tsgr1.realTime() << endl;

  cout << "SmartDigraph (sorted arcs) - Building   ";
  Timer tsgr2;
  SmartDigraph sgr2;
  vector<SmartDigraph::Node> snodes2;
  for (int i = 0; i != n; ++i) {
    snodes2.push_back(sgr2.addNode());
  }  
  for (int j = 0; j != m; ++j) {
    sgr2.addArc(snodes2[arcs2[j].first], snodes2[arcs2[j].second]);
  }
  tsgr2.stop();
  cout << tsgr2.realTime() << endl;

  cout << endl;
  
  // Iteration test
  cout << "ListDigraph - Iteration" << endl;
  benchmarkGraph(lgr1, n, m);
  
  cout << "ListDigraph (sorted arcs) - Iteration" << endl;
  benchmarkGraph(lgr2, n, m);
  
  cout << "SmartDigraph - Iteration" << endl;
  benchmarkGraph(sgr1, n, m);
  
  cout << "SmartDigraph (sorted arcs) - Iteration" << endl;
  benchmarkGraph(sgr2, n, m);
  
  return 0;
}