1.1 --- a/lemon/graph_utils.h Thu Oct 12 10:51:51 2006 +0000
1.2 +++ b/lemon/graph_utils.h Thu Oct 12 10:53:25 2006 +0000
1.3 @@ -23,6 +23,7 @@
1.4 #include <vector>
1.5 #include <map>
1.6 #include <cmath>
1.7 +#include <algorithm>
1.8
1.9 #include <lemon/bits/invalid.h>
1.10 #include <lemon/bits/utility.h>
1.11 @@ -374,6 +375,8 @@
1.12 /// }
1.13 ///\endcode
1.14 ///
1.15 + ///\sa EdgeLookUp
1.16 + ///\se AllEdgeLookup
1.17 ///\sa ConEdgeIt
1.18 template <typename Graph>
1.19 inline typename Graph::Edge findEdge(const Graph &g,
1.20 @@ -395,6 +398,8 @@
1.21 ///\endcode
1.22 ///
1.23 ///\sa findEdge()
1.24 + ///\sa EdgeLookUp
1.25 + ///\se AllEdgeLookup
1.26 ///
1.27 /// \author Balazs Dezso
1.28 template <typename _Graph>
1.29 @@ -1838,6 +1843,242 @@
1.30 };
1.31
1.32
1.33 + ///Fast edge look up between given endpoints.
1.34 +
1.35 + ///\ingroup gutils
1.36 + ///Using this class, you can find an edge in a graph from a given
1.37 + ///source to a given target in time <em>O(log d)</em>,
1.38 + ///where <em>d</em> is the out-degree of the source node.
1.39 + ///
1.40 + ///It is not possible to find \e all parallel edges between two nodes.
1.41 + ///Use \ref AllEdgeLookUp for this purpose.
1.42 + ///
1.43 + ///\warning This class is static, so you should refresh() (or at least
1.44 + ///refresh(Node)) this data structure
1.45 + ///whenever the graph changes. This is a time consuming (superlinearly
1.46 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
1.47 + ///
1.48 + ///\param G The type of the underlying graph.
1.49 + ///
1.50 + ///\sa AllEdgeLookUp
1.51 + template<class G>
1.52 + class EdgeLookUp
1.53 + {
1.54 + public:
1.55 + GRAPH_TYPEDEFS(typename G)
1.56 + typedef G Graph;
1.57 +
1.58 + protected:
1.59 + const Graph &_g;
1.60 + typename Graph::template NodeMap<Edge> _head;
1.61 + typename Graph::template EdgeMap<Edge> _left;
1.62 + typename Graph::template EdgeMap<Edge> _right;
1.63 +
1.64 + class EdgeLess {
1.65 + const Graph &g;
1.66 + public:
1.67 + EdgeLess(const Graph &_g) : g(_g) {}
1.68 + bool operator()(Edge a,Edge b) const
1.69 + {
1.70 + return g.target(a)<g.target(b);
1.71 + }
1.72 + };
1.73 +
1.74 + public:
1.75 +
1.76 + ///Constructor
1.77 +
1.78 + ///Constructor.
1.79 + ///
1.80 + ///It builds up the search database, which remains valid until the graph
1.81 + ///changes.
1.82 + EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1.83 +
1.84 + private:
1.85 + Edge refresh_rec(std::vector<Edge> &v,int a,int b)
1.86 + {
1.87 + int m=(a+b)/2;
1.88 + Edge me=v[m];
1.89 + _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
1.90 + _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
1.91 + return me;
1.92 + }
1.93 + public:
1.94 + ///Refresh the data structure at a node.
1.95 +
1.96 + ///Build up the search database of node \c n.
1.97 + ///
1.98 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.99 + ///the number of the outgoing edges of \c n.
1.100 + void refresh(Node n)
1.101 + {
1.102 + std::vector<Edge> v;
1.103 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.104 + if(v.size()) {
1.105 + std::sort(v.begin(),v.end(),EdgeLess(_g));
1.106 + _head[n]=refresh_rec(v,0,v.size()-1);
1.107 + }
1.108 + else _head[n]=INVALID;
1.109 + }
1.110 + ///Refresh the full data structure.
1.111 +
1.112 + ///Build up the full search database. In fact, it simply calls
1.113 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.114 + ///
1.115 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.116 + ///the number of the edges of \c n and <em>D</em> is the maximum
1.117 + ///out-degree of the graph.
1.118 +
1.119 + void refresh()
1.120 + {
1.121 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.122 + }
1.123 +
1.124 + ///Find an edge between two nodes.
1.125 +
1.126 + ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
1.127 + /// <em>d</em> is the number of outgoing edges of \c s.
1.128 + ///\param s The source node
1.129 + ///\param t The target node
1.130 + ///\return An edge from \c s to \c t if there exists,
1.131 + ///\ref INVALID otherwise.
1.132 + ///
1.133 + ///\warning If you change the graph, refresh() must be called before using
1.134 + ///this operator. If you change the outgoing edges of
1.135 + ///a single node \c n, then
1.136 + ///\ref refresh(Node) "refresh(n)" is enough.
1.137 + ///
1.138 + Edge operator()(Node s, Node t) const
1.139 + {
1.140 + Edge e;
1.141 + for(e=_head[s];
1.142 + e!=INVALID&&_g.target(e)!=t;
1.143 + e = t < _g.target(e)?_left[e]:_right[e]) ;
1.144 + return e;
1.145 + }
1.146 +
1.147 + };
1.148 +
1.149 + ///Fast look up of all edges between given endpoints.
1.150 +
1.151 + ///\ingroup gutils
1.152 + ///This class is the same as \ref EdgeLookUp, with the addition
1.153 + ///that it makes it possible to find all edges between given endpoints.
1.154 + ///
1.155 + ///\warning This class is static, so you should refresh() (or at least
1.156 + ///refresh(Node)) this data structure
1.157 + ///whenever the graph changes. This is a time consuming (superlinearly
1.158 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
1.159 + ///
1.160 + ///\param G The type of the underlying graph.
1.161 + ///
1.162 + ///\sa EdgeLookUp
1.163 + template<class G>
1.164 + class AllEdgeLookUp : public EdgeLookUp<G>
1.165 + {
1.166 + using EdgeLookUp<G>::_g;
1.167 + using EdgeLookUp<G>::_right;
1.168 + using EdgeLookUp<G>::_left;
1.169 + using EdgeLookUp<G>::_head;
1.170 +
1.171 + GRAPH_TYPEDEFS(typename G)
1.172 + typedef G Graph;
1.173 +
1.174 + typename Graph::template EdgeMap<Edge> _next;
1.175 +
1.176 + Edge refreshNext(Edge head,Edge next=INVALID)
1.177 + {
1.178 + if(head==INVALID) return next;
1.179 + else {
1.180 + next=refreshNext(_right[head],next);
1.181 +// _next[head]=next;
1.182 + _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1.183 + ? next : INVALID;
1.184 + return refreshNext(_left[head],head);
1.185 + }
1.186 + }
1.187 +
1.188 + void refreshNext()
1.189 + {
1.190 + for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1.191 + }
1.192 +
1.193 + public:
1.194 + ///Constructor
1.195 +
1.196 + ///Constructor.
1.197 + ///
1.198 + ///It builds up the search database, which remains valid until the graph
1.199 + ///changes.
1.200 + AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
1.201 +
1.202 + ///Refresh the data structure at a node.
1.203 +
1.204 + ///Build up the search database of node \c n.
1.205 + ///
1.206 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.207 + ///the number of the outgoing edges of \c n.
1.208 +
1.209 + void refresh(Node n)
1.210 + {
1.211 + EdgeLookUp<G>::refresh(n);
1.212 + refreshNext(_head[n]);
1.213 + }
1.214 +
1.215 + ///Refresh the full data structure.
1.216 +
1.217 + ///Build up the full search database. In fact, it simply calls
1.218 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.219 + ///
1.220 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.221 + ///the number of the edges of \c n and <em>D</em> is the maximum
1.222 + ///out-degree of the graph.
1.223 +
1.224 + void refresh()
1.225 + {
1.226 + for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1.227 + }
1.228 +
1.229 + ///Find an edge between two nodes.
1.230 +
1.231 + ///Find an edge between two nodes.
1.232 + ///\param s The source node
1.233 + ///\param t The target node
1.234 + ///\param prev The previous edge between \c s and \c t. It it is INVALID or
1.235 + ///not given, the operator finds the first appropriate edge.
1.236 + ///\return An edge from \c s to \c t after \prev or
1.237 + ///\ref INVALID if there is no more.
1.238 + ///
1.239 + ///For example, you can count the number of edges from \c u to \c v in the
1.240 + ///following way.
1.241 + ///\code
1.242 + ///AllEdgeLookUp<ListGraph> ae(g);
1.243 + ///...
1.244 + ///int n=0;
1.245 + ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
1.246 + ///\endcode
1.247 + ///
1.248 + ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
1.249 + /// <em>d</em> is the number of outgoing edges of \c s. Then, the
1.250 + ///consecutive edges are found in constant time.
1.251 + ///
1.252 + ///\warning If you change the graph, refresh() must be called before using
1.253 + ///this operator. If you change the outgoing edges of
1.254 + ///a single node \c n, then
1.255 + ///\ref refresh(Node) "refresh(n)" is enough.
1.256 + ///
1.257 +#ifdef DOXYGEN
1.258 + Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
1.259 +#else
1.260 + using EdgeLookUp<G>::operator() ;
1.261 + Edge operator()(Node s, Node t, Edge prev) const
1.262 + {
1.263 + return prev==INVALID?(*this)(s,t):_next[prev];
1.264 + }
1.265 +#endif
1.266 +
1.267 + };
1.268 +
1.269 /// @}
1.270
1.271 } //END OF NAMESPACE LEMON