COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup.cc @ 2539:c25f62a6452d

Last change on this file since 2539:c25f62a6452d was 2539:c25f62a6452d, checked in by Balazs Dezso, 11 years ago

DynEdgeLookUp? implementation based on splay trees
In general case it is slower than the static version, but it should not
refreshed on the change of the graph

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