lemon: comparison lemon/core.h

equal deleted inserted replaced

-:eab500975184
+:16844a528923
 ///\file
 ///\brief LEMON core utilities.
 ///
 ///This header file contains core utilities for LEMON.
 ///It is automatically included by all graph types, therefore it usually
 ///do not have to be included directly.
 namespace lemon {
 /// \brief Dummy type to make it easier to create invalid iterators.
 ///Dynamic arc look up between given endpoints.
 ///Using this class, you can find an arc in a digraph from a given
-///source to a given target in amortized time <em>O(log d)</em>,
+///source to a given target in amortized time <em>O(log</em>d<em>)</em>,
 ///where <em>d</em> is the out-degree of the source node.
 ///
 ///It is possible to find \e all parallel arcs between two nodes with
-///the \c findFirst() and \c findNext() members.
+///the \c operator() member.
 ///
 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
 ///digraph is not changed so frequently.
 ///
 ///This class uses a self-adjusting binary search tree, Sleator's
 }
 void refresh() {
 for(NodeIt n(_g);n!=INVALID;++n) {
 std::vector<Arc> v;
-for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
+for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
-if(v.size()) {
+if (!v.empty()) {
 std::sort(v.begin(),v.end(),ArcLess(_g));
 Arc head = refreshRec(v,0,v.size()-1);
 _head.set(n, head);
 _parent.set(head, INVALID);
 }
 public:
 ///Find an arc between two nodes.
-///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
+///Find an arc between two nodes.
-/// <em>d</em> is the number of outgoing arcs of \c s.
 ///\param s The source node
 ///\param t The target node
-///\return An arc from \c s to \c t if there exists,
+///\param p The previous arc between \c s and \c t. It it is INVALID or
-///\ref INVALID otherwise.
+///not given, the operator finds the first appropriate arc.
-Arc operator()(Node s, Node t) const
+///\return An arc from \c s to \c t after \c p or
-{
+///\ref INVALID if there is no more.
-Arc a = _head[s];
+///
-if (a == INVALID) return INVALID;
+///For example, you can count the number of arcs from \c u to \c v in the
-while (true) {
+///following way.
-if (_g.target(a) == t) {
+///\code
+///DynArcLookUp<ListDigraph> ae(g);
+///...
+///int n=0;
+///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
+///\endcode
+///
+///Finding the arcs take at most <em>O(</em>log<em>d)</em>
+///amortized time, specifically, the time complexity of the lookups
+///is equal to the optimal search tree implementation for the
+///current query distribution in a constant factor.
+///
+///\note This is a dynamic data structure, therefore the data
+///structure is updated after each graph alteration. However,
+///theoretically this data structure is faster than \c ArcLookUp
+///or AllEdgeLookup, but it often provides worse performance than
+///them.
+///
+Arc operator()(Node s, Node t, Arc p = INVALID) const  {
+if (p == INVALID) {
+Arc a = _head[s];
+if (a == INVALID) return INVALID;
+Arc r = INVALID;
+while (true) {
+if (_g.target(a) < t) {
+if (_right[a] == INVALID) {
+const_cast<DynArcLookUp&>(*this).splay(a);
+return r;
+} else {
+a = _right[a];
+}
+} else {
+if (_g.target(a) == t) {
+r = a;
+}
+if (_left[a] == INVALID) {
+const_cast<DynArcLookUp&>(*this).splay(a);
+return r;
+} else {
+a = _left[a];
+}
+}
+}
+} else {
+Arc a = p;
+if (_right[a] != INVALID) {
+a = _right[a];
+while (_left[a] != INVALID) {
+a = _left[a];
+}
 const_cast<DynArcLookUp&>(*this).splay(a);
-return a;
+} else {
-} else if (t < _g.target(a)) {
+while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
-if (_left[a] == INVALID) {
+a = _parent[a];
-const_cast<DynArcLookUp&>(*this).splay(a);
+}
+if (_parent[a] == INVALID) {
 return INVALID;
 } else {
-a = _left[a];
+a = _parent[a];
+const_cast<DynArcLookUp&>(*this).splay(a);
 }
-} else  {
+}
-if (_right[a] == INVALID) {
+if (_g.target(a) == t) return a;
-const_cast<DynArcLookUp&>(*this).splay(a);
+else return INVALID;
-return INVALID;
+}
-} else {
-a = _right[a];
-}
-}
-}
-}
-///Find the first arc between two nodes.
-///Find the first arc between two nodes in time
-/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
-/// outgoing arcs of \c s.
-///\param s The source node
-///\param t The target node
-///\return An arc from \c s to \c t if there exists, \ref INVALID
-/// otherwise.
-Arc findFirst(Node s, Node t) const
-{
-Arc a = _head[s];
-if (a == INVALID) return INVALID;
-Arc r = INVALID;
-while (true) {
-if (_g.target(a) < t) {
-if (_right[a] == INVALID) {
-const_cast<DynArcLookUp&>(*this).splay(a);
-return r;
-} else {
-a = _right[a];
-}
-} else {
-if (_g.target(a) == t) {
-r = a;
-}
-if (_left[a] == INVALID) {
-const_cast<DynArcLookUp&>(*this).splay(a);
-return r;
-} else {
-a = _left[a];
-}
-}
-}
-}
-///Find the next arc between two nodes.
-///Find the next arc between two nodes in time
-/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
-/// outgoing arcs of \c s.
-///\param s The source node
-///\param t The target node
-///\return An arc from \c s to \c t if there exists, \ref INVALID
-/// otherwise.
-///\note If \c e is not the result of the previous \c findFirst()
-///operation then the amorized time bound can not be guaranteed.
-#ifdef DOXYGEN
-Arc findNext(Node s, Node t, Arc a) const
-#else
-Arc findNext(Node, Node t, Arc a) const
-#endif
-{
-if (_right[a] != INVALID) {
-a = _right[a];
-while (_left[a] != INVALID) {
-a = _left[a];
-}
-const_cast<DynArcLookUp&>(*this).splay(a);
-} else {
-while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
-a = _parent[a];
-}
-if (_parent[a] == INVALID) {
-return INVALID;
-} else {
-a = _parent[a];
-const_cast<DynArcLookUp&>(*this).splay(a);
-}
-}
-if (_g.target(a) == t) return a;
-else return INVALID;
 }
 };
 ///Fast arc look up between given endpoints.

changeset 233	28239207a8a3
parent 232	e39056157d24
child 282	dc9e8d2c0df9