COIN-OR::LEMON - Graph Library

Changeset 233:28239207a8a3 in lemon-1.2 for lemon


Ignore:
Timestamp:
07/23/08 19:32:48 (16 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Unify DynArcLookUp? interface (ticket #127)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r232 r233  
    3030///
    3131///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
    3333///do not have to be included directly.
    3434
     
    11721172
    11731173  ///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>,
    11751175  ///where <em>d</em> is the out-degree of the source node.
    11761176  ///
    11771177  ///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.
    11791179  ///
    11801180  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
     
    14241424      for(NodeIt n(_g);n!=INVALID;++n) {
    14251425        std::vector<Arc> v;
    1426         for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
    1427         if(v.size()) {
     1426        for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
     1427        if (!v.empty()) {
    14281428          std::sort(v.begin(),v.end(),ArcLess(_g));
    14291429          Arc head = refreshRec(v,0,v.size()-1);
     
    15071507    ///Find an arc between two nodes.
    15081508
    1509     ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
    1510     /// <em>d</em> is the number of outgoing arcs of \c s.
     1509    ///Find an arc between two nodes.
    15111510    ///\param s The source node
    15121511    ///\param t The target node
    1513     ///\return An arc from \c s to \c t if there exists,
    1514     ///\ref INVALID otherwise.
    1515     Arc operator()(Node s, Node t) const
    1516     {
    1517       Arc a = _head[s];
    1518       if (a == INVALID) return INVALID;
    1519       while (true) {
    1520         if (_g.target(a) == t) {
     1512    ///\param p The previous arc between \c s and \c t. It it is INVALID or
     1513    ///not given, the operator finds the first appropriate arc.
     1514    ///\return An arc from \c s to \c t after \c p or
     1515    ///\ref INVALID if there is no more.
     1516    ///
     1517    ///For example, you can count the number of arcs from \c u to \c v in the
     1518    ///following way.
     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          }
    15211569          const_cast<DynArcLookUp&>(*this).splay(a);
    1522           return a;
    1523         } else if (t < _g.target(a)) {
    1524           if (_left[a] == INVALID) {
    1525             const_cast<DynArcLookUp&>(*this).splay(a);
     1570        } else {
     1571          while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
     1572            a = _parent[a];
     1573          }
     1574          if (_parent[a] == INVALID) {
    15261575            return INVALID;
    15271576          } else {
    1528             a = _left[a];
     1577            a = _parent[a];
     1578            const_cast<DynArcLookUp&>(*this).splay(a);
    15291579          }
    1530         } else  {
    1531           if (_right[a] == INVALID) {
    1532             const_cast<DynArcLookUp&>(*this).splay(a);
    1533             return INVALID;
    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;
     1580        }
     1581        if (_g.target(a) == t) return a;
     1582        else return INVALID;
     1583      }
    16141584    }
    16151585
Note: See TracChangeset for help on using the changeset viewer.