# Changeset 286:da414906fe21 in lemon

Ignore:
Timestamp:
09/26/08 12:40:11 (12 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); }