1.1 --- a/lemon/core.h Wed Jul 23 19:21:20 2008 +0200
1.2 +++ b/lemon/core.h Wed Jul 23 19:32:48 2008 +0200
1.3 @@ -29,7 +29,7 @@
1.4 ///\brief LEMON core utilities.
1.5 ///
1.6 ///This header file contains core utilities for LEMON.
1.7 -///It is automatically included by all graph types, therefore it usually
1.8 +///It is automatically included by all graph types, therefore it usually
1.9 ///do not have to be included directly.
1.10
1.11 namespace lemon {
1.12 @@ -1171,11 +1171,11 @@
1.13 ///Dynamic arc look up between given endpoints.
1.14
1.15 ///Using this class, you can find an arc in a digraph from a given
1.16 - ///source to a given target in amortized time <em>O(log d)</em>,
1.17 + ///source to a given target in amortized time <em>O(log</em>d<em>)</em>,
1.18 ///where <em>d</em> is the out-degree of the source node.
1.19 ///
1.20 ///It is possible to find \e all parallel arcs between two nodes with
1.21 - ///the \c findFirst() and \c findNext() members.
1.22 + ///the \c operator() member.
1.23 ///
1.24 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
1.25 ///digraph is not changed so frequently.
1.26 @@ -1423,8 +1423,8 @@
1.27 void refresh() {
1.28 for(NodeIt n(_g);n!=INVALID;++n) {
1.29 std::vector<Arc> v;
1.30 - for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.31 - if(v.size()) {
1.32 + for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
1.33 + if (!v.empty()) {
1.34 std::sort(v.begin(),v.end(),ArcLess(_g));
1.35 Arc head = refreshRec(v,0,v.size()-1);
1.36 _head.set(n, head);
1.37 @@ -1506,113 +1506,83 @@
1.38
1.39 ///Find an arc between two nodes.
1.40
1.41 - ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.42 - /// <em>d</em> is the number of outgoing arcs of \c s.
1.43 + ///Find an arc between two nodes.
1.44 ///\param s The source node
1.45 ///\param t The target node
1.46 - ///\return An arc from \c s to \c t if there exists,
1.47 - ///\ref INVALID otherwise.
1.48 - Arc operator()(Node s, Node t) const
1.49 - {
1.50 - Arc a = _head[s];
1.51 - if (a == INVALID) return INVALID;
1.52 - while (true) {
1.53 - if (_g.target(a) == t) {
1.54 + ///\param p The previous arc between \c s and \c t. It it is INVALID or
1.55 + ///not given, the operator finds the first appropriate arc.
1.56 + ///\return An arc from \c s to \c t after \c p or
1.57 + ///\ref INVALID if there is no more.
1.58 + ///
1.59 + ///For example, you can count the number of arcs from \c u to \c v in the
1.60 + ///following way.
1.61 + ///\code
1.62 + ///DynArcLookUp<ListDigraph> ae(g);
1.63 + ///...
1.64 + ///int n=0;
1.65 + ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
1.66 + ///\endcode
1.67 + ///
1.68 + ///Finding the arcs take at most <em>O(</em>log<em>d)</em>
1.69 + ///amortized time, specifically, the time complexity of the lookups
1.70 + ///is equal to the optimal search tree implementation for the
1.71 + ///current query distribution in a constant factor.
1.72 + ///
1.73 + ///\note This is a dynamic data structure, therefore the data
1.74 + ///structure is updated after each graph alteration. However,
1.75 + ///theoretically this data structure is faster than \c ArcLookUp
1.76 + ///or AllEdgeLookup, but it often provides worse performance than
1.77 + ///them.
1.78 + ///
1.79 + Arc operator()(Node s, Node t, Arc p = INVALID) const {
1.80 + if (p == INVALID) {
1.81 + Arc a = _head[s];
1.82 + if (a == INVALID) return INVALID;
1.83 + Arc r = INVALID;
1.84 + while (true) {
1.85 + if (_g.target(a) < t) {
1.86 + if (_right[a] == INVALID) {
1.87 + const_cast<DynArcLookUp&>(*this).splay(a);
1.88 + return r;
1.89 + } else {
1.90 + a = _right[a];
1.91 + }
1.92 + } else {
1.93 + if (_g.target(a) == t) {
1.94 + r = a;
1.95 + }
1.96 + if (_left[a] == INVALID) {
1.97 + const_cast<DynArcLookUp&>(*this).splay(a);
1.98 + return r;
1.99 + } else {
1.100 + a = _left[a];
1.101 + }
1.102 + }
1.103 + }
1.104 + } else {
1.105 + Arc a = p;
1.106 + if (_right[a] != INVALID) {
1.107 + a = _right[a];
1.108 + while (_left[a] != INVALID) {
1.109 + a = _left[a];
1.110 + }
1.111 const_cast<DynArcLookUp&>(*this).splay(a);
1.112 - return a;
1.113 - } else if (t < _g.target(a)) {
1.114 - if (_left[a] == INVALID) {
1.115 - const_cast<DynArcLookUp&>(*this).splay(a);
1.116 + } else {
1.117 + while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.118 + a = _parent[a];
1.119 + }
1.120 + if (_parent[a] == INVALID) {
1.121 return INVALID;
1.122 } else {
1.123 - a = _left[a];
1.124 - }
1.125 - } else {
1.126 - if (_right[a] == INVALID) {
1.127 + a = _parent[a];
1.128 const_cast<DynArcLookUp&>(*this).splay(a);
1.129 - return INVALID;
1.130 - } else {
1.131 - a = _right[a];
1.132 }
1.133 }
1.134 + if (_g.target(a) == t) return a;
1.135 + else return INVALID;
1.136 }
1.137 }
1.138
1.139 - ///Find the first arc between two nodes.
1.140 -
1.141 - ///Find the first arc between two nodes in time
1.142 - /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.143 - /// outgoing arcs of \c s.
1.144 - ///\param s The source node
1.145 - ///\param t The target node
1.146 - ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.147 - /// otherwise.
1.148 - Arc findFirst(Node s, Node t) const
1.149 - {
1.150 - Arc a = _head[s];
1.151 - if (a == INVALID) return INVALID;
1.152 - Arc r = INVALID;
1.153 - while (true) {
1.154 - if (_g.target(a) < t) {
1.155 - if (_right[a] == INVALID) {
1.156 - const_cast<DynArcLookUp&>(*this).splay(a);
1.157 - return r;
1.158 - } else {
1.159 - a = _right[a];
1.160 - }
1.161 - } else {
1.162 - if (_g.target(a) == t) {
1.163 - r = a;
1.164 - }
1.165 - if (_left[a] == INVALID) {
1.166 - const_cast<DynArcLookUp&>(*this).splay(a);
1.167 - return r;
1.168 - } else {
1.169 - a = _left[a];
1.170 - }
1.171 - }
1.172 - }
1.173 - }
1.174 -
1.175 - ///Find the next arc between two nodes.
1.176 -
1.177 - ///Find the next arc between two nodes in time
1.178 - /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.179 - /// outgoing arcs of \c s.
1.180 - ///\param s The source node
1.181 - ///\param t The target node
1.182 - ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.183 - /// otherwise.
1.184 -
1.185 - ///\note If \c e is not the result of the previous \c findFirst()
1.186 - ///operation then the amorized time bound can not be guaranteed.
1.187 -#ifdef DOXYGEN
1.188 - Arc findNext(Node s, Node t, Arc a) const
1.189 -#else
1.190 - Arc findNext(Node, Node t, Arc a) const
1.191 -#endif
1.192 - {
1.193 - if (_right[a] != INVALID) {
1.194 - a = _right[a];
1.195 - while (_left[a] != INVALID) {
1.196 - a = _left[a];
1.197 - }
1.198 - const_cast<DynArcLookUp&>(*this).splay(a);
1.199 - } else {
1.200 - while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.201 - a = _parent[a];
1.202 - }
1.203 - if (_parent[a] == INVALID) {
1.204 - return INVALID;
1.205 - } else {
1.206 - a = _parent[a];
1.207 - const_cast<DynArcLookUp&>(*this).splay(a);
1.208 - }
1.209 - }
1.210 - if (_g.target(a) == t) return a;
1.211 - else return INVALID;
1.212 - }
1.213 -
1.214 };
1.215
1.216 ///Fast arc look up between given endpoints.