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