COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup.cc @ 2235:48801095a410

Last change on this file since 2235:48801095a410 was 2235:48801095a410, checked in by Alpar Juttner, 17 years ago

EdgeLookUp? and AllEdgeLookUp? added.

File size: 2.3 KB
Line 
1// #include<lemon/edge_lookup.h>
2#include<lemon/edge_lookup_test.h>
3#include<lemon/smart_graph.h>
4#include<vector>
5#include<lemon/time_measure.h>
6
7using namespace lemon;
8
9GRAPH_TYPEDEFS(SmartGraph)
10typedef SmartGraph Graph;
11
12class FE
13{
14public:
15  Graph &_g;
16  FE(Graph &g) :_g(g) {}
17  void operator()()
18  {
19    Edge e;
20   
21    for(NodeIt v(_g);v!=INVALID;++v)
22      for(NodeIt u(_g);u!=INVALID;++u)
23        e=findEdge(_g,u,v);
24  }
25 
26};
27
28class EL
29{
30public:
31  Graph &_g;
32  EdgeLookUp<Graph> _el;
33  EL(Graph &g) :_g(g), _el(g) {}
34  void operator()()
35  {
36    Edge e;
37   
38    for(NodeIt v(_g);v!=INVALID;++v)
39      for(NodeIt u(_g);u!=INVALID;++u)
40        e=_el(u,v);
41  }
42 
43};
44class EL2
45{
46public:
47  Graph &_g;
48  EdgeLookUp2<Graph> _el;
49  EL2(Graph &g) :_g(g), _el(g) {}
50  void operator()()
51  {
52    Edge e;
53   
54    for(NodeIt v(_g);v!=INVALID;++v)
55      for(NodeIt u(_g);u!=INVALID;++u)
56        e=_el(u,v);
57  }
58 
59};
60
61class EL3
62{
63public:
64  Graph &_g;
65  EdgeLookUp3<Graph> _el;
66  EL3(Graph &g) :_g(g), _el(g) {}
67  void operator()()
68  {
69    Edge e;
70   
71    for(NodeIt v(_g);v!=INVALID;++v)
72      for(NodeIt u(_g);u!=INVALID;++u)
73        e=_el(u,v);
74  }
75 
76};
77
78class EL4
79{
80public:
81  Graph &_g;
82  EdgeLookUp4<Graph> _el;
83  EL4(Graph &g) :_g(g), _el(g) {}
84  void operator()()
85  {
86    Edge e;
87   
88    for(NodeIt v(_g);v!=INVALID;++v)
89      for(NodeIt u(_g);u!=INVALID;++u)
90        e=_el(u,v);
91  }
92 
93};
94
95int main(int argc, char**argv)
96{
97  int N=atoi(argv[1]);
98  int M=int(N*atof(argv[2]));
99 
100  Graph g;
101 
102  std::vector<Node> v;
103  for(int i=0;i<N;i++) v.push_back(g.addNode());
104  for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*N)]);
105
106//   {
107//     Edge e;
108   
109//     TimeReport t("findEdge: ");
110//     for(NodeIt u(g);u!=INVALID;++u)
111//       for(NodeIt v(g);v!=INVALID;++v)
112//      e=findEdge(g,u,v);
113//   }
114//   {
115//     Edge e;
116//     EdgeLookUp<Graph> el(g);
117   
118//     TimeReport t("EdgeLookUp: ");
119//     for(NodeIt u(g);u!=INVALID;++u)
120//       for(NodeIt v(g);v!=INVALID;++v)
121//      e=el(u,v);
122//   }
123
124
125  TimeStamp t1 = runningTimeTest(FE(g),1);
126  TimeStamp t2 = runningTimeTest(EL(g),1);
127  TimeStamp t3 = runningTimeTest(EL2(g),1);
128  TimeStamp t4 = runningTimeTest(EL3(g),1);
129  TimeStamp t5 = runningTimeTest(EL4(g),1);
130
131  std::cout << t1.userTime()/N/N << ' '
132            << t2.userTime()/N/N << ' '
133            << t3.userTime()/N/N << ' '
134            << t4.userTime()/N/N << ' '
135            << t5.userTime()/N/N << std::endl;
136}
137
Note: See TracBrowser for help on using the repository browser.