benchmark/edge_lookup.cc
author kpeter
Fri, 29 Feb 2008 15:55:13 +0000
changeset 2586 37fb2c384c78
parent 2539 c25f62a6452d
permissions -rw-r--r--
Reimplemented Suurballe class.

- The new version is the specialized version of CapacityScaling.
- It is about 10-20 times faster than the former Suurballe algorithm
and about 20-50 percent faster than CapacityScaling.
- Doc improvements.
- The test file is also replaced.
     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  */
    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 
   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;
   425     
   426     for(NodeIt v(_g);v!=INVALID;++v)
   427       for(NodeIt u(_g);u!=INVALID;++u)
   428 	e=_el(u,v);
   429   }
   430   
   431 };
   432 
   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;
   442     
   443     for(NodeIt v(_g);v!=INVALID;++v)
   444       for(NodeIt u(_g);u!=INVALID;++u)
   445 	e=_el(u,v);
   446   }
   447   
   448 };
   449 
   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;
   459     
   460     for(NodeIt v(_g);v!=INVALID;++v)
   461       for(NodeIt u(_g);u!=INVALID;++u)
   462 	e=_el(u,v);
   463   }
   464   
   465 };
   466 
   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;
   476     
   477 //     for(NodeIt v(_g);v!=INVALID;++v)
   478 //       for(NodeIt u(_g);u!=INVALID;++u)
   479 // 	e=_el(u,v);
   480 //   }
   481   
   482 // };
   483 
   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;
   493     
   494 //     for(NodeIt v(_g);v!=INVALID;++v)
   495 //       for(NodeIt u(_g);u!=INVALID;++u)
   496 // 	e=_el(u,v);
   497 //   }
   498   
   499 // };
   500 
   501 int main(int, char**argv)
   502 {
   503   int N=atoi(argv[1]);
   504   int M=int(N*atof(argv[2]));
   505   
   506   Graph g;
   507   
   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]]);
   511 
   512 //   {
   513 //     Edge e;
   514     
   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);
   523     
   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 //   }
   529 
   530 
   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);
   538 
   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 }
   556