COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup.cc @ 2271:a2ab63454152

Last change on this file since 2271:a2ab63454152 was 2271:a2ab63454152, checked in by Alpar Juttner, 17 years ago

repository cleanup

File size: 10.7 KB
Line 
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>
7
8using namespace lemon;
9
10  template<class G>
11  class EdgeLookUp2
12  {
13  public:
14    GRAPH_TYPEDEFS(typename G)
15    typedef G Graph;
16
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;
22   
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    };
32   
33  public:
34   
35    ///Constructor
36    EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
37   
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    }
54   
55    ///Find an edge between two nodes.
56   
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.
62
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    }
77
78    ///Find the next edge
79     
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    }
85     
86  };
87
88  template<class G>
89  class EdgeLookUp3
90  {
91  public:
92    GRAPH_TYPEDEFS(typename G)
93    typedef G Graph;
94
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;
100   
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    };
110   
111  public:
112   
113    ///Constructor
114    EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
115   
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        }
139     
140    }
141   
142    ///Find an edge between two nodes.
143   
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.
149
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    }
164
165    ///Find the next edge
166     
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    }
172     
173  };
174
175  template<class G>
176  class EdgeLookUp4
177  {
178  public:
179    GRAPH_TYPEDEFS(typename G)
180    typedef G Graph;
181   
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;
187   
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    };
197   
198  public:
199   
200    ///Constructor
201    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
202   
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        }
226     
227    }
228   
229    ///Find an edge between two nodes.
230   
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.
236
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    }
257
258    ///Find the next edge
259     
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    }
265     
266  };
267
268  template<class G>
269  class EdgeLookUp5
270  {
271  public:
272    GRAPH_TYPEDEFS(typename G)
273    typedef G Graph;
274   
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;
280   
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    };
290   
291  public:
292   
293    ///Constructor
294    EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
295   
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        }
319     
320    }
321   
322    ///Find an edge between two nodes.
323   
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.
329
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    }
351
352    ///Find the next edge
353     
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    }
359     
360  };
361
362GRAPH_TYPEDEFS(SmartGraph)
363typedef SmartGraph Graph;
364
365class FE
366{
367public:
368  Graph &_g;
369  FE(Graph &g) :_g(g) {}
370  void operator()()
371  {
372    Edge e;
373   
374    for(NodeIt v(_g);v!=INVALID;++v)
375      for(NodeIt u(_g);u!=INVALID;++u)
376        e=findEdge(_g,u,v);
377  }
378 
379};
380
381class EL
382{
383public:
384  Graph &_g;
385  EdgeLookUp<Graph> _el;
386  EL(Graph &g) :_g(g), _el(g) {}
387  void operator()()
388  {
389    Edge e;
390   
391    for(NodeIt v(_g);v!=INVALID;++v)
392      for(NodeIt u(_g);u!=INVALID;++u)
393        e=_el(u,v);
394  }
395 
396};
397class EL2
398{
399public:
400  Graph &_g;
401  EdgeLookUp2<Graph> _el;
402  EL2(Graph &g) :_g(g), _el(g) {}
403  void operator()()
404  {
405    Edge e;
406   
407    for(NodeIt v(_g);v!=INVALID;++v)
408      for(NodeIt u(_g);u!=INVALID;++u)
409        e=_el(u,v);
410  }
411 
412};
413
414class EL3
415{
416public:
417  Graph &_g;
418  EdgeLookUp3<Graph> _el;
419  EL3(Graph &g) :_g(g), _el(g) {}
420  void operator()()
421  {
422    Edge e;
423   
424    for(NodeIt v(_g);v!=INVALID;++v)
425      for(NodeIt u(_g);u!=INVALID;++u)
426        e=_el(u,v);
427  }
428 
429};
430
431class EL4
432{
433public:
434  Graph &_g;
435  EdgeLookUp4<Graph> _el;
436  EL4(Graph &g) :_g(g), _el(g) {}
437  void operator()()
438  {
439    Edge e;
440   
441    for(NodeIt v(_g);v!=INVALID;++v)
442      for(NodeIt u(_g);u!=INVALID;++u)
443        e=_el(u,v);
444  }
445 
446};
447
448class EL5
449{
450public:
451  Graph &_g;
452  EdgeLookUp5<Graph> _el;
453  EL5(Graph &g) :_g(g), _el(g) {}
454  void operator()()
455  {
456    Edge e;
457   
458    for(NodeIt v(_g);v!=INVALID;++v)
459      for(NodeIt u(_g);u!=INVALID;++u)
460        e=_el(u,v);
461  }
462 
463};
464
465int main(int, char**argv)
466{
467  int N=atoi(argv[1]);
468  int M=int(N*atof(argv[2]));
469 
470  Graph g;
471 
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]]);
475
476//   {
477//     Edge e;
478   
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);
487   
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//   }
493
494
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);
501
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}
510
Note: See TracBrowser for help on using the repository browser.