1.1 --- a/benchmark/edge_lookup.cc Mon Oct 30 12:25:43 2006 +0000
1.2 +++ b/benchmark/edge_lookup.cc Mon Oct 30 15:23:35 2006 +0000
1.3 @@ -1,11 +1,364 @@
1.4 -#include"edge_lookup_test.h"
1.5 #include<lemon/smart_graph.h>
1.6 #include<vector>
1.7 #include<lemon/time_measure.h>
1.8 #include<lemon/random.h>
1.9 +#include<lemon/graph_utils.h>
1.10 +#include<algorithm>
1.11
1.12 using namespace lemon;
1.13
1.14 + template<class G>
1.15 + class EdgeLookUp2
1.16 + {
1.17 + public:
1.18 + GRAPH_TYPEDEFS(typename G)
1.19 + typedef G Graph;
1.20 +
1.21 + private:
1.22 + const Graph &_g;
1.23 + typename Graph::template NodeMap<int> _start;
1.24 + typename Graph::template NodeMap<int> _end;
1.25 + std::vector<Edge> _edges;
1.26 +
1.27 + class EdgeLess {
1.28 + const Graph &g;
1.29 + public:
1.30 + EdgeLess(const Graph &_g) : g(_g) {}
1.31 + bool operator()(Edge a,Edge b) const
1.32 + {
1.33 + return g.target(a)<g.target(b);
1.34 + }
1.35 + };
1.36 +
1.37 + public:
1.38 +
1.39 + ///Constructor
1.40 + EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.41 +
1.42 + public:
1.43 + ///Refresh the data structure at a node.
1.44 + void refresh(Node n)
1.45 + {
1.46 + const int bi = _start[n] = _edges.size();
1.47 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.48 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.49 + _end[n]=_edges.size();
1.50 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.51 + }
1.52 + ///Refresh the full data structure.
1.53 + void refresh()
1.54 + {
1.55 + _edges.clear();
1.56 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.57 + }
1.58 +
1.59 + ///Find an edge between two nodes.
1.60 +
1.61 + ///Find an edge between two nodes.
1.62 + ///\param s The source node
1.63 + ///\param t The target node
1.64 + ///\return An edge from \c s to \c t if there exists,
1.65 + ///\ref INVALID otherwise.
1.66 +
1.67 + Edge operator()(Node s, Node t)
1.68 + {
1.69 + int a=_start[s];
1.70 + int b=_end[s];
1.71 + while(a<b)
1.72 + {
1.73 + int n=(a+b)/2;
1.74 + Node tt = _g.target(_edges[n]);
1.75 + if(tt==t) return _edges[n];
1.76 + else if(tt<t) a=n+1;
1.77 + else b=n;
1.78 + }
1.79 + return INVALID;
1.80 + }
1.81 +
1.82 + ///Find the next edge
1.83 +
1.84 + ///\warning This function is unimplemented.
1.85 + Edge operator()(Node s, Node t, Edge prev)
1.86 + {
1.87 + return prev==INVALID?(*this)(s,t):INVALID;
1.88 + }
1.89 +
1.90 + };
1.91 +
1.92 + template<class G>
1.93 + class EdgeLookUp3
1.94 + {
1.95 + public:
1.96 + GRAPH_TYPEDEFS(typename G)
1.97 + typedef G Graph;
1.98 +
1.99 + private:
1.100 + const Graph &_g;
1.101 + typename Graph::template NodeMap<Edge*> _start;
1.102 + typename Graph::template NodeMap<Edge*> _end;
1.103 + std::vector<Edge> _edges;
1.104 +
1.105 + class EdgeLess {
1.106 + const Graph &g;
1.107 + public:
1.108 + EdgeLess(const Graph &_g) : g(_g) {}
1.109 + bool operator()(Edge a,Edge b) const
1.110 + {
1.111 + return g.target(a)<g.target(b);
1.112 + }
1.113 + };
1.114 +
1.115 + public:
1.116 +
1.117 + ///Constructor
1.118 + EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.119 +
1.120 + public:
1.121 + ///Refresh the data structure at a node.
1.122 + void refresh(Node n)
1.123 + {
1.124 + const int bi = _start[n] = _edges.size();
1.125 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.126 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.127 + _end[n]=_edges.size();
1.128 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.129 + }
1.130 + ///Refresh the full data structure.
1.131 + void refresh()
1.132 + {
1.133 + _edges.resize(countEdges(_g));
1.134 + int l=0;
1.135 + for(NodeIt n(_g);n!=INVALID;++n)
1.136 + {
1.137 + int ls = l;
1.138 + _start[n]=&(_edges[l]);
1.139 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.140 + _end[n]=&(_edges[l]);
1.141 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.142 + }
1.143 +
1.144 + }
1.145 +
1.146 + ///Find an edge between two nodes.
1.147 +
1.148 + ///Find an edge between two nodes.
1.149 + ///\param s The source node
1.150 + ///\param t The target node
1.151 + ///\return An edge from \c s to \c t if there exists,
1.152 + ///\ref INVALID otherwise.
1.153 +
1.154 + Edge operator()(Node s, Node t)
1.155 + {
1.156 + Edge *a=_start[s];
1.157 + Edge *b=_end[s];
1.158 + while(a!=b)
1.159 + {
1.160 + Edge *m=a+((b-a)/2);
1.161 + Node tt = _g.target(*m);
1.162 + if(tt==t) return *m;
1.163 + else if(tt<t) a=m+1;
1.164 + else b=m;
1.165 + }
1.166 + return INVALID;
1.167 + }
1.168 +
1.169 + ///Find the next edge
1.170 +
1.171 + ///\warning This function is unimplemented.
1.172 + Edge operator()(Node s, Node t, Edge prev)
1.173 + {
1.174 + return prev==INVALID?(*this)(s,t):INVALID;
1.175 + }
1.176 +
1.177 + };
1.178 +
1.179 + template<class G>
1.180 + class EdgeLookUp4
1.181 + {
1.182 + public:
1.183 + GRAPH_TYPEDEFS(typename G)
1.184 + typedef G Graph;
1.185 +
1.186 + private:
1.187 + const Graph &_g;
1.188 + typename Graph::template NodeMap<Edge*> _start;
1.189 + typename Graph::template NodeMap<Edge*> _end;
1.190 + std::vector<Edge> _edges;
1.191 +
1.192 + class EdgeLess {
1.193 + const Graph &g;
1.194 + public:
1.195 + EdgeLess(const Graph &_g) : g(_g) {}
1.196 + bool operator()(Edge a,Edge b) const
1.197 + {
1.198 + return g.target(a)<g.target(b);
1.199 + }
1.200 + };
1.201 +
1.202 + public:
1.203 +
1.204 + ///Constructor
1.205 + EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.206 +
1.207 + public:
1.208 + ///Refresh the data structure at a node.
1.209 + void refresh(Node n)
1.210 + {
1.211 + const int bi = _start[n] = _edges.size();
1.212 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.213 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.214 + _end[n]=_edges.size();
1.215 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.216 + }
1.217 + ///Refresh the full data structure.
1.218 + void refresh()
1.219 + {
1.220 + _edges.resize(countEdges(_g));
1.221 + int l=0;
1.222 + for(NodeIt n(_g);n!=INVALID;++n)
1.223 + {
1.224 + int ls = l;
1.225 + _start[n]=&(_edges[l]);
1.226 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.227 + _end[n]=&(_edges[l]);
1.228 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.229 + }
1.230 +
1.231 + }
1.232 +
1.233 + ///Find an edge between two nodes.
1.234 +
1.235 + ///Find an edge between two nodes.
1.236 + ///\param s The source node
1.237 + ///\param t The target node
1.238 + ///\return An edge from \c s to \c t if there exists,
1.239 + ///\ref INVALID otherwise.
1.240 +
1.241 + Edge operator()(Node s, Node t)
1.242 + {
1.243 + Edge *a=_start[s];
1.244 + Edge *b=_end[s];
1.245 + while(a!=b)
1.246 + {
1.247 +// #ifdef X86
1.248 + Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.249 +// #elif X86_64
1.250 +// Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
1.251 +// #else
1.252 +// Edge *m=a+((b-a)/2);
1.253 +// #endif
1.254 + Node tt = _g.target(*m);
1.255 + if(tt==t) return *m;
1.256 + else if(tt<t) a=m+1;
1.257 + else b=m;
1.258 + }
1.259 + return INVALID;
1.260 + }
1.261 +
1.262 + ///Find the next edge
1.263 +
1.264 + ///\warning This function is unimplemented.
1.265 + Edge operator()(Node s, Node t, Edge prev)
1.266 + {
1.267 + return prev==INVALID?(*this)(s,t):INVALID;
1.268 + }
1.269 +
1.270 + };
1.271 +
1.272 + template<class G>
1.273 + class EdgeLookUp5
1.274 + {
1.275 + public:
1.276 + GRAPH_TYPEDEFS(typename G)
1.277 + typedef G Graph;
1.278 +
1.279 + private:
1.280 + const Graph &_g;
1.281 + typename Graph::template NodeMap<Edge*> _start;
1.282 + typename Graph::template NodeMap<Edge*> _end;
1.283 + std::vector<Edge> _edges;
1.284 +
1.285 + class EdgeLess {
1.286 + const Graph &g;
1.287 + public:
1.288 + EdgeLess(const Graph &_g) : g(_g) {}
1.289 + bool operator()(Edge a,Edge b) const
1.290 + {
1.291 + return g.target(a)<g.target(b);
1.292 + }
1.293 + };
1.294 +
1.295 + public:
1.296 +
1.297 + ///Constructor
1.298 + EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.299 +
1.300 + public:
1.301 + ///Refresh the data structure at a node.
1.302 + void refresh(Node n)
1.303 + {
1.304 + const int bi = _start[n] = _edges.size();
1.305 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.306 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.307 + _end[n]=_edges.size();
1.308 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.309 + }
1.310 + ///Refresh the full data structure.
1.311 + void refresh()
1.312 + {
1.313 + _edges.resize(countEdges(_g));
1.314 + int l=0;
1.315 + for(NodeIt n(_g);n!=INVALID;++n)
1.316 + {
1.317 + int ls = l;
1.318 + _start[n]=&(_edges[l]);
1.319 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.320 + _end[n]=&(_edges[l]);
1.321 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.322 + }
1.323 +
1.324 + }
1.325 +
1.326 + ///Find an edge between two nodes.
1.327 +
1.328 + ///Find an edge between two nodes.
1.329 + ///\param s The source node
1.330 + ///\param t The target node
1.331 + ///\return An edge from \c s to \c t if there exists,
1.332 + ///\ref INVALID otherwise.
1.333 +
1.334 + Edge operator()(Node s, Node t)
1.335 + {
1.336 + Edge *a=_start[s];
1.337 + Edge *b=_end[s];
1.338 + while(a!=b)
1.339 + {
1.340 +// #ifdef X86
1.341 + Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
1.342 + & 0xfffffffc);
1.343 +// #elif X86_64
1.344 +// Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
1.345 +// #else
1.346 +// Edge *m=a+((b-a)/2);
1.347 +// #endif
1.348 + Node tt = _g.target(*m);
1.349 + if(tt==t) return *m;
1.350 + else if(tt<t) a=m+1;
1.351 + else b=m;
1.352 + }
1.353 + return INVALID;
1.354 + }
1.355 +
1.356 + ///Find the next edge
1.357 +
1.358 + ///\warning This function is unimplemented.
1.359 + Edge operator()(Node s, Node t, Edge prev)
1.360 + {
1.361 + return prev==INVALID?(*this)(s,t):INVALID;
1.362 + }
1.363 +
1.364 + };
1.365 +
1.366 GRAPH_TYPEDEFS(SmartGraph)
1.367 typedef SmartGraph Graph;
1.368
1.369 @@ -92,6 +445,23 @@
1.370
1.371 };
1.372
1.373 +class EL5
1.374 +{
1.375 +public:
1.376 + Graph &_g;
1.377 + EdgeLookUp5<Graph> _el;
1.378 + EL5(Graph &g) :_g(g), _el(g) {}
1.379 + void operator()()
1.380 + {
1.381 + Edge e;
1.382 +
1.383 + for(NodeIt v(_g);v!=INVALID;++v)
1.384 + for(NodeIt u(_g);u!=INVALID;++u)
1.385 + e=_el(u,v);
1.386 + }
1.387 +
1.388 +};
1.389 +
1.390 int main(int, char**argv)
1.391 {
1.392 int N=atoi(argv[1]);
1.393 @@ -126,13 +496,15 @@
1.394 TimeStamp t2 = runningTimeTest(EL(g),1);
1.395 TimeStamp t3 = runningTimeTest(EL2(g),1);
1.396 TimeStamp t4 = runningTimeTest(EL3(g),1);
1.397 -// TimeStamp t5 = runningTimeTest(EL4(g),1);
1.398 + TimeStamp t5 = runningTimeTest(EL4(g),1);
1.399 + TimeStamp t6 = runningTimeTest(EL5(g),1);
1.400
1.401 std::cout << t1.userTime()/N/N << ' '
1.402 << t2.userTime()/N/N << ' '
1.403 << t3.userTime()/N/N << ' '
1.404 << t4.userTime()/N/N << ' '
1.405 -// << t5.userTime()/N/N
1.406 + << t5.userTime()/N/N << ' '
1.407 + << t6.userTime()/N/N
1.408 << std::endl;
1.409 }
1.410