Changeset 2239:18c24fe93b99 in lemon0.x for benchmark/edge_lookup_test.h
 Timestamp:
 10/12/06 13:53:31 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2983
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

benchmark/edge_lookup_test.h
r2235 r2239 190 190 }; 191 191 192 template<class G>193 class EdgeLookUp4194 {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) const210 {211 return g.target(a)<g.target(b);212 }213 };214 215 public:216 217 ///Constructor218 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 node250 ///\param t The target node251 ///\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 edge270 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 // 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 // }; 278 278 279 279 }
Note: See TracChangeset
for help on using the changeset viewer.