Changeset 233:28239207a8a3 in lemon
 Timestamp:
 07/23/08 19:32:48 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/core.h
r232 r233 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 … … 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 d)</em>,1174 ///source to a given target in amortized time <em>O(log</em>d<em>)</em>, 1175 1175 ///where <em>d</em> is the outdegree of the source node. 1176 1176 /// 1177 1177 ///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. 1179 1179 /// 1180 1180 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your … … 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); … … 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]; 1577 a = _parent[a]; 1578 const_cast<DynArcLookUp&>(*this).splay(a); 1529 1579 } 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 } 1614 1584 } 1615 1585
Note: See TracChangeset
for help on using the changeset viewer.