# Changeset 287:bb40b6db0a58 in lemon-1.2

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) {
• ## lemon/dfs.h

 r281 /// ///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/dfs.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 _stack_head; ///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 _stack_head; ///Creates the maps if necessary. ///\todo Better memory allocation (instead of new). //Creates the maps if necessary. void create_maps() { if(!_reached) {
• ## lemon/dijkstra.h

 r281 } ///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]; } ///@}
• ## lemon/dijkstra.h

 r286 ///\param g is the digraph, to which we would like to define the ///\ref PredMap. ///\todo The digraph alone may be insufficient for the initialization static PredMap *createPredMap(const Digraph &g) { ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///\todo If it is set to a real map, ///Dijkstra::processed() should read this. typedef NullMap ProcessedMap; ///Instantiates a \ref ProcessedMap. bool local_heap; ///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 /// HeapCrossRef. /// \todo The digraph alone may be insufficient for the initialization static HeapCrossRef *createHeapCrossRef(const Digraph &g) { ///\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) { ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///\todo If it is set to a real map, ///Dijkstra::processed() should read this. ///\todo named parameter to set this type, function to read and write. typedef NullMap ProcessedMap; ///Instantiates a \ref ProcessedMap. /// The \ref DijkstraWizardBase is a class to be the default traits of the /// \ref DijkstraWizard class. /// \todo More named parameters are required... template class DijkstraWizardBase : public DijkstraWizardDefaultTraits
Note: See TracChangeset for help on using the changeset viewer.