lemon-0.x: benchmark/edge_lookup.cc@4d3bc1d04c1d

     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     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  */

    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>

    26 using namespace lemon;

    28   template<class G>

    29   class EdgeLookUp2

    30   {

    31   public:

    32     GRAPH_TYPEDEFS(typename G);

    33     typedef G Graph;

    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;

    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     };

    51   public:

    53     ///Constructor

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

    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     }

    73     ///Find an edge between two nodes.

    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.

    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     }

    96     ///Find the next edge

    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     }

   104   };

   106   template<class G>

   107   class EdgeLookUp3

   108   {

   109   public:

   110     GRAPH_TYPEDEFS(typename G);

   111     typedef G Graph;

   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;

   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     };

   129   public:

   131     ///Constructor

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

   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 	}

   158     }

   160     ///Find an edge between two nodes.

   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.

   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     }

   183     ///Find the next edge

   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     }

   191   };

   193 //   template<class G>

   194 //   class EdgeLookUp4

   195 //   {

   196 //   public:

   197 //     GRAPH_TYPEDEFS(typename G);

   198 //     typedef G Graph;

   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;

   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 //     };

   216 //   public:

   218 //     ///Constructor

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

   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 // 	}

   245 //     }

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

   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.

   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 //     }

   276 //     ///Find the next edge

   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 //     }

   284 //   };

   286 //   template<class G>

   287 //   class EdgeLookUp5

   288 //   {

   289 //   public:

   290 //     GRAPH_TYPEDEFS(typename G);

   291 //     typedef G Graph;

   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;

   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 //     };

   309 //   public:

   311 //     ///Constructor

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

   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 // 	}

   338 //     }

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

   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.

   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 //     }

   370 //     ///Find the next edge

   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 //     }

   378 //   };

   380 GRAPH_TYPEDEFS(SmartGraph);

   381 typedef SmartGraph Graph;

   383 class FE

   384 {

   385 public:

   386   Graph &_g;

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

   388   void operator()()

   389   {

   390     Edge e;

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

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

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

   395   }

   397 };

   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;

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

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

   411 	e=_el(u,v);

   412   }

   414 };

   416 class DEL

   417 {

   418 public:

   419   Graph &_g;

   420   DynEdgeLookUp<Graph> _el;

   421   DEL(Graph &g) :_g(g), _el(g) {}

   422   void operator()()

   423   {

   424     Edge e;

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

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

   428 	e=_el(u,v);

   429   }

   431 };

   433 class EL2

   434 {

   435 public:

   436   Graph &_g;

   437   EdgeLookUp2<Graph> _el;

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

   439   void operator()()

   440   {

   441     Edge e;

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

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

   445 	e=_el(u,v);

   446   }

   448 };

   450 class EL3

   451 {

   452 public:

   453   Graph &_g;

   454   EdgeLookUp3<Graph> _el;

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

   456   void operator()()

   457   {

   458     Edge e;

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

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

   462 	e=_el(u,v);

   463   }

   465 };

   467 // class EL4

   468 // {

   469 // public:

   470 //   Graph &_g;

   471 //   EdgeLookUp4<Graph> _el;

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

   473 //   void operator()()

   474 //   {

   475 //     Edge e;

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

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

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

   480 //   }

   482 // };

   484 // class EL5

   485 // {

   486 // public:

   487 //   Graph &_g;

   488 //   EdgeLookUp5<Graph> _el;

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

   490 //   void operator()()

   491 //   {

   492 //     Edge e;

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

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

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

   497 //   }

   499 // };

   501 int main(int, char**argv)

   502 {

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

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

   506   Graph g;

   508   std::vector<Node> v;

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

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

   512 //   {

   513 //     Edge e;

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

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

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

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

   519 //   }

   520 //   {

   521 //     Edge e;

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

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

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

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

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

   528 //   }

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

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

   533   TimeStamp t3 = runningTimeTest(DEL(g),1);

   534   TimeStamp t4 = runningTimeTest(EL2(g),1);

   535   TimeStamp t5 = runningTimeTest(EL3(g),1);

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

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

   539   std::cout << t1.userTime() << ' '

   540 	    << t2.userTime() << ' '

   541 	    << t3.userTime() << ' '

   542 	    << t4.userTime() << ' '

   543 	    << t5.userTime() << ' '

   544 // 	    << t5.userTime() << ' '

   545 //  	    << t6.userTime()

   546 	    << std::endl;

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

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

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

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

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

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

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

   554 	    << std::endl;

   555 }

author	kpeter
	Fri, 29 Feb 2008 15:57:52 +0000
changeset 2588	4d3bc1d04c1d
parent 2539	c25f62a6452d
permissions	-rw-r--r--