COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup.cc @ 2392:4bbeaf115cdb

Last change on this file since 2392:4bbeaf115cdb was 2391:14a343be7a5a, checked in by Alpar Juttner, 18 years ago

Happy New Year to all source files!

File size: 11.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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};
415class EL2
416{
417public:
418  Graph &_g;
419  EdgeLookUp2<Graph> _el;
420  EL2(Graph &g) :_g(g), _el(g) {}
421  void operator()()
422  {
423    Edge e;
424   
425    for(NodeIt v(_g);v!=INVALID;++v)
426      for(NodeIt u(_g);u!=INVALID;++u)
427        e=_el(u,v);
428  }
429 
430};
431
432class EL3
433{
434public:
435  Graph &_g;
436  EdgeLookUp3<Graph> _el;
437  EL3(Graph &g) :_g(g), _el(g) {}
438  void operator()()
439  {
440    Edge e;
441   
442    for(NodeIt v(_g);v!=INVALID;++v)
443      for(NodeIt u(_g);u!=INVALID;++u)
444        e=_el(u,v);
445  }
446 
447};
448
449// class EL4
450// {
451// public:
452//   Graph &_g;
453//   EdgeLookUp4<Graph> _el;
454//   EL4(Graph &g) :_g(g), _el(g) {}
455//   void operator()()
456//   {
457//     Edge e;
458   
459//     for(NodeIt v(_g);v!=INVALID;++v)
460//       for(NodeIt u(_g);u!=INVALID;++u)
461//      e=_el(u,v);
462//   }
463 
464// };
465
466// class EL5
467// {
468// public:
469//   Graph &_g;
470//   EdgeLookUp5<Graph> _el;
471//   EL5(Graph &g) :_g(g), _el(g) {}
472//   void operator()()
473//   {
474//     Edge e;
475   
476//     for(NodeIt v(_g);v!=INVALID;++v)
477//       for(NodeIt u(_g);u!=INVALID;++u)
478//      e=_el(u,v);
479//   }
480 
481// };
482
483int main(int, char**argv)
484{
485  int N=atoi(argv[1]);
486  int M=int(N*atof(argv[2]));
487 
488  Graph g;
489 
490  std::vector<Node> v;
491  for(int i=0;i<N;i++) v.push_back(g.addNode());
492  for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
493
494//   {
495//     Edge e;
496   
497//     TimeReport t("findEdge: ");
498//     for(NodeIt u(g);u!=INVALID;++u)
499//       for(NodeIt v(g);v!=INVALID;++v)
500//      e=findEdge(g,u,v);
501//   }
502//   {
503//     Edge e;
504//     EdgeLookUp<Graph> el(g);
505   
506//     TimeReport t("EdgeLookUp: ");
507//     for(NodeIt u(g);u!=INVALID;++u)
508//       for(NodeIt v(g);v!=INVALID;++v)
509//      e=el(u,v);
510//   }
511
512
513  TimeStamp t1 = runningTimeTest(FE(g),1);
514  TimeStamp t2 = runningTimeTest(EL(g),1);
515  TimeStamp t3 = runningTimeTest(EL2(g),1);
516  TimeStamp t4 = runningTimeTest(EL3(g),1);
517//   TimeStamp t5 = runningTimeTest(EL4(g),1);
518//   TimeStamp t6 = runningTimeTest(EL5(g),1);
519
520  std::cout << t1.userTime()/N/N << ' '
521            << t2.userTime()/N/N << ' '
522            << t3.userTime()/N/N << ' '
523            << t4.userTime()/N/N << ' '
524//          << t5.userTime()/N/N << ' '
525//          << t6.userTime()/N/N
526            << std::endl;
527}
528
Note: See TracBrowser for help on using the repository browser.