1.1 --- a/benchmark/edge_lookup.cc Mon Dec 10 16:34:31 2007 +0000
1.2 +++ b/benchmark/edge_lookup.cc Tue Dec 11 17:37:08 2007 +0000
1.3 @@ -412,6 +412,24 @@
1.4 }
1.5
1.6 };
1.7 +
1.8 +class DEL
1.9 +{
1.10 +public:
1.11 + Graph &_g;
1.12 + DynEdgeLookUp<Graph> _el;
1.13 + DEL(Graph &g) :_g(g), _el(g) {}
1.14 + void operator()()
1.15 + {
1.16 + Edge e;
1.17 +
1.18 + for(NodeIt v(_g);v!=INVALID;++v)
1.19 + for(NodeIt u(_g);u!=INVALID;++u)
1.20 + e=_el(u,v);
1.21 + }
1.22 +
1.23 +};
1.24 +
1.25 class EL2
1.26 {
1.27 public:
1.28 @@ -512,15 +530,25 @@
1.29
1.30 TimeStamp t1 = runningTimeTest(FE(g),1);
1.31 TimeStamp t2 = runningTimeTest(EL(g),1);
1.32 - TimeStamp t3 = runningTimeTest(EL2(g),1);
1.33 - TimeStamp t4 = runningTimeTest(EL3(g),1);
1.34 + TimeStamp t3 = runningTimeTest(DEL(g),1);
1.35 + TimeStamp t4 = runningTimeTest(EL2(g),1);
1.36 + TimeStamp t5 = runningTimeTest(EL3(g),1);
1.37 // TimeStamp t5 = runningTimeTest(EL4(g),1);
1.38 // TimeStamp t6 = runningTimeTest(EL5(g),1);
1.39
1.40 + std::cout << t1.userTime() << ' '
1.41 + << t2.userTime() << ' '
1.42 + << t3.userTime() << ' '
1.43 + << t4.userTime() << ' '
1.44 + << t5.userTime() << ' '
1.45 +// << t5.userTime() << ' '
1.46 +// << t6.userTime()
1.47 + << std::endl;
1.48 std::cout << t1.userTime()/N/N << ' '
1.49 << t2.userTime()/N/N << ' '
1.50 << t3.userTime()/N/N << ' '
1.51 << t4.userTime()/N/N << ' '
1.52 + << t5.userTime()/N/N << ' '
1.53 // << t5.userTime()/N/N << ' '
1.54 // << t6.userTime()/N/N
1.55 << std::endl;
2.1 --- a/lemon/graph_utils.h Mon Dec 10 16:34:31 2007 +0000
2.2 +++ b/lemon/graph_utils.h Tue Dec 11 17:37:08 2007 +0000
2.3 @@ -382,6 +382,7 @@
2.4 ///
2.5 ///\sa EdgeLookUp
2.6 ///\sa AllEdgeLookUp
2.7 + ///\sa DynEdgeLookUp
2.8 ///\sa ConEdgeIt
2.9 template <typename Graph>
2.10 inline typename Graph::Edge
2.11 @@ -404,6 +405,7 @@
2.12 ///\sa findEdge()
2.13 ///\sa EdgeLookUp
2.14 ///\sa AllEdgeLookUp
2.15 + ///\sa DynEdgeLookUp
2.16 ///
2.17 /// \author Balazs Dezso
2.18 template <typename _Graph>
2.19 @@ -2296,6 +2298,15 @@
2.20 Parent::set(keys[i], 0);
2.21 }
2.22 }
2.23 +
2.24 + virtual void build() {
2.25 + Parent::build();
2.26 + Key it;
2.27 + typename Parent::Notifier* nf = Parent::notifier();
2.28 + for (nf->first(it); it != INVALID; nf->next(it)) {
2.29 + Parent::set(it, 0);
2.30 + }
2.31 + }
2.32 };
2.33
2.34 public:
2.35 @@ -2408,6 +2419,14 @@
2.36 Parent::set(keys[i], 0);
2.37 }
2.38 }
2.39 + virtual void build() {
2.40 + Parent::build();
2.41 + Key it;
2.42 + typename Parent::Notifier* nf = Parent::notifier();
2.43 + for (nf->first(it); it != INVALID; nf->next(it)) {
2.44 + Parent::set(it, 0);
2.45 + }
2.46 + }
2.47 };
2.48
2.49 public:
2.50 @@ -2470,6 +2489,451 @@
2.51 };
2.52
2.53
2.54 + ///Dynamic edge look up between given endpoints.
2.55 +
2.56 + ///\ingroup gutils
2.57 + ///Using this class, you can find an edge in a graph from a given
2.58 + ///source to a given target in amortized time <em>O(log d)</em>,
2.59 + ///where <em>d</em> is the out-degree of the source node.
2.60 + ///
2.61 + ///It is possible to find \e all parallel edges between two nodes with
2.62 + ///the \c findFirst() and \c findNext() members.
2.63 + ///
2.64 + ///See the \ref EdgeLookUp and \ref AllEdgeLookUp classes if your
2.65 + ///graph do not changed so frequently.
2.66 + ///
2.67 + ///This class uses a self-adjusting binary search tree, Sleator's
2.68 + ///and Tarjan's Splay tree for guarantee the logarithmic amortized
2.69 + ///time bound for edge lookups. This class also guarantees the
2.70 + ///optimal time bound in a constant factor for any distribution of
2.71 + ///queries.
2.72 + ///
2.73 + ///\param G The type of the underlying graph.
2.74 + ///
2.75 + ///\sa EdgeLookUp
2.76 + ///\sa AllEdgeLookUp
2.77 + template<class G>
2.78 + class DynEdgeLookUp
2.79 + : protected ItemSetTraits<G, typename G::Edge>::ItemNotifier::ObserverBase
2.80 + {
2.81 + public:
2.82 + typedef typename ItemSetTraits<G, typename G::Edge>
2.83 + ::ItemNotifier::ObserverBase Parent;
2.84 +
2.85 + GRAPH_TYPEDEFS(typename G);
2.86 + typedef G Graph;
2.87 +
2.88 + protected:
2.89 +
2.90 + class AutoNodeMap : public DefaultMap<Graph, Node, Edge> {
2.91 + public:
2.92 +
2.93 + typedef DefaultMap<Graph, Node, Edge> Parent;
2.94 +
2.95 + AutoNodeMap(const Graph& graph) : Parent(graph, INVALID) {}
2.96 +
2.97 + virtual void add(const Node& node) {
2.98 + Parent::add(node);
2.99 + Parent::set(node, INVALID);
2.100 + }
2.101 +
2.102 + virtual void add(const std::vector<Node>& nodes) {
2.103 + Parent::add(nodes);
2.104 + for (int i = 0; i < int(nodes.size()); ++i) {
2.105 + Parent::set(nodes[i], INVALID);
2.106 + }
2.107 + }
2.108 +
2.109 + virtual void build() {
2.110 + Parent::build();
2.111 + Node it;
2.112 + typename Parent::Notifier* nf = Parent::notifier();
2.113 + for (nf->first(it); it != INVALID; nf->next(it)) {
2.114 + Parent::set(it, INVALID);
2.115 + }
2.116 + }
2.117 + };
2.118 +
2.119 + const Graph &_g;
2.120 + AutoNodeMap _head;
2.121 + typename Graph::template EdgeMap<Edge> _parent;
2.122 + typename Graph::template EdgeMap<Edge> _left;
2.123 + typename Graph::template EdgeMap<Edge> _right;
2.124 +
2.125 + class EdgeLess {
2.126 + const Graph &g;
2.127 + public:
2.128 + EdgeLess(const Graph &_g) : g(_g) {}
2.129 + bool operator()(Edge a,Edge b) const
2.130 + {
2.131 + return g.target(a)<g.target(b);
2.132 + }
2.133 + };
2.134 +
2.135 + public:
2.136 +
2.137 + ///Constructor
2.138 +
2.139 + ///Constructor.
2.140 + ///
2.141 + ///It builds up the search database.
2.142 + DynEdgeLookUp(const Graph &g)
2.143 + : _g(g),_head(g),_parent(g),_left(g),_right(g)
2.144 + {
2.145 + Parent::attach(_g.notifier(typename Graph::Edge()));
2.146 + refresh();
2.147 + }
2.148 +
2.149 + protected:
2.150 +
2.151 + virtual void add(const Edge& edge) {
2.152 + insert(edge);
2.153 + }
2.154 +
2.155 + virtual void add(const std::vector<Edge>& edges) {
2.156 + for (int i = 0; i < int(edges.size()); ++i) {
2.157 + insert(edges[i]);
2.158 + }
2.159 + }
2.160 +
2.161 + virtual void erase(const Edge& edge) {
2.162 + remove(edge);
2.163 + }
2.164 +
2.165 + virtual void erase(const std::vector<Edge>& edges) {
2.166 + for (int i = 0; i < int(edges.size()); ++i) {
2.167 + remove(edges[i]);
2.168 + }
2.169 + }
2.170 +
2.171 + virtual void build() {
2.172 + refresh();
2.173 + }
2.174 +
2.175 + virtual void clear() {
2.176 + for(NodeIt n(_g);n!=INVALID;++n) {
2.177 + _head.set(n, INVALID);
2.178 + }
2.179 + }
2.180 +
2.181 + void insert(Edge edge) {
2.182 + Node s = _g.source(edge);
2.183 + Node t = _g.target(edge);
2.184 + _left.set(edge, INVALID);
2.185 + _right.set(edge, INVALID);
2.186 +
2.187 + Edge e = _head[s];
2.188 + if (e == INVALID) {
2.189 + _head.set(s, edge);
2.190 + _parent.set(edge, INVALID);
2.191 + return;
2.192 + }
2.193 + while (true) {
2.194 + if (t < _g.target(e)) {
2.195 + if (_left[e] == INVALID) {
2.196 + _left.set(e, edge);
2.197 + _parent.set(edge, e);
2.198 + splay(edge);
2.199 + return;
2.200 + } else {
2.201 + e = _left[e];
2.202 + }
2.203 + } else {
2.204 + if (_right[e] == INVALID) {
2.205 + _right.set(e, edge);
2.206 + _parent.set(edge, e);
2.207 + splay(edge);
2.208 + return;
2.209 + } else {
2.210 + e = _right[e];
2.211 + }
2.212 + }
2.213 + }
2.214 + }
2.215 +
2.216 + void remove(Edge edge) {
2.217 + if (_left[edge] == INVALID) {
2.218 + if (_right[edge] != INVALID) {
2.219 + _parent.set(_right[edge], _parent[edge]);
2.220 + }
2.221 + if (_parent[edge] != INVALID) {
2.222 + if (_left[_parent[edge]] == edge) {
2.223 + _left.set(_parent[edge], _right[edge]);
2.224 + } else {
2.225 + _right.set(_parent[edge], _right[edge]);
2.226 + }
2.227 + } else {
2.228 + _head.set(_g.source(edge), _right[edge]);
2.229 + }
2.230 + } else if (_right[edge] == INVALID) {
2.231 + _parent.set(_left[edge], _parent[edge]);
2.232 + if (_parent[edge] != INVALID) {
2.233 + if (_left[_parent[edge]] == edge) {
2.234 + _left.set(_parent[edge], _left[edge]);
2.235 + } else {
2.236 + _right.set(_parent[edge], _left[edge]);
2.237 + }
2.238 + } else {
2.239 + _head.set(_g.source(edge), _left[edge]);
2.240 + }
2.241 + } else {
2.242 + Edge e = _left[edge];
2.243 + if (_right[e] != INVALID) {
2.244 + e = _right[e];
2.245 + while (_right[e] != INVALID) {
2.246 + e = _right[e];
2.247 + }
2.248 + Edge s = _parent[e];
2.249 + _right.set(_parent[e], _left[e]);
2.250 + if (_left[e] != INVALID) {
2.251 + _parent.set(_left[e], _parent[e]);
2.252 + }
2.253 +
2.254 + _left.set(e, _left[edge]);
2.255 + _parent.set(_left[edge], e);
2.256 + _right.set(e, _right[edge]);
2.257 + _parent.set(_right[edge], e);
2.258 +
2.259 + _parent.set(e, _parent[edge]);
2.260 + if (_parent[edge] != INVALID) {
2.261 + if (_left[_parent[edge]] == edge) {
2.262 + _left.set(_parent[edge], e);
2.263 + } else {
2.264 + _right.set(_parent[edge], e);
2.265 + }
2.266 + }
2.267 + splay(s);
2.268 + } else {
2.269 + _right.set(e, _right[edge]);
2.270 + _parent.set(_right[edge], e);
2.271 +
2.272 + if (_parent[edge] != INVALID) {
2.273 + if (_left[_parent[edge]] == edge) {
2.274 + _left.set(_parent[edge], e);
2.275 + } else {
2.276 + _right.set(_parent[edge], e);
2.277 + }
2.278 + } else {
2.279 + _head.set(_g.source(edge), e);
2.280 + }
2.281 + }
2.282 + }
2.283 + }
2.284 +
2.285 + Edge refreshRec(std::vector<Edge> &v,int a,int b)
2.286 + {
2.287 + int m=(a+b)/2;
2.288 + Edge me=v[m];
2.289 + if (a < m) {
2.290 + Edge left = refreshRec(v,a,m-1);
2.291 + _left.set(me, left);
2.292 + _parent.set(left, me);
2.293 + } else {
2.294 + _left.set(me, INVALID);
2.295 + }
2.296 + if (m < b) {
2.297 + Edge right = refreshRec(v,m+1,b);
2.298 + _right.set(me, right);
2.299 + _parent.set(right, me);
2.300 + } else {
2.301 + _right.set(me, INVALID);
2.302 + }
2.303 + return me;
2.304 + }
2.305 +
2.306 + void refresh() {
2.307 + for(NodeIt n(_g);n!=INVALID;++n) {
2.308 + std::vector<Edge> v;
2.309 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2.310 + if(v.size()) {
2.311 + std::sort(v.begin(),v.end(),EdgeLess(_g));
2.312 + Edge head = refreshRec(v,0,v.size()-1);
2.313 + _head.set(n, head);
2.314 + _parent.set(head, INVALID);
2.315 + }
2.316 + else _head.set(n, INVALID);
2.317 + }
2.318 + }
2.319 +
2.320 + void zig(Edge v) {
2.321 + Edge w = _parent[v];
2.322 + _parent.set(v, _parent[w]);
2.323 + _parent.set(w, v);
2.324 + _left.set(w, _right[v]);
2.325 + _right.set(v, w);
2.326 + if (_parent[v] != INVALID) {
2.327 + if (_right[_parent[v]] == w) {
2.328 + _right.set(_parent[v], v);
2.329 + } else {
2.330 + _left.set(_parent[v], v);
2.331 + }
2.332 + }
2.333 + if (_left[w] != INVALID){
2.334 + _parent.set(_left[w], w);
2.335 + }
2.336 + }
2.337 +
2.338 + void zag(Edge v) {
2.339 + Edge w = _parent[v];
2.340 + _parent.set(v, _parent[w]);
2.341 + _parent.set(w, v);
2.342 + _right.set(w, _left[v]);
2.343 + _left.set(v, w);
2.344 + if (_parent[v] != INVALID){
2.345 + if (_left[_parent[v]] == w) {
2.346 + _left.set(_parent[v], v);
2.347 + } else {
2.348 + _right.set(_parent[v], v);
2.349 + }
2.350 + }
2.351 + if (_right[w] != INVALID){
2.352 + _parent.set(_right[w], w);
2.353 + }
2.354 + }
2.355 +
2.356 + void splay(Edge v) {
2.357 + while (_parent[v] != INVALID) {
2.358 + if (v == _left[_parent[v]]) {
2.359 + if (_parent[_parent[v]] == INVALID) {
2.360 + zig(v);
2.361 + } else {
2.362 + if (_parent[v] == _left[_parent[_parent[v]]]) {
2.363 + zig(_parent[v]);
2.364 + zig(v);
2.365 + } else {
2.366 + zig(v);
2.367 + zag(v);
2.368 + }
2.369 + }
2.370 + } else {
2.371 + if (_parent[_parent[v]] == INVALID) {
2.372 + zag(v);
2.373 + } else {
2.374 + if (_parent[v] == _left[_parent[_parent[v]]]) {
2.375 + zag(v);
2.376 + zig(v);
2.377 + } else {
2.378 + zag(_parent[v]);
2.379 + zag(v);
2.380 + }
2.381 + }
2.382 + }
2.383 + }
2.384 + _head[_g.source(v)] = v;
2.385 + }
2.386 +
2.387 +
2.388 + public:
2.389 +
2.390 + ///Find an edge between two nodes.
2.391 +
2.392 + ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2.393 + /// <em>d</em> is the number of outgoing edges of \c s.
2.394 + ///\param s The source node
2.395 + ///\param t The target node
2.396 + ///\return An edge from \c s to \c t if there exists,
2.397 + ///\ref INVALID otherwise.
2.398 + Edge operator()(Node s, Node t) const
2.399 + {
2.400 + Edge e = _head[s];
2.401 + while (true) {
2.402 + if (_g.target(e) == t) {
2.403 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.404 + return e;
2.405 + } else if (t < _g.target(e)) {
2.406 + if (_left[e] == INVALID) {
2.407 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.408 + return INVALID;
2.409 + } else {
2.410 + e = _left[e];
2.411 + }
2.412 + } else {
2.413 + if (_right[e] == INVALID) {
2.414 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.415 + return INVALID;
2.416 + } else {
2.417 + e = _right[e];
2.418 + }
2.419 + }
2.420 + }
2.421 + }
2.422 +
2.423 + ///Find the first edge between two nodes.
2.424 +
2.425 + ///Find the first edge between two nodes in time
2.426 + /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2.427 + /// outgoing edges of \c s.
2.428 + ///\param s The source node
2.429 + ///\param t The target node
2.430 + ///\return An edge from \c s to \c t if there exists, \ref INVALID
2.431 + /// otherwise.
2.432 + Edge findFirst(Node s, Node t) const
2.433 + {
2.434 + Edge e = _head[s];
2.435 + Edge r = INVALID;
2.436 + while (true) {
2.437 + if (_g.target(e) < t) {
2.438 + if (_right[e] == INVALID) {
2.439 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.440 + return r;
2.441 + } else {
2.442 + e = _right[e];
2.443 + }
2.444 + } else {
2.445 + if (_g.target(e) == t) {
2.446 + r = e;
2.447 + }
2.448 + if (_left[e] == INVALID) {
2.449 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.450 + return r;
2.451 + } else {
2.452 + e = _left[e];
2.453 + }
2.454 + }
2.455 + }
2.456 + }
2.457 +
2.458 + ///Find the next edge between two nodes.
2.459 +
2.460 + ///Find the next edge between two nodes in time
2.461 + /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2.462 + /// outgoing edges of \c s.
2.463 + ///\param s The source node
2.464 + ///\param t The target node
2.465 + ///\return An edge from \c s to \c t if there exists, \ref INVALID
2.466 + /// otherwise.
2.467 +
2.468 + ///\note If \c e is not the result of the previous \c findFirst()
2.469 + ///operation then the amorized time bound can not be guaranteed.
2.470 +#ifdef DOXYGEN
2.471 + Edge findNext(Node s, Node t, Edge e) const
2.472 +#else
2.473 + Edge findNext(Node, Node t, Edge e) const
2.474 +#endif
2.475 + {
2.476 + if (_right[e] != INVALID) {
2.477 + e = _right[e];
2.478 + while (_left[e] != INVALID) {
2.479 + e = _left[e];
2.480 + }
2.481 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.482 + } else {
2.483 + while (_parent[e] != INVALID && _right[_parent[e]] == e) {
2.484 + e = _parent[e];
2.485 + }
2.486 + if (_parent[e] == INVALID) {
2.487 + return INVALID;
2.488 + } else {
2.489 + e = _parent[e];
2.490 + const_cast<DynEdgeLookUp&>(*this).splay(e);
2.491 + }
2.492 + }
2.493 + if (_g.target(e) == t) return e;
2.494 + else return INVALID;
2.495 + }
2.496 +
2.497 + };
2.498 +
2.499 ///Fast edge look up between given endpoints.
2.500
2.501 ///\ingroup gutils
2.502 @@ -2487,6 +2951,7 @@
2.503 ///
2.504 ///\param G The type of the underlying graph.
2.505 ///
2.506 + ///\sa DynEdgeLookUp
2.507 ///\sa AllEdgeLookUp
2.508 template<class G>
2.509 class EdgeLookUp
2.510 @@ -2522,12 +2987,12 @@
2.511 EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2.512
2.513 private:
2.514 - Edge refresh_rec(std::vector<Edge> &v,int a,int b)
2.515 + Edge refreshRec(std::vector<Edge> &v,int a,int b)
2.516 {
2.517 int m=(a+b)/2;
2.518 Edge me=v[m];
2.519 - _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
2.520 - _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
2.521 + _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2.522 + _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2.523 return me;
2.524 }
2.525 public:
2.526 @@ -2543,7 +3008,7 @@
2.527 for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2.528 if(v.size()) {
2.529 std::sort(v.begin(),v.end(),EdgeLess(_g));
2.530 - _head[n]=refresh_rec(v,0,v.size()-1);
2.531 + _head[n]=refreshRec(v,0,v.size()-1);
2.532 }
2.533 else _head[n]=INVALID;
2.534 }
2.535 @@ -2599,6 +3064,7 @@
2.536 ///
2.537 ///\param G The type of the underlying graph.
2.538 ///
2.539 + ///\sa DynEdgeLookUp
2.540 ///\sa EdgeLookUp
2.541 template<class G>
2.542 class AllEdgeLookUp : public EdgeLookUp<G>