1 #include<lemon/smart_graph.h>
3 #include<lemon/time_measure.h>
4 #include<lemon/random.h>
5 #include<lemon/graph_utils.h>
14 GRAPH_TYPEDEFS(typename G)
19 typename Graph::template NodeMap<int> _start;
20 typename Graph::template NodeMap<int> _end;
21 std::vector<Edge> _edges;
26 EdgeLess(const Graph &_g) : g(_g) {}
27 bool operator()(Edge a,Edge b) const
29 return g.target(a)<g.target(b);
36 EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
39 ///Refresh the data structure at a node.
42 const int bi = _start[n] = _edges.size();
43 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
44 const typename std::vector<Edge>::iterator ei=_edges.end();
45 _end[n]=_edges.size();
46 std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
48 ///Refresh the full data structure.
52 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
55 ///Find an edge between two nodes.
57 ///Find an edge between two nodes.
58 ///\param s The source node
59 ///\param t The target node
60 ///\return An edge from \c s to \c t if there exists,
61 ///\ref INVALID otherwise.
63 Edge operator()(Node s, Node t)
70 Node tt = _g.target(_edges[n]);
71 if(tt==t) return _edges[n];
80 ///\warning This function is unimplemented.
81 Edge operator()(Node s, Node t, Edge prev)
83 return prev==INVALID?(*this)(s,t):INVALID;
92 GRAPH_TYPEDEFS(typename G)
97 typename Graph::template NodeMap<Edge*> _start;
98 typename Graph::template NodeMap<Edge*> _end;
99 std::vector<Edge> _edges;
104 EdgeLess(const Graph &_g) : g(_g) {}
105 bool operator()(Edge a,Edge b) const
107 return g.target(a)<g.target(b);
114 EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
117 ///Refresh the data structure at a node.
120 const int bi = _start[n] = _edges.size();
121 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
122 const typename std::vector<Edge>::iterator ei=_edges.end();
123 _end[n]=_edges.size();
124 std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
126 ///Refresh the full data structure.
129 _edges.resize(countEdges(_g));
131 for(NodeIt n(_g);n!=INVALID;++n)
134 _start[n]=&(_edges[l]);
135 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
136 _end[n]=&(_edges[l]);
137 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
142 ///Find an edge between two nodes.
144 ///Find an edge between two nodes.
145 ///\param s The source node
146 ///\param t The target node
147 ///\return An edge from \c s to \c t if there exists,
148 ///\ref INVALID otherwise.
150 Edge operator()(Node s, Node t)
157 Node tt = _g.target(*m);
165 ///Find the next edge
167 ///\warning This function is unimplemented.
168 Edge operator()(Node s, Node t, Edge prev)
170 return prev==INVALID?(*this)(s,t):INVALID;
179 // GRAPH_TYPEDEFS(typename G)
184 // typename Graph::template NodeMap<Edge*> _start;
185 // typename Graph::template NodeMap<Edge*> _end;
186 // std::vector<Edge> _edges;
191 // EdgeLess(const Graph &_g) : g(_g) {}
192 // bool operator()(Edge a,Edge b) const
194 // return g.target(a)<g.target(b);
201 // EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
204 // ///Refresh the data structure at a node.
205 // void refresh(Node n)
207 // const int bi = _start[n] = _edges.size();
208 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
209 // const typename std::vector<Edge>::iterator ei=_edges.end();
210 // _end[n]=_edges.size();
211 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
213 // ///Refresh the full data structure.
216 // _edges.resize(countEdges(_g));
218 // for(NodeIt n(_g);n!=INVALID;++n)
221 // _start[n]=&(_edges[l]);
222 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
223 // _end[n]=&(_edges[l]);
224 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
229 // ///Find an edge between two nodes.
231 // ///Find an edge between two nodes.
232 // ///\param s The source node
233 // ///\param t The target node
234 // ///\return An edge from \c s to \c t if there exists,
235 // ///\ref INVALID otherwise.
237 // Edge operator()(Node s, Node t)
239 // Edge *a=_start[s];
244 // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
246 // // Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
248 // // Edge *m=a+((b-a)/2);
250 // Node tt = _g.target(*m);
251 // if(tt==t) return *m;
252 // else if(tt<t) a=m+1;
258 // ///Find the next edge
260 // ///\warning This function is unimplemented.
261 // Edge operator()(Node s, Node t, Edge prev)
263 // return prev==INVALID?(*this)(s,t):INVALID;
272 // GRAPH_TYPEDEFS(typename G)
277 // typename Graph::template NodeMap<Edge*> _start;
278 // typename Graph::template NodeMap<Edge*> _end;
279 // std::vector<Edge> _edges;
284 // EdgeLess(const Graph &_g) : g(_g) {}
285 // bool operator()(Edge a,Edge b) const
287 // return g.target(a)<g.target(b);
294 // EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
297 // ///Refresh the data structure at a node.
298 // void refresh(Node n)
300 // const int bi = _start[n] = _edges.size();
301 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
302 // const typename std::vector<Edge>::iterator ei=_edges.end();
303 // _end[n]=_edges.size();
304 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
306 // ///Refresh the full data structure.
309 // _edges.resize(countEdges(_g));
311 // for(NodeIt n(_g);n!=INVALID;++n)
314 // _start[n]=&(_edges[l]);
315 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
316 // _end[n]=&(_edges[l]);
317 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
322 // ///Find an edge between two nodes.
324 // ///Find an edge between two nodes.
325 // ///\param s The source node
326 // ///\param t The target node
327 // ///\return An edge from \c s to \c t if there exists,
328 // ///\ref INVALID otherwise.
330 // Edge operator()(Node s, Node t)
332 // Edge *a=_start[s];
337 // Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
340 // // Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
342 // // Edge *m=a+((b-a)/2);
344 // Node tt = _g.target(*m);
345 // if(tt==t) return *m;
346 // else if(tt<t) a=m+1;
352 // ///Find the next edge
354 // ///\warning This function is unimplemented.
355 // Edge operator()(Node s, Node t, Edge prev)
357 // return prev==INVALID?(*this)(s,t):INVALID;
362 GRAPH_TYPEDEFS(SmartGraph)
363 typedef SmartGraph Graph;
369 FE(Graph &g) :_g(g) {}
374 for(NodeIt v(_g);v!=INVALID;++v)
375 for(NodeIt u(_g);u!=INVALID;++u)
385 EdgeLookUp<Graph> _el;
386 EL(Graph &g) :_g(g), _el(g) {}
391 for(NodeIt v(_g);v!=INVALID;++v)
392 for(NodeIt u(_g);u!=INVALID;++u)
401 EdgeLookUp2<Graph> _el;
402 EL2(Graph &g) :_g(g), _el(g) {}
407 for(NodeIt v(_g);v!=INVALID;++v)
408 for(NodeIt u(_g);u!=INVALID;++u)
418 EdgeLookUp3<Graph> _el;
419 EL3(Graph &g) :_g(g), _el(g) {}
424 for(NodeIt v(_g);v!=INVALID;++v)
425 for(NodeIt u(_g);u!=INVALID;++u)
435 // EdgeLookUp4<Graph> _el;
436 // EL4(Graph &g) :_g(g), _el(g) {}
441 // for(NodeIt v(_g);v!=INVALID;++v)
442 // for(NodeIt u(_g);u!=INVALID;++u)
452 // EdgeLookUp5<Graph> _el;
453 // EL5(Graph &g) :_g(g), _el(g) {}
458 // for(NodeIt v(_g);v!=INVALID;++v)
459 // for(NodeIt u(_g);u!=INVALID;++u)
465 int main(int, char**argv)
468 int M=int(N*atof(argv[2]));
473 for(int i=0;i<N;i++) v.push_back(g.addNode());
474 for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
479 // TimeReport t("findEdge: ");
480 // for(NodeIt u(g);u!=INVALID;++u)
481 // for(NodeIt v(g);v!=INVALID;++v)
482 // e=findEdge(g,u,v);
486 // EdgeLookUp<Graph> el(g);
488 // TimeReport t("EdgeLookUp: ");
489 // for(NodeIt u(g);u!=INVALID;++u)
490 // for(NodeIt v(g);v!=INVALID;++v)
495 TimeStamp t1 = runningTimeTest(FE(g),1);
496 TimeStamp t2 = runningTimeTest(EL(g),1);
497 TimeStamp t3 = runningTimeTest(EL2(g),1);
498 TimeStamp t4 = runningTimeTest(EL3(g),1);
499 // TimeStamp t5 = runningTimeTest(EL4(g),1);
500 // TimeStamp t6 = runningTimeTest(EL5(g),1);
502 std::cout << t1.userTime()/N/N << ' '
503 << t2.userTime()/N/N << ' '
504 << t3.userTime()/N/N << ' '
505 << t4.userTime()/N/N << ' '
506 // << t5.userTime()/N/N << ' '
507 // << t6.userTime()/N/N