Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
benchmark/edge_lookup.cc
author alpar
Thu, 12 Oct 2006 10:53:49 +0000
changeset 2236 9f329faa4aee
child 2238 8d623100ab13
permissions -rw-r--r--
EdgeLookUp and AllEdgeLookUp tests added. 
     1 // #include<lemon/edge_lookup.h>

     2 #include<lemon/edge_lookup_test.h>

     3 #include<lemon/smart_graph.h>

     4 #include<vector>

     5 #include<lemon/time_measure.h>

     6 

     7 using namespace lemon;

     8 

     9 GRAPH_TYPEDEFS(SmartGraph)

    10 typedef SmartGraph Graph;

    11 

    12 class FE 

    13 {

    14 public:

    15   Graph &_g;

    16   FE(Graph &g) :_g(g) {}

    17   void operator()() 

    18   {

    19     Edge e;

    20     

    21     for(NodeIt v(_g);v!=INVALID;++v)

    22       for(NodeIt u(_g);u!=INVALID;++u)

    23 	e=findEdge(_g,u,v);

    24   }

    25   

    26 };

    27 

    28 class EL 

    29 {

    30 public:

    31   Graph &_g;

    32   EdgeLookUp<Graph> _el;

    33   EL(Graph &g) :_g(g), _el(g) {}

    34   void operator()() 

    35   {

    36     Edge e;

    37     

    38     for(NodeIt v(_g);v!=INVALID;++v)

    39       for(NodeIt u(_g);u!=INVALID;++u)

    40 	e=_el(u,v);

    41   }

    42   

    43 };

    44 class EL2

    45 {

    46 public:

    47   Graph &_g;

    48   EdgeLookUp2<Graph> _el;

    49   EL2(Graph &g) :_g(g), _el(g) {}

    50   void operator()() 

    51   {

    52     Edge e;

    53     

    54     for(NodeIt v(_g);v!=INVALID;++v)

    55       for(NodeIt u(_g);u!=INVALID;++u)

    56 	e=_el(u,v);

    57   }

    58   

    59 };

    60 

    61 class EL3

    62 {

    63 public:

    64   Graph &_g;

    65   EdgeLookUp3<Graph> _el;

    66   EL3(Graph &g) :_g(g), _el(g) {}

    67   void operator()() 

    68   {

    69     Edge e;

    70     

    71     for(NodeIt v(_g);v!=INVALID;++v)

    72       for(NodeIt u(_g);u!=INVALID;++u)

    73 	e=_el(u,v);

    74   }

    75   

    76 };

    77 

    78 class EL4

    79 {

    80 public:

    81   Graph &_g;

    82   EdgeLookUp4<Graph> _el;

    83   EL4(Graph &g) :_g(g), _el(g) {}

    84   void operator()() 

    85   {

    86     Edge e;

    87     

    88     for(NodeIt v(_g);v!=INVALID;++v)

    89       for(NodeIt u(_g);u!=INVALID;++u)

    90 	e=_el(u,v);

    91   }

    92   

    93 };

    94 

    95 int main(int argc, char**argv)

    96 {

    97   int N=atoi(argv[1]);

    98   int M=int(N*atof(argv[2]));

    99   

   100   Graph g;

   101   

   102   std::vector<Node> v;

   103   for(int i=0;i<N;i++) v.push_back(g.addNode());

   104   for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*N)]);

   105 

   106 //   {

   107 //     Edge e;

   108     

   109 //     TimeReport t("findEdge: ");

   110 //     for(NodeIt u(g);u!=INVALID;++u)

   111 //       for(NodeIt v(g);v!=INVALID;++v)

   112 // 	e=findEdge(g,u,v);

   113 //   }

   114 //   {

   115 //     Edge e;

   116 //     EdgeLookUp<Graph> el(g);

   117     

   118 //     TimeReport t("EdgeLookUp: ");

   119 //     for(NodeIt u(g);u!=INVALID;++u)

   120 //       for(NodeIt v(g);v!=INVALID;++v)

   121 // 	e=el(u,v);

   122 //   }

   123 

   124 

   125   TimeStamp t1 = runningTimeTest(FE(g),1);

   126   TimeStamp t2 = runningTimeTest(EL(g),1);

   127   TimeStamp t3 = runningTimeTest(EL2(g),1);

   128   TimeStamp t4 = runningTimeTest(EL3(g),1);

   129   TimeStamp t5 = runningTimeTest(EL4(g),1);

   130 

   131   std::cout << t1.userTime()/N/N << ' ' 

   132 	    << t2.userTime()/N/N << ' '

   133 	    << t3.userTime()/N/N << ' '

   134 	    << t4.userTime()/N/N << ' '

   135 	    << t5.userTime()/N/N << std::endl;

   136 }

   137
lemon-0.x