# HG changeset patch # User Peter Kovacs # Date 2008-09-26 12:40:11 # Node ID da414906fe21ec93e3eda81f6c24fc846576bc96 # Parent 6307bbbf285b3f46e46905f1647b5892ef680e0d Improvements related to BFS/DFS/Dijkstra (ticket #96) - Add run(s,t) function to BfsVisit. - Modify run(s,t) functions in the class interfaces to return bool value. - Bug fix in Dijkstra::start(t) function. - Improve Dijkstra::currentDist(). - Extend test files to check named class template parameters. - Doc improvements. diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -607,11 +607,11 @@ ///Executes the algorithm until the given target node is reached. /// ///This method runs the %BFS algorithm from the root node(s) - ///in order to compute the shortest path to \c dest. + ///in order to compute the shortest path to \c t. /// ///The algorithm computes - ///- the shortest path to \c dest, - ///- the distance of \c dest from the root(s). + ///- the shortest path to \c t, + ///- the distance of \c t from the root(s). /// ///\pre init() must be called and at least one root node should be ///added with addSource() before using this function. @@ -623,10 +623,10 @@ /// b.processNextNode(t, reach); /// } ///\endcode - void start(Node dest) + void start(Node t) { bool reach = false; - while ( !emptyQueue() && !reach ) processNextNode(dest, reach); + while ( !emptyQueue() && !reach ) processNextNode(t, reach); } ///Executes the algorithm until a condition is met. @@ -664,7 +664,7 @@ return rnode; } - ///Runs the algorithm from the given node. + ///Runs the algorithm from the given source node. ///This method runs the %BFS algorithm from node \c s ///in order to compute the shortest path to each node. @@ -688,10 +688,10 @@ ///Finds the shortest path between \c s and \c t. ///This method runs the %BFS algorithm from node \c s - ///in order to compute the shortest path to \c t. + ///in order to compute the shortest path to node \c t + ///(it stops searching when \c t is processed). /// - ///\return The length of the shortest s--t path, - ///if \c t is reachable form \c s, \c 0 otherwise. + ///\return \c true if \c t is reachable form \c s. /// ///\note Apart from the return value, b.run(s,t) is just a ///shortcut of the following code. @@ -700,11 +700,11 @@ /// b.addSource(s); /// b.start(t); ///\endcode - int run(Node s,Node t) { + bool run(Node s,Node t) { init(); addSource(s); start(t); - return reached(t) ? _curr_dist : 0; + return reached(t); } ///Runs the algorithm to visit all nodes in the digraph. @@ -1621,11 +1621,11 @@ /// Executes the algorithm until the given target node is reached. /// /// This method runs the %BFS algorithm from the root node(s) - /// in order to compute the shortest path to \c dest. + /// in order to compute the shortest path to \c t. /// /// The algorithm computes - /// - the shortest path to \c dest, - /// - the distance of \c dest from the root(s). + /// - the shortest path to \c t, + /// - the distance of \c t from the root(s). /// /// \pre init() must be called and at least one root node should be /// added with addSource() before using this function. @@ -1637,9 +1637,9 @@ /// b.processNextNode(t, reach); /// } /// \endcode - void start(Node dest) { + void start(Node t) { bool reach = false; - while ( !emptyQueue() && !reach ) processNextNode(dest, reach); + while ( !emptyQueue() && !reach ) processNextNode(t, reach); } /// \brief Executes the algorithm until a condition is met. @@ -1677,7 +1677,7 @@ return rnode; } - /// \brief Runs the algorithm from the given node. + /// \brief Runs the algorithm from the given source node. /// /// This method runs the %BFS algorithm from node \c s /// in order to compute the shortest path to each node. @@ -1698,6 +1698,28 @@ start(); } + /// \brief Finds the shortest path between \c s and \c t. + /// + /// This method runs the %BFS algorithm from node \c s + /// in order to compute the shortest path to node \c t + /// (it stops searching when \c t is processed). + /// + /// \return \c true if \c t is reachable form \c s. + /// + /// \note Apart from the return value, b.run(s,t) is just a + /// shortcut of the following code. + ///\code + /// b.init(); + /// b.addSource(s); + /// b.start(t); + ///\endcode + bool run(Node s,Node t) { + init(); + addSource(s); + start(t); + return reached(t); + } + /// \brief Runs the algorithm to visit all nodes in the digraph. /// /// This method runs the %BFS algorithm in order to diff --git a/lemon/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -558,17 +558,17 @@ ///Executes the algorithm until the given target node is reached. /// ///This method runs the %DFS algorithm from the root node - ///in order to compute the DFS path to \c dest. + ///in order to compute the DFS path to \c t. /// ///The algorithm computes - ///- the %DFS path to \c dest, - ///- the distance of \c dest from the root in the %DFS tree. + ///- the %DFS path to \c t, + ///- the distance of \c t from the root in the %DFS tree. /// ///\pre init() must be called and a root node should be ///added with addSource() before using this function. - void start(Node dest) + void start(Node t) { - while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) + while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) processNextArc(); } @@ -598,7 +598,7 @@ return emptyQueue() ? INVALID : _stack[_stack_head]; } - ///Runs the algorithm from the given node. + ///Runs the algorithm from the given source node. ///This method runs the %DFS algorithm from node \c s ///in order to compute the DFS path to each node. @@ -622,10 +622,10 @@ ///Finds the %DFS path between \c s and \c t. ///This method runs the %DFS algorithm from node \c s - ///in order to compute the DFS path to \c t. + ///in order to compute the DFS path to node \c t + ///(it stops searching when \c t is processed) /// - ///\return The length of the s--t DFS path, - ///if \c t is reachable form \c s, \c 0 otherwise. + ///\return \c true if \c t is reachable form \c s. /// ///\note Apart from the return value, d.run(s,t) is ///just a shortcut of the following code. @@ -634,11 +634,11 @@ /// d.addSource(s); /// d.start(t); ///\endcode - int run(Node s,Node t) { + bool run(Node s,Node t) { init(); addSource(s); start(t); - return reached(t)?_stack_head+1:0; + return reached(t); } ///Runs the algorithm to visit all nodes in the digraph. @@ -1526,16 +1526,16 @@ /// Executes the algorithm until the given target node is reached. /// /// This method runs the %DFS algorithm from the root node - /// in order to compute the DFS path to \c dest. + /// in order to compute the DFS path to \c t. /// /// The algorithm computes - /// - the %DFS path to \c dest, - /// - the distance of \c dest from the root in the %DFS tree. + /// - the %DFS path to \c t, + /// - the distance of \c t from the root in the %DFS tree. /// /// \pre init() must be called and a root node should be added /// with addSource() before using this function. - void start(Node dest) { - while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) + void start(Node t) { + while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) processNextArc(); } @@ -1564,7 +1564,7 @@ return emptyQueue() ? INVALID : _stack[_stack_head]; } - /// \brief Runs the algorithm from the given node. + /// \brief Runs the algorithm from the given source node. /// /// This method runs the %DFS algorithm from node \c s. /// in order to compute the DFS path to each node. @@ -1588,10 +1588,10 @@ /// \brief Finds the %DFS path between \c s and \c t. /// This method runs the %DFS algorithm from node \c s - /// in order to compute the DFS path to \c t. + /// in order to compute the DFS path to node \c t + /// (it stops searching when \c t is processed). /// - /// \return The length of the s--t DFS path, - /// if \c t is reachable form \c s, \c 0 otherwise. + /// \return \c true if \c t is reachable form \c s. /// /// \note Apart from the return value, d.run(s,t) is /// just a shortcut of the following code. @@ -1600,11 +1600,11 @@ /// d.addSource(s); /// d.start(t); ///\endcode - int run(Node s,Node t) { + bool run(Node s,Node t) { init(); addSource(s); start(t); - return reached(t)?_stack_head+1:0; + return reached(t); } /// \brief Runs the algorithm to visit all nodes in the digraph. diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -728,23 +728,26 @@ while ( !emptyQueue() ) processNextNode(); } - ///Executes the algorithm until the given target node is reached. + ///Executes the algorithm until the given target node is processed. - ///Executes the algorithm until the given target node is reached. + ///Executes the algorithm until the given target node is processed. /// ///This method runs the %Dijkstra algorithm from the root node(s) - ///in order to compute the shortest path to \c dest. + ///in order to compute the shortest path to \c t. /// ///The algorithm computes - ///- the shortest path to \c dest, - ///- the distance of \c dest from the root(s). + ///- the shortest path to \c t, + ///- the distance of \c t from the root(s). /// ///\pre init() must be called and at least one root node should be ///added with addSource() before using this function. - void start(Node dest) + void start(Node t) { - while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); - if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); + while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); + if ( !_heap->empty() ) { + finalizeNodeData(_heap->top(),_heap->prio()); + _heap->pop(); + } } ///Executes the algorithm until a condition is met. @@ -772,7 +775,7 @@ return _heap->top(); } - ///Runs the algorithm from the given node. + ///Runs the algorithm from the given source node. ///This method runs the %Dijkstra algorithm from node \c s ///in order to compute the shortest path to each node. @@ -796,10 +799,10 @@ ///Finds the shortest path between \c s and \c t. ///This method runs the %Dijkstra algorithm from node \c s - ///in order to compute the shortest path to \c t. + ///in order to compute the shortest path to node \c t + ///(it stops searching when \c t is processed). /// - ///\return The length of the shortest s--t path, - ///if \c t is reachable form \c s, \c 0 otherwise. + ///\return \c true if \c t is reachable form \c s. /// ///\note Apart from the return value, d.run(s,t) is just a ///shortcut of the following code. @@ -808,11 +811,11 @@ /// d.addSource(s); /// d.start(t); ///\endcode - Value run(Node s,Node t) { + bool run(Node s,Node t) { init(); addSource(s); start(t); - return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t]; + return (*_heap_cross_ref)[t] == Heap::POST_HEAP; } ///@} @@ -908,7 +911,7 @@ ///Returns \c true if \c v is processed, i.e. the shortest ///path to \c v has already found. - ///\pre Either \ref run() or \ref start() + ///\pre Either \ref run() or \ref init() ///must be called before using this function. bool processed(Node v) const { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } @@ -917,8 +920,12 @@ ///Returns the current distance of a node from the root(s). ///It may be decreased in the following processes. - ///\pre \c v should be reached but not processed. - Value currentDist(Node v) const { return (*_heap)[v]; } + ///\pre Either \ref run() or \ref init() + ///must be called before using this function and + ///node \c v must be reached but not necessarily processed. + Value currentDist(Node v) const { + return processed(v) ? (*_dist)[v] : (*_heap)[v]; + } ///@} }; diff --git a/test/bfs_test.cc b/test/bfs_test.cc --- a/test/bfs_test.cc +++ b/test/bfs_test.cc @@ -54,27 +54,52 @@ { typedef concepts::Digraph Digraph; typedef Bfs BType; + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; Digraph G; - Digraph::Node n; - Digraph::Arc e; + Node s, t; + Arc e; int l; bool b; BType::DistMap d(G); BType::PredMap p(G); + Path pp; - BType bfs_test(G); + { + BType bfs_test(G); - bfs_test.run(n); + bfs_test.run(s); + bfs_test.run(s,t); + bfs_test.run(); - l = bfs_test.dist(n); - e = bfs_test.predArc(n); - n = bfs_test.predNode(n); - d = bfs_test.distMap(); - p = bfs_test.predMap(); - b = bfs_test.reached(n); + l = bfs_test.dist(t); + e = bfs_test.predArc(t); + s = bfs_test.predNode(t); + b = bfs_test.reached(t); + d = bfs_test.distMap(); + p = bfs_test.predMap(); + pp = bfs_test.path(t); + } + { + BType + ::SetPredMap > + ::SetDistMap > + ::SetReachedMap > + ::SetProcessedMap > + ::SetStandardProcessedMap + ::Create bfs_test(G); - Path pp = bfs_test.path(n); + bfs_test.run(s); + bfs_test.run(s,t); + bfs_test.run(); + + l = bfs_test.dist(t); + e = bfs_test.predArc(t); + s = bfs_test.predNode(t); + b = bfs_test.reached(t); + pp = bfs_test.path(t); + } } void checkBfsFunctionCompile() diff --git a/test/dfs_test.cc b/test/dfs_test.cc --- a/test/dfs_test.cc +++ b/test/dfs_test.cc @@ -56,27 +56,52 @@ { typedef concepts::Digraph Digraph; typedef Dfs DType; + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; Digraph G; - Digraph::Node n; - Digraph::Arc e; + Node s, t; + Arc e; int l; bool b; DType::DistMap d(G); DType::PredMap p(G); + Path pp; - DType dfs_test(G); + { + DType dfs_test(G); - dfs_test.run(n); + dfs_test.run(s); + dfs_test.run(s,t); + dfs_test.run(); - l = dfs_test.dist(n); - e = dfs_test.predArc(n); - n = dfs_test.predNode(n); - d = dfs_test.distMap(); - p = dfs_test.predMap(); - b = dfs_test.reached(n); + l = dfs_test.dist(t); + e = dfs_test.predArc(t); + s = dfs_test.predNode(t); + b = dfs_test.reached(t); + d = dfs_test.distMap(); + p = dfs_test.predMap(); + pp = dfs_test.path(t); + } + { + DType + ::SetPredMap > + ::SetDistMap > + ::SetReachedMap > + ::SetProcessedMap > + ::SetStandardProcessedMap + ::Create dfs_test(G); - Path pp = dfs_test.path(n); + dfs_test.run(s); + dfs_test.run(s,t); + dfs_test.run(); + + l = dfs_test.dist(t); + e = dfs_test.predArc(t); + s = dfs_test.predNode(t); + b = dfs_test.reached(t); + pp = dfs_test.path(t); + } } void checkDfsFunctionCompile() diff --git a/test/dijkstra_test.cc b/test/dijkstra_test.cc --- a/test/dijkstra_test.cc +++ b/test/dijkstra_test.cc @@ -22,6 +22,7 @@ #include #include #include +#include #include "graph_test.h" #include "test_tools.h" @@ -55,28 +56,54 @@ typedef concepts::Digraph Digraph; typedef concepts::ReadMap LengthMap; typedef Dijkstra DType; + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; Digraph G; - Digraph::Node n; - Digraph::Arc e; + Node s, t; + Arc e; VType l; bool b; DType::DistMap d(G); DType::PredMap p(G); LengthMap length; + Path pp; - DType dijkstra_test(G,length); + { + DType dijkstra_test(G,length); - dijkstra_test.run(n); + dijkstra_test.run(s); + dijkstra_test.run(s,t); - l = dijkstra_test.dist(n); - e = dijkstra_test.predArc(n); - n = dijkstra_test.predNode(n); - d = dijkstra_test.distMap(); - p = dijkstra_test.predMap(); - b = dijkstra_test.reached(n); + l = dijkstra_test.dist(t); + e = dijkstra_test.predArc(t); + s = dijkstra_test.predNode(t); + b = dijkstra_test.reached(t); + d = dijkstra_test.distMap(); + p = dijkstra_test.predMap(); + pp = dijkstra_test.path(t); + } + { + DType + ::SetPredMap > + ::SetDistMap > + ::SetProcessedMap > + ::SetStandardProcessedMap + ::SetOperationTraits > + ::SetHeap > > + ::SetStandardHeap > > + ::Create dijkstra_test(G,length); - Path pp = dijkstra_test.path(n); + dijkstra_test.run(s); + dijkstra_test.run(s,t); + + l = dijkstra_test.dist(t); + e = dijkstra_test.predArc(t); + s = dijkstra_test.predNode(t); + b = dijkstra_test.reached(t); + pp = dijkstra_test.path(t); + } + } void checkDijkstraFunctionCompile()