Changeset 286:da414906fe21 in lemon-1.2 for lemon
- Timestamp:
- 09/26/08 12:40:11 (16 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r278 r286 608 608 /// 609 609 ///This method runs the %BFS algorithm from the root node(s) 610 ///in order to compute the shortest path to \c dest.610 ///in order to compute the shortest path to \c t. 611 611 /// 612 612 ///The algorithm computes 613 ///- the shortest path to \c dest,614 ///- the distance of \c dest from the root(s).613 ///- the shortest path to \c t, 614 ///- the distance of \c t from the root(s). 615 615 /// 616 616 ///\pre init() must be called and at least one root node should be … … 624 624 /// } 625 625 ///\endcode 626 void start(Node dest)626 void start(Node t) 627 627 { 628 628 bool reach = false; 629 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);629 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 630 630 } 631 631 … … 665 665 } 666 666 667 ///Runs the algorithm from the given node.667 ///Runs the algorithm from the given source node. 668 668 669 669 ///This method runs the %BFS algorithm from node \c s … … 689 689 690 690 ///This method runs the %BFS algorithm from node \c s 691 ///in order to compute the shortest path to \c t.692 /// 693 /// \return The length of the shortest <tt>s</tt>--<tt>t</tt> path,694 /// if \c t is reachable form \c s, \c 0 otherwise.691 ///in order to compute the shortest path to node \c t 692 ///(it stops searching when \c t is processed). 693 /// 694 ///\return \c true if \c t is reachable form \c s. 695 695 /// 696 696 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a … … 701 701 /// b.start(t); 702 702 ///\endcode 703 intrun(Node s,Node t) {703 bool run(Node s,Node t) { 704 704 init(); 705 705 addSource(s); 706 706 start(t); 707 return reached(t) ? _curr_dist : 0;707 return reached(t); 708 708 } 709 709 … … 1622 1622 /// 1623 1623 /// This method runs the %BFS algorithm from the root node(s) 1624 /// in order to compute the shortest path to \c dest.1624 /// in order to compute the shortest path to \c t. 1625 1625 /// 1626 1626 /// The algorithm computes 1627 /// - the shortest path to \c dest,1628 /// - the distance of \c dest from the root(s).1627 /// - the shortest path to \c t, 1628 /// - the distance of \c t from the root(s). 1629 1629 /// 1630 1630 /// \pre init() must be called and at least one root node should be … … 1638 1638 /// } 1639 1639 /// \endcode 1640 void start(Node dest) {1640 void start(Node t) { 1641 1641 bool reach = false; 1642 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);1642 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 1643 1643 } 1644 1644 … … 1678 1678 } 1679 1679 1680 /// \brief Runs the algorithm from the given node.1680 /// \brief Runs the algorithm from the given source node. 1681 1681 /// 1682 1682 /// This method runs the %BFS algorithm from node \c s … … 1697 1697 addSource(s); 1698 1698 start(); 1699 } 1700 1701 /// \brief Finds the shortest path between \c s and \c t. 1702 /// 1703 /// This method runs the %BFS algorithm from node \c s 1704 /// in order to compute the shortest path to node \c t 1705 /// (it stops searching when \c t is processed). 1706 /// 1707 /// \return \c true if \c t is reachable form \c s. 1708 /// 1709 /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a 1710 /// shortcut of the following code. 1711 ///\code 1712 /// b.init(); 1713 /// b.addSource(s); 1714 /// b.start(t); 1715 ///\endcode 1716 bool run(Node s,Node t) { 1717 init(); 1718 addSource(s); 1719 start(t); 1720 return reached(t); 1699 1721 } 1700 1722 -
lemon/dfs.h
r278 r286 559 559 /// 560 560 ///This method runs the %DFS algorithm from the root node 561 ///in order to compute the DFS path to \c dest.561 ///in order to compute the DFS path to \c t. 562 562 /// 563 563 ///The algorithm computes 564 ///- the %DFS path to \c dest,565 ///- the distance of \c dest from the root in the %DFS tree.564 ///- the %DFS path to \c t, 565 ///- the distance of \c t from the root in the %DFS tree. 566 566 /// 567 567 ///\pre init() must be called and a root node should be 568 568 ///added with addSource() before using this function. 569 void start(Node dest)570 { 571 while ( !emptyQueue() && G->target(_stack[_stack_head])!= dest )569 void start(Node t) 570 { 571 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) 572 572 processNextArc(); 573 573 } … … 599 599 } 600 600 601 ///Runs the algorithm from the given node.601 ///Runs the algorithm from the given source node. 602 602 603 603 ///This method runs the %DFS algorithm from node \c s … … 623 623 624 624 ///This method runs the %DFS algorithm from node \c s 625 ///in order to compute the DFS path to \c t.626 /// 627 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,628 /// if \c t is reachable form \c s, \c 0 otherwise.625 ///in order to compute the DFS path to node \c t 626 ///(it stops searching when \c t is processed) 627 /// 628 ///\return \c true if \c t is reachable form \c s. 629 629 /// 630 630 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is … … 635 635 /// d.start(t); 636 636 ///\endcode 637 intrun(Node s,Node t) {637 bool run(Node s,Node t) { 638 638 init(); 639 639 addSource(s); 640 640 start(t); 641 return reached(t) ?_stack_head+1:0;641 return reached(t); 642 642 } 643 643 … … 1527 1527 /// 1528 1528 /// This method runs the %DFS algorithm from the root node 1529 /// in order to compute the DFS path to \c dest.1529 /// in order to compute the DFS path to \c t. 1530 1530 /// 1531 1531 /// The algorithm computes 1532 /// - the %DFS path to \c dest,1533 /// - the distance of \c dest from the root in the %DFS tree.1532 /// - the %DFS path to \c t, 1533 /// - the distance of \c t from the root in the %DFS tree. 1534 1534 /// 1535 1535 /// \pre init() must be called and a root node should be added 1536 1536 /// with addSource() before using this function. 1537 void start(Node dest) {1538 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )1537 void start(Node t) { 1538 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) 1539 1539 processNextArc(); 1540 1540 } … … 1565 1565 } 1566 1566 1567 /// \brief Runs the algorithm from the given node.1567 /// \brief Runs the algorithm from the given source node. 1568 1568 /// 1569 1569 /// This method runs the %DFS algorithm from node \c s. … … 1589 1589 1590 1590 /// This method runs the %DFS algorithm from node \c s 1591 /// in order to compute the DFS path to \c t.1592 /// 1593 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,1594 /// if \c t is reachable form \c s, \c 0 otherwise.1591 /// in order to compute the DFS path to node \c t 1592 /// (it stops searching when \c t is processed). 1593 /// 1594 /// \return \c true if \c t is reachable form \c s. 1595 1595 /// 1596 1596 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is … … 1601 1601 /// d.start(t); 1602 1602 ///\endcode 1603 intrun(Node s,Node t) {1603 bool run(Node s,Node t) { 1604 1604 init(); 1605 1605 addSource(s); 1606 1606 start(t); 1607 return reached(t) ?_stack_head+1:0;1607 return reached(t); 1608 1608 } 1609 1609 -
lemon/dijkstra.h
r278 r286 729 729 } 730 730 731 ///Executes the algorithm until the given target node is reached.732 733 ///Executes the algorithm until the given target node is reached.731 ///Executes the algorithm until the given target node is processed. 732 733 ///Executes the algorithm until the given target node is processed. 734 734 /// 735 735 ///This method runs the %Dijkstra algorithm from the root node(s) 736 ///in order to compute the shortest path to \c dest.736 ///in order to compute the shortest path to \c t. 737 737 /// 738 738 ///The algorithm computes 739 ///- the shortest path to \c dest,740 ///- the distance of \c dest from the root(s).739 ///- the shortest path to \c t, 740 ///- the distance of \c t from the root(s). 741 741 /// 742 742 ///\pre init() must be called and at least one root node should be 743 743 ///added with addSource() before using this function. 744 void start(Node dest) 745 { 746 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); 747 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 744 void start(Node t) 745 { 746 while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); 747 if ( !_heap->empty() ) { 748 finalizeNodeData(_heap->top(),_heap->prio()); 749 _heap->pop(); 750 } 748 751 } 749 752 … … 773 776 } 774 777 775 ///Runs the algorithm from the given node.778 ///Runs the algorithm from the given source node. 776 779 777 780 ///This method runs the %Dijkstra algorithm from node \c s … … 797 800 798 801 ///This method runs the %Dijkstra algorithm from node \c s 799 ///in order to compute the shortest path to \c t.800 /// 801 /// \return The length of the shortest <tt>s</tt>--<tt>t</tt> path,802 /// if \c t is reachable form \c s, \c 0 otherwise.802 ///in order to compute the shortest path to node \c t 803 ///(it stops searching when \c t is processed). 804 /// 805 ///\return \c true if \c t is reachable form \c s. 803 806 /// 804 807 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a … … 809 812 /// d.start(t); 810 813 ///\endcode 811 Valuerun(Node s,Node t) {814 bool run(Node s,Node t) { 812 815 init(); 813 816 addSource(s); 814 817 start(t); 815 return (*_ pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];818 return (*_heap_cross_ref)[t] == Heap::POST_HEAP; 816 819 } 817 820 … … 909 912 ///Returns \c true if \c v is processed, i.e. the shortest 910 913 ///path to \c v has already found. 911 ///\pre Either \ref run() or \ref start()914 ///\pre Either \ref run() or \ref init() 912 915 ///must be called before using this function. 913 916 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 918 921 ///Returns the current distance of a node from the root(s). 919 922 ///It may be decreased in the following processes. 920 ///\pre \c v should be reached but not processed. 921 Value currentDist(Node v) const { return (*_heap)[v]; } 923 ///\pre Either \ref run() or \ref init() 924 ///must be called before using this function and 925 ///node \c v must be reached but not necessarily processed. 926 Value currentDist(Node v) const { 927 return processed(v) ? (*_dist)[v] : (*_heap)[v]; 928 } 922 929 923 930 ///@}
Note: See TracChangeset
for help on using the changeset viewer.