Changes in / [287:bb40b6db0a58:285:d8dc5acf739b] in lemon-1.0
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r287 r281 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 t.607 ///in order to compute the shortest path to \c dest. 608 608 /// 609 609 ///The algorithm computes 610 ///- the shortest path to \c t,611 ///- the distance of \c t from the root(s).610 ///- the shortest path to \c dest, 611 ///- the distance of \c dest 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 t)623 void start(Node dest) 624 624 { 625 625 bool reach = false; 626 while ( !emptyQueue() && !reach ) processNextNode( t, reach);626 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); 627 627 } 628 628 … … 662 662 } 663 663 664 ///Runs the algorithm from the given sourcenode.664 ///Runs the algorithm from the given 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 node \c t689 /// (it stops searching when \c t is processed).690 /// 691 /// \return \c true if \c t is reachable form \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. 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 boolrun(Node s,Node t) {700 int run(Node s,Node t) { 701 701 init(); 702 702 addSource(s); 703 703 start(t); 704 return reached(t) ;704 return reached(t) ? _curr_dist : 0; 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 t.1619 /// in order to compute the shortest path to \c dest. 1620 1620 /// 1621 1621 /// The algorithm computes 1622 /// - the shortest path to \c t,1623 /// - the distance of \c t from the root(s).1622 /// - the shortest path to \c dest, 1623 /// - the distance of \c dest 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 t) {1635 void start(Node dest) { 1636 1636 bool reach = false; 1637 while ( !emptyQueue() && !reach ) processNextNode( t, reach);1637 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); 1638 1638 } 1639 1639 … … 1673 1673 } 1674 1674 1675 /// \brief Runs the algorithm from the given sourcenode.1675 /// \brief Runs the algorithm from the given 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 s1699 /// in order to compute the shortest path to node \c t1700 /// (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 a1705 /// shortcut of the following code.1706 ///\code1707 /// b.init();1708 /// b.addSource(s);1709 /// b.start(t);1710 ///\endcode1711 bool run(Node s,Node t) {1712 init();1713 addSource(s);1714 start(t);1715 return reached(t);1716 1694 } 1717 1695 -
lemon/dfs.h
r287 r281 556 556 /// 557 557 ///This method runs the %DFS algorithm from the root node 558 ///in order to compute the DFS path to \c t.558 ///in order to compute the DFS path to \c dest. 559 559 /// 560 560 ///The algorithm computes 561 ///- the %DFS path to \c t,562 ///- the distance of \c t from the root in the %DFS tree.561 ///- the %DFS path to \c dest, 562 ///- the distance of \c dest 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 t)567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!= t )566 void start(Node dest) 567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 569 569 processNextArc(); 570 570 } … … 596 596 } 597 597 598 ///Runs the algorithm from the given sourcenode.598 ///Runs the algorithm from the given 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 node \c t623 /// (it stops searching when \c t is processed)624 /// 625 /// \return \c true if \c t is reachable form \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. 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 boolrun(Node s,Node t) {634 int run(Node s,Node t) { 635 635 init(); 636 636 addSource(s); 637 637 start(t); 638 return reached(t) ;638 return reached(t)?_stack_head+1:0; 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 t.1524 /// in order to compute the DFS path to \c dest. 1525 1525 /// 1526 1526 /// The algorithm computes 1527 /// - the %DFS path to \c t,1528 /// - the distance of \c t from the root in the %DFS tree.1527 /// - the %DFS path to \c dest, 1528 /// - the distance of \c dest 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 t) {1533 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )1532 void start(Node dest) { 1533 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) 1534 1534 processNextArc(); 1535 1535 } … … 1560 1560 } 1561 1561 1562 /// \brief Runs the algorithm from the given sourcenode.1562 /// \brief Runs the algorithm from the given 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 node \c t1587 /// (it stops searching when \c t is processed).1588 /// 1589 /// \return \c true if \c t is reachable form \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. 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 boolrun(Node s,Node t) {1598 int run(Node s,Node t) { 1599 1599 init(); 1600 1600 addSource(s); 1601 1601 start(t); 1602 return reached(t) ;1602 return reached(t)?_stack_head+1:0; 1603 1603 } 1604 1604 -
lemon/dijkstra.h
r287 r281 725 725 } 726 726 727 ///Executes the algorithm until the given target node is processed.728 729 ///Executes the algorithm until the given target node is processed.727 ///Executes the algorithm until the given target node is reached. 728 729 ///Executes the algorithm until the given target node is reached. 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 t.732 ///in order to compute the shortest path to \c dest. 733 733 /// 734 734 ///The algorithm computes 735 ///- the shortest path to \c t,736 ///- the distance of \c t from the root(s).735 ///- the shortest path to \c dest, 736 ///- the distance of \c dest 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 t) 741 { 742 while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); 743 if ( !_heap->empty() ) { 744 finalizeNodeData(_heap->top(),_heap->prio()); 745 _heap->pop(); 746 } 740 void start(Node dest) 741 { 742 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); 743 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 747 744 } 748 745 … … 772 769 } 773 770 774 ///Runs the algorithm from the given sourcenode.771 ///Runs the algorithm from the given node. 775 772 776 773 ///This method runs the %Dijkstra algorithm from node \c s … … 796 793 797 794 ///This method runs the %Dijkstra algorithm from node \c s 798 ///in order to compute the shortest path to node \c t799 /// (it stops searching when \c t is processed).800 /// 801 /// \return \c true if \c t is reachable form \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. 802 799 /// 803 800 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a … … 808 805 /// d.start(t); 809 806 ///\endcode 810 boolrun(Node s,Node t) {807 Value run(Node s,Node t) { 811 808 init(); 812 809 addSource(s); 813 810 start(t); 814 return (*_ heap_cross_ref)[t] == Heap::POST_HEAP;811 return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t]; 815 812 } 816 813 … … 908 905 ///Returns \c true if \c v is processed, i.e. the shortest 909 906 ///path to \c v has already found. 910 ///\pre Either \ref run() or \ref init()907 ///\pre Either \ref run() or \ref start() 911 908 ///must be called before using this function. 912 909 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 917 914 ///Returns the current distance of a node from the root(s). 918 915 ///It may be decreased in the following processes. 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 } 916 ///\pre \c v should be reached but not processed. 917 Value currentDist(Node v) const { return (*_heap)[v]; } 925 918 926 919 ///@} -
test/bfs_test.cc
r286 r278 55 55 typedef concepts::Digraph Digraph; 56 56 typedef Bfs<Digraph> BType; 57 typedef Digraph::Node Node;58 typedef Digraph::Arc Arc;59 57 60 58 Digraph G; 61 Node s, t;62 Arc e;59 Digraph::Node n; 60 Digraph::Arc e; 63 61 int l; 64 62 bool b; 65 63 BType::DistMap d(G); 66 64 BType::PredMap p(G); 67 Path<Digraph> pp;68 65 69 { 70 BType bfs_test(G); 66 BType bfs_test(G); 71 67 72 bfs_test.run(s); 73 bfs_test.run(s,t); 74 bfs_test.run(); 68 bfs_test.run(n); 75 69 76 l = bfs_test.dist(t); 77 e = bfs_test.predArc(t); 78 s = bfs_test.predNode(t); 79 b = bfs_test.reached(t); 80 d = bfs_test.distMap(); 81 p = bfs_test.predMap(); 82 pp = bfs_test.path(t); 83 } 84 { 85 BType 86 ::SetPredMap<concepts::ReadWriteMap<Node,Arc> > 87 ::SetDistMap<concepts::ReadWriteMap<Node,int> > 88 ::SetReachedMap<concepts::ReadWriteMap<Node,bool> > 89 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 90 ::SetStandardProcessedMap 91 ::Create bfs_test(G); 70 l = bfs_test.dist(n); 71 e = bfs_test.predArc(n); 72 n = bfs_test.predNode(n); 73 d = bfs_test.distMap(); 74 p = bfs_test.predMap(); 75 b = bfs_test.reached(n); 92 76 93 bfs_test.run(s); 94 bfs_test.run(s,t); 95 bfs_test.run(); 96 97 l = bfs_test.dist(t); 98 e = bfs_test.predArc(t); 99 s = bfs_test.predNode(t); 100 b = bfs_test.reached(t); 101 pp = bfs_test.path(t); 102 } 77 Path<Digraph> pp = bfs_test.path(n); 103 78 } 104 79 -
test/dfs_test.cc
r286 r278 57 57 typedef concepts::Digraph Digraph; 58 58 typedef Dfs<Digraph> DType; 59 typedef Digraph::Node Node;60 typedef Digraph::Arc Arc;61 59 62 60 Digraph G; 63 Node s, t;64 Arc e;61 Digraph::Node n; 62 Digraph::Arc e; 65 63 int l; 66 64 bool b; 67 65 DType::DistMap d(G); 68 66 DType::PredMap p(G); 69 Path<Digraph> pp;70 67 71 { 72 DType dfs_test(G); 68 DType dfs_test(G); 73 69 74 dfs_test.run(s); 75 dfs_test.run(s,t); 76 dfs_test.run(); 70 dfs_test.run(n); 77 71 78 l = dfs_test.dist(t); 79 e = dfs_test.predArc(t); 80 s = dfs_test.predNode(t); 81 b = dfs_test.reached(t); 82 d = dfs_test.distMap(); 83 p = dfs_test.predMap(); 84 pp = dfs_test.path(t); 85 } 86 { 87 DType 88 ::SetPredMap<concepts::ReadWriteMap<Node,Arc> > 89 ::SetDistMap<concepts::ReadWriteMap<Node,int> > 90 ::SetReachedMap<concepts::ReadWriteMap<Node,bool> > 91 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 92 ::SetStandardProcessedMap 93 ::Create dfs_test(G); 72 l = dfs_test.dist(n); 73 e = dfs_test.predArc(n); 74 n = dfs_test.predNode(n); 75 d = dfs_test.distMap(); 76 p = dfs_test.predMap(); 77 b = dfs_test.reached(n); 94 78 95 dfs_test.run(s); 96 dfs_test.run(s,t); 97 dfs_test.run(); 98 99 l = dfs_test.dist(t); 100 e = dfs_test.predArc(t); 101 s = dfs_test.predNode(t); 102 b = dfs_test.reached(t); 103 pp = dfs_test.path(t); 104 } 79 Path<Digraph> pp = dfs_test.path(n); 105 80 } 106 81 -
test/dijkstra_test.cc
r286 r278 23 23 #include <lemon/dijkstra.h> 24 24 #include <lemon/path.h> 25 #include <lemon/bin_heap.h>26 25 27 26 #include "graph_test.h" … … 57 56 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; 58 57 typedef Dijkstra<Digraph, LengthMap> DType; 59 typedef Digraph::Node Node;60 typedef Digraph::Arc Arc;61 58 62 59 Digraph G; 63 Node s, t;64 Arc e;60 Digraph::Node n; 61 Digraph::Arc e; 65 62 VType l; 66 63 bool b; … … 68 65 DType::PredMap p(G); 69 66 LengthMap length; 70 Path<Digraph> pp;71 67 72 { 73 DType dijkstra_test(G,length); 68 DType dijkstra_test(G,length); 74 69 75 dijkstra_test.run(s); 76 dijkstra_test.run(s,t); 70 dijkstra_test.run(n); 77 71 78 l = dijkstra_test.dist(t); 79 e = dijkstra_test.predArc(t); 80 s = dijkstra_test.predNode(t); 81 b = dijkstra_test.reached(t); 82 d = dijkstra_test.distMap(); 83 p = dijkstra_test.predMap(); 84 pp = dijkstra_test.path(t); 85 } 86 { 87 DType 88 ::SetPredMap<concepts::ReadWriteMap<Node,Arc> > 89 ::SetDistMap<concepts::ReadWriteMap<Node,VType> > 90 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 91 ::SetStandardProcessedMap 92 ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> > 93 ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > 94 ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > 95 ::Create dijkstra_test(G,length); 72 l = dijkstra_test.dist(n); 73 e = dijkstra_test.predArc(n); 74 n = dijkstra_test.predNode(n); 75 d = dijkstra_test.distMap(); 76 p = dijkstra_test.predMap(); 77 b = dijkstra_test.reached(n); 96 78 97 dijkstra_test.run(s); 98 dijkstra_test.run(s,t); 99 100 l = dijkstra_test.dist(t); 101 e = dijkstra_test.predArc(t); 102 s = dijkstra_test.predNode(t); 103 b = dijkstra_test.reached(t); 104 pp = dijkstra_test.path(t); 105 } 106 79 Path<Digraph> pp = dijkstra_test.path(n); 107 80 } 108 81
Note: See TracChangeset
for help on using the changeset viewer.