alpar@2235
|
1 |
#include<lemon/smart_graph.h>
|
alpar@2235
|
2 |
#include<vector>
|
alpar@2235
|
3 |
#include<lemon/time_measure.h>
|
deba@2242
|
4 |
#include<lemon/random.h>
|
alpar@2271
|
5 |
#include<lemon/graph_utils.h>
|
alpar@2271
|
6 |
#include<algorithm>
|
alpar@2235
|
7 |
|
alpar@2235
|
8 |
using namespace lemon;
|
alpar@2235
|
9 |
|
alpar@2271
|
10 |
template<class G>
|
alpar@2271
|
11 |
class EdgeLookUp2
|
alpar@2271
|
12 |
{
|
alpar@2271
|
13 |
public:
|
alpar@2271
|
14 |
GRAPH_TYPEDEFS(typename G)
|
alpar@2271
|
15 |
typedef G Graph;
|
alpar@2271
|
16 |
|
alpar@2271
|
17 |
private:
|
alpar@2271
|
18 |
const Graph &_g;
|
alpar@2271
|
19 |
typename Graph::template NodeMap<int> _start;
|
alpar@2271
|
20 |
typename Graph::template NodeMap<int> _end;
|
alpar@2271
|
21 |
std::vector<Edge> _edges;
|
alpar@2271
|
22 |
|
alpar@2271
|
23 |
class EdgeLess {
|
alpar@2271
|
24 |
const Graph &g;
|
alpar@2271
|
25 |
public:
|
alpar@2271
|
26 |
EdgeLess(const Graph &_g) : g(_g) {}
|
alpar@2271
|
27 |
bool operator()(Edge a,Edge b) const
|
alpar@2271
|
28 |
{
|
alpar@2271
|
29 |
return g.target(a)<g.target(b);
|
alpar@2271
|
30 |
}
|
alpar@2271
|
31 |
};
|
alpar@2271
|
32 |
|
alpar@2271
|
33 |
public:
|
alpar@2271
|
34 |
|
alpar@2271
|
35 |
///Constructor
|
alpar@2271
|
36 |
EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
|
alpar@2271
|
37 |
|
alpar@2271
|
38 |
public:
|
alpar@2271
|
39 |
///Refresh the data structure at a node.
|
alpar@2271
|
40 |
void refresh(Node n)
|
alpar@2271
|
41 |
{
|
alpar@2271
|
42 |
const int bi = _start[n] = _edges.size();
|
alpar@2271
|
43 |
for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
|
alpar@2271
|
44 |
const typename std::vector<Edge>::iterator ei=_edges.end();
|
alpar@2271
|
45 |
_end[n]=_edges.size();
|
alpar@2271
|
46 |
std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
|
alpar@2271
|
47 |
}
|
alpar@2271
|
48 |
///Refresh the full data structure.
|
alpar@2271
|
49 |
void refresh()
|
alpar@2271
|
50 |
{
|
alpar@2271
|
51 |
_edges.clear();
|
alpar@2271
|
52 |
for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
|
alpar@2271
|
53 |
}
|
alpar@2271
|
54 |
|
alpar@2271
|
55 |
///Find an edge between two nodes.
|
alpar@2271
|
56 |
|
alpar@2271
|
57 |
///Find an edge between two nodes.
|
alpar@2271
|
58 |
///\param s The source node
|
alpar@2271
|
59 |
///\param t The target node
|
alpar@2271
|
60 |
///\return An edge from \c s to \c t if there exists,
|
alpar@2271
|
61 |
///\ref INVALID otherwise.
|
alpar@2271
|
62 |
|
alpar@2271
|
63 |
Edge operator()(Node s, Node t)
|
alpar@2271
|
64 |
{
|
alpar@2271
|
65 |
int a=_start[s];
|
alpar@2271
|
66 |
int b=_end[s];
|
alpar@2271
|
67 |
while(a<b)
|
alpar@2271
|
68 |
{
|
alpar@2271
|
69 |
int n=(a+b)/2;
|
alpar@2271
|
70 |
Node tt = _g.target(_edges[n]);
|
alpar@2271
|
71 |
if(tt==t) return _edges[n];
|
alpar@2271
|
72 |
else if(tt<t) a=n+1;
|
alpar@2271
|
73 |
else b=n;
|
alpar@2271
|
74 |
}
|
alpar@2271
|
75 |
return INVALID;
|
alpar@2271
|
76 |
}
|
alpar@2271
|
77 |
|
alpar@2271
|
78 |
///Find the next edge
|
alpar@2271
|
79 |
|
alpar@2271
|
80 |
///\warning This function is unimplemented.
|
alpar@2271
|
81 |
Edge operator()(Node s, Node t, Edge prev)
|
alpar@2271
|
82 |
{
|
alpar@2271
|
83 |
return prev==INVALID?(*this)(s,t):INVALID;
|
alpar@2271
|
84 |
}
|
alpar@2271
|
85 |
|
alpar@2271
|
86 |
};
|
alpar@2271
|
87 |
|
alpar@2271
|
88 |
template<class G>
|
alpar@2271
|
89 |
class EdgeLookUp3
|
alpar@2271
|
90 |
{
|
alpar@2271
|
91 |
public:
|
alpar@2271
|
92 |
GRAPH_TYPEDEFS(typename G)
|
alpar@2271
|
93 |
typedef G Graph;
|
alpar@2271
|
94 |
|
alpar@2271
|
95 |
private:
|
alpar@2271
|
96 |
const Graph &_g;
|
alpar@2271
|
97 |
typename Graph::template NodeMap<Edge*> _start;
|
alpar@2271
|
98 |
typename Graph::template NodeMap<Edge*> _end;
|
alpar@2271
|
99 |
std::vector<Edge> _edges;
|
alpar@2271
|
100 |
|
alpar@2271
|
101 |
class EdgeLess {
|
alpar@2271
|
102 |
const Graph &g;
|
alpar@2271
|
103 |
public:
|
alpar@2271
|
104 |
EdgeLess(const Graph &_g) : g(_g) {}
|
alpar@2271
|
105 |
bool operator()(Edge a,Edge b) const
|
alpar@2271
|
106 |
{
|
alpar@2271
|
107 |
return g.target(a)<g.target(b);
|
alpar@2271
|
108 |
}
|
alpar@2271
|
109 |
};
|
alpar@2271
|
110 |
|
alpar@2271
|
111 |
public:
|
alpar@2271
|
112 |
|
alpar@2271
|
113 |
///Constructor
|
alpar@2271
|
114 |
EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
|
alpar@2271
|
115 |
|
alpar@2271
|
116 |
public:
|
alpar@2271
|
117 |
///Refresh the data structure at a node.
|
alpar@2271
|
118 |
void refresh(Node n)
|
alpar@2271
|
119 |
{
|
alpar@2271
|
120 |
const int bi = _start[n] = _edges.size();
|
alpar@2271
|
121 |
for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
|
alpar@2271
|
122 |
const typename std::vector<Edge>::iterator ei=_edges.end();
|
alpar@2271
|
123 |
_end[n]=_edges.size();
|
alpar@2271
|
124 |
std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
|
alpar@2271
|
125 |
}
|
alpar@2271
|
126 |
///Refresh the full data structure.
|
alpar@2271
|
127 |
void refresh()
|
alpar@2271
|
128 |
{
|
alpar@2271
|
129 |
_edges.resize(countEdges(_g));
|
alpar@2271
|
130 |
int l=0;
|
alpar@2271
|
131 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@2271
|
132 |
{
|
alpar@2271
|
133 |
int ls = l;
|
alpar@2271
|
134 |
_start[n]=&(_edges[l]);
|
alpar@2271
|
135 |
for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
|
alpar@2271
|
136 |
_end[n]=&(_edges[l]);
|
alpar@2271
|
137 |
std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
|
alpar@2271
|
138 |
}
|
alpar@2271
|
139 |
|
alpar@2271
|
140 |
}
|
alpar@2271
|
141 |
|
alpar@2271
|
142 |
///Find an edge between two nodes.
|
alpar@2271
|
143 |
|
alpar@2271
|
144 |
///Find an edge between two nodes.
|
alpar@2271
|
145 |
///\param s The source node
|
alpar@2271
|
146 |
///\param t The target node
|
alpar@2271
|
147 |
///\return An edge from \c s to \c t if there exists,
|
alpar@2271
|
148 |
///\ref INVALID otherwise.
|
alpar@2271
|
149 |
|
alpar@2271
|
150 |
Edge operator()(Node s, Node t)
|
alpar@2271
|
151 |
{
|
alpar@2271
|
152 |
Edge *a=_start[s];
|
alpar@2271
|
153 |
Edge *b=_end[s];
|
alpar@2271
|
154 |
while(a!=b)
|
alpar@2271
|
155 |
{
|
alpar@2271
|
156 |
Edge *m=a+((b-a)/2);
|
alpar@2271
|
157 |
Node tt = _g.target(*m);
|
alpar@2271
|
158 |
if(tt==t) return *m;
|
alpar@2271
|
159 |
else if(tt<t) a=m+1;
|
alpar@2271
|
160 |
else b=m;
|
alpar@2271
|
161 |
}
|
alpar@2271
|
162 |
return INVALID;
|
alpar@2271
|
163 |
}
|
alpar@2271
|
164 |
|
alpar@2271
|
165 |
///Find the next edge
|
alpar@2271
|
166 |
|
alpar@2271
|
167 |
///\warning This function is unimplemented.
|
alpar@2271
|
168 |
Edge operator()(Node s, Node t, Edge prev)
|
alpar@2271
|
169 |
{
|
alpar@2271
|
170 |
return prev==INVALID?(*this)(s,t):INVALID;
|
alpar@2271
|
171 |
}
|
alpar@2271
|
172 |
|
alpar@2271
|
173 |
};
|
alpar@2271
|
174 |
|
alpar@2272
|
175 |
// template<class G>
|
alpar@2272
|
176 |
// class EdgeLookUp4
|
alpar@2272
|
177 |
// {
|
alpar@2272
|
178 |
// public:
|
alpar@2272
|
179 |
// GRAPH_TYPEDEFS(typename G)
|
alpar@2272
|
180 |
// typedef G Graph;
|
alpar@2271
|
181 |
|
alpar@2272
|
182 |
// private:
|
alpar@2272
|
183 |
// const Graph &_g;
|
alpar@2272
|
184 |
// typename Graph::template NodeMap<Edge*> _start;
|
alpar@2272
|
185 |
// typename Graph::template NodeMap<Edge*> _end;
|
alpar@2272
|
186 |
// std::vector<Edge> _edges;
|
alpar@2271
|
187 |
|
alpar@2272
|
188 |
// class EdgeLess {
|
alpar@2272
|
189 |
// const Graph &g;
|
alpar@2272
|
190 |
// public:
|
alpar@2272
|
191 |
// EdgeLess(const Graph &_g) : g(_g) {}
|
alpar@2272
|
192 |
// bool operator()(Edge a,Edge b) const
|
alpar@2272
|
193 |
// {
|
alpar@2272
|
194 |
// return g.target(a)<g.target(b);
|
alpar@2272
|
195 |
// }
|
alpar@2272
|
196 |
// };
|
alpar@2271
|
197 |
|
alpar@2272
|
198 |
// public:
|
alpar@2271
|
199 |
|
alpar@2272
|
200 |
// ///Constructor
|
alpar@2272
|
201 |
// EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
|
alpar@2271
|
202 |
|
alpar@2272
|
203 |
// public:
|
alpar@2272
|
204 |
// ///Refresh the data structure at a node.
|
alpar@2272
|
205 |
// void refresh(Node n)
|
alpar@2272
|
206 |
// {
|
alpar@2272
|
207 |
// const int bi = _start[n] = _edges.size();
|
alpar@2272
|
208 |
// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
|
alpar@2272
|
209 |
// const typename std::vector<Edge>::iterator ei=_edges.end();
|
alpar@2272
|
210 |
// _end[n]=_edges.size();
|
alpar@2272
|
211 |
// std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
|
alpar@2272
|
212 |
// }
|
alpar@2272
|
213 |
// ///Refresh the full data structure.
|
alpar@2272
|
214 |
// void refresh()
|
alpar@2272
|
215 |
// {
|
alpar@2272
|
216 |
// _edges.resize(countEdges(_g));
|
alpar@2272
|
217 |
// int l=0;
|
alpar@2272
|
218 |
// for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@2272
|
219 |
// {
|
alpar@2272
|
220 |
// int ls = l;
|
alpar@2272
|
221 |
// _start[n]=&(_edges[l]);
|
alpar@2272
|
222 |
// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
|
alpar@2272
|
223 |
// _end[n]=&(_edges[l]);
|
alpar@2272
|
224 |
// std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
|
alpar@2272
|
225 |
// }
|
alpar@2271
|
226 |
|
alpar@2272
|
227 |
// }
|
alpar@2271
|
228 |
|
alpar@2272
|
229 |
// ///Find an edge between two nodes.
|
alpar@2271
|
230 |
|
alpar@2272
|
231 |
// ///Find an edge between two nodes.
|
alpar@2272
|
232 |
// ///\param s The source node
|
alpar@2272
|
233 |
// ///\param t The target node
|
alpar@2272
|
234 |
// ///\return An edge from \c s to \c t if there exists,
|
alpar@2272
|
235 |
// ///\ref INVALID otherwise.
|
alpar@2271
|
236 |
|
alpar@2272
|
237 |
// Edge operator()(Node s, Node t)
|
alpar@2272
|
238 |
// {
|
alpar@2272
|
239 |
// Edge *a=_start[s];
|
alpar@2272
|
240 |
// Edge *b=_end[s];
|
alpar@2272
|
241 |
// while(a!=b)
|
alpar@2272
|
242 |
// {
|
alpar@2272
|
243 |
// // #ifdef X86
|
alpar@2272
|
244 |
// Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
|
alpar@2272
|
245 |
// // #elif X86_64
|
alpar@2272
|
246 |
// // Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
|
alpar@2272
|
247 |
// // #else
|
alpar@2272
|
248 |
// // Edge *m=a+((b-a)/2);
|
alpar@2272
|
249 |
// // #endif
|
alpar@2272
|
250 |
// Node tt = _g.target(*m);
|
alpar@2272
|
251 |
// if(tt==t) return *m;
|
alpar@2272
|
252 |
// else if(tt<t) a=m+1;
|
alpar@2272
|
253 |
// else b=m;
|
alpar@2272
|
254 |
// }
|
alpar@2272
|
255 |
// return INVALID;
|
alpar@2272
|
256 |
// }
|
alpar@2271
|
257 |
|
alpar@2272
|
258 |
// ///Find the next edge
|
alpar@2271
|
259 |
|
alpar@2272
|
260 |
// ///\warning This function is unimplemented.
|
alpar@2272
|
261 |
// Edge operator()(Node s, Node t, Edge prev)
|
alpar@2272
|
262 |
// {
|
alpar@2272
|
263 |
// return prev==INVALID?(*this)(s,t):INVALID;
|
alpar@2272
|
264 |
// }
|
alpar@2271
|
265 |
|
alpar@2272
|
266 |
// };
|
alpar@2271
|
267 |
|
alpar@2272
|
268 |
// template<class G>
|
alpar@2272
|
269 |
// class EdgeLookUp5
|
alpar@2272
|
270 |
// {
|
alpar@2272
|
271 |
// public:
|
alpar@2272
|
272 |
// GRAPH_TYPEDEFS(typename G)
|
alpar@2272
|
273 |
// typedef G Graph;
|
alpar@2271
|
274 |
|
alpar@2272
|
275 |
// private:
|
alpar@2272
|
276 |
// const Graph &_g;
|
alpar@2272
|
277 |
// typename Graph::template NodeMap<Edge*> _start;
|
alpar@2272
|
278 |
// typename Graph::template NodeMap<Edge*> _end;
|
alpar@2272
|
279 |
// std::vector<Edge> _edges;
|
alpar@2271
|
280 |
|
alpar@2272
|
281 |
// class EdgeLess {
|
alpar@2272
|
282 |
// const Graph &g;
|
alpar@2272
|
283 |
// public:
|
alpar@2272
|
284 |
// EdgeLess(const Graph &_g) : g(_g) {}
|
alpar@2272
|
285 |
// bool operator()(Edge a,Edge b) const
|
alpar@2272
|
286 |
// {
|
alpar@2272
|
287 |
// return g.target(a)<g.target(b);
|
alpar@2272
|
288 |
// }
|
alpar@2272
|
289 |
// };
|
alpar@2271
|
290 |
|
alpar@2272
|
291 |
// public:
|
alpar@2271
|
292 |
|
alpar@2272
|
293 |
// ///Constructor
|
alpar@2272
|
294 |
// EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
|
alpar@2271
|
295 |
|
alpar@2272
|
296 |
// public:
|
alpar@2272
|
297 |
// ///Refresh the data structure at a node.
|
alpar@2272
|
298 |
// void refresh(Node n)
|
alpar@2272
|
299 |
// {
|
alpar@2272
|
300 |
// const int bi = _start[n] = _edges.size();
|
alpar@2272
|
301 |
// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
|
alpar@2272
|
302 |
// const typename std::vector<Edge>::iterator ei=_edges.end();
|
alpar@2272
|
303 |
// _end[n]=_edges.size();
|
alpar@2272
|
304 |
// std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
|
alpar@2272
|
305 |
// }
|
alpar@2272
|
306 |
// ///Refresh the full data structure.
|
alpar@2272
|
307 |
// void refresh()
|
alpar@2272
|
308 |
// {
|
alpar@2272
|
309 |
// _edges.resize(countEdges(_g));
|
alpar@2272
|
310 |
// int l=0;
|
alpar@2272
|
311 |
// for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@2272
|
312 |
// {
|
alpar@2272
|
313 |
// int ls = l;
|
alpar@2272
|
314 |
// _start[n]=&(_edges[l]);
|
alpar@2272
|
315 |
// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
|
alpar@2272
|
316 |
// _end[n]=&(_edges[l]);
|
alpar@2272
|
317 |
// std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
|
alpar@2272
|
318 |
// }
|
alpar@2271
|
319 |
|
alpar@2272
|
320 |
// }
|
alpar@2271
|
321 |
|
alpar@2272
|
322 |
// ///Find an edge between two nodes.
|
alpar@2271
|
323 |
|
alpar@2272
|
324 |
// ///Find an edge between two nodes.
|
alpar@2272
|
325 |
// ///\param s The source node
|
alpar@2272
|
326 |
// ///\param t The target node
|
alpar@2272
|
327 |
// ///\return An edge from \c s to \c t if there exists,
|
alpar@2272
|
328 |
// ///\ref INVALID otherwise.
|
alpar@2271
|
329 |
|
alpar@2272
|
330 |
// Edge operator()(Node s, Node t)
|
alpar@2272
|
331 |
// {
|
alpar@2272
|
332 |
// Edge *a=_start[s];
|
alpar@2272
|
333 |
// Edge *b=_end[s];
|
alpar@2272
|
334 |
// while(a!=b)
|
alpar@2272
|
335 |
// {
|
alpar@2272
|
336 |
// // #ifdef X86
|
alpar@2272
|
337 |
// Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
|
alpar@2272
|
338 |
// & 0xfffffffc);
|
alpar@2272
|
339 |
// // #elif X86_64
|
alpar@2272
|
340 |
// // Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
|
alpar@2272
|
341 |
// // #else
|
alpar@2272
|
342 |
// // Edge *m=a+((b-a)/2);
|
alpar@2272
|
343 |
// // #endif
|
alpar@2272
|
344 |
// Node tt = _g.target(*m);
|
alpar@2272
|
345 |
// if(tt==t) return *m;
|
alpar@2272
|
346 |
// else if(tt<t) a=m+1;
|
alpar@2272
|
347 |
// else b=m;
|
alpar@2272
|
348 |
// }
|
alpar@2272
|
349 |
// return INVALID;
|
alpar@2272
|
350 |
// }
|
alpar@2271
|
351 |
|
alpar@2272
|
352 |
// ///Find the next edge
|
alpar@2271
|
353 |
|
alpar@2272
|
354 |
// ///\warning This function is unimplemented.
|
alpar@2272
|
355 |
// Edge operator()(Node s, Node t, Edge prev)
|
alpar@2272
|
356 |
// {
|
alpar@2272
|
357 |
// return prev==INVALID?(*this)(s,t):INVALID;
|
alpar@2272
|
358 |
// }
|
alpar@2271
|
359 |
|
alpar@2272
|
360 |
// };
|
alpar@2271
|
361 |
|
alpar@2235
|
362 |
GRAPH_TYPEDEFS(SmartGraph)
|
alpar@2235
|
363 |
typedef SmartGraph Graph;
|
alpar@2235
|
364 |
|
alpar@2235
|
365 |
class FE
|
alpar@2235
|
366 |
{
|
alpar@2235
|
367 |
public:
|
alpar@2235
|
368 |
Graph &_g;
|
alpar@2235
|
369 |
FE(Graph &g) :_g(g) {}
|
alpar@2235
|
370 |
void operator()()
|
alpar@2235
|
371 |
{
|
alpar@2235
|
372 |
Edge e;
|
alpar@2235
|
373 |
|
alpar@2235
|
374 |
for(NodeIt v(_g);v!=INVALID;++v)
|
alpar@2235
|
375 |
for(NodeIt u(_g);u!=INVALID;++u)
|
alpar@2235
|
376 |
e=findEdge(_g,u,v);
|
alpar@2235
|
377 |
}
|
alpar@2235
|
378 |
|
alpar@2235
|
379 |
};
|
alpar@2235
|
380 |
|
alpar@2235
|
381 |
class EL
|
alpar@2235
|
382 |
{
|
alpar@2235
|
383 |
public:
|
alpar@2235
|
384 |
Graph &_g;
|
alpar@2235
|
385 |
EdgeLookUp<Graph> _el;
|
alpar@2235
|
386 |
EL(Graph &g) :_g(g), _el(g) {}
|
alpar@2235
|
387 |
void operator()()
|
alpar@2235
|
388 |
{
|
alpar@2235
|
389 |
Edge e;
|
alpar@2235
|
390 |
|
alpar@2235
|
391 |
for(NodeIt v(_g);v!=INVALID;++v)
|
alpar@2235
|
392 |
for(NodeIt u(_g);u!=INVALID;++u)
|
alpar@2235
|
393 |
e=_el(u,v);
|
alpar@2235
|
394 |
}
|
alpar@2235
|
395 |
|
alpar@2235
|
396 |
};
|
alpar@2235
|
397 |
class EL2
|
alpar@2235
|
398 |
{
|
alpar@2235
|
399 |
public:
|
alpar@2235
|
400 |
Graph &_g;
|
alpar@2235
|
401 |
EdgeLookUp2<Graph> _el;
|
alpar@2235
|
402 |
EL2(Graph &g) :_g(g), _el(g) {}
|
alpar@2235
|
403 |
void operator()()
|
alpar@2235
|
404 |
{
|
alpar@2235
|
405 |
Edge e;
|
alpar@2235
|
406 |
|
alpar@2235
|
407 |
for(NodeIt v(_g);v!=INVALID;++v)
|
alpar@2235
|
408 |
for(NodeIt u(_g);u!=INVALID;++u)
|
alpar@2235
|
409 |
e=_el(u,v);
|
alpar@2235
|
410 |
}
|
alpar@2235
|
411 |
|
alpar@2235
|
412 |
};
|
alpar@2235
|
413 |
|
alpar@2235
|
414 |
class EL3
|
alpar@2235
|
415 |
{
|
alpar@2235
|
416 |
public:
|
alpar@2235
|
417 |
Graph &_g;
|
alpar@2235
|
418 |
EdgeLookUp3<Graph> _el;
|
alpar@2235
|
419 |
EL3(Graph &g) :_g(g), _el(g) {}
|
alpar@2235
|
420 |
void operator()()
|
alpar@2235
|
421 |
{
|
alpar@2235
|
422 |
Edge e;
|
alpar@2235
|
423 |
|
alpar@2235
|
424 |
for(NodeIt v(_g);v!=INVALID;++v)
|
alpar@2235
|
425 |
for(NodeIt u(_g);u!=INVALID;++u)
|
alpar@2235
|
426 |
e=_el(u,v);
|
alpar@2235
|
427 |
}
|
alpar@2235
|
428 |
|
alpar@2235
|
429 |
};
|
alpar@2235
|
430 |
|
alpar@2252
|
431 |
class EL4
|
alpar@2252
|
432 |
{
|
alpar@2252
|
433 |
public:
|
alpar@2252
|
434 |
Graph &_g;
|
alpar@2252
|
435 |
EdgeLookUp4<Graph> _el;
|
alpar@2252
|
436 |
EL4(Graph &g) :_g(g), _el(g) {}
|
alpar@2252
|
437 |
void operator()()
|
alpar@2252
|
438 |
{
|
alpar@2252
|
439 |
Edge e;
|
alpar@2235
|
440 |
|
alpar@2252
|
441 |
for(NodeIt v(_g);v!=INVALID;++v)
|
alpar@2252
|
442 |
for(NodeIt u(_g);u!=INVALID;++u)
|
alpar@2252
|
443 |
e=_el(u,v);
|
alpar@2252
|
444 |
}
|
alpar@2235
|
445 |
|
alpar@2252
|
446 |
};
|
alpar@2235
|
447 |
|
alpar@2271
|
448 |
class EL5
|
alpar@2271
|
449 |
{
|
alpar@2271
|
450 |
public:
|
alpar@2271
|
451 |
Graph &_g;
|
alpar@2271
|
452 |
EdgeLookUp5<Graph> _el;
|
alpar@2271
|
453 |
EL5(Graph &g) :_g(g), _el(g) {}
|
alpar@2271
|
454 |
void operator()()
|
alpar@2271
|
455 |
{
|
alpar@2271
|
456 |
Edge e;
|
alpar@2271
|
457 |
|
alpar@2271
|
458 |
for(NodeIt v(_g);v!=INVALID;++v)
|
alpar@2271
|
459 |
for(NodeIt u(_g);u!=INVALID;++u)
|
alpar@2271
|
460 |
e=_el(u,v);
|
alpar@2271
|
461 |
}
|
alpar@2271
|
462 |
|
alpar@2271
|
463 |
};
|
alpar@2271
|
464 |
|
alpar@2238
|
465 |
int main(int, char**argv)
|
alpar@2235
|
466 |
{
|
alpar@2235
|
467 |
int N=atoi(argv[1]);
|
alpar@2235
|
468 |
int M=int(N*atof(argv[2]));
|
alpar@2235
|
469 |
|
alpar@2235
|
470 |
Graph g;
|
alpar@2235
|
471 |
|
alpar@2235
|
472 |
std::vector<Node> v;
|
alpar@2235
|
473 |
for(int i=0;i<N;i++) v.push_back(g.addNode());
|
deba@2242
|
474 |
for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
|
alpar@2235
|
475 |
|
alpar@2235
|
476 |
// {
|
alpar@2235
|
477 |
// Edge e;
|
alpar@2235
|
478 |
|
alpar@2235
|
479 |
// TimeReport t("findEdge: ");
|
alpar@2235
|
480 |
// for(NodeIt u(g);u!=INVALID;++u)
|
alpar@2235
|
481 |
// for(NodeIt v(g);v!=INVALID;++v)
|
alpar@2235
|
482 |
// e=findEdge(g,u,v);
|
alpar@2235
|
483 |
// }
|
alpar@2235
|
484 |
// {
|
alpar@2235
|
485 |
// Edge e;
|
alpar@2235
|
486 |
// EdgeLookUp<Graph> el(g);
|
alpar@2235
|
487 |
|
alpar@2235
|
488 |
// TimeReport t("EdgeLookUp: ");
|
alpar@2235
|
489 |
// for(NodeIt u(g);u!=INVALID;++u)
|
alpar@2235
|
490 |
// for(NodeIt v(g);v!=INVALID;++v)
|
alpar@2235
|
491 |
// e=el(u,v);
|
alpar@2235
|
492 |
// }
|
alpar@2235
|
493 |
|
alpar@2235
|
494 |
|
alpar@2235
|
495 |
TimeStamp t1 = runningTimeTest(FE(g),1);
|
alpar@2235
|
496 |
TimeStamp t2 = runningTimeTest(EL(g),1);
|
alpar@2235
|
497 |
TimeStamp t3 = runningTimeTest(EL2(g),1);
|
alpar@2235
|
498 |
TimeStamp t4 = runningTimeTest(EL3(g),1);
|
alpar@2272
|
499 |
// TimeStamp t5 = runningTimeTest(EL4(g),1);
|
alpar@2272
|
500 |
// TimeStamp t6 = runningTimeTest(EL5(g),1);
|
alpar@2235
|
501 |
|
alpar@2235
|
502 |
std::cout << t1.userTime()/N/N << ' '
|
alpar@2235
|
503 |
<< t2.userTime()/N/N << ' '
|
alpar@2235
|
504 |
<< t3.userTime()/N/N << ' '
|
alpar@2235
|
505 |
<< t4.userTime()/N/N << ' '
|
alpar@2272
|
506 |
// << t5.userTime()/N/N << ' '
|
alpar@2272
|
507 |
// << t6.userTime()/N/N
|
alpar@2240
|
508 |
<< std::endl;
|
alpar@2235
|
509 |
}
|
alpar@2235
|
510 |
|