r232:e39056157d24
Wed, 23 Jul 2008 19:21:20
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -1371,32 +1371,33 @@ |
| 1371 | 1371 |
_parent.set(_left[arc], e); |
| 1372 | 1372 |
_right.set(e, _right[arc]); |
| 1373 | 1373 |
_parent.set(_right[arc], e); |
| 1374 | 1374 |
|
| 1375 | 1375 |
_parent.set(e, _parent[arc]); |
| 1376 | 1376 |
if (_parent[arc] != INVALID) {
|
| 1377 | 1377 |
if (_left[_parent[arc]] == arc) {
|
| 1378 | 1378 |
_left.set(_parent[arc], e); |
| 1379 | 1379 |
} else {
|
| 1380 | 1380 |
_right.set(_parent[arc], e); |
| 1381 | 1381 |
} |
| 1382 | 1382 |
} |
| 1383 | 1383 |
splay(s); |
| 1384 | 1384 |
} else {
|
| 1385 | 1385 |
_right.set(e, _right[arc]); |
| 1386 | 1386 |
_parent.set(_right[arc], e); |
| 1387 |
_parent.set(e, _parent[arc]); |
|
| 1387 | 1388 |
|
| 1388 | 1389 |
if (_parent[arc] != INVALID) {
|
| 1389 | 1390 |
if (_left[_parent[arc]] == arc) {
|
| 1390 | 1391 |
_left.set(_parent[arc], e); |
| 1391 | 1392 |
} else {
|
| 1392 | 1393 |
_right.set(_parent[arc], e); |
| 1393 | 1394 |
} |
| 1394 | 1395 |
} else {
|
| 1395 | 1396 |
_head.set(_g.source(arc), e); |
| 1396 | 1397 |
} |
| 1397 | 1398 |
} |
| 1398 | 1399 |
} |
| 1399 | 1400 |
} |
| 1400 | 1401 |
|
| 1401 | 1402 |
Arc refreshRec(std::vector<Arc> &v,int a,int b) |
| 1402 | 1403 |
{
|
| ... | ... |
@@ -1501,32 +1502,33 @@ |
| 1501 | 1502 |
} |
| 1502 | 1503 |
|
| 1503 | 1504 |
|
| 1504 | 1505 |
public: |
| 1505 | 1506 |
|
| 1506 | 1507 |
///Find an arc between two nodes. |
| 1507 | 1508 |
|
| 1508 | 1509 |
///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where |
| 1509 | 1510 |
/// <em>d</em> is the number of outgoing arcs of \c s. |
| 1510 | 1511 |
///\param s The source node |
| 1511 | 1512 |
///\param t The target node |
| 1512 | 1513 |
///\return An arc from \c s to \c t if there exists, |
| 1513 | 1514 |
///\ref INVALID otherwise. |
| 1514 | 1515 |
Arc operator()(Node s, Node t) const |
| 1515 | 1516 |
{
|
| 1516 | 1517 |
Arc a = _head[s]; |
| 1518 |
if (a == INVALID) return INVALID; |
|
| 1517 | 1519 |
while (true) {
|
| 1518 | 1520 |
if (_g.target(a) == t) {
|
| 1519 | 1521 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1520 | 1522 |
return a; |
| 1521 | 1523 |
} else if (t < _g.target(a)) {
|
| 1522 | 1524 |
if (_left[a] == INVALID) {
|
| 1523 | 1525 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1524 | 1526 |
return INVALID; |
| 1525 | 1527 |
} else {
|
| 1526 | 1528 |
a = _left[a]; |
| 1527 | 1529 |
} |
| 1528 | 1530 |
} else {
|
| 1529 | 1531 |
if (_right[a] == INVALID) {
|
| 1530 | 1532 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1531 | 1533 |
return INVALID; |
| 1532 | 1534 |
} else {
|
| ... | ... |
@@ -1535,32 +1537,33 @@ |
| 1535 | 1537 |
} |
| 1536 | 1538 |
} |
| 1537 | 1539 |
} |
| 1538 | 1540 |
|
| 1539 | 1541 |
///Find the first arc between two nodes. |
| 1540 | 1542 |
|
| 1541 | 1543 |
///Find the first arc between two nodes in time |
| 1542 | 1544 |
/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of |
| 1543 | 1545 |
/// outgoing arcs of \c s. |
| 1544 | 1546 |
///\param s The source node |
| 1545 | 1547 |
///\param t The target node |
| 1546 | 1548 |
///\return An arc from \c s to \c t if there exists, \ref INVALID |
| 1547 | 1549 |
/// otherwise. |
| 1548 | 1550 |
Arc findFirst(Node s, Node t) const |
| 1549 | 1551 |
{
|
| 1550 | 1552 |
Arc a = _head[s]; |
| 1553 |
if (a == INVALID) return INVALID; |
|
| 1551 | 1554 |
Arc r = INVALID; |
| 1552 | 1555 |
while (true) {
|
| 1553 | 1556 |
if (_g.target(a) < t) {
|
| 1554 | 1557 |
if (_right[a] == INVALID) {
|
| 1555 | 1558 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1556 | 1559 |
return r; |
| 1557 | 1560 |
} else {
|
| 1558 | 1561 |
a = _right[a]; |
| 1559 | 1562 |
} |
| 1560 | 1563 |
} else {
|
| 1561 | 1564 |
if (_g.target(a) == t) {
|
| 1562 | 1565 |
r = a; |
| 1563 | 1566 |
} |
| 1564 | 1567 |
if (_left[a] == INVALID) {
|
| 1565 | 1568 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1566 | 1569 |
return r; |
0 comments (0 inline)