# Changeset 286:da414906fe21 in lemon

Ignore:
Timestamp:
09/26/08 12:40:11 (11 years ago)
Branch:
default
Phase:
public
Message:

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.
Files:
6 edited

Unmodified
Removed
• ## lemon/bfs.h

 r278 /// ///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 ///  } ///\endcode void start(Node dest) void start(Node t) { bool reach = false; while ( !emptyQueue() && !reach ) processNextNode(dest, reach); while ( !emptyQueue() && !reach ) processNextNode(t, reach); } } ///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 ///This method runs the %BFS algorithm from node \c s ///in order to compute the shortest path to \c t. /// ///\return The length of the shortest s--t path, ///if \c t is reachable form \c s, \c 0 otherwise. ///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 ///  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); } /// /// 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 ///   } /// \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 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 addSource(s); 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); }
• ## lemon/dfs.h

 r278 /// ///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() && G->target(_stack[_stack_head])!=dest ) void start(Node t) { while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) processNextArc(); } } ///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 ///This method runs the %DFS algorithm from node \c s ///in order to compute the DFS path to \c t. /// ///\return The length of the s--t DFS path, ///if \c t is reachable form \c s, \c 0 otherwise. ///in order to compute the DFS 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, d.run(s,t) is ///  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); } /// /// 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(); } } /// \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. /// This method runs the %DFS algorithm from node \c s /// in order to compute the DFS path to \c t. /// /// \return The length of the s--t DFS path, /// if \c t is reachable form \c s, \c 0 otherwise. /// in order to compute the DFS 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, d.run(s,t) is ///   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); }
• ## lemon/dijkstra.h

 r278 } ///Executes the algorithm until the given target node is reached. ///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 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) { while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); void start(Node t) { while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); if ( !_heap->empty() ) { finalizeNodeData(_heap->top(),_heap->prio()); _heap->pop(); } } } ///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 ///This method runs the %Dijkstra algorithm from node \c s ///in order to compute the shortest path to \c t. /// ///\return The length of the shortest s--t path, ///if \c t is reachable form \c s, \c 0 otherwise. ///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, d.run(s,t) is just a ///  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; } ///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] == ///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]; } ///@}
• ## test/bfs_test.cc

 r278 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); } }
• ## test/dfs_test.cc

 r278 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); } }
• ## test/dijkstra_test.cc

 r278 #include #include #include #include "graph_test.h" 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::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); } }
Note: See TracChangeset for help on using the changeset viewer.