lemon-0.x: benchmark/edge_lookup.cc@bd09e00b64bb

     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>

     8 using namespace lemon;

    10   template<class G>

    11   class EdgeLookUp2

    12   {

    13   public:

    14     GRAPH_TYPEDEFS(typename G)

    15     typedef G Graph;

    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;

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

    33   public:

    35     ///Constructor

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

    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     }

    55     ///Find an edge between two nodes.

    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.

    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     }

    78     ///Find the next edge

    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     }

    86   };

    88   template<class G>

    89   class EdgeLookUp3

    90   {

    91   public:

    92     GRAPH_TYPEDEFS(typename G)

    93     typedef G Graph;

    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;

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

   111   public:

   113     ///Constructor

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

   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 	}

   140     }

   142     ///Find an edge between two nodes.

   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.

   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     }

   165     ///Find the next edge

   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     }

   173   };

   175 //   template<class G>

   176 //   class EdgeLookUp4

   177 //   {

   178 //   public:

   179 //     GRAPH_TYPEDEFS(typename G)

   180 //     typedef G Graph;

   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;

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

   198 //   public:

   200 //     ///Constructor

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

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

   227 //     }

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

   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.

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

   258 //     ///Find the next edge

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

   266 //   };

   268 //   template<class G>

   269 //   class EdgeLookUp5

   270 //   {

   271 //   public:

   272 //     GRAPH_TYPEDEFS(typename G)

   273 //     typedef G Graph;

   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;

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

   291 //   public:

   293 //     ///Constructor

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

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

   320 //     }

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

   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.

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

   352 //     ///Find the next edge

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

   360 //   };

   362 GRAPH_TYPEDEFS(SmartGraph)

   363 typedef SmartGraph Graph;

   365 class FE

   366 {

   367 public:

   368   Graph &_g;

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

   370   void operator()()

   371   {

   372     Edge e;

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

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

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

   377   }

   379 };

   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;

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

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

   393 	e=_el(u,v);

   394   }

   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;

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

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

   409 	e=_el(u,v);

   410   }

   412 };

   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;

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

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

   426 	e=_el(u,v);

   427   }

   429 };

   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;

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

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

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

   444 //   }

   446 // };

   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;

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

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

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

   461 //   }

   463 // };

   465 int main(int, char**argv)

   466 {

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

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

   470   Graph g;

   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]]);

   476 //   {

   477 //     Edge e;

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

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

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

   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 }

author	deba
	Wed, 29 Nov 2006 17:34:29 +0000
changeset 2315	bd09e00b64bb
parent 2272	f6b352fdc6b1
child 2391	14a343be7a5a
permissions	-rw-r--r--