r232:e39056157d24
Wed, 23 Jul 2008 19:21:20
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -1363,48 +1363,49 @@ |
| 1363 | 1363 |
} |
| 1364 | 1364 |
Arc s = _parent[e]; |
| 1365 | 1365 |
_right.set(_parent[e], _left[e]); |
| 1366 | 1366 |
if (_left[e] != INVALID) {
|
| 1367 | 1367 |
_parent.set(_left[e], _parent[e]); |
| 1368 | 1368 |
} |
| 1369 | 1369 |
|
| 1370 | 1370 |
_left.set(e, _left[arc]); |
| 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 |
{
|
| 1403 | 1404 |
int m=(a+b)/2; |
| 1404 | 1405 |
Arc me=v[m]; |
| 1405 | 1406 |
if (a < m) {
|
| 1406 | 1407 |
Arc left = refreshRec(v,a,m-1); |
| 1407 | 1408 |
_left.set(me, left); |
| 1408 | 1409 |
_parent.set(left, me); |
| 1409 | 1410 |
} else {
|
| 1410 | 1411 |
_left.set(me, INVALID); |
| ... | ... |
@@ -1493,82 +1494,84 @@ |
| 1493 | 1494 |
} else {
|
| 1494 | 1495 |
zag(_parent[v]); |
| 1495 | 1496 |
zag(v); |
| 1496 | 1497 |
} |
| 1497 | 1498 |
} |
| 1498 | 1499 |
} |
| 1499 | 1500 |
} |
| 1500 | 1501 |
_head[_g.source(v)] = v; |
| 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 {
|
| 1533 | 1535 |
a = _right[a]; |
| 1534 | 1536 |
} |
| 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; |
| 1567 | 1570 |
} else {
|
| 1568 | 1571 |
a = _left[a]; |
| 1569 | 1572 |
} |
| 1570 | 1573 |
} |
| 1571 | 1574 |
} |
| 1572 | 1575 |
} |
| 1573 | 1576 |
|
| 1574 | 1577 |
///Find the next arc between two nodes. |
0 comments (0 inline)