1.1 --- a/benchmark/Makefile.am Thu Oct 12 10:51:51 2006 +0000
1.2 +++ b/benchmark/Makefile.am Thu Oct 12 10:53:25 2006 +0000
1.3 @@ -1,5 +1,6 @@
1.4 EXTRA_DIST += \
1.5 benchmark/Makefile
1.6 + benchmark/edge_lookup_test
1.7
1.8 noinst_HEADERS += benchmark/bench_tools.h
1.9
1.10 @@ -11,7 +12,8 @@
1.11 benchmark/swap_bipartite_bench \
1.12 benchmark/bfs-bench \
1.13 benchmark/radix_sort-bench \
1.14 - benchmark/swap_bipartite_bench
1.15 + benchmark/swap_bipartite_bench \
1.16 + benchmark/edge_lookup
1.17
1.18 endif WANT_BENCHMARK
1.19
1.20 @@ -24,3 +26,5 @@
1.21 benchmark_radix_sort_bench_SOURCES = benchmark/radix_sort-bench.cc
1.22
1.23 benchmark_swap_bipartite_bench_SOURCES = benchmark/swap_bipartite_bench.cc
1.24 +
1.25 +benchmark_edge_lookup_SOURCES = benchmark/edge_lookup.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/benchmark/edge_lookup.cc Thu Oct 12 10:53:25 2006 +0000
2.3 @@ -0,0 +1,137 @@
2.4 +// #include<lemon/edge_lookup.h>
2.5 +#include<lemon/edge_lookup_test.h>
2.6 +#include<lemon/smart_graph.h>
2.7 +#include<vector>
2.8 +#include<lemon/time_measure.h>
2.9 +
2.10 +using namespace lemon;
2.11 +
2.12 +GRAPH_TYPEDEFS(SmartGraph)
2.13 +typedef SmartGraph Graph;
2.14 +
2.15 +class FE
2.16 +{
2.17 +public:
2.18 + Graph &_g;
2.19 + FE(Graph &g) :_g(g) {}
2.20 + void operator()()
2.21 + {
2.22 + Edge e;
2.23 +
2.24 + for(NodeIt v(_g);v!=INVALID;++v)
2.25 + for(NodeIt u(_g);u!=INVALID;++u)
2.26 + e=findEdge(_g,u,v);
2.27 + }
2.28 +
2.29 +};
2.30 +
2.31 +class EL
2.32 +{
2.33 +public:
2.34 + Graph &_g;
2.35 + EdgeLookUp<Graph> _el;
2.36 + EL(Graph &g) :_g(g), _el(g) {}
2.37 + void operator()()
2.38 + {
2.39 + Edge e;
2.40 +
2.41 + for(NodeIt v(_g);v!=INVALID;++v)
2.42 + for(NodeIt u(_g);u!=INVALID;++u)
2.43 + e=_el(u,v);
2.44 + }
2.45 +
2.46 +};
2.47 +class EL2
2.48 +{
2.49 +public:
2.50 + Graph &_g;
2.51 + EdgeLookUp2<Graph> _el;
2.52 + EL2(Graph &g) :_g(g), _el(g) {}
2.53 + void operator()()
2.54 + {
2.55 + Edge e;
2.56 +
2.57 + for(NodeIt v(_g);v!=INVALID;++v)
2.58 + for(NodeIt u(_g);u!=INVALID;++u)
2.59 + e=_el(u,v);
2.60 + }
2.61 +
2.62 +};
2.63 +
2.64 +class EL3
2.65 +{
2.66 +public:
2.67 + Graph &_g;
2.68 + EdgeLookUp3<Graph> _el;
2.69 + EL3(Graph &g) :_g(g), _el(g) {}
2.70 + void operator()()
2.71 + {
2.72 + Edge e;
2.73 +
2.74 + for(NodeIt v(_g);v!=INVALID;++v)
2.75 + for(NodeIt u(_g);u!=INVALID;++u)
2.76 + e=_el(u,v);
2.77 + }
2.78 +
2.79 +};
2.80 +
2.81 +class EL4
2.82 +{
2.83 +public:
2.84 + Graph &_g;
2.85 + EdgeLookUp4<Graph> _el;
2.86 + EL4(Graph &g) :_g(g), _el(g) {}
2.87 + void operator()()
2.88 + {
2.89 + Edge e;
2.90 +
2.91 + for(NodeIt v(_g);v!=INVALID;++v)
2.92 + for(NodeIt u(_g);u!=INVALID;++u)
2.93 + e=_el(u,v);
2.94 + }
2.95 +
2.96 +};
2.97 +
2.98 +int main(int argc, char**argv)
2.99 +{
2.100 + int N=atoi(argv[1]);
2.101 + int M=int(N*atof(argv[2]));
2.102 +
2.103 + Graph g;
2.104 +
2.105 + std::vector<Node> v;
2.106 + for(int i=0;i<N;i++) v.push_back(g.addNode());
2.107 + for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*N)]);
2.108 +
2.109 +// {
2.110 +// Edge e;
2.111 +
2.112 +// TimeReport t("findEdge: ");
2.113 +// for(NodeIt u(g);u!=INVALID;++u)
2.114 +// for(NodeIt v(g);v!=INVALID;++v)
2.115 +// e=findEdge(g,u,v);
2.116 +// }
2.117 +// {
2.118 +// Edge e;
2.119 +// EdgeLookUp<Graph> el(g);
2.120 +
2.121 +// TimeReport t("EdgeLookUp: ");
2.122 +// for(NodeIt u(g);u!=INVALID;++u)
2.123 +// for(NodeIt v(g);v!=INVALID;++v)
2.124 +// e=el(u,v);
2.125 +// }
2.126 +
2.127 +
2.128 + TimeStamp t1 = runningTimeTest(FE(g),1);
2.129 + TimeStamp t2 = runningTimeTest(EL(g),1);
2.130 + TimeStamp t3 = runningTimeTest(EL2(g),1);
2.131 + TimeStamp t4 = runningTimeTest(EL3(g),1);
2.132 + TimeStamp t5 = runningTimeTest(EL4(g),1);
2.133 +
2.134 + std::cout << t1.userTime()/N/N << ' '
2.135 + << t2.userTime()/N/N << ' '
2.136 + << t3.userTime()/N/N << ' '
2.137 + << t4.userTime()/N/N << ' '
2.138 + << t5.userTime()/N/N << std::endl;
2.139 +}
2.140 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/benchmark/edge_lookup_test Thu Oct 12 10:53:25 2006 +0000
3.3 @@ -0,0 +1,7 @@
3.4 +#!/bin/bash
3.5 +
3.6 +for((i=1;i<50;i++))
3.7 +do
3.8 + echo -n $i ''
3.9 + edge_lookup 100 $i
3.10 +done
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/benchmark/edge_lookup_test.h Thu Oct 12 10:53:25 2006 +0000
4.3 @@ -0,0 +1,281 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2006
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_EDGE_LOOKUP_H
4.23 +#define LEMON_EDGE_LOOKUP_H
4.24 +
4.25 +#include<lemon/graph_utils.h>
4.26 +#include<algorithm>
4.27 +#include<vector>
4.28 +
4.29 +namespace lemon {
4.30 + template<class G>
4.31 + class EdgeLookUp2
4.32 + {
4.33 + public:
4.34 + GRAPH_TYPEDEFS(typename G)
4.35 + typedef G Graph;
4.36 +
4.37 + private:
4.38 + const Graph &_g;
4.39 + typename Graph::template NodeMap<int> _start;
4.40 + typename Graph::template NodeMap<int> _end;
4.41 + std::vector<Edge> _edges;
4.42 +
4.43 + class EdgeLess {
4.44 + const Graph &g;
4.45 + public:
4.46 + EdgeLess(const Graph &_g) : g(_g) {}
4.47 + bool operator()(Edge a,Edge b) const
4.48 + {
4.49 + return g.target(a)<g.target(b);
4.50 + }
4.51 + };
4.52 +
4.53 + public:
4.54 +
4.55 + ///Constructor
4.56 + EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
4.57 +
4.58 + public:
4.59 + ///Refresh the data structure at a node.
4.60 + void refresh(Node n)
4.61 + {
4.62 + const int bi = _start[n] = _edges.size();
4.63 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
4.64 + const typename std::vector<Edge>::iterator ei=_edges.end();
4.65 + _end[n]=_edges.size();
4.66 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
4.67 + }
4.68 + ///Refresh the full data structure.
4.69 + void refresh()
4.70 + {
4.71 + _edges.clear();
4.72 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
4.73 + }
4.74 +
4.75 + ///Find an edge between two nodes.
4.76 +
4.77 + ///Find an edge between two nodes.
4.78 + ///\param s The source node
4.79 + ///\param t The target node
4.80 + ///\return An edge from \c s to \c t if there exists,
4.81 + ///\ref INVALID otherwise.
4.82 +
4.83 + Edge operator()(Node s, Node t)
4.84 + {
4.85 + int a=_start[s];
4.86 + int b=_end[s];
4.87 + while(a<b)
4.88 + {
4.89 + int n=(a+b)/2;
4.90 + Node tt = _g.target(_edges[n]);
4.91 + if(tt==t) return _edges[n];
4.92 + else if(tt<t) a=n+1;
4.93 + else b=n;
4.94 + }
4.95 + return INVALID;
4.96 + }
4.97 +
4.98 + ///Find the next edge
4.99 +
4.100 + ///\warning This function is unimplemented.
4.101 + Edge operator()(Node s, Node t, Edge prev)
4.102 + {
4.103 + return prev==INVALID?(*this)(s,t):INVALID;
4.104 + }
4.105 +
4.106 + };
4.107 +
4.108 + template<class G>
4.109 + class EdgeLookUp3
4.110 + {
4.111 + public:
4.112 + GRAPH_TYPEDEFS(typename G)
4.113 + typedef G Graph;
4.114 +
4.115 + private:
4.116 + const Graph &_g;
4.117 + typename Graph::template NodeMap<Edge*> _start;
4.118 + typename Graph::template NodeMap<Edge*> _end;
4.119 + std::vector<Edge> _edges;
4.120 +
4.121 + class EdgeLess {
4.122 + const Graph &g;
4.123 + public:
4.124 + EdgeLess(const Graph &_g) : g(_g) {}
4.125 + bool operator()(Edge a,Edge b) const
4.126 + {
4.127 + return g.target(a)<g.target(b);
4.128 + }
4.129 + };
4.130 +
4.131 + public:
4.132 +
4.133 + ///Constructor
4.134 + EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
4.135 +
4.136 + public:
4.137 + ///Refresh the data structure at a node.
4.138 + void refresh(Node n)
4.139 + {
4.140 + const int bi = _start[n] = _edges.size();
4.141 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
4.142 + const typename std::vector<Edge>::iterator ei=_edges.end();
4.143 + _end[n]=_edges.size();
4.144 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
4.145 + }
4.146 + ///Refresh the full data structure.
4.147 + void refresh()
4.148 + {
4.149 + _edges.resize(countEdges(_g));
4.150 + int l=0;
4.151 + for(NodeIt n(_g);n!=INVALID;++n)
4.152 + {
4.153 + int ls = l;
4.154 + _start[n]=&(_edges[l]);
4.155 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
4.156 + _end[n]=&(_edges[l]);
4.157 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
4.158 + }
4.159 +
4.160 + }
4.161 +
4.162 + ///Find an edge between two nodes.
4.163 +
4.164 + ///Find an edge between two nodes.
4.165 + ///\param s The source node
4.166 + ///\param t The target node
4.167 + ///\return An edge from \c s to \c t if there exists,
4.168 + ///\ref INVALID otherwise.
4.169 +
4.170 + Edge operator()(Node s, Node t)
4.171 + {
4.172 + Edge *a=_start[s];
4.173 + Edge *b=_end[s];
4.174 + while(a!=b)
4.175 + {
4.176 + Edge *m=a+((b-a)/2);
4.177 + Node tt = _g.target(*m);
4.178 + if(tt==t) return *m;
4.179 + else if(tt<t) a=m+1;
4.180 + else b=m;
4.181 + }
4.182 + return INVALID;
4.183 + }
4.184 +
4.185 + ///Find the next edge
4.186 +
4.187 + ///\warning This function is unimplemented.
4.188 + Edge operator()(Node s, Node t, Edge prev)
4.189 + {
4.190 + return prev==INVALID?(*this)(s,t):INVALID;
4.191 + }
4.192 +
4.193 + };
4.194 +
4.195 + template<class G>
4.196 + class EdgeLookUp4
4.197 + {
4.198 + public:
4.199 + GRAPH_TYPEDEFS(typename G)
4.200 + typedef G Graph;
4.201 +
4.202 + private:
4.203 + const Graph &_g;
4.204 + typename Graph::template NodeMap<Edge*> _start;
4.205 + typename Graph::template NodeMap<Edge*> _end;
4.206 + std::vector<Edge> _edges;
4.207 +
4.208 + class EdgeLess {
4.209 + const Graph &g;
4.210 + public:
4.211 + EdgeLess(const Graph &_g) : g(_g) {}
4.212 + bool operator()(Edge a,Edge b) const
4.213 + {
4.214 + return g.target(a)<g.target(b);
4.215 + }
4.216 + };
4.217 +
4.218 + public:
4.219 +
4.220 + ///Constructor
4.221 + EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
4.222 +
4.223 + public:
4.224 + ///Refresh the data structure at a node.
4.225 + void refresh(Node n)
4.226 + {
4.227 + const int bi = _start[n] = _edges.size();
4.228 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
4.229 + const typename std::vector<Edge>::iterator ei=_edges.end();
4.230 + _end[n]=_edges.size();
4.231 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
4.232 + }
4.233 + ///Refresh the full data structure.
4.234 + void refresh()
4.235 + {
4.236 + _edges.resize(countEdges(_g));
4.237 + int l=0;
4.238 + for(NodeIt n(_g);n!=INVALID;++n)
4.239 + {
4.240 + int ls = l;
4.241 + _start[n]=&(_edges[l]);
4.242 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
4.243 + _end[n]=&(_edges[l]);
4.244 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
4.245 + }
4.246 +
4.247 + }
4.248 +
4.249 + ///Find an edge between two nodes.
4.250 +
4.251 + ///Find an edge between two nodes.
4.252 + ///\param s The source node
4.253 + ///\param t The target node
4.254 + ///\return An edge from \c s to \c t if there exists,
4.255 + ///\ref INVALID otherwise.
4.256 +
4.257 + Edge operator()(Node s, Node t)
4.258 + {
4.259 + Edge *a=_start[s];
4.260 + Edge *b=_end[s];
4.261 + while(a!=b)
4.262 + {
4.263 + Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
4.264 + Node tt = _g.target(*m);
4.265 + if(tt==t) return *m;
4.266 + else if(tt<t) a=m+1;
4.267 + else b=m;
4.268 + }
4.269 + return INVALID;
4.270 + }
4.271 +
4.272 + ///Find the next edge
4.273 +
4.274 + ///\warning This function is unimplemented.
4.275 + Edge operator()(Node s, Node t, Edge prev)
4.276 + {
4.277 + return prev==INVALID?(*this)(s,t):INVALID;
4.278 + }
4.279 +
4.280 + };
4.281 +
4.282 +}
4.283 +
4.284 +#endif
5.1 --- a/lemon/graph_utils.h Thu Oct 12 10:51:51 2006 +0000
5.2 +++ b/lemon/graph_utils.h Thu Oct 12 10:53:25 2006 +0000
5.3 @@ -23,6 +23,7 @@
5.4 #include <vector>
5.5 #include <map>
5.6 #include <cmath>
5.7 +#include <algorithm>
5.8
5.9 #include <lemon/bits/invalid.h>
5.10 #include <lemon/bits/utility.h>
5.11 @@ -374,6 +375,8 @@
5.12 /// }
5.13 ///\endcode
5.14 ///
5.15 + ///\sa EdgeLookUp
5.16 + ///\se AllEdgeLookup
5.17 ///\sa ConEdgeIt
5.18 template <typename Graph>
5.19 inline typename Graph::Edge findEdge(const Graph &g,
5.20 @@ -395,6 +398,8 @@
5.21 ///\endcode
5.22 ///
5.23 ///\sa findEdge()
5.24 + ///\sa EdgeLookUp
5.25 + ///\se AllEdgeLookup
5.26 ///
5.27 /// \author Balazs Dezso
5.28 template <typename _Graph>
5.29 @@ -1838,6 +1843,242 @@
5.30 };
5.31
5.32
5.33 + ///Fast edge look up between given endpoints.
5.34 +
5.35 + ///\ingroup gutils
5.36 + ///Using this class, you can find an edge in a graph from a given
5.37 + ///source to a given target in time <em>O(log d)</em>,
5.38 + ///where <em>d</em> is the out-degree of the source node.
5.39 + ///
5.40 + ///It is not possible to find \e all parallel edges between two nodes.
5.41 + ///Use \ref AllEdgeLookUp for this purpose.
5.42 + ///
5.43 + ///\warning This class is static, so you should refresh() (or at least
5.44 + ///refresh(Node)) this data structure
5.45 + ///whenever the graph changes. This is a time consuming (superlinearly
5.46 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
5.47 + ///
5.48 + ///\param G The type of the underlying graph.
5.49 + ///
5.50 + ///\sa AllEdgeLookUp
5.51 + template<class G>
5.52 + class EdgeLookUp
5.53 + {
5.54 + public:
5.55 + GRAPH_TYPEDEFS(typename G)
5.56 + typedef G Graph;
5.57 +
5.58 + protected:
5.59 + const Graph &_g;
5.60 + typename Graph::template NodeMap<Edge> _head;
5.61 + typename Graph::template EdgeMap<Edge> _left;
5.62 + typename Graph::template EdgeMap<Edge> _right;
5.63 +
5.64 + class EdgeLess {
5.65 + const Graph &g;
5.66 + public:
5.67 + EdgeLess(const Graph &_g) : g(_g) {}
5.68 + bool operator()(Edge a,Edge b) const
5.69 + {
5.70 + return g.target(a)<g.target(b);
5.71 + }
5.72 + };
5.73 +
5.74 + public:
5.75 +
5.76 + ///Constructor
5.77 +
5.78 + ///Constructor.
5.79 + ///
5.80 + ///It builds up the search database, which remains valid until the graph
5.81 + ///changes.
5.82 + EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
5.83 +
5.84 + private:
5.85 + Edge refresh_rec(std::vector<Edge> &v,int a,int b)
5.86 + {
5.87 + int m=(a+b)/2;
5.88 + Edge me=v[m];
5.89 + _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
5.90 + _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
5.91 + return me;
5.92 + }
5.93 + public:
5.94 + ///Refresh the data structure at a node.
5.95 +
5.96 + ///Build up the search database of node \c n.
5.97 + ///
5.98 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
5.99 + ///the number of the outgoing edges of \c n.
5.100 + void refresh(Node n)
5.101 + {
5.102 + std::vector<Edge> v;
5.103 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
5.104 + if(v.size()) {
5.105 + std::sort(v.begin(),v.end(),EdgeLess(_g));
5.106 + _head[n]=refresh_rec(v,0,v.size()-1);
5.107 + }
5.108 + else _head[n]=INVALID;
5.109 + }
5.110 + ///Refresh the full data structure.
5.111 +
5.112 + ///Build up the full search database. In fact, it simply calls
5.113 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
5.114 + ///
5.115 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
5.116 + ///the number of the edges of \c n and <em>D</em> is the maximum
5.117 + ///out-degree of the graph.
5.118 +
5.119 + void refresh()
5.120 + {
5.121 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
5.122 + }
5.123 +
5.124 + ///Find an edge between two nodes.
5.125 +
5.126 + ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
5.127 + /// <em>d</em> is the number of outgoing edges of \c s.
5.128 + ///\param s The source node
5.129 + ///\param t The target node
5.130 + ///\return An edge from \c s to \c t if there exists,
5.131 + ///\ref INVALID otherwise.
5.132 + ///
5.133 + ///\warning If you change the graph, refresh() must be called before using
5.134 + ///this operator. If you change the outgoing edges of
5.135 + ///a single node \c n, then
5.136 + ///\ref refresh(Node) "refresh(n)" is enough.
5.137 + ///
5.138 + Edge operator()(Node s, Node t) const
5.139 + {
5.140 + Edge e;
5.141 + for(e=_head[s];
5.142 + e!=INVALID&&_g.target(e)!=t;
5.143 + e = t < _g.target(e)?_left[e]:_right[e]) ;
5.144 + return e;
5.145 + }
5.146 +
5.147 + };
5.148 +
5.149 + ///Fast look up of all edges between given endpoints.
5.150 +
5.151 + ///\ingroup gutils
5.152 + ///This class is the same as \ref EdgeLookUp, with the addition
5.153 + ///that it makes it possible to find all edges between given endpoints.
5.154 + ///
5.155 + ///\warning This class is static, so you should refresh() (or at least
5.156 + ///refresh(Node)) this data structure
5.157 + ///whenever the graph changes. This is a time consuming (superlinearly
5.158 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
5.159 + ///
5.160 + ///\param G The type of the underlying graph.
5.161 + ///
5.162 + ///\sa EdgeLookUp
5.163 + template<class G>
5.164 + class AllEdgeLookUp : public EdgeLookUp<G>
5.165 + {
5.166 + using EdgeLookUp<G>::_g;
5.167 + using EdgeLookUp<G>::_right;
5.168 + using EdgeLookUp<G>::_left;
5.169 + using EdgeLookUp<G>::_head;
5.170 +
5.171 + GRAPH_TYPEDEFS(typename G)
5.172 + typedef G Graph;
5.173 +
5.174 + typename Graph::template EdgeMap<Edge> _next;
5.175 +
5.176 + Edge refreshNext(Edge head,Edge next=INVALID)
5.177 + {
5.178 + if(head==INVALID) return next;
5.179 + else {
5.180 + next=refreshNext(_right[head],next);
5.181 +// _next[head]=next;
5.182 + _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
5.183 + ? next : INVALID;
5.184 + return refreshNext(_left[head],head);
5.185 + }
5.186 + }
5.187 +
5.188 + void refreshNext()
5.189 + {
5.190 + for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
5.191 + }
5.192 +
5.193 + public:
5.194 + ///Constructor
5.195 +
5.196 + ///Constructor.
5.197 + ///
5.198 + ///It builds up the search database, which remains valid until the graph
5.199 + ///changes.
5.200 + AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
5.201 +
5.202 + ///Refresh the data structure at a node.
5.203 +
5.204 + ///Build up the search database of node \c n.
5.205 + ///
5.206 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
5.207 + ///the number of the outgoing edges of \c n.
5.208 +
5.209 + void refresh(Node n)
5.210 + {
5.211 + EdgeLookUp<G>::refresh(n);
5.212 + refreshNext(_head[n]);
5.213 + }
5.214 +
5.215 + ///Refresh the full data structure.
5.216 +
5.217 + ///Build up the full search database. In fact, it simply calls
5.218 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
5.219 + ///
5.220 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
5.221 + ///the number of the edges of \c n and <em>D</em> is the maximum
5.222 + ///out-degree of the graph.
5.223 +
5.224 + void refresh()
5.225 + {
5.226 + for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
5.227 + }
5.228 +
5.229 + ///Find an edge between two nodes.
5.230 +
5.231 + ///Find an edge between two nodes.
5.232 + ///\param s The source node
5.233 + ///\param t The target node
5.234 + ///\param prev The previous edge between \c s and \c t. It it is INVALID or
5.235 + ///not given, the operator finds the first appropriate edge.
5.236 + ///\return An edge from \c s to \c t after \prev or
5.237 + ///\ref INVALID if there is no more.
5.238 + ///
5.239 + ///For example, you can count the number of edges from \c u to \c v in the
5.240 + ///following way.
5.241 + ///\code
5.242 + ///AllEdgeLookUp<ListGraph> ae(g);
5.243 + ///...
5.244 + ///int n=0;
5.245 + ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
5.246 + ///\endcode
5.247 + ///
5.248 + ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
5.249 + /// <em>d</em> is the number of outgoing edges of \c s. Then, the
5.250 + ///consecutive edges are found in constant time.
5.251 + ///
5.252 + ///\warning If you change the graph, refresh() must be called before using
5.253 + ///this operator. If you change the outgoing edges of
5.254 + ///a single node \c n, then
5.255 + ///\ref refresh(Node) "refresh(n)" is enough.
5.256 + ///
5.257 +#ifdef DOXYGEN
5.258 + Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
5.259 +#else
5.260 + using EdgeLookUp<G>::operator() ;
5.261 + Edge operator()(Node s, Node t, Edge prev) const
5.262 + {
5.263 + return prev==INVALID?(*this)(s,t):_next[prev];
5.264 + }
5.265 +#endif
5.266 +
5.267 + };
5.268 +
5.269 /// @}
5.270
5.271 } //END OF NAMESPACE LEMON