lemon/core.h
changeset 255 914c5432be97
parent 232 e39056157d24
child 282 dc9e8d2c0df9
equal deleted inserted replaced
2:eab500975184 3:16844a528923
    27 
    27 
    28 ///\file
    28 ///\file
    29 ///\brief LEMON core utilities.
    29 ///\brief LEMON core utilities.
    30 ///
    30 ///
    31 ///This header file contains core utilities for LEMON.
    31 ///This header file contains core utilities for LEMON.
    32 ///It is automatically included by all graph types, therefore it usually 
    32 ///It is automatically included by all graph types, therefore it usually
    33 ///do not have to be included directly.
    33 ///do not have to be included directly.
    34 
    34 
    35 namespace lemon {
    35 namespace lemon {
    36 
    36 
    37   /// \brief Dummy type to make it easier to create invalid iterators.
    37   /// \brief Dummy type to make it easier to create invalid iterators.
  1169 
  1169 
  1170 
  1170 
  1171   ///Dynamic arc look up between given endpoints.
  1171   ///Dynamic arc look up between given endpoints.
  1172 
  1172 
  1173   ///Using this class, you can find an arc in a digraph from a given
  1173   ///Using this class, you can find an arc in a digraph from a given
  1174   ///source to a given target in amortized time <em>O(log d)</em>,
  1174   ///source to a given target in amortized time <em>O(log</em>d<em>)</em>,
  1175   ///where <em>d</em> is the out-degree of the source node.
  1175   ///where <em>d</em> is the out-degree of the source node.
  1176   ///
  1176   ///
  1177   ///It is possible to find \e all parallel arcs between two nodes with
  1177   ///It is possible to find \e all parallel arcs between two nodes with
  1178   ///the \c findFirst() and \c findNext() members.
  1178   ///the \c operator() member.
  1179   ///
  1179   ///
  1180   ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
  1180   ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
  1181   ///digraph is not changed so frequently.
  1181   ///digraph is not changed so frequently.
  1182   ///
  1182   ///
  1183   ///This class uses a self-adjusting binary search tree, Sleator's
  1183   ///This class uses a self-adjusting binary search tree, Sleator's
  1421     }
  1421     }
  1422 
  1422 
  1423     void refresh() {
  1423     void refresh() {
  1424       for(NodeIt n(_g);n!=INVALID;++n) {
  1424       for(NodeIt n(_g);n!=INVALID;++n) {
  1425         std::vector<Arc> v;
  1425         std::vector<Arc> v;
  1426         for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
  1426         for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
  1427         if(v.size()) {
  1427         if (!v.empty()) {
  1428           std::sort(v.begin(),v.end(),ArcLess(_g));
  1428           std::sort(v.begin(),v.end(),ArcLess(_g));
  1429           Arc head = refreshRec(v,0,v.size()-1);
  1429           Arc head = refreshRec(v,0,v.size()-1);
  1430           _head.set(n, head);
  1430           _head.set(n, head);
  1431           _parent.set(head, INVALID);
  1431           _parent.set(head, INVALID);
  1432         }
  1432         }
  1504 
  1504 
  1505   public:
  1505   public:
  1506 
  1506 
  1507     ///Find an arc between two nodes.
  1507     ///Find an arc between two nodes.
  1508 
  1508 
  1509     ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
  1509     ///Find an arc between two nodes.
  1510     /// <em>d</em> is the number of outgoing arcs of \c s.
       
  1511     ///\param s The source node
  1510     ///\param s The source node
  1512     ///\param t The target node
  1511     ///\param t The target node
  1513     ///\return An arc from \c s to \c t if there exists,
  1512     ///\param p The previous arc between \c s and \c t. It it is INVALID or
  1514     ///\ref INVALID otherwise.
  1513     ///not given, the operator finds the first appropriate arc.
  1515     Arc operator()(Node s, Node t) const
  1514     ///\return An arc from \c s to \c t after \c p or
  1516     {
  1515     ///\ref INVALID if there is no more.
  1517       Arc a = _head[s];
  1516     ///
  1518       if (a == INVALID) return INVALID;
  1517     ///For example, you can count the number of arcs from \c u to \c v in the
  1519       while (true) {
  1518     ///following way.
  1520         if (_g.target(a) == t) {
  1519     ///\code
       
  1520     ///DynArcLookUp<ListDigraph> ae(g);
       
  1521     ///...
       
  1522     ///int n=0;
       
  1523     ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
       
  1524     ///\endcode
       
  1525     ///
       
  1526     ///Finding the arcs take at most <em>O(</em>log<em>d)</em>
       
  1527     ///amortized time, specifically, the time complexity of the lookups
       
  1528     ///is equal to the optimal search tree implementation for the
       
  1529     ///current query distribution in a constant factor.
       
  1530     ///
       
  1531     ///\note This is a dynamic data structure, therefore the data
       
  1532     ///structure is updated after each graph alteration. However,
       
  1533     ///theoretically this data structure is faster than \c ArcLookUp
       
  1534     ///or AllEdgeLookup, but it often provides worse performance than
       
  1535     ///them.
       
  1536     ///
       
  1537     Arc operator()(Node s, Node t, Arc p = INVALID) const  {
       
  1538       if (p == INVALID) {
       
  1539         Arc a = _head[s];
       
  1540         if (a == INVALID) return INVALID;
       
  1541         Arc r = INVALID;
       
  1542         while (true) {
       
  1543           if (_g.target(a) < t) {
       
  1544             if (_right[a] == INVALID) {
       
  1545               const_cast<DynArcLookUp&>(*this).splay(a);
       
  1546               return r;
       
  1547             } else {
       
  1548               a = _right[a];
       
  1549             }
       
  1550           } else {
       
  1551             if (_g.target(a) == t) {
       
  1552               r = a;
       
  1553             }
       
  1554             if (_left[a] == INVALID) {
       
  1555               const_cast<DynArcLookUp&>(*this).splay(a);
       
  1556               return r;
       
  1557             } else {
       
  1558               a = _left[a];
       
  1559             }
       
  1560           }
       
  1561         }
       
  1562       } else {
       
  1563         Arc a = p;
       
  1564         if (_right[a] != INVALID) {
       
  1565           a = _right[a];
       
  1566           while (_left[a] != INVALID) {
       
  1567             a = _left[a];
       
  1568           }
  1521           const_cast<DynArcLookUp&>(*this).splay(a);
  1569           const_cast<DynArcLookUp&>(*this).splay(a);
  1522           return a;
  1570         } else {
  1523         } else if (t < _g.target(a)) {
  1571           while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
  1524           if (_left[a] == INVALID) {
  1572             a = _parent[a];
  1525             const_cast<DynArcLookUp&>(*this).splay(a);
  1573           }
       
  1574           if (_parent[a] == INVALID) {
  1526             return INVALID;
  1575             return INVALID;
  1527           } else {
  1576           } else {
  1528             a = _left[a];
  1577             a = _parent[a];
       
  1578             const_cast<DynArcLookUp&>(*this).splay(a);
  1529           }
  1579           }
  1530         } else  {
  1580         }
  1531           if (_right[a] == INVALID) {
  1581         if (_g.target(a) == t) return a;
  1532             const_cast<DynArcLookUp&>(*this).splay(a);
  1582         else return INVALID;
  1533             return INVALID;
  1583       }
  1534           } else {
       
  1535             a = _right[a];
       
  1536           }
       
  1537         }
       
  1538       }
       
  1539     }
       
  1540 
       
  1541     ///Find the first arc between two nodes.
       
  1542 
       
  1543     ///Find the first arc between two nodes in time
       
  1544     /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
       
  1545     /// outgoing arcs of \c s.
       
  1546     ///\param s The source node
       
  1547     ///\param t The target node
       
  1548     ///\return An arc from \c s to \c t if there exists, \ref INVALID
       
  1549     /// otherwise.
       
  1550     Arc findFirst(Node s, Node t) const
       
  1551     {
       
  1552       Arc a = _head[s];
       
  1553       if (a == INVALID) return INVALID;
       
  1554       Arc r = INVALID;
       
  1555       while (true) {
       
  1556         if (_g.target(a) < t) {
       
  1557           if (_right[a] == INVALID) {
       
  1558             const_cast<DynArcLookUp&>(*this).splay(a);
       
  1559             return r;
       
  1560           } else {
       
  1561             a = _right[a];
       
  1562           }
       
  1563         } else {
       
  1564           if (_g.target(a) == t) {
       
  1565             r = a;
       
  1566           }
       
  1567           if (_left[a] == INVALID) {
       
  1568             const_cast<DynArcLookUp&>(*this).splay(a);
       
  1569             return r;
       
  1570           } else {
       
  1571             a = _left[a];
       
  1572           }
       
  1573         }
       
  1574       }
       
  1575     }
       
  1576 
       
  1577     ///Find the next arc between two nodes.
       
  1578 
       
  1579     ///Find the next arc between two nodes in time
       
  1580     /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
       
  1581     /// outgoing arcs of \c s.
       
  1582     ///\param s The source node
       
  1583     ///\param t The target node
       
  1584     ///\return An arc from \c s to \c t if there exists, \ref INVALID
       
  1585     /// otherwise.
       
  1586 
       
  1587     ///\note If \c e is not the result of the previous \c findFirst()
       
  1588     ///operation then the amorized time bound can not be guaranteed.
       
  1589 #ifdef DOXYGEN
       
  1590     Arc findNext(Node s, Node t, Arc a) const
       
  1591 #else
       
  1592     Arc findNext(Node, Node t, Arc a) const
       
  1593 #endif
       
  1594     {
       
  1595       if (_right[a] != INVALID) {
       
  1596         a = _right[a];
       
  1597         while (_left[a] != INVALID) {
       
  1598           a = _left[a];
       
  1599         }
       
  1600         const_cast<DynArcLookUp&>(*this).splay(a);
       
  1601       } else {
       
  1602         while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
       
  1603           a = _parent[a];
       
  1604         }
       
  1605         if (_parent[a] == INVALID) {
       
  1606           return INVALID;
       
  1607         } else {
       
  1608           a = _parent[a];
       
  1609           const_cast<DynArcLookUp&>(*this).splay(a);
       
  1610         }
       
  1611       }
       
  1612       if (_g.target(a) == t) return a;
       
  1613       else return INVALID;
       
  1614     }
  1584     }
  1615 
  1585 
  1616   };
  1586   };
  1617 
  1587 
  1618   ///Fast arc look up between given endpoints.
  1588   ///Fast arc look up between given endpoints.