Changeset 2272:f6b352fdc6b1 in lemon0.x for benchmark/edge_lookup.cc
 Timestamp:
 10/30/06 16:29:50 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3034
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

benchmark/edge_lookup.cc
r2271 r2272 173 173 }; 174 174 175 template<class G>176 class EdgeLookUp4177 {178 public:179 GRAPH_TYPEDEFS(typename G)180 typedef G Graph;181 182 private:183 const Graph &_g;184 typename Graph::template NodeMap<Edge*> _start;185 typename Graph::template NodeMap<Edge*> _end;186 std::vector<Edge> _edges;187 188 class EdgeLess {189 const Graph &g;190 public:191 EdgeLess(const Graph &_g) : g(_g) {}192 bool operator()(Edge a,Edge b) const193 {194 return g.target(a)<g.target(b);195 }196 };197 198 public:199 200 ///Constructor201 EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}202 203 public:204 ///Refresh the data structure at a node.205 void refresh(Node n)206 {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));212 }213 ///Refresh the full data structure.214 void refresh()215 {216 _edges.resize(countEdges(_g));217 int l=0;218 for(NodeIt n(_g);n!=INVALID;++n)219 {220 int ls = l;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));225 }226 227 }228 229 ///Find an edge between two nodes.230 231 ///Find an edge between two nodes.232 ///\param s The source node233 ///\param t The target node234 ///\return An edge from \c s to \c t if there exists,235 ///\ref INVALID otherwise.236 237 Edge operator()(Node s, Node t)238 {239 Edge *a=_start[s];240 Edge *b=_end[s];241 while(a!=b)242 {243 // #ifdef X86244 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);245 // #elif X86_64246 // Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);247 // #else248 // Edge *m=a+((ba)/2);249 // #endif250 Node tt = _g.target(*m);251 if(tt==t) return *m;252 else if(tt<t) a=m+1;253 else b=m;254 }255 return INVALID;256 }257 258 ///Find the next edge259 260 ///\warning This function is unimplemented.261 Edge operator()(Node s, Node t, Edge prev)262 {263 return prev==INVALID?(*this)(s,t):INVALID;264 }265 266 };267 268 template<class G>269 class EdgeLookUp5270 {271 public:272 GRAPH_TYPEDEFS(typename G)273 typedef G Graph;274 275 private:276 const Graph &_g;277 typename Graph::template NodeMap<Edge*> _start;278 typename Graph::template NodeMap<Edge*> _end;279 std::vector<Edge> _edges;280 281 class EdgeLess {282 const Graph &g;283 public:284 EdgeLess(const Graph &_g) : g(_g) {}285 bool operator()(Edge a,Edge b) const286 {287 return g.target(a)<g.target(b);288 }289 };290 291 public:292 293 ///Constructor294 EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}295 296 public:297 ///Refresh the data structure at a node.298 void refresh(Node n)299 {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));305 }306 ///Refresh the full data structure.307 void refresh()308 {309 _edges.resize(countEdges(_g));310 int l=0;311 for(NodeIt n(_g);n!=INVALID;++n)312 {313 int ls = l;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));318 }319 320 }321 322 ///Find an edge between two nodes.323 324 ///Find an edge between two nodes.325 ///\param s The source node326 ///\param t The target node327 ///\return An edge from \c s to \c t if there exists,328 ///\ref INVALID otherwise.329 330 Edge operator()(Node s, Node t)331 {332 Edge *a=_start[s];333 Edge *b=_end[s];334 while(a!=b)335 {336 // #ifdef X86337 Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)338 & 0xfffffffc);339 // #elif X86_64340 // Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);341 // #else342 // Edge *m=a+((ba)/2);343 // #endif344 Node tt = _g.target(*m);345 if(tt==t) return *m;346 else if(tt<t) a=m+1;347 else b=m;348 }349 return INVALID;350 }351 352 ///Find the next edge353 354 ///\warning This function is unimplemented.355 Edge operator()(Node s, Node t, Edge prev)356 {357 return prev==INVALID?(*this)(s,t):INVALID;358 }359 360 };175 // template<class G> 176 // class EdgeLookUp4 177 // { 178 // public: 179 // GRAPH_TYPEDEFS(typename G) 180 // typedef G Graph; 181 182 // private: 183 // const Graph &_g; 184 // typename Graph::template NodeMap<Edge*> _start; 185 // typename Graph::template NodeMap<Edge*> _end; 186 // std::vector<Edge> _edges; 187 188 // class EdgeLess { 189 // const Graph &g; 190 // public: 191 // EdgeLess(const Graph &_g) : g(_g) {} 192 // bool operator()(Edge a,Edge b) const 193 // { 194 // return g.target(a)<g.target(b); 195 // } 196 // }; 197 198 // public: 199 200 // ///Constructor 201 // EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 202 203 // public: 204 // ///Refresh the data structure at a node. 205 // void refresh(Node n) 206 // { 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)); 212 // } 213 // ///Refresh the full data structure. 214 // void refresh() 215 // { 216 // _edges.resize(countEdges(_g)); 217 // int l=0; 218 // for(NodeIt n(_g);n!=INVALID;++n) 219 // { 220 // int ls = l; 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)); 225 // } 226 227 // } 228 229 // ///Find an edge between two nodes. 230 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. 236 237 // Edge operator()(Node s, Node t) 238 // { 239 // Edge *a=_start[s]; 240 // Edge *b=_end[s]; 241 // while(a!=b) 242 // { 243 // // #ifdef X86 244 // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); 245 // // #elif X86_64 246 // // Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc); 247 // // #else 248 // // Edge *m=a+((ba)/2); 249 // // #endif 250 // Node tt = _g.target(*m); 251 // if(tt==t) return *m; 252 // else if(tt<t) a=m+1; 253 // else b=m; 254 // } 255 // return INVALID; 256 // } 257 258 // ///Find the next edge 259 260 // ///\warning This function is unimplemented. 261 // Edge operator()(Node s, Node t, Edge prev) 262 // { 263 // return prev==INVALID?(*this)(s,t):INVALID; 264 // } 265 266 // }; 267 268 // template<class G> 269 // class EdgeLookUp5 270 // { 271 // public: 272 // GRAPH_TYPEDEFS(typename G) 273 // typedef G Graph; 274 275 // private: 276 // const Graph &_g; 277 // typename Graph::template NodeMap<Edge*> _start; 278 // typename Graph::template NodeMap<Edge*> _end; 279 // std::vector<Edge> _edges; 280 281 // class EdgeLess { 282 // const Graph &g; 283 // public: 284 // EdgeLess(const Graph &_g) : g(_g) {} 285 // bool operator()(Edge a,Edge b) const 286 // { 287 // return g.target(a)<g.target(b); 288 // } 289 // }; 290 291 // public: 292 293 // ///Constructor 294 // EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 295 296 // public: 297 // ///Refresh the data structure at a node. 298 // void refresh(Node n) 299 // { 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)); 305 // } 306 // ///Refresh the full data structure. 307 // void refresh() 308 // { 309 // _edges.resize(countEdges(_g)); 310 // int l=0; 311 // for(NodeIt n(_g);n!=INVALID;++n) 312 // { 313 // int ls = l; 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)); 318 // } 319 320 // } 321 322 // ///Find an edge between two nodes. 323 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. 329 330 // Edge operator()(Node s, Node t) 331 // { 332 // Edge *a=_start[s]; 333 // Edge *b=_end[s]; 334 // while(a!=b) 335 // { 336 // // #ifdef X86 337 // Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1) 338 // & 0xfffffffc); 339 // // #elif X86_64 340 // // Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc); 341 // // #else 342 // // Edge *m=a+((ba)/2); 343 // // #endif 344 // Node tt = _g.target(*m); 345 // if(tt==t) return *m; 346 // else if(tt<t) a=m+1; 347 // else b=m; 348 // } 349 // return INVALID; 350 // } 351 352 // ///Find the next edge 353 354 // ///\warning This function is unimplemented. 355 // Edge operator()(Node s, Node t, Edge prev) 356 // { 357 // return prev==INVALID?(*this)(s,t):INVALID; 358 // } 359 360 // }; 361 361 362 362 GRAPH_TYPEDEFS(SmartGraph) … … 497 497 TimeStamp t3 = runningTimeTest(EL2(g),1); 498 498 TimeStamp t4 = runningTimeTest(EL3(g),1); 499 TimeStamp t5 = runningTimeTest(EL4(g),1);500 TimeStamp t6 = runningTimeTest(EL5(g),1);499 // TimeStamp t5 = runningTimeTest(EL4(g),1); 500 // TimeStamp t6 = runningTimeTest(EL5(g),1); 501 501 502 502 std::cout << t1.userTime()/N/N << ' ' … … 504 504 << t3.userTime()/N/N << ' ' 505 505 << t4.userTime()/N/N << ' ' 506 << t5.userTime()/N/N << ' '507 << t6.userTime()/N/N506 // << t5.userTime()/N/N << ' ' 507 // << t6.userTime()/N/N 508 508 << std::endl; 509 509 }
Note: See TracChangeset
for help on using the changeset viewer.