187 return prev==INVALID?(*this)(s,t):INVALID; |
187 return prev==INVALID?(*this)(s,t):INVALID; |
188 } |
188 } |
189 |
189 |
190 }; |
190 }; |
191 |
191 |
192 // template<class G> |
192 template<class G> |
193 // class EdgeLookUp4 |
193 class EdgeLookUp4 |
194 // { |
194 { |
195 // public: |
195 public: |
196 // GRAPH_TYPEDEFS(typename G) |
196 GRAPH_TYPEDEFS(typename G) |
197 // typedef G Graph; |
197 typedef G Graph; |
198 |
198 |
199 // private: |
199 private: |
200 // const Graph &_g; |
200 const Graph &_g; |
201 // typename Graph::template NodeMap<Edge*> _start; |
201 typename Graph::template NodeMap<Edge*> _start; |
202 // typename Graph::template NodeMap<Edge*> _end; |
202 typename Graph::template NodeMap<Edge*> _end; |
203 // std::vector<Edge> _edges; |
203 std::vector<Edge> _edges; |
204 |
204 |
205 // class EdgeLess { |
205 class EdgeLess { |
206 // const Graph &g; |
206 const Graph &g; |
207 // public: |
207 public: |
208 // EdgeLess(const Graph &_g) : g(_g) {} |
208 EdgeLess(const Graph &_g) : g(_g) {} |
209 // bool operator()(Edge a,Edge b) const |
209 bool operator()(Edge a,Edge b) const |
210 // { |
210 { |
211 // return g.target(a)<g.target(b); |
211 return g.target(a)<g.target(b); |
212 // } |
212 } |
213 // }; |
213 }; |
214 |
214 |
215 // public: |
215 public: |
216 |
216 |
217 // ///Constructor |
217 ///Constructor |
218 // EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} |
218 EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} |
219 |
219 |
220 // public: |
220 public: |
221 // ///Refresh the data structure at a node. |
221 ///Refresh the data structure at a node. |
222 // void refresh(Node n) |
222 void refresh(Node n) |
223 // { |
223 { |
224 // const int bi = _start[n] = _edges.size(); |
224 const int bi = _start[n] = _edges.size(); |
225 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); |
225 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); |
226 // const typename std::vector<Edge>::iterator ei=_edges.end(); |
226 const typename std::vector<Edge>::iterator ei=_edges.end(); |
227 // _end[n]=_edges.size(); |
227 _end[n]=_edges.size(); |
228 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); |
228 std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); |
229 // } |
229 } |
230 // ///Refresh the full data structure. |
230 ///Refresh the full data structure. |
231 // void refresh() |
231 void refresh() |
232 // { |
232 { |
233 // _edges.resize(countEdges(_g)); |
233 _edges.resize(countEdges(_g)); |
234 // int l=0; |
234 int l=0; |
235 // for(NodeIt n(_g);n!=INVALID;++n) |
235 for(NodeIt n(_g);n!=INVALID;++n) |
236 // { |
236 { |
237 // int ls = l; |
237 int ls = l; |
238 // _start[n]=&(_edges[l]); |
238 _start[n]=&(_edges[l]); |
239 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; |
239 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; |
240 // _end[n]=&(_edges[l]); |
240 _end[n]=&(_edges[l]); |
241 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); |
241 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); |
242 // } |
242 } |
243 |
243 |
244 // } |
244 } |
245 |
245 |
246 // ///Find an edge between two nodes. |
246 ///Find an edge between two nodes. |
247 |
247 |
248 // ///Find an edge between two nodes. |
248 ///Find an edge between two nodes. |
249 // ///\param s The source node |
249 ///\param s The source node |
250 // ///\param t The target node |
250 ///\param t The target node |
251 // ///\return An edge from \c s to \c t if there exists, |
251 ///\return An edge from \c s to \c t if there exists, |
252 // ///\ref INVALID otherwise. |
252 ///\ref INVALID otherwise. |
253 |
253 |
254 // Edge operator()(Node s, Node t) |
254 Edge operator()(Node s, Node t) |
255 // { |
255 { |
256 // Edge *a=_start[s]; |
256 Edge *a=_start[s]; |
257 // Edge *b=_end[s]; |
257 Edge *b=_end[s]; |
258 // while(a!=b) |
258 while(a!=b) |
259 // { |
259 { |
260 // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); |
260 #ifdef X86 |
261 // Node tt = _g.target(*m); |
261 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); |
262 // if(tt==t) return *m; |
262 #elif X86_64 |
263 // else if(tt<t) a=m+1; |
263 Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc); |
264 // else b=m; |
264 #else |
265 // } |
265 Edge *m=a+((b-a)/2); |
266 // return INVALID; |
266 #endif |
267 // } |
267 Node tt = _g.target(*m); |
268 |
268 if(tt==t) return *m; |
269 // ///Find the next edge |
269 else if(tt<t) a=m+1; |
270 |
270 else b=m; |
271 // ///\warning This function is unimplemented. |
271 } |
272 // Edge operator()(Node s, Node t, Edge prev) |
272 return INVALID; |
273 // { |
273 } |
274 // return prev==INVALID?(*this)(s,t):INVALID; |
274 |
275 // } |
275 ///Find the next edge |
276 |
276 |
277 // }; |
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 } |
280 |
286 |
281 #endif |
287 #endif |