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 deba
Sun, 25 Nov 2007 22:56:44 +0000
changeset 2521 05c0ba99cc27
parent 2391 14a343be7a5a
child 2539 c25f62a6452d
permissions -rw-r--r--
Bugfix: using read-write map instead reference map 
     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2007

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    18 

    19 #include<lemon/smart_graph.h>

    20 #include<vector>

    21 #include<lemon/time_measure.h>

    22 #include<lemon/random.h>

    23 #include<lemon/graph_utils.h>

    24 #include<algorithm>

    25 

    26 using namespace lemon;

    27 

    28   template<class G>

    29   class EdgeLookUp2

    30   {

    31   public:

    32     GRAPH_TYPEDEFS(typename G);

    33     typedef G Graph;

    34 

    35   private:

    36     const Graph &_g;

    37     typename Graph::template NodeMap<int> _start;

    38     typename Graph::template NodeMap<int> _end;

    39     std::vector<Edge> _edges;

    40     

    41     class EdgeLess {

    42       const Graph &g;

    43     public:

    44       EdgeLess(const Graph &_g) : g(_g) {}

    45       bool operator()(Edge a,Edge b) const 

    46       {

    47 	return g.target(a)<g.target(b);

    48       }

    49     };

    50     

    51   public:

    52     

    53     ///Constructor

    54     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

    55     

    56   public:

    57     ///Refresh the data structure at a node.

    58     void refresh(Node n) 

    59     {

    60       const int bi = _start[n] = _edges.size();

    61       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

    62       const typename std::vector<Edge>::iterator ei=_edges.end();

    63       _end[n]=_edges.size();

    64       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

    65     }

    66     ///Refresh the full data structure.

    67     void refresh() 

    68     {

    69       _edges.clear();

    70       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    71     }

    72     

    73     ///Find an edge between two nodes.

    74     

    75     ///Find an edge between two nodes.

    76     ///\param s The source node

    77     ///\param t The target node

    78     ///\return An edge from \c s to \c t if there exists,

    79     ///\ref INVALID otherwise.

    80 

    81     Edge operator()(Node s, Node t) 

    82     {

    83       int a=_start[s];

    84       int b=_end[s];

    85       while(a<b) 

    86 	{

    87 	  int n=(a+b)/2;

    88 	  Node tt = _g.target(_edges[n]);

    89 	  if(tt==t) return _edges[n];

    90 	  else if(tt<t) a=n+1;

    91 	  else b=n;

    92 	}

    93       return INVALID;

    94     }

    95 

    96     ///Find the next edge

    97       

    98       ///\warning This function is unimplemented.

    99     Edge operator()(Node s, Node t, Edge prev) 

   100     {

   101       return prev==INVALID?(*this)(s,t):INVALID;

   102     }

   103       

   104   };

   105 

   106   template<class G>

   107   class EdgeLookUp3

   108   {

   109   public:

   110     GRAPH_TYPEDEFS(typename G);

   111     typedef G Graph;

   112 

   113   private:

   114     const Graph &_g;

   115     typename Graph::template NodeMap<Edge*> _start;

   116     typename Graph::template NodeMap<Edge*> _end;

   117     std::vector<Edge> _edges;

   118     

   119     class EdgeLess {

   120       const Graph &g;

   121     public:

   122       EdgeLess(const Graph &_g) : g(_g) {}

   123       bool operator()(Edge a,Edge b) const 

   124       {

   125 	return g.target(a)<g.target(b);

   126       }

   127     };

   128     

   129   public:

   130     

   131     ///Constructor

   132     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   133     

   134   public:

   135     ///Refresh the data structure at a node.

   136     void refresh(Node n) 

   137     {

   138       const int bi = _start[n] = _edges.size();

   139       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   140       const typename std::vector<Edge>::iterator ei=_edges.end();

   141       _end[n]=_edges.size();

   142       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   143     }

   144     ///Refresh the full data structure.

   145     void refresh() 

   146     {

   147       _edges.resize(countEdges(_g));

   148       int l=0;

   149       for(NodeIt n(_g);n!=INVALID;++n)

   150 	{

   151 	  int ls = l;

   152 	  _start[n]=&(_edges[l]);	

   153 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   154 	  _end[n]=&(_edges[l]);

   155 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   156 	}

   157       

   158     }

   159     

   160     ///Find an edge between two nodes.

   161     

   162     ///Find an edge between two nodes.

   163     ///\param s The source node

   164     ///\param t The target node

   165     ///\return An edge from \c s to \c t if there exists,

   166     ///\ref INVALID otherwise.

   167 

   168     Edge operator()(Node s, Node t) 

   169     {

   170       Edge *a=_start[s];

   171       Edge *b=_end[s];

   172       while(a!=b) 

   173 	{

   174  	  Edge *m=a+((b-a)/2);

   175 	  Node tt = _g.target(*m);

   176 	  if(tt==t) return *m;

   177 	  else if(tt<t) a=m+1;

   178 	  else b=m;

   179 	}

   180       return INVALID;

   181     }

   182 

   183     ///Find the next edge

   184       

   185       ///\warning This function is unimplemented.

   186     Edge operator()(Node s, Node t, Edge prev) 

   187     {

   188       return prev==INVALID?(*this)(s,t):INVALID;

   189     }

   190       

   191   };

   192 

   193 //   template<class G>

   194 //   class EdgeLookUp4

   195 //   {

   196 //   public:

   197 //     GRAPH_TYPEDEFS(typename G);

   198 //     typedef G Graph;

   199     

   200 //   private:

   201 //     const Graph &_g;

   202 //     typename Graph::template NodeMap<Edge*> _start;

   203 //     typename Graph::template NodeMap<Edge*> _end;

   204 //     std::vector<Edge> _edges;

   205     

   206 //     class EdgeLess {

   207 //       const Graph &g;

   208 //     public:

   209 //       EdgeLess(const Graph &_g) : g(_g) {}

   210 //       bool operator()(Edge a,Edge b) const 

   211 //       {

   212 // 	return g.target(a)<g.target(b);

   213 //       }

   214 //     };

   215     

   216 //   public:

   217     

   218 //     ///Constructor

   219 //     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   220     

   221 //   public:

   222 //     ///Refresh the data structure at a node.

   223 //     void refresh(Node n) 

   224 //     {

   225 //       const int bi = _start[n] = _edges.size();

   226 //       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   227 //       const typename std::vector<Edge>::iterator ei=_edges.end();

   228 //       _end[n]=_edges.size();

   229 //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   230 //     }

   231 //     ///Refresh the full data structure.

   232 //     void refresh() 

   233 //     {

   234 //       _edges.resize(countEdges(_g));

   235 //       int l=0;

   236 //       for(NodeIt n(_g);n!=INVALID;++n)

   237 // 	{

   238 // 	  int ls = l;

   239 // 	  _start[n]=&(_edges[l]);	

   240 // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   241 // 	  _end[n]=&(_edges[l]);

   242 // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   243 // 	}

   244       

   245 //     }

   246     

   247 //     ///Find an edge between two nodes.

   248     

   249 //     ///Find an edge between two nodes.

   250 //     ///\param s The source node

   251 //     ///\param t The target node

   252 //     ///\return An edge from \c s to \c t if there exists,

   253 //     ///\ref INVALID otherwise.

   254 

   255 //     Edge operator()(Node s, Node t) 

   256 //     {

   257 //       Edge *a=_start[s];

   258 //       Edge *b=_end[s];

   259 //       while(a!=b) 

   260 // 	{

   261 // // #ifdef X86

   262 //  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);

   263 // // #elif X86_64

   264 // // 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);

   265 // // #else

   266 // //  	  Edge *m=a+((b-a)/2);

   267 // // #endif

   268 // 	  Node tt = _g.target(*m);

   269 // 	  if(tt==t) return *m;

   270 // 	  else if(tt<t) a=m+1;

   271 // 	  else b=m;

   272 // 	}

   273 //       return INVALID;

   274 //     }

   275 

   276 //     ///Find the next edge

   277       

   278 //       ///\warning This function is unimplemented.

   279 //     Edge operator()(Node s, Node t, Edge prev) 

   280 //     {

   281 //       return prev==INVALID?(*this)(s,t):INVALID;

   282 //     }

   283       

   284 //   };

   285 

   286 //   template<class G>

   287 //   class EdgeLookUp5

   288 //   {

   289 //   public:

   290 //     GRAPH_TYPEDEFS(typename G);

   291 //     typedef G Graph;

   292     

   293 //   private:

   294 //     const Graph &_g;

   295 //     typename Graph::template NodeMap<Edge*> _start;

   296 //     typename Graph::template NodeMap<Edge*> _end;

   297 //     std::vector<Edge> _edges;

   298     

   299 //     class EdgeLess {

   300 //       const Graph &g;

   301 //     public:

   302 //       EdgeLess(const Graph &_g) : g(_g) {}

   303 //       bool operator()(Edge a,Edge b) const 

   304 //       {

   305 // 	return g.target(a)<g.target(b);

   306 //       }

   307 //     };

   308     

   309 //   public:

   310     

   311 //     ///Constructor

   312 //     EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   313     

   314 //   public:

   315 //     ///Refresh the data structure at a node.

   316 //     void refresh(Node n) 

   317 //     {

   318 //       const int bi = _start[n] = _edges.size();

   319 //       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   320 //       const typename std::vector<Edge>::iterator ei=_edges.end();

   321 //       _end[n]=_edges.size();

   322 //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   323 //     }

   324 //     ///Refresh the full data structure.

   325 //     void refresh() 

   326 //     {

   327 //       _edges.resize(countEdges(_g));

   328 //       int l=0;

   329 //       for(NodeIt n(_g);n!=INVALID;++n)

   330 // 	{

   331 // 	  int ls = l;

   332 // 	  _start[n]=&(_edges[l]);	

   333 // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   334 // 	  _end[n]=&(_edges[l]);

   335 // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   336 // 	}

   337       

   338 //     }

   339     

   340 //     ///Find an edge between two nodes.

   341     

   342 //     ///Find an edge between two nodes.

   343 //     ///\param s The source node

   344 //     ///\param t The target node

   345 //     ///\return An edge from \c s to \c t if there exists,

   346 //     ///\ref INVALID otherwise.

   347 

   348 //     Edge operator()(Node s, Node t) 

   349 //     {

   350 //       Edge *a=_start[s];

   351 //       Edge *b=_end[s];

   352 //       while(a!=b) 

   353 // 	{

   354 // // #ifdef X86

   355 //  	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)

   356 // 			  & 0xfffffffc);

   357 // // #elif X86_64

   358 // // 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);

   359 // // #else

   360 // //  	  Edge *m=a+((b-a)/2);

   361 // // #endif

   362 // 	  Node tt = _g.target(*m);

   363 // 	  if(tt==t) return *m;

   364 // 	  else if(tt<t) a=m+1;

   365 // 	  else b=m;

   366 // 	}

   367 //       return INVALID;

   368 //     }

   369 

   370 //     ///Find the next edge

   371       

   372 //       ///\warning This function is unimplemented.

   373 //     Edge operator()(Node s, Node t, Edge prev) 

   374 //     {

   375 //       return prev==INVALID?(*this)(s,t):INVALID;

   376 //     }

   377       

   378 //   };

   379 

   380 GRAPH_TYPEDEFS(SmartGraph);

   381 typedef SmartGraph Graph;

   382 

   383 class FE 

   384 {

   385 public:

   386   Graph &_g;

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

   388   void operator()() 

   389   {

   390     Edge e;

   391     

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

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

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

   395   }

   396   

   397 };

   398 

   399 class EL 

   400 {

   401 public:

   402   Graph &_g;

   403   EdgeLookUp<Graph> _el;

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

   405   void operator()() 

   406   {

   407     Edge e;

   408     

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

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

   411 	e=_el(u,v);

   412   }

   413   

   414 };

   415 class EL2

   416 {

   417 public:

   418   Graph &_g;

   419   EdgeLookUp2<Graph> _el;

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

   421   void operator()() 

   422   {

   423     Edge e;

   424     

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

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

   427 	e=_el(u,v);

   428   }

   429   

   430 };

   431 

   432 class EL3

   433 {

   434 public:

   435   Graph &_g;

   436   EdgeLookUp3<Graph> _el;

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

   438   void operator()() 

   439   {

   440     Edge e;

   441     

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

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

   444 	e=_el(u,v);

   445   }

   446   

   447 };

   448 

   449 // class EL4

   450 // {

   451 // public:

   452 //   Graph &_g;

   453 //   EdgeLookUp4<Graph> _el;

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

   455 //   void operator()() 

   456 //   {

   457 //     Edge e;

   458     

   459 //     for(NodeIt v(_g);v!=INVALID;++v)

   460 //       for(NodeIt u(_g);u!=INVALID;++u)

   461 // 	e=_el(u,v);

   462 //   }

   463   

   464 // };

   465 

   466 // class EL5

   467 // {

   468 // public:

   469 //   Graph &_g;

   470 //   EdgeLookUp5<Graph> _el;

   471 //   EL5(Graph &g) :_g(g), _el(g) {}

   472 //   void operator()() 

   473 //   {

   474 //     Edge e;

   475     

   476 //     for(NodeIt v(_g);v!=INVALID;++v)

   477 //       for(NodeIt u(_g);u!=INVALID;++u)

   478 // 	e=_el(u,v);

   479 //   }

   480   

   481 // };

   482 

   483 int main(int, char**argv)

   484 {

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

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

   487   

   488   Graph g;

   489   

   490   std::vector<Node> v;

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

   492   for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);

   493 

   494 //   {

   495 //     Edge e;

   496     

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

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

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

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

   501 //   }

   502 //   {

   503 //     Edge e;

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

   505     

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

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

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

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

   510 //   }

   511 

   512 

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

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

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

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

   517 //   TimeStamp t5 = runningTimeTest(EL4(g),1);

   518 //   TimeStamp t6 = runningTimeTest(EL5(g),1);

   519 

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

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

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

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

   524 // 	    << t5.userTime()/N/N << ' '

   525 //  	    << t6.userTime()/N/N

   526 	    << std::endl;

   527 }

   528
lemon-0.x