# Changeset 287:bb40b6db0a58 in lemon

Ignore:
Timestamp:
09/27/08 14:33:28 (14 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
Message:

Merge

Location:
lemon
Files:
6 edited

Unmodified
Removed
• ## lemon/bfs.h

 r281 /// ///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/bfs.h

 r286 ///\param g is the digraph, to which we would like to define the ///\ref PredMap. ///\todo The digraph alone may be insufficient to initialize static PredMap *createPredMap(const Digraph &g) { ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \ref ProcessedMap. int _curr_dist; ///Creates the maps if necessary. ///\todo Better memory allocation (instead of new). //Creates the maps if necessary. void create_maps() { ///\param g is the digraph, to which we would like to define the ///\ref PredMap. ///\todo The digraph alone may be insufficient to initialize static PredMap *createPredMap(const Digraph &g) { int _list_front, _list_back; ///Creates the maps if necessary. ///\todo Better memory allocation (instead of new). //Creates the maps if necessary. void create_maps() { if(!_reached) {