Changeset 287:bb40b6db0a58 in lemon
- Timestamp:
- 09/27/08 14:33:28 (16 years ago)
- Branch:
- default
- Children:
- 288:47b3a3b67837, 290:f6899946c1ac
- Parents:
- 286:da414906fe21 (diff), 285:d8dc5acf739b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Location:
- lemon
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r281 r287 605 605 /// 606 606 ///This method runs the %BFS algorithm from the root node(s) 607 ///in order to compute the shortest path to \c dest.607 ///in order to compute the shortest path to \c t. 608 608 /// 609 609 ///The algorithm computes 610 ///- the shortest path to \c dest,611 ///- the distance of \c dest from the root(s).610 ///- the shortest path to \c t, 611 ///- the distance of \c t from the root(s). 612 612 /// 613 613 ///\pre init() must be called and at least one root node should be … … 621 621 /// } 622 622 ///\endcode 623 void start(Node dest)623 void start(Node t) 624 624 { 625 625 bool reach = false; 626 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);626 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 627 627 } 628 628 … … 662 662 } 663 663 664 ///Runs the algorithm from the given node.664 ///Runs the algorithm from the given source node. 665 665 666 666 ///This method runs the %BFS algorithm from node \c s … … 686 686 687 687 ///This method runs the %BFS algorithm from node \c s 688 ///in order to compute the shortest path to \c t.689 /// 690 /// \return The length of the shortest <tt>s</tt>--<tt>t</tt> path,691 /// if \c t is reachable form \c s, \c 0 otherwise.688 ///in order to compute the shortest path to node \c t 689 ///(it stops searching when \c t is processed). 690 /// 691 ///\return \c true if \c t is reachable form \c s. 692 692 /// 693 693 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a … … 698 698 /// b.start(t); 699 699 ///\endcode 700 intrun(Node s,Node t) {700 bool run(Node s,Node t) { 701 701 init(); 702 702 addSource(s); 703 703 start(t); 704 return reached(t) ? _curr_dist : 0;704 return reached(t); 705 705 } 706 706 … … 1617 1617 /// 1618 1618 /// This method runs the %BFS algorithm from the root node(s) 1619 /// in order to compute the shortest path to \c dest.1619 /// in order to compute the shortest path to \c t. 1620 1620 /// 1621 1621 /// The algorithm computes 1622 /// - the shortest path to \c dest,1623 /// - the distance of \c dest from the root(s).1622 /// - the shortest path to \c t, 1623 /// - the distance of \c t from the root(s). 1624 1624 /// 1625 1625 /// \pre init() must be called and at least one root node should be … … 1633 1633 /// } 1634 1634 /// \endcode 1635 void start(Node dest) {1635 void start(Node t) { 1636 1636 bool reach = false; 1637 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);1637 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 1638 1638 } 1639 1639 … … 1673 1673 } 1674 1674 1675 /// \brief Runs the algorithm from the given node.1675 /// \brief Runs the algorithm from the given source node. 1676 1676 /// 1677 1677 /// This method runs the %BFS algorithm from node \c s … … 1692 1692 addSource(s); 1693 1693 start(); 1694 } 1695 1696 /// \brief Finds the shortest path between \c s and \c t. 1697 /// 1698 /// This method runs the %BFS algorithm from node \c s 1699 /// in order to compute the shortest path to node \c t 1700 /// (it stops searching when \c t is processed). 1701 /// 1702 /// \return \c true if \c t is reachable form \c s. 1703 /// 1704 /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a 1705 /// shortcut of the following code. 1706 ///\code 1707 /// b.init(); 1708 /// b.addSource(s); 1709 /// b.start(t); 1710 ///\endcode 1711 bool run(Node s,Node t) { 1712 init(); 1713 addSource(s); 1714 start(t); 1715 return reached(t); 1694 1716 } 1695 1717 -
lemon/bfs.h
r286 r287 55 55 ///\param g is the digraph, to which we would like to define the 56 56 ///\ref PredMap. 57 ///\todo The digraph alone may be insufficient to initialize58 57 static PredMap *createPredMap(const Digraph &g) 59 58 { … … 65 64 ///The type of the map that indicates which nodes are processed. 66 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 67 ///By default it is a NullMap.68 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 69 67 ///Instantiates a \ref ProcessedMap. … … 197 195 int _curr_dist; 198 196 199 ///Creates the maps if necessary. 200 ///\todo Better memory allocation (instead of new). 197 //Creates the maps if necessary. 201 198 void create_maps() 202 199 { … … 849 846 ///\param g is the digraph, to which we would like to define the 850 847 ///\ref PredMap. 851 ///\todo The digraph alone may be insufficient to initialize852 848 static PredMap *createPredMap(const Digraph &g) 853 849 { … … 1371 1367 int _list_front, _list_back; 1372 1368 1373 ///Creates the maps if necessary. 1374 ///\todo Better memory allocation (instead of new). 1369 //Creates the maps if necessary. 1375 1370 void create_maps() { 1376 1371 if(!_reached) { -
lemon/dfs.h
r281 r287 556 556 /// 557 557 ///This method runs the %DFS algorithm from the root node 558 ///in order to compute the DFS path to \c dest.558 ///in order to compute the DFS path to \c t. 559 559 /// 560 560 ///The algorithm computes 561 ///- the %DFS path to \c dest,562 ///- the distance of \c dest from the root in the %DFS tree.561 ///- the %DFS path to \c t, 562 ///- the distance of \c t from the root in the %DFS tree. 563 563 /// 564 564 ///\pre init() must be called and a root node should be 565 565 ///added with addSource() before using this function. 566 void start(Node dest)567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!= dest )566 void start(Node t) 567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) 569 569 processNextArc(); 570 570 } … … 596 596 } 597 597 598 ///Runs the algorithm from the given node.598 ///Runs the algorithm from the given source node. 599 599 600 600 ///This method runs the %DFS algorithm from node \c s … … 620 620 621 621 ///This method runs the %DFS algorithm from node \c s 622 ///in order to compute the DFS path to \c t.623 /// 624 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,625 /// if \c t is reachable form \c s, \c 0 otherwise.622 ///in order to compute the DFS path to node \c t 623 ///(it stops searching when \c t is processed) 624 /// 625 ///\return \c true if \c t is reachable form \c s. 626 626 /// 627 627 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is … … 632 632 /// d.start(t); 633 633 ///\endcode 634 intrun(Node s,Node t) {634 bool run(Node s,Node t) { 635 635 init(); 636 636 addSource(s); 637 637 start(t); 638 return reached(t) ?_stack_head+1:0;638 return reached(t); 639 639 } 640 640 … … 1522 1522 /// 1523 1523 /// This method runs the %DFS algorithm from the root node 1524 /// in order to compute the DFS path to \c dest.1524 /// in order to compute the DFS path to \c t. 1525 1525 /// 1526 1526 /// The algorithm computes 1527 /// - the %DFS path to \c dest,1528 /// - the distance of \c dest from the root in the %DFS tree.1527 /// - the %DFS path to \c t, 1528 /// - the distance of \c t from the root in the %DFS tree. 1529 1529 /// 1530 1530 /// \pre init() must be called and a root node should be added 1531 1531 /// with addSource() before using this function. 1532 void start(Node dest) {1533 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )1532 void start(Node t) { 1533 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) 1534 1534 processNextArc(); 1535 1535 } … … 1560 1560 } 1561 1561 1562 /// \brief Runs the algorithm from the given node.1562 /// \brief Runs the algorithm from the given source node. 1563 1563 /// 1564 1564 /// This method runs the %DFS algorithm from node \c s. … … 1584 1584 1585 1585 /// This method runs the %DFS algorithm from node \c s 1586 /// in order to compute the DFS path to \c t.1587 /// 1588 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,1589 /// if \c t is reachable form \c s, \c 0 otherwise.1586 /// in order to compute the DFS path to node \c t 1587 /// (it stops searching when \c t is processed). 1588 /// 1589 /// \return \c true if \c t is reachable form \c s. 1590 1590 /// 1591 1591 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is … … 1596 1596 /// d.start(t); 1597 1597 ///\endcode 1598 intrun(Node s,Node t) {1598 bool run(Node s,Node t) { 1599 1599 init(); 1600 1600 addSource(s); 1601 1601 start(t); 1602 return reached(t) ?_stack_head+1:0;1602 return reached(t); 1603 1603 } 1604 1604 -
lemon/dfs.h
r286 r287 56 56 ///\param g is the digraph, to which we would like to define the 57 57 ///\ref PredMap. 58 ///\todo The digraph alone may be insufficient to initialize59 58 static PredMap *createPredMap(const Digraph &g) 60 59 { … … 66 65 ///The type of the map that indicates which nodes are processed. 67 66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 68 ///By default it is a NullMap.69 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 70 68 ///Instantiates a \ref ProcessedMap. … … 197 195 int _stack_head; 198 196 199 ///Creates the maps if necessary. 200 ///\todo Better memory allocation (instead of new). 197 //Creates the maps if necessary. 201 198 void create_maps() 202 199 { … … 783 780 ///\param g is the digraph, to which we would like to define the 784 781 ///\ref PredMap. 785 ///\todo The digraph alone may be insufficient to initialize786 782 static PredMap *createPredMap(const Digraph &g) 787 783 { … … 1318 1314 int _stack_head; 1319 1315 1320 ///Creates the maps if necessary. 1321 ///\todo Better memory allocation (instead of new). 1316 //Creates the maps if necessary. 1322 1317 void create_maps() { 1323 1318 if(!_reached) { -
lemon/dijkstra.h
r281 r287 725 725 } 726 726 727 ///Executes the algorithm until the given target node is reached.728 729 ///Executes the algorithm until the given target node is reached.727 ///Executes the algorithm until the given target node is processed. 728 729 ///Executes the algorithm until the given target node is processed. 730 730 /// 731 731 ///This method runs the %Dijkstra algorithm from the root node(s) 732 ///in order to compute the shortest path to \c dest.732 ///in order to compute the shortest path to \c t. 733 733 /// 734 734 ///The algorithm computes 735 ///- the shortest path to \c dest,736 ///- the distance of \c dest from the root(s).735 ///- the shortest path to \c t, 736 ///- the distance of \c t from the root(s). 737 737 /// 738 738 ///\pre init() must be called and at least one root node should be 739 739 ///added with addSource() before using this function. 740 void start(Node dest) 741 { 742 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); 743 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 740 void start(Node t) 741 { 742 while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); 743 if ( !_heap->empty() ) { 744 finalizeNodeData(_heap->top(),_heap->prio()); 745 _heap->pop(); 746 } 744 747 } 745 748 … … 769 772 } 770 773 771 ///Runs the algorithm from the given node.774 ///Runs the algorithm from the given source node. 772 775 773 776 ///This method runs the %Dijkstra algorithm from node \c s … … 793 796 794 797 ///This method runs the %Dijkstra algorithm from node \c s 795 ///in order to compute the shortest path to \c t.796 /// 797 /// \return The length of the shortest <tt>s</tt>--<tt>t</tt> path,798 /// if \c t is reachable form \c s, \c 0 otherwise.798 ///in order to compute the shortest path to node \c t 799 ///(it stops searching when \c t is processed). 800 /// 801 ///\return \c true if \c t is reachable form \c s. 799 802 /// 800 803 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a … … 805 808 /// d.start(t); 806 809 ///\endcode 807 Valuerun(Node s,Node t) {810 bool run(Node s,Node t) { 808 811 init(); 809 812 addSource(s); 810 813 start(t); 811 return (*_ pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];814 return (*_heap_cross_ref)[t] == Heap::POST_HEAP; 812 815 } 813 816 … … 905 908 ///Returns \c true if \c v is processed, i.e. the shortest 906 909 ///path to \c v has already found. 907 ///\pre Either \ref run() or \ref start()910 ///\pre Either \ref run() or \ref init() 908 911 ///must be called before using this function. 909 912 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 914 917 ///Returns the current distance of a node from the root(s). 915 918 ///It may be decreased in the following processes. 916 ///\pre \c v should be reached but not processed. 917 Value currentDist(Node v) const { return (*_heap)[v]; } 919 ///\pre Either \ref run() or \ref init() 920 ///must be called before using this function and 921 ///node \c v must be reached but not necessarily processed. 922 Value currentDist(Node v) const { 923 return processed(v) ? (*_dist)[v] : (*_heap)[v]; 924 } 918 925 919 926 ///@} -
lemon/dijkstra.h
r286 r287 145 145 ///\param g is the digraph, to which we would like to define the 146 146 ///\ref PredMap. 147 ///\todo The digraph alone may be insufficient for the initialization148 147 static PredMap *createPredMap(const Digraph &g) 149 148 { … … 156 155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 157 156 ///By default it is a NullMap. 158 ///\todo If it is set to a real map,159 ///Dijkstra::processed() should read this.160 157 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 161 158 ///Instantiates a \ref ProcessedMap. … … 298 295 bool local_heap; 299 296 300 ///Creates the maps if necessary. 301 ///\todo Better memory allocation (instead of new). 297 //Creates the maps if necessary. 302 298 void create_maps() 303 299 { … … 966 962 /// \param g is the digraph, to which we would like to define the 967 963 /// HeapCrossRef. 968 /// \todo The digraph alone may be insufficient for the initialization969 964 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 970 965 { … … 1002 997 ///\param g is the digraph, to which we would like to define the 1003 998 ///\ref PredMap. 1004 ///\todo The digraph alone may be insufficient to initialize1005 999 static PredMap *createPredMap(const Digraph &g) 1006 1000 { … … 1013 1007 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1014 1008 ///By default it is a NullMap. 1015 ///\todo If it is set to a real map,1016 ///Dijkstra::processed() should read this.1017 ///\todo named parameter to set this type, function to read and write.1018 1009 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 1019 1010 ///Instantiates a \ref ProcessedMap. … … 1061 1052 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1062 1053 /// \ref DijkstraWizard class. 1063 /// \todo More named parameters are required...1064 1054 template<class GR,class LM> 1065 1055 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
Note: See TracChangeset
for help on using the changeset viewer.
