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 11:09:17 +0000
changeset 2238 8d623100ab13
parent 2235 48801095a410
child 2240 d93c034d3c98
permissions -rw-r--r--
Bugfix 
     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
lemon-0.x