lemon/core.h
 changeset 233 28239207a8a3 parent 232 e39056157d24 child 282 dc9e8d2c0df9
     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.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.