1.1 --- a/benchmark/edge_lookup.cc Mon Oct 30 12:25:43 2006 +0000
1.2 +++ b/benchmark/edge_lookup.cc Mon Oct 30 15:23:35 2006 +0000
1.3 @@ -1,11 +1,364 @@
1.4 -#include"edge_lookup_test.h"
1.5 #include<lemon/smart_graph.h>
1.6 #include<vector>
1.7 #include<lemon/time_measure.h>
1.8 #include<lemon/random.h>
1.9 +#include<lemon/graph_utils.h>
1.10 +#include<algorithm>
1.11
1.12 using namespace lemon;
1.13
1.14 + template<class G>
1.15 + class EdgeLookUp2
1.16 + {
1.17 + public:
1.18 + GRAPH_TYPEDEFS(typename G)
1.19 + typedef G Graph;
1.20 +
1.21 + private:
1.22 + const Graph &_g;
1.23 + typename Graph::template NodeMap<int> _start;
1.24 + typename Graph::template NodeMap<int> _end;
1.25 + std::vector<Edge> _edges;
1.26 +
1.27 + class EdgeLess {
1.28 + const Graph &g;
1.29 + public:
1.30 + EdgeLess(const Graph &_g) : g(_g) {}
1.31 + bool operator()(Edge a,Edge b) const
1.32 + {
1.33 + return g.target(a)<g.target(b);
1.34 + }
1.35 + };
1.36 +
1.37 + public:
1.38 +
1.39 + ///Constructor
1.40 + EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.41 +
1.42 + public:
1.43 + ///Refresh the data structure at a node.
1.44 + void refresh(Node n)
1.45 + {
1.46 + const int bi = _start[n] = _edges.size();
1.47 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.48 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.49 + _end[n]=_edges.size();
1.50 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.51 + }
1.52 + ///Refresh the full data structure.
1.53 + void refresh()
1.54 + {
1.55 + _edges.clear();
1.56 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.57 + }
1.58 +
1.59 + ///Find an edge between two nodes.
1.60 +
1.61 + ///Find an edge between two nodes.
1.62 + ///\param s The source node
1.63 + ///\param t The target node
1.64 + ///\return An edge from \c s to \c t if there exists,
1.65 + ///\ref INVALID otherwise.
1.66 +
1.67 + Edge operator()(Node s, Node t)
1.68 + {
1.69 + int a=_start[s];
1.70 + int b=_end[s];
1.71 + while(a<b)
1.72 + {
1.73 + int n=(a+b)/2;
1.74 + Node tt = _g.target(_edges[n]);
1.75 + if(tt==t) return _edges[n];
1.76 + else if(tt<t) a=n+1;
1.77 + else b=n;
1.78 + }
1.79 + return INVALID;
1.80 + }
1.81 +
1.82 + ///Find the next edge
1.83 +
1.84 + ///\warning This function is unimplemented.
1.85 + Edge operator()(Node s, Node t, Edge prev)
1.86 + {
1.87 + return prev==INVALID?(*this)(s,t):INVALID;
1.88 + }
1.89 +
1.90 + };
1.91 +
1.92 + template<class G>
1.93 + class EdgeLookUp3
1.94 + {
1.95 + public:
1.96 + GRAPH_TYPEDEFS(typename G)
1.97 + typedef G Graph;
1.98 +
1.99 + private:
1.100 + const Graph &_g;
1.101 + typename Graph::template NodeMap<Edge*> _start;
1.102 + typename Graph::template NodeMap<Edge*> _end;
1.103 + std::vector<Edge> _edges;
1.104 +
1.105 + class EdgeLess {
1.106 + const Graph &g;
1.107 + public:
1.108 + EdgeLess(const Graph &_g) : g(_g) {}
1.109 + bool operator()(Edge a,Edge b) const
1.110 + {
1.111 + return g.target(a)<g.target(b);
1.112 + }
1.113 + };
1.114 +
1.115 + public:
1.116 +
1.117 + ///Constructor
1.118 + EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.119 +
1.120 + public:
1.121 + ///Refresh the data structure at a node.
1.122 + void refresh(Node n)
1.123 + {
1.124 + const int bi = _start[n] = _edges.size();
1.125 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.126 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.127 + _end[n]=_edges.size();
1.128 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.129 + }
1.130 + ///Refresh the full data structure.
1.131 + void refresh()
1.132 + {
1.133 + _edges.resize(countEdges(_g));
1.134 + int l=0;
1.135 + for(NodeIt n(_g);n!=INVALID;++n)
1.136 + {
1.137 + int ls = l;
1.138 + _start[n]=&(_edges[l]);
1.139 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.140 + _end[n]=&(_edges[l]);
1.141 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.142 + }
1.143 +
1.144 + }
1.145 +
1.146 + ///Find an edge between two nodes.
1.147 +
1.148 + ///Find an edge between two nodes.
1.149 + ///\param s The source node
1.150 + ///\param t The target node
1.151 + ///\return An edge from \c s to \c t if there exists,
1.152 + ///\ref INVALID otherwise.
1.153 +
1.154 + Edge operator()(Node s, Node t)
1.155 + {
1.156 + Edge *a=_start[s];
1.157 + Edge *b=_end[s];
1.158 + while(a!=b)
1.159 + {
1.160 + Edge *m=a+((b-a)/2);
1.161 + Node tt = _g.target(*m);
1.162 + if(tt==t) return *m;
1.163 + else if(tt<t) a=m+1;
1.164 + else b=m;
1.165 + }
1.166 + return INVALID;
1.167 + }
1.168 +
1.169 + ///Find the next edge
1.170 +
1.171 + ///\warning This function is unimplemented.
1.172 + Edge operator()(Node s, Node t, Edge prev)
1.173 + {
1.174 + return prev==INVALID?(*this)(s,t):INVALID;
1.175 + }
1.176 +
1.177 + };
1.178 +
1.179 + template<class G>
1.180 + class EdgeLookUp4
1.181 + {
1.182 + public:
1.183 + GRAPH_TYPEDEFS(typename G)
1.184 + typedef G Graph;
1.185 +
1.186 + private:
1.187 + const Graph &_g;
1.188 + typename Graph::template NodeMap<Edge*> _start;
1.189 + typename Graph::template NodeMap<Edge*> _end;
1.190 + std::vector<Edge> _edges;
1.191 +
1.192 + class EdgeLess {
1.193 + const Graph &g;
1.194 + public:
1.195 + EdgeLess(const Graph &_g) : g(_g) {}
1.196 + bool operator()(Edge a,Edge b) const
1.197 + {
1.198 + return g.target(a)<g.target(b);
1.199 + }
1.200 + };
1.201 +
1.202 + public:
1.203 +
1.204 + ///Constructor
1.205 + EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.206 +
1.207 + public:
1.208 + ///Refresh the data structure at a node.
1.209 + void refresh(Node n)
1.210 + {
1.211 + const int bi = _start[n] = _edges.size();
1.212 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.213 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.214 + _end[n]=_edges.size();
1.215 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.216 + }
1.217 + ///Refresh the full data structure.
1.218 + void refresh()
1.219 + {
1.220 + _edges.resize(countEdges(_g));
1.221 + int l=0;
1.222 + for(NodeIt n(_g);n!=INVALID;++n)
1.223 + {
1.224 + int ls = l;
1.225 + _start[n]=&(_edges[l]);
1.226 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.227 + _end[n]=&(_edges[l]);
1.228 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.229 + }
1.230 +
1.231 + }
1.232 +
1.233 + ///Find an edge between two nodes.
1.234 +
1.235 + ///Find an edge between two nodes.
1.236 + ///\param s The source node
1.237 + ///\param t The target node
1.238 + ///\return An edge from \c s to \c t if there exists,
1.239 + ///\ref INVALID otherwise.
1.240 +
1.241 + Edge operator()(Node s, Node t)
1.242 + {
1.243 + Edge *a=_start[s];
1.244 + Edge *b=_end[s];
1.245 + while(a!=b)
1.246 + {
1.247 +// #ifdef X86
1.248 + Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.249 +// #elif X86_64
1.250 +// Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
1.251 +// #else
1.252 +// Edge *m=a+((b-a)/2);
1.253 +// #endif
1.254 + Node tt = _g.target(*m);
1.255 + if(tt==t) return *m;
1.256 + else if(tt<t) a=m+1;
1.257 + else b=m;
1.258 + }
1.259 + return INVALID;
1.260 + }
1.261 +
1.262 + ///Find the next edge
1.263 +
1.264 + ///\warning This function is unimplemented.
1.265 + Edge operator()(Node s, Node t, Edge prev)
1.266 + {
1.267 + return prev==INVALID?(*this)(s,t):INVALID;
1.268 + }
1.269 +
1.270 + };
1.271 +
1.272 + template<class G>
1.273 + class EdgeLookUp5
1.274 + {
1.275 + public:
1.276 + GRAPH_TYPEDEFS(typename G)
1.277 + typedef G Graph;
1.278 +
1.279 + private:
1.280 + const Graph &_g;
1.281 + typename Graph::template NodeMap<Edge*> _start;
1.282 + typename Graph::template NodeMap<Edge*> _end;
1.283 + std::vector<Edge> _edges;
1.284 +
1.285 + class EdgeLess {
1.286 + const Graph &g;
1.287 + public:
1.288 + EdgeLess(const Graph &_g) : g(_g) {}
1.289 + bool operator()(Edge a,Edge b) const
1.290 + {
1.291 + return g.target(a)<g.target(b);
1.292 + }
1.293 + };
1.294 +
1.295 + public:
1.296 +
1.297 + ///Constructor
1.298 + EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.299 +
1.300 + public:
1.301 + ///Refresh the data structure at a node.
1.302 + void refresh(Node n)
1.303 + {
1.304 + const int bi = _start[n] = _edges.size();
1.305 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.306 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.307 + _end[n]=_edges.size();
1.308 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.309 + }
1.310 + ///Refresh the full data structure.
1.311 + void refresh()
1.312 + {
1.313 + _edges.resize(countEdges(_g));
1.314 + int l=0;
1.315 + for(NodeIt n(_g);n!=INVALID;++n)
1.316 + {
1.317 + int ls = l;
1.318 + _start[n]=&(_edges[l]);
1.319 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.320 + _end[n]=&(_edges[l]);
1.321 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.322 + }
1.323 +
1.324 + }
1.325 +
1.326 + ///Find an edge between two nodes.
1.327 +
1.328 + ///Find an edge between two nodes.
1.329 + ///\param s The source node
1.330 + ///\param t The target node
1.331 + ///\return An edge from \c s to \c t if there exists,
1.332 + ///\ref INVALID otherwise.
1.333 +
1.334 + Edge operator()(Node s, Node t)
1.335 + {
1.336 + Edge *a=_start[s];
1.337 + Edge *b=_end[s];
1.338 + while(a!=b)
1.339 + {
1.340 +// #ifdef X86
1.341 + Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
1.342 + & 0xfffffffc);
1.343 +// #elif X86_64
1.344 +// Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
1.345 +// #else
1.346 +// Edge *m=a+((b-a)/2);
1.347 +// #endif
1.348 + Node tt = _g.target(*m);
1.349 + if(tt==t) return *m;
1.350 + else if(tt<t) a=m+1;
1.351 + else b=m;
1.352 + }
1.353 + return INVALID;
1.354 + }
1.355 +
1.356 + ///Find the next edge
1.357 +
1.358 + ///\warning This function is unimplemented.
1.359 + Edge operator()(Node s, Node t, Edge prev)
1.360 + {
1.361 + return prev==INVALID?(*this)(s,t):INVALID;
1.362 + }
1.363 +
1.364 + };
1.365 +
1.366 GRAPH_TYPEDEFS(SmartGraph)
1.367 typedef SmartGraph Graph;
1.368
1.369 @@ -92,6 +445,23 @@
1.370
1.371 };
1.372
1.373 +class EL5
1.374 +{
1.375 +public:
1.376 + Graph &_g;
1.377 + EdgeLookUp5<Graph> _el;
1.378 + EL5(Graph &g) :_g(g), _el(g) {}
1.379 + void operator()()
1.380 + {
1.381 + Edge e;
1.382 +
1.383 + for(NodeIt v(_g);v!=INVALID;++v)
1.384 + for(NodeIt u(_g);u!=INVALID;++u)
1.385 + e=_el(u,v);
1.386 + }
1.387 +
1.388 +};
1.389 +
1.390 int main(int, char**argv)
1.391 {
1.392 int N=atoi(argv[1]);
1.393 @@ -126,13 +496,15 @@
1.394 TimeStamp t2 = runningTimeTest(EL(g),1);
1.395 TimeStamp t3 = runningTimeTest(EL2(g),1);
1.396 TimeStamp t4 = runningTimeTest(EL3(g),1);
1.397 -// TimeStamp t5 = runningTimeTest(EL4(g),1);
1.398 + TimeStamp t5 = runningTimeTest(EL4(g),1);
1.399 + TimeStamp t6 = runningTimeTest(EL5(g),1);
1.400
1.401 std::cout << t1.userTime()/N/N << ' '
1.402 << t2.userTime()/N/N << ' '
1.403 << t3.userTime()/N/N << ' '
1.404 << t4.userTime()/N/N << ' '
1.405 -// << t5.userTime()/N/N
1.406 + << t5.userTime()/N/N << ' '
1.407 + << t6.userTime()/N/N
1.408 << std::endl;
1.409 }
1.410
2.1 --- a/benchmark/edge_lookup_test.h Mon Oct 30 12:25:43 2006 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,287 +0,0 @@
2.4 -/* -*- C++ -*-
2.5 - *
2.6 - * This file is a part of LEMON, a generic C++ optimization library
2.7 - *
2.8 - * Copyright (C) 2003-2006
2.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 - *
2.12 - * Permission to use, modify and distribute this software is granted
2.13 - * provided that this copyright notice appears in all copies. For
2.14 - * precise terms see the accompanying LICENSE file.
2.15 - *
2.16 - * This software is provided "AS IS" with no warranty of any kind,
2.17 - * express or implied, and with no claim as to its suitability for any
2.18 - * purpose.
2.19 - *
2.20 - */
2.21 -
2.22 -#ifndef LEMON_EDGE_LOOKUP_H
2.23 -#define LEMON_EDGE_LOOKUP_H
2.24 -
2.25 -#include<lemon/graph_utils.h>
2.26 -#include<algorithm>
2.27 -#include<vector>
2.28 -
2.29 -namespace lemon {
2.30 - template<class G>
2.31 - class EdgeLookUp2
2.32 - {
2.33 - public:
2.34 - GRAPH_TYPEDEFS(typename G)
2.35 - typedef G Graph;
2.36 -
2.37 - private:
2.38 - const Graph &_g;
2.39 - typename Graph::template NodeMap<int> _start;
2.40 - typename Graph::template NodeMap<int> _end;
2.41 - std::vector<Edge> _edges;
2.42 -
2.43 - class EdgeLess {
2.44 - const Graph &g;
2.45 - public:
2.46 - EdgeLess(const Graph &_g) : g(_g) {}
2.47 - bool operator()(Edge a,Edge b) const
2.48 - {
2.49 - return g.target(a)<g.target(b);
2.50 - }
2.51 - };
2.52 -
2.53 - public:
2.54 -
2.55 - ///Constructor
2.56 - EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
2.57 -
2.58 - public:
2.59 - ///Refresh the data structure at a node.
2.60 - void refresh(Node n)
2.61 - {
2.62 - const int bi = _start[n] = _edges.size();
2.63 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
2.64 - const typename std::vector<Edge>::iterator ei=_edges.end();
2.65 - _end[n]=_edges.size();
2.66 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
2.67 - }
2.68 - ///Refresh the full data structure.
2.69 - void refresh()
2.70 - {
2.71 - _edges.clear();
2.72 - for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2.73 - }
2.74 -
2.75 - ///Find an edge between two nodes.
2.76 -
2.77 - ///Find an edge between two nodes.
2.78 - ///\param s The source node
2.79 - ///\param t The target node
2.80 - ///\return An edge from \c s to \c t if there exists,
2.81 - ///\ref INVALID otherwise.
2.82 -
2.83 - Edge operator()(Node s, Node t)
2.84 - {
2.85 - int a=_start[s];
2.86 - int b=_end[s];
2.87 - while(a<b)
2.88 - {
2.89 - int n=(a+b)/2;
2.90 - Node tt = _g.target(_edges[n]);
2.91 - if(tt==t) return _edges[n];
2.92 - else if(tt<t) a=n+1;
2.93 - else b=n;
2.94 - }
2.95 - return INVALID;
2.96 - }
2.97 -
2.98 - ///Find the next edge
2.99 -
2.100 - ///\warning This function is unimplemented.
2.101 - Edge operator()(Node s, Node t, Edge prev)
2.102 - {
2.103 - return prev==INVALID?(*this)(s,t):INVALID;
2.104 - }
2.105 -
2.106 - };
2.107 -
2.108 - template<class G>
2.109 - class EdgeLookUp3
2.110 - {
2.111 - public:
2.112 - GRAPH_TYPEDEFS(typename G)
2.113 - typedef G Graph;
2.114 -
2.115 - private:
2.116 - const Graph &_g;
2.117 - typename Graph::template NodeMap<Edge*> _start;
2.118 - typename Graph::template NodeMap<Edge*> _end;
2.119 - std::vector<Edge> _edges;
2.120 -
2.121 - class EdgeLess {
2.122 - const Graph &g;
2.123 - public:
2.124 - EdgeLess(const Graph &_g) : g(_g) {}
2.125 - bool operator()(Edge a,Edge b) const
2.126 - {
2.127 - return g.target(a)<g.target(b);
2.128 - }
2.129 - };
2.130 -
2.131 - public:
2.132 -
2.133 - ///Constructor
2.134 - EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
2.135 -
2.136 - public:
2.137 - ///Refresh the data structure at a node.
2.138 - void refresh(Node n)
2.139 - {
2.140 - const int bi = _start[n] = _edges.size();
2.141 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
2.142 - const typename std::vector<Edge>::iterator ei=_edges.end();
2.143 - _end[n]=_edges.size();
2.144 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
2.145 - }
2.146 - ///Refresh the full data structure.
2.147 - void refresh()
2.148 - {
2.149 - _edges.resize(countEdges(_g));
2.150 - int l=0;
2.151 - for(NodeIt n(_g);n!=INVALID;++n)
2.152 - {
2.153 - int ls = l;
2.154 - _start[n]=&(_edges[l]);
2.155 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
2.156 - _end[n]=&(_edges[l]);
2.157 - std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
2.158 - }
2.159 -
2.160 - }
2.161 -
2.162 - ///Find an edge between two nodes.
2.163 -
2.164 - ///Find an edge between two nodes.
2.165 - ///\param s The source node
2.166 - ///\param t The target node
2.167 - ///\return An edge from \c s to \c t if there exists,
2.168 - ///\ref INVALID otherwise.
2.169 -
2.170 - Edge operator()(Node s, Node t)
2.171 - {
2.172 - Edge *a=_start[s];
2.173 - Edge *b=_end[s];
2.174 - while(a!=b)
2.175 - {
2.176 - Edge *m=a+((b-a)/2);
2.177 - Node tt = _g.target(*m);
2.178 - if(tt==t) return *m;
2.179 - else if(tt<t) a=m+1;
2.180 - else b=m;
2.181 - }
2.182 - return INVALID;
2.183 - }
2.184 -
2.185 - ///Find the next edge
2.186 -
2.187 - ///\warning This function is unimplemented.
2.188 - Edge operator()(Node s, Node t, Edge prev)
2.189 - {
2.190 - return prev==INVALID?(*this)(s,t):INVALID;
2.191 - }
2.192 -
2.193 - };
2.194 -
2.195 - template<class G>
2.196 - class EdgeLookUp4
2.197 - {
2.198 - public:
2.199 - GRAPH_TYPEDEFS(typename G)
2.200 - typedef G Graph;
2.201 -
2.202 - private:
2.203 - const Graph &_g;
2.204 - typename Graph::template NodeMap<Edge*> _start;
2.205 - typename Graph::template NodeMap<Edge*> _end;
2.206 - std::vector<Edge> _edges;
2.207 -
2.208 - class EdgeLess {
2.209 - const Graph &g;
2.210 - public:
2.211 - EdgeLess(const Graph &_g) : g(_g) {}
2.212 - bool operator()(Edge a,Edge b) const
2.213 - {
2.214 - return g.target(a)<g.target(b);
2.215 - }
2.216 - };
2.217 -
2.218 - public:
2.219 -
2.220 - ///Constructor
2.221 - EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
2.222 -
2.223 - public:
2.224 - ///Refresh the data structure at a node.
2.225 - void refresh(Node n)
2.226 - {
2.227 - const int bi = _start[n] = _edges.size();
2.228 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
2.229 - const typename std::vector<Edge>::iterator ei=_edges.end();
2.230 - _end[n]=_edges.size();
2.231 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
2.232 - }
2.233 - ///Refresh the full data structure.
2.234 - void refresh()
2.235 - {
2.236 - _edges.resize(countEdges(_g));
2.237 - int l=0;
2.238 - for(NodeIt n(_g);n!=INVALID;++n)
2.239 - {
2.240 - int ls = l;
2.241 - _start[n]=&(_edges[l]);
2.242 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
2.243 - _end[n]=&(_edges[l]);
2.244 - std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
2.245 - }
2.246 -
2.247 - }
2.248 -
2.249 - ///Find an edge between two nodes.
2.250 -
2.251 - ///Find an edge between two nodes.
2.252 - ///\param s The source node
2.253 - ///\param t The target node
2.254 - ///\return An edge from \c s to \c t if there exists,
2.255 - ///\ref INVALID otherwise.
2.256 -
2.257 - Edge operator()(Node s, Node t)
2.258 - {
2.259 - Edge *a=_start[s];
2.260 - Edge *b=_end[s];
2.261 - while(a!=b)
2.262 - {
2.263 -#ifdef X86
2.264 - Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
2.265 -#elif X86_64
2.266 - Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
2.267 -#else
2.268 - Edge *m=a+((b-a)/2);
2.269 -#endif
2.270 - Node tt = _g.target(*m);
2.271 - if(tt==t) return *m;
2.272 - else if(tt<t) a=m+1;
2.273 - else b=m;
2.274 - }
2.275 - return INVALID;
2.276 - }
2.277 -
2.278 - ///Find the next edge
2.279 -
2.280 - ///\warning This function is unimplemented.
2.281 - Edge operator()(Node s, Node t, Edge prev)
2.282 - {
2.283 - return prev==INVALID?(*this)(s,t):INVALID;
2.284 - }
2.285 -
2.286 - };
2.287 -
2.288 -}
2.289 -
2.290 -#endif