r233:28239207a8a3
Wed, 23 Jul 2008 19:32:48
[Not Reviewed]
0 comments (0 inline)
0
1
0
71
101
| ... | ... |
@@ -26,13 +26,13 @@ |
| 26 | 26 |
#include <lemon/bits/traits.h> |
| 27 | 27 |
|
| 28 | 28 |
///\file |
| 29 | 29 |
///\brief LEMON core utilities. |
| 30 | 30 |
/// |
| 31 | 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 | 33 |
///do not have to be included directly. |
| 34 | 34 |
|
| 35 | 35 |
namespace lemon {
|
| 36 | 36 |
|
| 37 | 37 |
/// \brief Dummy type to make it easier to create invalid iterators. |
| 38 | 38 |
/// |
| ... | ... |
@@ -1168,17 +1168,17 @@ |
| 1168 | 1168 |
}; |
| 1169 | 1169 |
|
| 1170 | 1170 |
|
| 1171 | 1171 |
///Dynamic arc look up between given endpoints. |
| 1172 | 1172 |
|
| 1173 | 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 |
|
| 1174 |
///source to a given target in amortized time <em>O(log</em>d<em>)</em>, |
|
| 1175 | 1175 |
///where <em>d</em> is the out-degree of the source node. |
| 1176 | 1176 |
/// |
| 1177 | 1177 |
///It is possible to find \e all parallel arcs between two nodes with |
| 1178 |
///the \c |
|
| 1178 |
///the \c operator() member. |
|
| 1179 | 1179 |
/// |
| 1180 | 1180 |
///See the \ref ArcLookUp and \ref AllArcLookUp classes if your |
| 1181 | 1181 |
///digraph is not changed so frequently. |
| 1182 | 1182 |
/// |
| 1183 | 1183 |
///This class uses a self-adjusting binary search tree, Sleator's |
| 1184 | 1184 |
///and Tarjan's Splay tree for guarantee the logarithmic amortized |
| ... | ... |
@@ -1420,14 +1420,14 @@ |
| 1420 | 1420 |
return me; |
| 1421 | 1421 |
} |
| 1422 | 1422 |
|
| 1423 | 1423 |
void refresh() {
|
| 1424 | 1424 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
| 1425 | 1425 |
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()) {
|
|
| 1428 | 1428 |
std::sort(v.begin(),v.end(),ArcLess(_g)); |
| 1429 | 1429 |
Arc head = refreshRec(v,0,v.size()-1); |
| 1430 | 1430 |
_head.set(n, head); |
| 1431 | 1431 |
_parent.set(head, INVALID); |
| 1432 | 1432 |
} |
| 1433 | 1433 |
else _head.set(n, INVALID); |
| ... | ... |
@@ -1503,119 +1503,89 @@ |
| 1503 | 1503 |
|
| 1504 | 1504 |
|
| 1505 | 1505 |
public: |
| 1506 | 1506 |
|
| 1507 | 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 |
|
| 1510 |
/// <em>d</em> is the number of outgoing arcs of \c s. |
|
| 1509 |
///Find an arc between two nodes. |
|
| 1511 | 1510 |
///\param s The source node |
| 1512 | 1511 |
///\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 |
} |
|
| 1521 | 1569 |
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) {
|
|
| 1526 | 1575 |
return INVALID; |
| 1527 | 1576 |
} else {
|
| 1528 |
a = _left[a]; |
|
| 1529 |
} |
|
| 1530 |
} else {
|
|
| 1531 |
if (_right[a] == INVALID) {
|
|
| 1577 |
a = _parent[a]; |
|
| 1532 | 1578 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1533 |
return INVALID; |
|
| 1534 |
} else {
|
|
| 1535 |
a = _right[a]; |
|
| 1536 | 1579 |
} |
| 1537 | 1580 |
} |
| 1581 |
if (_g.target(a) == t) return a; |
|
| 1582 |
else return INVALID; |
|
| 1538 | 1583 |
} |
| 1539 | 1584 |
} |
| 1540 | 1585 |
|
| 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 |
} |
|
| 1615 |
|
|
| 1616 | 1586 |
}; |
| 1617 | 1587 |
|
| 1618 | 1588 |
///Fast arc look up between given endpoints. |
| 1619 | 1589 |
|
| 1620 | 1590 |
///Using this class, you can find an arc in a digraph from a given |
| 1621 | 1591 |
///source to a given target in time <em>O(log d)</em>, |
0 comments (0 inline)