equal
deleted
inserted
replaced
1552 ///current query distribution in a constant factor. |
1552 ///current query distribution in a constant factor. |
1553 /// |
1553 /// |
1554 ///\note This is a dynamic data structure, therefore the data |
1554 ///\note This is a dynamic data structure, therefore the data |
1555 ///structure is updated after each graph alteration. Thus although |
1555 ///structure is updated after each graph alteration. Thus although |
1556 ///this data structure is theoretically faster than \ref ArcLookUp |
1556 ///this data structure is theoretically faster than \ref ArcLookUp |
1557 ///and \ref AllArcLookup, it often provides worse performance than |
1557 ///and \ref AllArcLookUp, it often provides worse performance than |
1558 ///them. |
1558 ///them. |
1559 Arc operator()(Node s, Node t, Arc p = INVALID) const { |
1559 Arc operator()(Node s, Node t, Arc p = INVALID) const { |
1560 if (p == INVALID) { |
1560 if (p == INVALID) { |
1561 Arc a = _head[s]; |
1561 Arc a = _head[s]; |
1562 if (a == INVALID) return INVALID; |
1562 if (a == INVALID) return INVALID; |
1697 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); |
1697 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); |
1698 } |
1698 } |
1699 |
1699 |
1700 ///Find an arc between two nodes. |
1700 ///Find an arc between two nodes. |
1701 |
1701 |
1702 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), where |
1702 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), |
1703 ///<em>d</em> is the number of outgoing arcs of \c s. |
1703 ///where <em>d</em> is the number of outgoing arcs of \c s. |
1704 ///\param s The source node. |
1704 ///\param s The source node. |
1705 ///\param t The target node. |
1705 ///\param t The target node. |
1706 ///\return An arc from \c s to \c t if there exists, |
1706 ///\return An arc from \c s to \c t if there exists, |
1707 ///\ref INVALID otherwise. |
1707 ///\ref INVALID otherwise. |
1708 /// |
1708 /// |
1815 ///... |
1815 ///... |
1816 ///int n = 0; |
1816 ///int n = 0; |
1817 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; |
1817 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; |
1818 ///\endcode |
1818 ///\endcode |
1819 /// |
1819 /// |
1820 ///Finding the first arc take <em>O</em>(log<em>d</em>) time, where |
1820 ///Finding the first arc take <em>O</em>(log<em>d</em>) time, |
1821 ///<em>d</em> is the number of outgoing arcs of \c s. Then, the |
1821 ///where <em>d</em> is the number of outgoing arcs of \c s. Then the |
1822 ///consecutive arcs are found in constant time. |
1822 ///consecutive arcs are found in constant time. |
1823 /// |
1823 /// |
1824 ///\warning If you change the digraph, refresh() must be called before using |
1824 ///\warning If you change the digraph, refresh() must be called before using |
1825 ///this operator. If you change the outgoing arcs of |
1825 ///this operator. If you change the outgoing arcs of |
1826 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. |
1826 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. |