benchmark/edge_lookup.cc
author alpar
Thu, 12 Oct 2006 11:53:31 +0000
changeset 2239 18c24fe93b99
parent 2235 48801095a410
child 2240 d93c034d3c98
permissions -rw-r--r--
Turn off 32bit specific tests.
     1 #include"edge_lookup_test.h"
     2 #include<lemon/smart_graph.h>
     3 #include<vector>
     4 #include<lemon/time_measure.h>
     5 
     6 using namespace lemon;
     7 
     8 GRAPH_TYPEDEFS(SmartGraph)
     9 typedef SmartGraph Graph;
    10 
    11 class FE 
    12 {
    13 public:
    14   Graph &_g;
    15   FE(Graph &g) :_g(g) {}
    16   void operator()() 
    17   {
    18     Edge e;
    19     
    20     for(NodeIt v(_g);v!=INVALID;++v)
    21       for(NodeIt u(_g);u!=INVALID;++u)
    22 	e=findEdge(_g,u,v);
    23   }
    24   
    25 };
    26 
    27 class EL 
    28 {
    29 public:
    30   Graph &_g;
    31   EdgeLookUp<Graph> _el;
    32   EL(Graph &g) :_g(g), _el(g) {}
    33   void operator()() 
    34   {
    35     Edge e;
    36     
    37     for(NodeIt v(_g);v!=INVALID;++v)
    38       for(NodeIt u(_g);u!=INVALID;++u)
    39 	e=_el(u,v);
    40   }
    41   
    42 };
    43 class EL2
    44 {
    45 public:
    46   Graph &_g;
    47   EdgeLookUp2<Graph> _el;
    48   EL2(Graph &g) :_g(g), _el(g) {}
    49   void operator()() 
    50   {
    51     Edge e;
    52     
    53     for(NodeIt v(_g);v!=INVALID;++v)
    54       for(NodeIt u(_g);u!=INVALID;++u)
    55 	e=_el(u,v);
    56   }
    57   
    58 };
    59 
    60 class EL3
    61 {
    62 public:
    63   Graph &_g;
    64   EdgeLookUp3<Graph> _el;
    65   EL3(Graph &g) :_g(g), _el(g) {}
    66   void operator()() 
    67   {
    68     Edge e;
    69     
    70     for(NodeIt v(_g);v!=INVALID;++v)
    71       for(NodeIt u(_g);u!=INVALID;++u)
    72 	e=_el(u,v);
    73   }
    74   
    75 };
    76 
    77 class EL4
    78 {
    79 public:
    80   Graph &_g;
    81   EdgeLookUp4<Graph> _el;
    82   EL4(Graph &g) :_g(g), _el(g) {}
    83   void operator()() 
    84   {
    85     Edge e;
    86     
    87     for(NodeIt v(_g);v!=INVALID;++v)
    88       for(NodeIt u(_g);u!=INVALID;++u)
    89 	e=_el(u,v);
    90   }
    91   
    92 };
    93 
    94 int main(int, char**argv)
    95 {
    96   int N=atoi(argv[1]);
    97   int M=int(N*atof(argv[2]));
    98   
    99   Graph g;
   100   
   101   std::vector<Node> v;
   102   for(int i=0;i<N;i++) v.push_back(g.addNode());
   103   for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*N)]);
   104 
   105 //   {
   106 //     Edge e;
   107     
   108 //     TimeReport t("findEdge: ");
   109 //     for(NodeIt u(g);u!=INVALID;++u)
   110 //       for(NodeIt v(g);v!=INVALID;++v)
   111 // 	e=findEdge(g,u,v);
   112 //   }
   113 //   {
   114 //     Edge e;
   115 //     EdgeLookUp<Graph> el(g);
   116     
   117 //     TimeReport t("EdgeLookUp: ");
   118 //     for(NodeIt u(g);u!=INVALID;++u)
   119 //       for(NodeIt v(g);v!=INVALID;++v)
   120 // 	e=el(u,v);
   121 //   }
   122 
   123 
   124   TimeStamp t1 = runningTimeTest(FE(g),1);
   125   TimeStamp t2 = runningTimeTest(EL(g),1);
   126   TimeStamp t3 = runningTimeTest(EL2(g),1);
   127   TimeStamp t4 = runningTimeTest(EL3(g),1);
   128   TimeStamp t5 = runningTimeTest(EL4(g),1);
   129 
   130   std::cout << t1.userTime()/N/N << ' ' 
   131 	    << t2.userTime()/N/N << ' '
   132 	    << t3.userTime()/N/N << ' '
   133 	    << t4.userTime()/N/N << ' '
   134 	    << t5.userTime()/N/N << std::endl;
   135 }
   136