|
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 |
|
7 using namespace lemon; |
|
8 |
|
9 GRAPH_TYPEDEFS(SmartGraph) |
|
10 typedef SmartGraph Graph; |
|
11 |
|
12 class FE |
|
13 { |
|
14 public: |
|
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 |
|
28 class EL |
|
29 { |
|
30 public: |
|
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 }; |
|
44 class EL2 |
|
45 { |
|
46 public: |
|
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 |
|
61 class EL3 |
|
62 { |
|
63 public: |
|
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 |
|
78 class EL4 |
|
79 { |
|
80 public: |
|
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 |
|
95 int 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 |