source: lemon-0.x/benchmark/edge_lookup.cc @ 2255:4a9cc8c800ae

#include"edge_lookup_test.h"
#include<lemon/smart_graph.h>
#include<vector>
#include<lemon/time_measure.h>
#include<lemon/random.h>

using namespace lemon;

GRAPH_TYPEDEFS(SmartGraph)
typedef SmartGraph Graph;

class FE 
{
public:
  Graph &_g;
  FE(Graph &g) :_g(g) {}
  void operator()() 
  {
    Edge e;
    
    for(NodeIt v(_g);v!=INVALID;++v)
      for(NodeIt u(_g);u!=INVALID;++u)
        e=findEdge(_g,u,v);
  }
  
};

class EL 
{
public:
  Graph &_g;
  EdgeLookUp<Graph> _el;
  EL(Graph &g) :_g(g), _el(g) {}
  void operator()() 
  {
    Edge e;
    
    for(NodeIt v(_g);v!=INVALID;++v)
      for(NodeIt u(_g);u!=INVALID;++u)
        e=_el(u,v);
  }
  
};
class EL2
{
public:
  Graph &_g;
  EdgeLookUp2<Graph> _el;
  EL2(Graph &g) :_g(g), _el(g) {}
  void operator()() 
  {
    Edge e;
    
    for(NodeIt v(_g);v!=INVALID;++v)
      for(NodeIt u(_g);u!=INVALID;++u)
        e=_el(u,v);
  }
  
};

class EL3
{
public:
  Graph &_g;
  EdgeLookUp3<Graph> _el;
  EL3(Graph &g) :_g(g), _el(g) {}
  void operator()() 
  {
    Edge e;
    
    for(NodeIt v(_g);v!=INVALID;++v)
      for(NodeIt u(_g);u!=INVALID;++u)
        e=_el(u,v);
  }
  
};

class EL4
{
public:
  Graph &_g;
  EdgeLookUp4<Graph> _el;
  EL4(Graph &g) :_g(g), _el(g) {}
  void operator()() 
  {
    Edge e;
    
    for(NodeIt v(_g);v!=INVALID;++v)
      for(NodeIt u(_g);u!=INVALID;++u)
        e=_el(u,v);
  }
  
};

int main(int, char**argv)
{
  int N=atoi(argv[1]);
  int M=int(N*atof(argv[2]));
  
  Graph g;
  
  std::vector<Node> v;
  for(int i=0;i<N;i++) v.push_back(g.addNode());
  for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);

//   {
//     Edge e;
    
//     TimeReport t("findEdge: ");
//     for(NodeIt u(g);u!=INVALID;++u)
//       for(NodeIt v(g);v!=INVALID;++v)
//      e=findEdge(g,u,v);
//   }
//   {
//     Edge e;
//     EdgeLookUp<Graph> el(g);
    
//     TimeReport t("EdgeLookUp: ");
//     for(NodeIt u(g);u!=INVALID;++u)
//       for(NodeIt v(g);v!=INVALID;++v)
//      e=el(u,v);
//   }


  TimeStamp t1 = runningTimeTest(FE(g),1);
  TimeStamp t2 = runningTimeTest(EL(g),1);
  TimeStamp t3 = runningTimeTest(EL2(g),1);
  TimeStamp t4 = runningTimeTest(EL3(g),1);
//   TimeStamp t5 = runningTimeTest(EL4(g),1);

  std::cout << t1.userTime()/N/N << ' ' 
            << t2.userTime()/N/N << ' '
            << t3.userTime()/N/N << ' '
            << t4.userTime()/N/N << ' '
//          << t5.userTime()/N/N
            << std::endl;
}