benchmark/edge_lookup.cc
author alpar
Thu, 09 Nov 2006 00:50:07 +0000
changeset 2299 227ea098a6b6
parent 2272 f6b352fdc6b1
child 2391 14a343be7a5a
permissions -rw-r--r--
Bugfix: didn't removed the lock file if something went wrong
     1 #include<lemon/smart_graph.h>
     2 #include<vector>
     3 #include<lemon/time_measure.h>
     4 #include<lemon/random.h>
     5 #include<lemon/graph_utils.h>
     6 #include<algorithm>
     7 
     8 using namespace lemon;
     9 
    10   template<class G>
    11   class EdgeLookUp2
    12   {
    13   public:
    14     GRAPH_TYPEDEFS(typename G)
    15     typedef G Graph;
    16 
    17   private:
    18     const Graph &_g;
    19     typename Graph::template NodeMap<int> _start;
    20     typename Graph::template NodeMap<int> _end;
    21     std::vector<Edge> _edges;
    22     
    23     class EdgeLess {
    24       const Graph &g;
    25     public:
    26       EdgeLess(const Graph &_g) : g(_g) {}
    27       bool operator()(Edge a,Edge b) const 
    28       {
    29 	return g.target(a)<g.target(b);
    30       }
    31     };
    32     
    33   public:
    34     
    35     ///Constructor
    36     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
    37     
    38   public:
    39     ///Refresh the data structure at a node.
    40     void refresh(Node n) 
    41     {
    42       const int bi = _start[n] = _edges.size();
    43       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
    44       const typename std::vector<Edge>::iterator ei=_edges.end();
    45       _end[n]=_edges.size();
    46       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
    47     }
    48     ///Refresh the full data structure.
    49     void refresh() 
    50     {
    51       _edges.clear();
    52       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
    53     }
    54     
    55     ///Find an edge between two nodes.
    56     
    57     ///Find an edge between two nodes.
    58     ///\param s The source node
    59     ///\param t The target node
    60     ///\return An edge from \c s to \c t if there exists,
    61     ///\ref INVALID otherwise.
    62 
    63     Edge operator()(Node s, Node t) 
    64     {
    65       int a=_start[s];
    66       int b=_end[s];
    67       while(a<b) 
    68 	{
    69 	  int n=(a+b)/2;
    70 	  Node tt = _g.target(_edges[n]);
    71 	  if(tt==t) return _edges[n];
    72 	  else if(tt<t) a=n+1;
    73 	  else b=n;
    74 	}
    75       return INVALID;
    76     }
    77 
    78     ///Find the next edge
    79       
    80       ///\warning This function is unimplemented.
    81     Edge operator()(Node s, Node t, Edge prev) 
    82     {
    83       return prev==INVALID?(*this)(s,t):INVALID;
    84     }
    85       
    86   };
    87 
    88   template<class G>
    89   class EdgeLookUp3
    90   {
    91   public:
    92     GRAPH_TYPEDEFS(typename G)
    93     typedef G Graph;
    94 
    95   private:
    96     const Graph &_g;
    97     typename Graph::template NodeMap<Edge*> _start;
    98     typename Graph::template NodeMap<Edge*> _end;
    99     std::vector<Edge> _edges;
   100     
   101     class EdgeLess {
   102       const Graph &g;
   103     public:
   104       EdgeLess(const Graph &_g) : g(_g) {}
   105       bool operator()(Edge a,Edge b) const 
   106       {
   107 	return g.target(a)<g.target(b);
   108       }
   109     };
   110     
   111   public:
   112     
   113     ///Constructor
   114     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
   115     
   116   public:
   117     ///Refresh the data structure at a node.
   118     void refresh(Node n) 
   119     {
   120       const int bi = _start[n] = _edges.size();
   121       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
   122       const typename std::vector<Edge>::iterator ei=_edges.end();
   123       _end[n]=_edges.size();
   124       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
   125     }
   126     ///Refresh the full data structure.
   127     void refresh() 
   128     {
   129       _edges.resize(countEdges(_g));
   130       int l=0;
   131       for(NodeIt n(_g);n!=INVALID;++n)
   132 	{
   133 	  int ls = l;
   134 	  _start[n]=&(_edges[l]);	
   135 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
   136 	  _end[n]=&(_edges[l]);
   137 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
   138 	}
   139       
   140     }
   141     
   142     ///Find an edge between two nodes.
   143     
   144     ///Find an edge between two nodes.
   145     ///\param s The source node
   146     ///\param t The target node
   147     ///\return An edge from \c s to \c t if there exists,
   148     ///\ref INVALID otherwise.
   149 
   150     Edge operator()(Node s, Node t) 
   151     {
   152       Edge *a=_start[s];
   153       Edge *b=_end[s];
   154       while(a!=b) 
   155 	{
   156  	  Edge *m=a+((b-a)/2);
   157 	  Node tt = _g.target(*m);
   158 	  if(tt==t) return *m;
   159 	  else if(tt<t) a=m+1;
   160 	  else b=m;
   161 	}
   162       return INVALID;
   163     }
   164 
   165     ///Find the next edge
   166       
   167       ///\warning This function is unimplemented.
   168     Edge operator()(Node s, Node t, Edge prev) 
   169     {
   170       return prev==INVALID?(*this)(s,t):INVALID;
   171     }
   172       
   173   };
   174 
   175 //   template<class G>
   176 //   class EdgeLookUp4
   177 //   {
   178 //   public:
   179 //     GRAPH_TYPEDEFS(typename G)
   180 //     typedef G Graph;
   181     
   182 //   private:
   183 //     const Graph &_g;
   184 //     typename Graph::template NodeMap<Edge*> _start;
   185 //     typename Graph::template NodeMap<Edge*> _end;
   186 //     std::vector<Edge> _edges;
   187     
   188 //     class EdgeLess {
   189 //       const Graph &g;
   190 //     public:
   191 //       EdgeLess(const Graph &_g) : g(_g) {}
   192 //       bool operator()(Edge a,Edge b) const 
   193 //       {
   194 // 	return g.target(a)<g.target(b);
   195 //       }
   196 //     };
   197     
   198 //   public:
   199     
   200 //     ///Constructor
   201 //     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
   202     
   203 //   public:
   204 //     ///Refresh the data structure at a node.
   205 //     void refresh(Node n) 
   206 //     {
   207 //       const int bi = _start[n] = _edges.size();
   208 //       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
   209 //       const typename std::vector<Edge>::iterator ei=_edges.end();
   210 //       _end[n]=_edges.size();
   211 //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
   212 //     }
   213 //     ///Refresh the full data structure.
   214 //     void refresh() 
   215 //     {
   216 //       _edges.resize(countEdges(_g));
   217 //       int l=0;
   218 //       for(NodeIt n(_g);n!=INVALID;++n)
   219 // 	{
   220 // 	  int ls = l;
   221 // 	  _start[n]=&(_edges[l]);	
   222 // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
   223 // 	  _end[n]=&(_edges[l]);
   224 // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
   225 // 	}
   226       
   227 //     }
   228     
   229 //     ///Find an edge between two nodes.
   230     
   231 //     ///Find an edge between two nodes.
   232 //     ///\param s The source node
   233 //     ///\param t The target node
   234 //     ///\return An edge from \c s to \c t if there exists,
   235 //     ///\ref INVALID otherwise.
   236 
   237 //     Edge operator()(Node s, Node t) 
   238 //     {
   239 //       Edge *a=_start[s];
   240 //       Edge *b=_end[s];
   241 //       while(a!=b) 
   242 // 	{
   243 // // #ifdef X86
   244 //  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
   245 // // #elif X86_64
   246 // // 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
   247 // // #else
   248 // //  	  Edge *m=a+((b-a)/2);
   249 // // #endif
   250 // 	  Node tt = _g.target(*m);
   251 // 	  if(tt==t) return *m;
   252 // 	  else if(tt<t) a=m+1;
   253 // 	  else b=m;
   254 // 	}
   255 //       return INVALID;
   256 //     }
   257 
   258 //     ///Find the next edge
   259       
   260 //       ///\warning This function is unimplemented.
   261 //     Edge operator()(Node s, Node t, Edge prev) 
   262 //     {
   263 //       return prev==INVALID?(*this)(s,t):INVALID;
   264 //     }
   265       
   266 //   };
   267 
   268 //   template<class G>
   269 //   class EdgeLookUp5
   270 //   {
   271 //   public:
   272 //     GRAPH_TYPEDEFS(typename G)
   273 //     typedef G Graph;
   274     
   275 //   private:
   276 //     const Graph &_g;
   277 //     typename Graph::template NodeMap<Edge*> _start;
   278 //     typename Graph::template NodeMap<Edge*> _end;
   279 //     std::vector<Edge> _edges;
   280     
   281 //     class EdgeLess {
   282 //       const Graph &g;
   283 //     public:
   284 //       EdgeLess(const Graph &_g) : g(_g) {}
   285 //       bool operator()(Edge a,Edge b) const 
   286 //       {
   287 // 	return g.target(a)<g.target(b);
   288 //       }
   289 //     };
   290     
   291 //   public:
   292     
   293 //     ///Constructor
   294 //     EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
   295     
   296 //   public:
   297 //     ///Refresh the data structure at a node.
   298 //     void refresh(Node n) 
   299 //     {
   300 //       const int bi = _start[n] = _edges.size();
   301 //       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
   302 //       const typename std::vector<Edge>::iterator ei=_edges.end();
   303 //       _end[n]=_edges.size();
   304 //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
   305 //     }
   306 //     ///Refresh the full data structure.
   307 //     void refresh() 
   308 //     {
   309 //       _edges.resize(countEdges(_g));
   310 //       int l=0;
   311 //       for(NodeIt n(_g);n!=INVALID;++n)
   312 // 	{
   313 // 	  int ls = l;
   314 // 	  _start[n]=&(_edges[l]);	
   315 // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
   316 // 	  _end[n]=&(_edges[l]);
   317 // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
   318 // 	}
   319       
   320 //     }
   321     
   322 //     ///Find an edge between two nodes.
   323     
   324 //     ///Find an edge between two nodes.
   325 //     ///\param s The source node
   326 //     ///\param t The target node
   327 //     ///\return An edge from \c s to \c t if there exists,
   328 //     ///\ref INVALID otherwise.
   329 
   330 //     Edge operator()(Node s, Node t) 
   331 //     {
   332 //       Edge *a=_start[s];
   333 //       Edge *b=_end[s];
   334 //       while(a!=b) 
   335 // 	{
   336 // // #ifdef X86
   337 //  	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
   338 // 			  & 0xfffffffc);
   339 // // #elif X86_64
   340 // // 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
   341 // // #else
   342 // //  	  Edge *m=a+((b-a)/2);
   343 // // #endif
   344 // 	  Node tt = _g.target(*m);
   345 // 	  if(tt==t) return *m;
   346 // 	  else if(tt<t) a=m+1;
   347 // 	  else b=m;
   348 // 	}
   349 //       return INVALID;
   350 //     }
   351 
   352 //     ///Find the next edge
   353       
   354 //       ///\warning This function is unimplemented.
   355 //     Edge operator()(Node s, Node t, Edge prev) 
   356 //     {
   357 //       return prev==INVALID?(*this)(s,t):INVALID;
   358 //     }
   359       
   360 //   };
   361 
   362 GRAPH_TYPEDEFS(SmartGraph)
   363 typedef SmartGraph Graph;
   364 
   365 class FE 
   366 {
   367 public:
   368   Graph &_g;
   369   FE(Graph &g) :_g(g) {}
   370   void operator()() 
   371   {
   372     Edge e;
   373     
   374     for(NodeIt v(_g);v!=INVALID;++v)
   375       for(NodeIt u(_g);u!=INVALID;++u)
   376 	e=findEdge(_g,u,v);
   377   }
   378   
   379 };
   380 
   381 class EL 
   382 {
   383 public:
   384   Graph &_g;
   385   EdgeLookUp<Graph> _el;
   386   EL(Graph &g) :_g(g), _el(g) {}
   387   void operator()() 
   388   {
   389     Edge e;
   390     
   391     for(NodeIt v(_g);v!=INVALID;++v)
   392       for(NodeIt u(_g);u!=INVALID;++u)
   393 	e=_el(u,v);
   394   }
   395   
   396 };
   397 class EL2
   398 {
   399 public:
   400   Graph &_g;
   401   EdgeLookUp2<Graph> _el;
   402   EL2(Graph &g) :_g(g), _el(g) {}
   403   void operator()() 
   404   {
   405     Edge e;
   406     
   407     for(NodeIt v(_g);v!=INVALID;++v)
   408       for(NodeIt u(_g);u!=INVALID;++u)
   409 	e=_el(u,v);
   410   }
   411   
   412 };
   413 
   414 class EL3
   415 {
   416 public:
   417   Graph &_g;
   418   EdgeLookUp3<Graph> _el;
   419   EL3(Graph &g) :_g(g), _el(g) {}
   420   void operator()() 
   421   {
   422     Edge e;
   423     
   424     for(NodeIt v(_g);v!=INVALID;++v)
   425       for(NodeIt u(_g);u!=INVALID;++u)
   426 	e=_el(u,v);
   427   }
   428   
   429 };
   430 
   431 // class EL4
   432 // {
   433 // public:
   434 //   Graph &_g;
   435 //   EdgeLookUp4<Graph> _el;
   436 //   EL4(Graph &g) :_g(g), _el(g) {}
   437 //   void operator()() 
   438 //   {
   439 //     Edge e;
   440     
   441 //     for(NodeIt v(_g);v!=INVALID;++v)
   442 //       for(NodeIt u(_g);u!=INVALID;++u)
   443 // 	e=_el(u,v);
   444 //   }
   445   
   446 // };
   447 
   448 // class EL5
   449 // {
   450 // public:
   451 //   Graph &_g;
   452 //   EdgeLookUp5<Graph> _el;
   453 //   EL5(Graph &g) :_g(g), _el(g) {}
   454 //   void operator()() 
   455 //   {
   456 //     Edge e;
   457     
   458 //     for(NodeIt v(_g);v!=INVALID;++v)
   459 //       for(NodeIt u(_g);u!=INVALID;++u)
   460 // 	e=_el(u,v);
   461 //   }
   462   
   463 // };
   464 
   465 int main(int, char**argv)
   466 {
   467   int N=atoi(argv[1]);
   468   int M=int(N*atof(argv[2]));
   469   
   470   Graph g;
   471   
   472   std::vector<Node> v;
   473   for(int i=0;i<N;i++) v.push_back(g.addNode());
   474   for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
   475 
   476 //   {
   477 //     Edge e;
   478     
   479 //     TimeReport t("findEdge: ");
   480 //     for(NodeIt u(g);u!=INVALID;++u)
   481 //       for(NodeIt v(g);v!=INVALID;++v)
   482 // 	e=findEdge(g,u,v);
   483 //   }
   484 //   {
   485 //     Edge e;
   486 //     EdgeLookUp<Graph> el(g);
   487     
   488 //     TimeReport t("EdgeLookUp: ");
   489 //     for(NodeIt u(g);u!=INVALID;++u)
   490 //       for(NodeIt v(g);v!=INVALID;++v)
   491 // 	e=el(u,v);
   492 //   }
   493 
   494 
   495   TimeStamp t1 = runningTimeTest(FE(g),1);
   496   TimeStamp t2 = runningTimeTest(EL(g),1);
   497   TimeStamp t3 = runningTimeTest(EL2(g),1);
   498   TimeStamp t4 = runningTimeTest(EL3(g),1);
   499 //   TimeStamp t5 = runningTimeTest(EL4(g),1);
   500 //   TimeStamp t6 = runningTimeTest(EL5(g),1);
   501 
   502   std::cout << t1.userTime()/N/N << ' ' 
   503 	    << t2.userTime()/N/N << ' '
   504 	    << t3.userTime()/N/N << ' '
   505 	    << t4.userTime()/N/N << ' '
   506 // 	    << t5.userTime()/N/N << ' '
   507 //  	    << t6.userTime()/N/N
   508 	    << std::endl;
   509 }
   510