Changeset 2252:133028e83940 in lemon0.x
 Timestamp:
 10/17/06 13:02:30 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3002
 Location:
 benchmark
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

benchmark/edge_lookup.cc
r2242 r2252 76 76 }; 77 77 78 //class EL479 //{80 //public:81 //Graph &_g;82 //EdgeLookUp4<Graph> _el;83 //EL4(Graph &g) :_g(g), _el(g) {}84 //void operator()()85 //{86 //Edge e;78 class EL4 79 { 80 public: 81 Graph &_g; 82 EdgeLookUp4<Graph> _el; 83 EL4(Graph &g) :_g(g), _el(g) {} 84 void operator()() 85 { 86 Edge e; 87 87 88 //for(NodeIt v(_g);v!=INVALID;++v)89 //for(NodeIt u(_g);u!=INVALID;++u)90 //e=_el(u,v);91 //}88 for(NodeIt v(_g);v!=INVALID;++v) 89 for(NodeIt u(_g);u!=INVALID;++u) 90 e=_el(u,v); 91 } 92 92 93 //};93 }; 94 94 95 95 int main(int, char**argv) 
benchmark/edge_lookup_test.h
r2239 r2252 190 190 }; 191 191 192 // template<class G> 193 // class EdgeLookUp4 194 // { 195 // public: 196 // GRAPH_TYPEDEFS(typename G) 197 // typedef G Graph; 198 199 // private: 200 // const Graph &_g; 201 // typename Graph::template NodeMap<Edge*> _start; 202 // typename Graph::template NodeMap<Edge*> _end; 203 // std::vector<Edge> _edges; 204 205 // class EdgeLess { 206 // const Graph &g; 207 // public: 208 // EdgeLess(const Graph &_g) : g(_g) {} 209 // bool operator()(Edge a,Edge b) const 210 // { 211 // return g.target(a)<g.target(b); 212 // } 213 // }; 214 215 // public: 216 217 // ///Constructor 218 // EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 219 220 // public: 221 // ///Refresh the data structure at a node. 222 // void refresh(Node n) 223 // { 224 // const int bi = _start[n] = _edges.size(); 225 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); 226 // const typename std::vector<Edge>::iterator ei=_edges.end(); 227 // _end[n]=_edges.size(); 228 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); 229 // } 230 // ///Refresh the full data structure. 231 // void refresh() 232 // { 233 // _edges.resize(countEdges(_g)); 234 // int l=0; 235 // for(NodeIt n(_g);n!=INVALID;++n) 236 // { 237 // int ls = l; 238 // _start[n]=&(_edges[l]); 239 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; 240 // _end[n]=&(_edges[l]); 241 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); 242 // } 243 244 // } 245 246 // ///Find an edge between two nodes. 247 248 // ///Find an edge between two nodes. 249 // ///\param s The source node 250 // ///\param t The target node 251 // ///\return An edge from \c s to \c t if there exists, 252 // ///\ref INVALID otherwise. 253 254 // Edge operator()(Node s, Node t) 255 // { 256 // Edge *a=_start[s]; 257 // Edge *b=_end[s]; 258 // while(a!=b) 259 // { 260 // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); 261 // Node tt = _g.target(*m); 262 // if(tt==t) return *m; 263 // else if(tt<t) a=m+1; 264 // else b=m; 265 // } 266 // return INVALID; 267 // } 268 269 // ///Find the next edge 270 271 // ///\warning This function is unimplemented. 272 // Edge operator()(Node s, Node t, Edge prev) 273 // { 274 // return prev==INVALID?(*this)(s,t):INVALID; 275 // } 276 277 // }; 192 template<class G> 193 class EdgeLookUp4 194 { 195 public: 196 GRAPH_TYPEDEFS(typename G) 197 typedef G Graph; 198 199 private: 200 const Graph &_g; 201 typename Graph::template NodeMap<Edge*> _start; 202 typename Graph::template NodeMap<Edge*> _end; 203 std::vector<Edge> _edges; 204 205 class EdgeLess { 206 const Graph &g; 207 public: 208 EdgeLess(const Graph &_g) : g(_g) {} 209 bool operator()(Edge a,Edge b) const 210 { 211 return g.target(a)<g.target(b); 212 } 213 }; 214 215 public: 216 217 ///Constructor 218 EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} 219 220 public: 221 ///Refresh the data structure at a node. 222 void refresh(Node n) 223 { 224 const int bi = _start[n] = _edges.size(); 225 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); 226 const typename std::vector<Edge>::iterator ei=_edges.end(); 227 _end[n]=_edges.size(); 228 std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); 229 } 230 ///Refresh the full data structure. 231 void refresh() 232 { 233 _edges.resize(countEdges(_g)); 234 int l=0; 235 for(NodeIt n(_g);n!=INVALID;++n) 236 { 237 int ls = l; 238 _start[n]=&(_edges[l]); 239 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; 240 _end[n]=&(_edges[l]); 241 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); 242 } 243 244 } 245 246 ///Find an edge between two nodes. 247 248 ///Find an edge between two nodes. 249 ///\param s The source node 250 ///\param t The target node 251 ///\return An edge from \c s to \c t if there exists, 252 ///\ref INVALID otherwise. 253 254 Edge operator()(Node s, Node t) 255 { 256 Edge *a=_start[s]; 257 Edge *b=_end[s]; 258 while(a!=b) 259 { 260 #ifdef X86 261 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); 262 #elif X86_64 263 Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc); 264 #else 265 Edge *m=a+((ba)/2); 266 #endif 267 Node tt = _g.target(*m); 268 if(tt==t) return *m; 269 else if(tt<t) a=m+1; 270 else b=m; 271 } 272 return INVALID; 273 } 274 275 ///Find the next edge 276 277 ///\warning This function is unimplemented. 278 Edge operator()(Node s, Node t, Edge prev) 279 { 280 return prev==INVALID?(*this)(s,t):INVALID; 281 } 282 283 }; 278 284 279 285 }
Note: See TracChangeset
for help on using the changeset viewer.