COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/benchmark/edge_lookup.cc @ 2362:eb37b9774ef6

Last change on this file since 2362:eb37b9774ef6 was 2274:432d0469a87e, checked in by Alpar Juttner, 19 years ago

Turn off 32 bit only tests, cont'd.
File size: 11.2 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
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;
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
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;
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.