Changeset 2271:a2ab63454152 in lemon0.x for benchmark/edge_lookup.cc
 Timestamp:
 10/30/06 16:23:35 (13 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3033
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

benchmark/edge_lookup.cc
r2252 r2271 1 #include"edge_lookup_test.h"2 1 #include<lemon/smart_graph.h> 3 2 #include<vector> 4 3 #include<lemon/time_measure.h> 5 4 #include<lemon/random.h> 5 #include<lemon/graph_utils.h> 6 #include<algorithm> 6 7 7 8 using namespace lemon; 9 10 template<class G> 11 class EdgeLookUp2 12 { 13 public: 14 GRAPH_TYPEDEFS(typename G) 15 typedef G Graph; 16 17 private: 18 const Graph &_g; 19 typename Graph::template NodeMap<int> _start; 20 typename Graph::template NodeMap<int> _end; 21 std::vector<Edge> _edges; 22 23 class EdgeLess { 24 const Graph &g; 25 public: 26 EdgeLess(const Graph &_g) : g(_g) {} 27 bool operator()(Edge a,Edge b) const 28 { 29 return g.target(a)<g.target(b); 30 } 31 }; 32 33 public: 34 35 ///Constructor 36 EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 37 38 public: 39 ///Refresh the data structure at a node. 40 void refresh(Node n) 41 { 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)); 47 } 48 ///Refresh the full data structure. 49 void refresh() 50 { 51 _edges.clear(); 52 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); 53 } 54 55 ///Find an edge between two nodes. 56 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. 62 63 Edge operator()(Node s, Node t) 64 { 65 int a=_start[s]; 66 int b=_end[s]; 67 while(a<b) 68 { 69 int n=(a+b)/2; 70 Node tt = _g.target(_edges[n]); 71 if(tt==t) return _edges[n]; 72 else if(tt<t) a=n+1; 73 else b=n; 74 } 75 return INVALID; 76 } 77 78 ///Find the next edge 79 80 ///\warning This function is unimplemented. 81 Edge operator()(Node s, Node t, Edge prev) 82 { 83 return prev==INVALID?(*this)(s,t):INVALID; 84 } 85 86 }; 87 88 template<class G> 89 class EdgeLookUp3 90 { 91 public: 92 GRAPH_TYPEDEFS(typename G) 93 typedef G Graph; 94 95 private: 96 const Graph &_g; 97 typename Graph::template NodeMap<Edge*> _start; 98 typename Graph::template NodeMap<Edge*> _end; 99 std::vector<Edge> _edges; 100 101 class EdgeLess { 102 const Graph &g; 103 public: 104 EdgeLess(const Graph &_g) : g(_g) {} 105 bool operator()(Edge a,Edge b) const 106 { 107 return g.target(a)<g.target(b); 108 } 109 }; 110 111 public: 112 113 ///Constructor 114 EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 115 116 public: 117 ///Refresh the data structure at a node. 118 void refresh(Node n) 119 { 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)); 125 } 126 ///Refresh the full data structure. 127 void refresh() 128 { 129 _edges.resize(countEdges(_g)); 130 int l=0; 131 for(NodeIt n(_g);n!=INVALID;++n) 132 { 133 int ls = l; 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)); 138 } 139 140 } 141 142 ///Find an edge between two nodes. 143 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. 149 150 Edge operator()(Node s, Node t) 151 { 152 Edge *a=_start[s]; 153 Edge *b=_end[s]; 154 while(a!=b) 155 { 156 Edge *m=a+((ba)/2); 157 Node tt = _g.target(*m); 158 if(tt==t) return *m; 159 else if(tt<t) a=m+1; 160 else b=m; 161 } 162 return INVALID; 163 } 164 165 ///Find the next edge 166 167 ///\warning This function is unimplemented. 168 Edge operator()(Node s, Node t, Edge prev) 169 { 170 return prev==INVALID?(*this)(s,t):INVALID; 171 } 172 173 }; 174 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 }; 8 361 9 362 GRAPH_TYPEDEFS(SmartGraph) … … 82 435 EdgeLookUp4<Graph> _el; 83 436 EL4(Graph &g) :_g(g), _el(g) {} 437 void operator()() 438 { 439 Edge e; 440 441 for(NodeIt v(_g);v!=INVALID;++v) 442 for(NodeIt u(_g);u!=INVALID;++u) 443 e=_el(u,v); 444 } 445 446 }; 447 448 class EL5 449 { 450 public: 451 Graph &_g; 452 EdgeLookUp5<Graph> _el; 453 EL5(Graph &g) :_g(g), _el(g) {} 84 454 void operator()() 85 455 { … … 127 497 TimeStamp t3 = runningTimeTest(EL2(g),1); 128 498 TimeStamp t4 = runningTimeTest(EL3(g),1); 129 // TimeStamp t5 = runningTimeTest(EL4(g),1); 499 TimeStamp t5 = runningTimeTest(EL4(g),1); 500 TimeStamp t6 = runningTimeTest(EL5(g),1); 130 501 131 502 std::cout << t1.userTime()/N/N << ' ' … … 133 504 << t3.userTime()/N/N << ' ' 134 505 << t4.userTime()/N/N << ' ' 135 // << t5.userTime()/N/N 506 << t5.userTime()/N/N << ' ' 507 << t6.userTime()/N/N 136 508 << std::endl; 137 509 }
Note: See TracChangeset
for help on using the changeset viewer.