COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup.cc @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 11 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 12.4 KB
Line 
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
26using 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
380GRAPH_TYPEDEFS(SmartGraph);
381typedef SmartGraph Graph;
382
383class FE
384{
385public:
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
399class EL
400{
401public:
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
416class DEL
417{
418public:
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
433class EL2
434{
435public:
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
450class EL3
451{
452public:
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
501int 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
Note: See TracBrowser for help on using the repository browser.