# HG changeset patch # User Peter Kovacs # Date 2008-08-03 13:34:57 # Node ID c30731a37f91837bfcfba1aac8844f022ef41554 # Parent b67149f0e6757cc1132d30f6ca7d4050e210b66c Many improvements in bfs.h, dfs.h and dijkstra.h - Add run() function to Bfs and run(s,t) function to DfsVisit. - Add debug checking to addSource() function of Dfs and DfsVisit. - Add a few missing named parameters (according to \todo notes). - Small fixes in the code (e.g. missing derivations). - Many doc improvements. - Remove \todo and \warning comments which are no longer valid. - Remove \author commands (see ticket #39). - Fixes in the the doc (e.g. wrong references). - Hide the doc of most of the private and protected members. - Use public typedefs instead of template parameters in public functions. - Use better parameter names for some functions. - Other small changes to make the doc more uniform. diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -21,7 +21,7 @@ ///\ingroup search ///\file -///\brief Bfs algorithm. +///\brief BFS algorithm. #include #include @@ -32,8 +32,6 @@ namespace lemon { - - ///Default traits class of Bfs class. ///Default traits class of Bfs class. @@ -41,73 +39,75 @@ template struct BfsDefaultTraits { - ///The digraph type the algorithm runs on. + ///The type of the digraph the algorithm runs on. typedef GR Digraph; - ///\brief The type of the map that stores the last + + ///\brief The type of the map that stores the predecessor ///arcs of the shortest paths. /// - ///The type of the map that stores the last + ///The type of the map that stores the predecessor ///arcs of the shortest paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef typename Digraph::template NodeMap PredMap; - ///Instantiates a PredMap. + typedef typename Digraph::template NodeMap PredMap; + ///Instantiates a \ref PredMap. ///This function instantiates a \ref PredMap. - ///\param G is the digraph, to which we would like to define the PredMap. + ///\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 GR &G) + static PredMap *createPredMap(const Digraph &g) { - return new PredMap(G); + return new PredMap(g); } + ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. + ///By default it is a NullMap. typedef NullMap ProcessedMap; - ///Instantiates a ProcessedMap. + ///Instantiates a \ref ProcessedMap. ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which ///we would like to define the \ref ProcessedMap #ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const GR &g) + static ProcessedMap *createProcessedMap(const Digraph &g) #else - static ProcessedMap *createProcessedMap(const GR &) + static ProcessedMap *createProcessedMap(const Digraph &) #endif { return new ProcessedMap(); } + ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - ///Instantiates a ReachedMap. + ///Instantiates a \ref ReachedMap. ///This function instantiates a \ref ReachedMap. - ///\param G is the digraph, to which + ///\param g is the digraph, to which ///we would like to define the \ref ReachedMap. - static ReachedMap *createReachedMap(const GR &G) + static ReachedMap *createReachedMap(const Digraph &g) { - return new ReachedMap(G); + return new ReachedMap(g); } - ///The type of the map that stores the dists of the nodes. - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. + + ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// typedef typename Digraph::template NodeMap DistMap; - ///Instantiates a DistMap. + ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. - ///\param G is the digraph, to which we would like to define - ///the \ref DistMap - static DistMap *createDistMap(const GR &G) + ///\param g is the digraph, to which we would like to define the + ///\ref DistMap. + static DistMap *createDistMap(const Digraph &g) { - return new DistMap(G); + return new DistMap(g); } }; @@ -116,15 +116,18 @@ ///\ingroup search ///This class provides an efficient implementation of the %BFS algorithm. /// - ///\tparam GR The digraph type the algorithm runs on. The default value is - ///\ref ListDigraph. The value of GR is not used directly by Bfs, it - ///is only passed to \ref BfsDefaultTraits. + ///There is also a \ref bfs() "function type interface" for the BFS + ///algorithm, which is convenient in the simplier cases and it can be + ///used easier. + /// + ///\tparam GR The type of the digraph the algorithm runs on. + ///The default value is \ref ListDigraph. The value of GR is not used + ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. ///\tparam TR Traits class to set various data types used by the algorithm. ///The default traits class is ///\ref BfsDefaultTraits "BfsDefaultTraits". ///See \ref BfsDefaultTraits for the documentation of ///a Bfs traits class. - #ifdef DOXYGEN template @@ -134,12 +137,10 @@ #endif class Bfs { public: - /** - * \brief \ref Exception for uninitialized parameters. - * - * This error represents problems in the initialization - * of the parameters of the algorithms. - */ + ///\ref Exception for uninitialized parameters. + + ///This error represents problems in the initialization of the + ///parameters of the algorithm. class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() { @@ -147,19 +148,24 @@ } }; - typedef TR Traits; - ///The type of the underlying digraph. + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - ///\brief The type of the map that stores the last - ///arcs of the shortest paths. + ///\brief The type of the map that stores the predecessor arcs of the + ///shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map indicating which nodes are reached. + ///The type of the map that stores the distances of the nodes. + typedef typename TR::DistMap DistMap; + ///The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///The type of the map indicating which nodes are processed. + ///The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the map that stores the dists of the nodes. - typedef typename TR::DistMap DistMap; + ///The type of the paths. + typedef PredMapPath Path; + + ///The traits class. + typedef TR Traits; + private: typedef typename Digraph::Node Node; @@ -167,23 +173,23 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - /// Pointer to the underlying digraph. + //Pointer to the underlying digraph. const Digraph *G; - ///Pointer to the map of predecessors arcs. + //Pointer to the map of predecessor arcs. PredMap *_pred; - ///Indicates if \ref _pred is locally allocated (\c true) or not. + //Indicates if _pred is locally allocated (true) or not. bool local_pred; - ///Pointer to the map of distances. + //Pointer to the map of distances. DistMap *_dist; - ///Indicates if \ref _dist is locally allocated (\c true) or not. + //Indicates if _dist is locally allocated (true) or not. bool local_dist; - ///Pointer to the map of reached status of the nodes. + //Pointer to the map of reached status of the nodes. ReachedMap *_reached; - ///Indicates if \ref _reached is locally allocated (\c true) or not. + //Indicates if _reached is locally allocated (true) or not. bool local_reached; - ///Pointer to the map of processed status of the nodes. + //Pointer to the map of processed status of the nodes. ProcessedMap *_processed; - ///Indicates if \ref _processed is locally allocated (\c true) or not. + //Indicates if _processed is locally allocated (true) or not. bool local_processed; std::vector _queue; @@ -191,7 +197,6 @@ int _curr_dist; ///Creates the maps if necessary. - ///\todo Better memory allocation (instead of new). void create_maps() { @@ -234,10 +239,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///PredMap type + ///\ref PredMap type. /// - ///\ref named-templ-param "Named parameter" for setting PredMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref PredMap type. template struct DefPredMap : public Bfs< Digraph, DefPredMapTraits > { typedef Bfs< Digraph, DefPredMapTraits > Create; @@ -252,10 +257,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///DistMap type + ///\ref DistMap type. /// - ///\ref named-templ-param "Named parameter" for setting DistMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref DistMap type. template struct DefDistMap : public Bfs< Digraph, DefDistMapTraits > { typedef Bfs< Digraph, DefDistMapTraits > Create; @@ -270,10 +275,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ReachedMap type + ///\ref ReachedMap type. /// - ///\ref named-templ-param "Named parameter" for setting ReachedMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref ReachedMap type. template struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits > { typedef Bfs< Digraph, DefReachedMapTraits > Create; @@ -288,10 +293,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ProcessedMap type + ///\ref ProcessedMap type. /// - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type. template struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits > { typedef Bfs< Digraph, DefProcessedMapTraits > Create; @@ -299,16 +304,16 @@ struct DefDigraphProcessedMapTraits : public Traits { typedef typename Digraph::template NodeMap ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &G) + static ProcessedMap *createProcessedMap(const Digraph &g) { - return new ProcessedMap(G); + return new ProcessedMap(g); } }; - ///\brief \ref named-templ-param "Named parameter" - ///for setting the ProcessedMap type to be Digraph::NodeMap. + ///\brief \ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type to be Digraph::NodeMap. /// - ///\ref named-templ-param "Named parameter" - ///for setting the ProcessedMap type to be Digraph::NodeMap. + ///\ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type to be Digraph::NodeMap. ///If you don't set it explicitly, it will be automatically allocated. template struct DefProcessedMapToBeDefaultMap : @@ -322,10 +327,10 @@ ///Constructor. - ///\param _G the digraph the algorithm will run on. - /// - Bfs(const Digraph& _G) : - G(&_G), + ///Constructor. + ///\param g The digraph the algorithm runs on. + Bfs(const Digraph &g) : + G(&g), _pred(NULL), local_pred(false), _dist(NULL), local_dist(false), _reached(NULL), local_reached(false), @@ -341,9 +346,9 @@ if(local_processed) delete _processed; } - ///Sets the map storing the predecessor arcs. + ///Sets the map that stores the predecessor arcs. - ///Sets the map storing the predecessor arcs. + ///Sets the map that stores the predecessor arcs. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. @@ -358,9 +363,9 @@ return *this; } - ///Sets the map indicating the reached nodes. + ///Sets the map that indicates which nodes are reached. - ///Sets the map indicating the reached nodes. + ///Sets the map that indicates which nodes are reached. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. @@ -375,9 +380,9 @@ return *this; } - ///Sets the map indicating the processed nodes. + ///Sets the map that indicates which nodes are processed. - ///Sets the map indicating the processed nodes. + ///Sets the map that indicates which nodes are processed. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. @@ -392,9 +397,10 @@ return *this; } - ///Sets the map storing the distances calculated by the algorithm. + ///Sets the map that stores the distances of the nodes. - ///Sets the map storing the distances calculated by the algorithm. + ///Sets the map that stores the distances of the nodes calculated by + ///the algorithm. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. @@ -410,20 +416,21 @@ } public: + ///\name Execution control ///The simplest way to execute the algorithm is to use - ///one of the member functions called \c run(...). + ///one of the member functions called \ref lemon::Bfs::run() "run()". ///\n - ///If you need more control on the execution, - ///first you must call \ref init(), then you can add several source nodes - ///with \ref addSource(). - ///Finally \ref start() will perform the actual path - ///computation. + ///If you need more control on the execution, first you must call + ///\ref lemon::Bfs::init() "init()", then you can add several source + ///nodes with \ref lemon::Bfs::addSource() "addSource()". + ///Finally \ref lemon::Bfs::start() "start()" will perform the + ///actual path computation. ///@{ - ///\brief Initializes the internal data structures. - /// + ///Initializes the internal data structures. + ///Initializes the internal data structures. /// void init() @@ -461,7 +468,7 @@ /// ///\return The processed node. /// - ///\warning The queue must not be empty! + ///\pre The queue must not be empty. Node processNextNode() { if(_queue_tail==_queue_next_dist) { @@ -483,16 +490,17 @@ ///Processes the next node. - ///Processes the next node. And checks that the given target node + ///Processes the next node and checks if the given target node ///is reached. If the target node is reachable from the processed - ///node then the reached parameter will be set true. The reached - ///parameter should be initially false. + ///node, then the \c reach parameter will be set to \c true. /// ///\param target The target node. - ///\retval reach Indicates that the target node is reached. + ///\retval reach Indicates if the target node is reached. + ///It should be initially \c false. + /// ///\return The processed node. /// - ///\warning The queue must not be empty! + ///\pre The queue must not be empty. Node processNextNode(Node target, bool& reach) { if(_queue_tail==_queue_next_dist) { @@ -515,16 +523,19 @@ ///Processes the next node. - ///Processes the next node. And checks that at least one of - ///reached node has true value in the \c nm node map. If one node - ///with true value is reachable from the processed node then the - ///rnode parameter will be set to the first of such nodes. + ///Processes the next node and checks if at least one of reached + ///nodes has \c true value in the \c nm node map. If one node + ///with \c true value is reachable from the processed node, then the + ///\c rnode parameter will be set to the first of such nodes. /// - ///\param nm The node map of possible targets. + ///\param nm A \c bool (or convertible) node map that indicates the + ///possible targets. ///\retval rnode The reached target node. + ///It should be initially \c INVALID. + /// ///\return The processed node. /// - ///\warning The queue must not be empty! + ///\pre The queue must not be empty. template Node processNextNode(const NM& nm, Node& rnode) { @@ -546,58 +557,73 @@ return n; } - ///Next node to be processed. + ///The next node to be processed. - ///Next node to be processed. - /// - ///\return The next node to be processed or INVALID if the queue is - /// empty. - Node nextNode() + ///Returns the next node to be processed or \c INVALID if the queue + ///is empty. + Node nextNode() const { return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; } ///\brief Returns \c false if there are nodes - ///to be processed in the queue + ///to be processed. /// ///Returns \c false if there are nodes - ///to be processed in the queue - bool emptyQueue() { return _queue_tail==_queue_head; } + ///to be processed in the queue. + bool emptyQueue() const { return _queue_tail==_queue_head; } + ///Returns the number of the nodes to be processed. ///Returns the number of the nodes to be processed in the queue. - int queueSize() { return _queue_head-_queue_tail; } + int queueSize() const { return _queue_head-_queue_tail; } ///Executes the algorithm. ///Executes the algorithm. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %BFS algorithm from the root node(s) + ///in order to compute the shortest path to each node. /// - ///This method runs the %BFS algorithm from the root node(s) - ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the root(s). + ///The algorithm computes + ///- the shortest path tree (forest), + ///- the distance of each node from the root(s). + /// + ///\pre init() must be called and at least one root node should be + ///added with addSource() before using this function. + /// + ///\note b.start() is just a shortcut of the following code. + ///\code + /// while ( !b.emptyQueue() ) { + /// b.processNextNode(); + /// } + ///\endcode void start() { while ( !emptyQueue() ) processNextNode(); } - ///Executes the algorithm until \c dest is reached. + ///Executes the algorithm until the given target node is reached. - ///Executes the algorithm until \c dest is reached. - /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///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. + /// ///The algorithm computes - ///- The shortest path to \c dest. - ///- The distance of \c dest from the root(s). + ///- the shortest path to \c dest, + ///- the distance of \c dest from the root(s). + /// + ///\pre init() must be called and at least one root node should be + ///added with addSource() before using this function. + /// + ///\note b.start(t) is just a shortcut of the following code. + ///\code + /// bool reach = false; + /// while ( !b.emptyQueue() && !reach ) { + /// b.processNextNode(t, reach); + /// } + ///\endcode void start(Node dest) { bool reach = false; @@ -608,17 +634,29 @@ ///Executes the algorithm until a condition is met. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %BFS algorithm from the root node(s) in + ///order to compute the shortest path to a node \c v with + /// nm[v] true, if such a node can be found. /// - ///\param nm must be a bool (or convertible) node map. The - ///algorithm will stop when it reaches a node \c v with - /// nm[v] true. + ///\param nm A \c bool (or convertible) node map. The algorithm + ///will stop when it reaches a node \c v with nm[v] true. /// ///\return The reached node \c v with nm[v] true or ///\c INVALID if no such node was found. - template - Node start(const NM &nm) + /// + ///\pre init() must be called and at least one root node should be + ///added with addSource() before using this function. + /// + ///\note b.start(nm) is just a shortcut of the following code. + ///\code + /// Node rnode = INVALID; + /// while ( !b.emptyQueue() && rnode == INVALID ) { + /// b.processNextNode(nm, rnode); + /// } + /// return rnode; + ///\endcode + template + Node start(const NodeBoolMap &nm) { Node rnode = INVALID; while ( !emptyQueue() && rnode == INVALID ) { @@ -627,16 +665,16 @@ return rnode; } - ///Runs %BFS algorithm from node \c s. + ///Runs the algorithm from the given node. - ///This method runs the %BFS algorithm from a root node \c s - ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the root. + ///This method runs the %BFS algorithm from node \c s + ///in order to compute the shortest path to each node. /// - ///\note b.run(s) is just a shortcut of the following code. + ///The algorithm computes + ///- the shortest path tree, + ///- the distance of each node from the root. + /// + ///\note b.run(s) is just a shortcut of the following code. ///\code /// b.init(); /// b.addSource(s); @@ -650,12 +688,14 @@ ///Finds the shortest path between \c s and \c t. - ///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. /// - ///\return The length of the shortest s---t path if there exists one, - ///0 otherwise. - ///\note Apart from the return value, b.run(s) is - ///just a shortcut of the following code. + ///\return The length of the shortest s--t path, + ///if \c t is reachable form \c s, \c 0 otherwise. + /// + ///\note Apart from the return value, b.run(s,t) is just a + ///shortcut of the following code. ///\code /// b.init(); /// b.addSource(s); @@ -668,116 +708,152 @@ return reached(t) ? _curr_dist : 0; } + ///Runs the algorithm to visit all nodes in the digraph. + + ///This method runs the %BFS algorithm in order to + ///compute the shortest path to each node. + /// + ///The algorithm computes + ///- the shortest path tree (forest), + ///- the distance of each node from the root(s). + /// + ///\note b.run(s) is just a shortcut of the following code. + ///\code + /// b.init(); + /// for (NodeIt n(gr); n != INVALID; ++n) { + /// if (!b.reached(n)) { + /// b.addSource(n); + /// b.start(); + /// } + /// } + ///\endcode + void run() { + init(); + for (NodeIt n(*G); n != INVALID; ++n) { + if (!reached(n)) { + addSource(n); + start(); + } + } + } + ///@} ///\name Query Functions ///The result of the %BFS algorithm can be obtained using these ///functions.\n - ///Before the use of these functions, - ///either run() or start() must be calleb. + ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() + ///"start()" must be called before using them. ///@{ - typedef PredMapPath Path; + ///The shortest path to a node. - ///Gives back the shortest path. - - ///Gives back the shortest path. - ///\pre The \c t should be reachable from the source. - Path path(Node t) - { - return Path(*G, *_pred, t); - } + ///Returns the shortest path to a node. + /// + ///\warning \c t should be reachable from the root(s). + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. + Path path(Node t) const { return Path(*G, *_pred, t); } ///The distance of a node from the root(s). ///Returns the distance of a node from the root(s). - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root(s) the return value - ///of this function is undefined. + /// + ///\warning If node \c v is not reachable from the root(s), then + ///the return value of this function is undefined. + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the shortest path tree. + ///Returns the 'previous arc' of the shortest path tree for a node. - ///For a node \c v it returns the 'previous arc' - ///of the shortest path tree, - ///i.e. it returns the last arc of a shortest path from the root(s) to \c - ///v. It is \ref INVALID - ///if \c v is unreachable from the root(s) or \c v is a root. The - ///shortest path tree used here is equal to the shortest path tree used in - ///\ref predNode(). - ///\pre Either \ref run() or \ref start() must be called before using - ///this function. + ///This function returns the 'previous arc' of the shortest path + ///tree for the node \c v, i.e. it returns the last arc of a + ///shortest path from the root(s) to \c v. It is \c INVALID if \c v + ///is not reachable from the root(s) or if \c v is a root. + /// + ///The shortest path tree used here is equal to the shortest path + ///tree used in \ref predNode(). + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the shortest path tree. + ///Returns the 'previous node' of the shortest path tree for a node. - ///For a node \c v it returns the 'previous node' - ///of the shortest path tree, - ///i.e. it returns the last but one node from a shortest path from the - ///root(a) to \c /v. - ///It is INVALID if \c v is unreachable from the root(s) or - ///if \c v itself a root. + ///This function returns the 'previous node' of the shortest path + ///tree for the node \c v, i.e. it returns the last but one node + ///from a shortest path from the root(s) to \c v. It is \c INVALID + ///if \c v is not reachable from the root(s) or if \c v is a root. + /// ///The shortest path tree used here is equal to the shortest path ///tree used in \ref predArc(). + /// ///\pre Either \ref run() or \ref start() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } - ///Returns a reference to the NodeMap of distances. - - ///Returns a reference to the NodeMap of distances. - ///\pre Either \ref run() or \ref init() must - ///be called before using this function. + ///\brief Returns a const reference to the node map that stores the + /// distances of the nodes. + /// + ///Returns a const reference to the node map that stores the distances + ///of the nodes calculated by the algorithm. + /// + ///\pre Either \ref run() or \ref init() + ///must be called before using this function. const DistMap &distMap() const { return *_dist;} - ///Returns a reference to the shortest path tree map. - - ///Returns a reference to the NodeMap of the arcs of the - ///shortest path tree. + ///\brief Returns a const reference to the node map that stores the + ///predecessor arcs. + /// + ///Returns a const reference to the node map that stores the predecessor + ///arcs, which form the shortest path tree. + /// ///\pre Either \ref run() or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reachable from the root. + ///Checks if a node is reachable from the root(s). - ///Returns \c true if \c v is reachable from the root. - ///\warning The source nodes are indicated as unreached. + ///Returns \c true if \c v is reachable from the root(s). ///\pre Either \ref run() or \ref start() ///must be called before using this function. - /// - bool reached(Node v) { return (*_reached)[v]; } + bool reached(Node v) const { return (*_reached)[v]; } ///@} }; - ///Default traits class of Bfs function. + ///Default traits class of bfs() function. - ///Default traits class of Bfs function. + ///Default traits class of bfs() function. ///\tparam GR Digraph type. template struct BfsWizardDefaultTraits { - ///The digraph type the algorithm runs on. + ///The type of the digraph the algorithm runs on. typedef GR Digraph; - ///\brief The type of the map that stores the last + + ///\brief The type of the map that stores the predecessor ///arcs of the shortest paths. /// - ///The type of the map that stores the last + ///The type of the map that stores the predecessor ///arcs of the shortest paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef NullMap PredMap; - ///Instantiates a PredMap. + typedef NullMap PredMap; + ///Instantiates a \ref PredMap. ///This function instantiates a \ref PredMap. - ///\param g is the digraph, to which we would like to define the PredMap. + ///\param g is the digraph, to which we would like to define the + ///\ref PredMap. ///\todo The digraph alone may be insufficient to initialize #ifdef DOXYGEN - static PredMap *createPredMap(const GR &g) + static PredMap *createPredMap(const Digraph &g) #else - static PredMap *createPredMap(const GR &) + static PredMap *createPredMap(const Digraph &) #endif { return new PredMap(); @@ -787,63 +863,63 @@ ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. typedef NullMap ProcessedMap; - ///Instantiates a ProcessedMap. + ///Instantiates a \ref ProcessedMap. ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which - ///we would like to define the \ref ProcessedMap + ///we would like to define the \ref ProcessedMap. #ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const GR &g) + static ProcessedMap *createProcessedMap(const Digraph &g) #else - static ProcessedMap *createProcessedMap(const GR &) + static ProcessedMap *createProcessedMap(const Digraph &) #endif { return new ProcessedMap(); } + ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - ///Instantiates a ReachedMap. + ///Instantiates a \ref ReachedMap. ///This function instantiates a \ref ReachedMap. - ///\param G is the digraph, to which + ///\param g is the digraph, to which ///we would like to define the \ref ReachedMap. - static ReachedMap *createReachedMap(const GR &G) + static ReachedMap *createReachedMap(const Digraph &g) { - return new ReachedMap(G); + return new ReachedMap(g); } - ///The type of the map that stores the dists of the nodes. - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. + + ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// typedef NullMap DistMap; - ///Instantiates a DistMap. + ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define ///the \ref DistMap #ifdef DOXYGEN - static DistMap *createDistMap(const GR &g) + static DistMap *createDistMap(const Digraph &g) #else - static DistMap *createDistMap(const GR &) + static DistMap *createDistMap(const Digraph &) #endif { return new DistMap(); } }; - /// Default traits used by \ref BfsWizard + /// Default traits class used by \ref BfsWizard /// To make it easier to use Bfs algorithm - ///we have created a wizard class. + /// we have created a wizard class. /// This \ref BfsWizard class needs default traits, - ///as well as the \ref Bfs class. + /// as well as the \ref Bfs class. /// The \ref BfsWizardBase is a class to be the default traits of the /// \ref BfsWizard class. template @@ -852,20 +928,20 @@ typedef BfsWizardDefaultTraits Base; protected: - /// Type of the nodes in the digraph. + //The type of the nodes in the digraph. typedef typename Base::Digraph::Node Node; - /// Pointer to the underlying digraph. + //Pointer to the digraph the algorithm runs on. void *_g; - ///Pointer to the map of reached nodes. + //Pointer to the map of reached nodes. void *_reached; - ///Pointer to the map of processed nodes. + //Pointer to the map of processed nodes. void *_processed; - ///Pointer to the map of predecessors arcs. + //Pointer to the map of predecessors arcs. void *_pred; - ///Pointer to the map of distances. + //Pointer to the map of distances. void *_dist; - ///Pointer to the source node. + //Pointer to the source node. Node _source; public: @@ -874,26 +950,28 @@ /// This constructor does not require parameters, therefore it initiates /// all of the attributes to default values (0, INVALID). BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), - _dist(0), _source(INVALID) {} + _dist(0), _source(INVALID) {} /// Constructor. /// This constructor requires some parameters, /// listed in the parameters list. /// Others are initiated to 0. - /// \param g is the initial value of \ref _g - /// \param s is the initial value of \ref _source + /// \param g The digraph the algorithm runs on. + /// \param s The source node. BfsWizardBase(const GR &g, Node s=INVALID) : _g(reinterpret_cast(const_cast(&g))), _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} }; - /// A class to make the usage of Bfs algorithm easier + /// Auxiliary class for the function type interface of BFS algorithm. - /// This class is created to make it easier to use Bfs algorithm. - /// It uses the functions and features of the plain \ref Bfs, - /// but it is much simpler to use it. + /// This auxiliary class is created to implement the function type + /// interface of \ref Bfs algorithm. It uses the functions and features + /// of the plain \ref Bfs, but it is much simpler to use it. + /// It should only be used through the \ref bfs() function, which makes + /// it easier to use the algorithm. /// /// Simplicity means that the way to change the types defined /// in the traits class is based on functions that returns the new class @@ -902,41 +980,37 @@ /// the new class with the modified type comes from /// the original class by using the :: /// operator. In the case of \ref BfsWizard only - /// a function have to be called and it will + /// a function have to be called, and it will /// return the needed class. /// - /// It does not have own \ref run method. When its \ref run method is called - /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run - /// method of it. + /// It does not have own \ref run() method. When its \ref run() method + /// is called, it initiates a plain \ref Bfs object, and calls the + /// \ref Bfs::run() method of it. template class BfsWizard : public TR { typedef TR Base; - ///The type of the underlying digraph. + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - //\e + typedef typename Digraph::Node Node; - //\e typedef typename Digraph::NodeIt NodeIt; - //\e typedef typename Digraph::Arc Arc; - //\e typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores - ///the reached nodes - typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that stores - ///the processed nodes - typedef typename TR::ProcessedMap ProcessedMap; - ///\brief The type of the map that stores the last + ///\brief The type of the map that stores the predecessor ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map that stores the dists of the nodes. + ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; + ///\brief The type of the map that indicates which nodes are reached. + typedef typename TR::ReachedMap ReachedMap; + ///\brief The type of the map that indicates which nodes are processed. + typedef typename TR::ProcessedMap ProcessedMap; public: + /// Constructor. BfsWizard() : TR() {} @@ -952,10 +1026,10 @@ ~BfsWizard() {} - ///Runs Bfs algorithm from a given node. + ///Runs BFS algorithm from a source node. - ///Runs Bfs algorithm from a given node. - ///The node can be given by the \ref source function. + ///Runs BFS algorithm from a source node. + ///The node can be given with the \ref source() function. void run() { if(Base::_source==INVALID) throw UninitializedParameter(); @@ -971,9 +1045,9 @@ alg.run(Base::_source); } - ///Runs Bfs algorithm from the given node. + ///Runs BFS algorithm from the given node. - ///Runs Bfs algorithm from the given node. + ///Runs BFS algorithm from the given node. ///\param s is the given source. void run(Node s) { @@ -981,89 +1055,6 @@ run(); } - template - struct DefPredMapBase : public Base { - typedef T PredMap; - static PredMap *createPredMap(const Digraph &) { return 0; }; - DefPredMapBase(const TR &b) : TR(b) {} - }; - - ///\brief \ref named-templ-param "Named parameter" - ///function for setting PredMap - /// - /// \ref named-templ-param "Named parameter" - ///function for setting PredMap - /// - template - BfsWizard > predMap(const T &t) - { - Base::_pred=reinterpret_cast(const_cast(&t)); - return BfsWizard >(*this); - } - - - template - struct DefReachedMapBase : public Base { - typedef T ReachedMap; - static ReachedMap *createReachedMap(const Digraph &) { return 0; }; - DefReachedMapBase(const TR &b) : TR(b) {} - }; - - ///\brief \ref named-templ-param "Named parameter" - ///function for setting ReachedMap - /// - /// \ref named-templ-param "Named parameter" - ///function for setting ReachedMap - /// - template - BfsWizard > reachedMap(const T &t) - { - Base::_reached=reinterpret_cast(const_cast(&t)); - return BfsWizard >(*this); - } - - - template - struct DefProcessedMapBase : public Base { - typedef T ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; - DefProcessedMapBase(const TR &b) : TR(b) {} - }; - - ///\brief \ref named-templ-param "Named parameter" - ///function for setting ProcessedMap - /// - /// \ref named-templ-param "Named parameter" - ///function for setting ProcessedMap - /// - template - BfsWizard > processedMap(const T &t) - { - Base::_processed=reinterpret_cast(const_cast(&t)); - return BfsWizard >(*this); - } - - - template - struct DefDistMapBase : public Base { - typedef T DistMap; - static DistMap *createDistMap(const Digraph &) { return 0; }; - DefDistMapBase(const TR &b) : TR(b) {} - }; - - ///\brief \ref named-templ-param "Named parameter" - ///function for setting DistMap type - /// - /// \ref named-templ-param "Named parameter" - ///function for setting DistMap type - /// - template - BfsWizard > distMap(const T &t) - { - Base::_dist=reinterpret_cast(const_cast(&t)); - return BfsWizard >(*this); - } - /// Sets the source node, from which the Bfs algorithm runs. /// Sets the source node, from which the Bfs algorithm runs. @@ -1074,6 +1065,78 @@ return *this; } + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Digraph &) { return 0; }; + DefPredMapBase(const TR &b) : TR(b) {} + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting \ref PredMap object. + /// + /// \ref named-templ-param "Named parameter" + ///for setting \ref PredMap object. + template + BfsWizard > predMap(const T &t) + { + Base::_pred=reinterpret_cast(const_cast(&t)); + return BfsWizard >(*this); + } + + template + struct DefReachedMapBase : public Base { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Digraph &) { return 0; }; + DefReachedMapBase(const TR &b) : TR(b) {} + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting \ref ReachedMap object. + /// + /// \ref named-templ-param "Named parameter" + ///for setting \ref ReachedMap object. + template + BfsWizard > reachedMap(const T &t) + { + Base::_reached=reinterpret_cast(const_cast(&t)); + return BfsWizard >(*this); + } + + template + struct DefProcessedMapBase : public Base { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; + DefProcessedMapBase(const TR &b) : TR(b) {} + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting \ref ProcessedMap object. + /// + /// \ref named-templ-param "Named parameter" + ///for setting \ref ProcessedMap object. + template + BfsWizard > processedMap(const T &t) + { + Base::_processed=reinterpret_cast(const_cast(&t)); + return BfsWizard >(*this); + } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Digraph &) { return 0; }; + DefDistMapBase(const TR &b) : TR(b) {} + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting \ref DistMap object. + /// + /// \ref named-templ-param "Named parameter" + ///for setting \ref DistMap object. + template + BfsWizard > distMap(const T &t) + { + Base::_dist=reinterpret_cast(const_cast(&t)); + return BfsWizard >(*this); + } + }; ///Function type interface for Bfs algorithm. @@ -1101,38 +1164,38 @@ } #ifdef DOXYGEN - /// \brief Visitor class for bfs. + /// \brief Visitor class for BFS. /// /// This class defines the interface of the BfsVisit events, and - /// it could be the base of a real Visitor class. + /// it could be the base of a real visitor class. template struct BfsVisitor { typedef _Digraph Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; - /// \brief Called when the arc reach a node. + /// \brief Called for the source node(s) of the BFS. /// - /// It is called when the bfs find an arc which target is not - /// reached yet. + /// This function is called for the source node(s) of the BFS. + void start(const Node& node) {} + /// \brief Called when a node is reached first time. + /// + /// This function is called when a node is reached first time. + void reach(const Node& node) {} + /// \brief Called when a node is processed. + /// + /// This function is called when a node is processed. + void process(const Node& node) {} + /// \brief Called when an arc reaches a new node. + /// + /// This function is called when the BFS finds an arc whose target node + /// is not reached yet. void discover(const Arc& arc) {} - /// \brief Called when the node reached first time. - /// - /// It is Called when the node reached first time. - void reach(const Node& node) {} - /// \brief Called when the arc examined but target of the arc + /// \brief Called when an arc is examined but its target node is /// already discovered. /// - /// It called when the arc examined but the target of the arc + /// This function is called when an arc is examined but its target node is /// already discovered. void examine(const Arc& arc) {} - /// \brief Called for the source node of the bfs. - /// - /// It is called for the source node of the bfs. - void start(const Node& node) {} - /// \brief Called when the node processed. - /// - /// It is Called when the node processed. - void process(const Node& node) {} }; #else template @@ -1140,22 +1203,22 @@ typedef _Digraph Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; + void start(const Node&) {} + void reach(const Node&) {} + void process(const Node&) {} void discover(const Arc&) {} - void reach(const Node&) {} void examine(const Arc&) {} - void start(const Node&) {} - void process(const Node&) {} template struct Constraints { void constraints() { Arc arc; Node node; + visitor.start(node); + visitor.reach(node); + visitor.process(node); visitor.discover(arc); - visitor.reach(node); visitor.examine(arc); - visitor.start(node); - visitor.process(node); } _Visitor& visitor; }; @@ -1165,21 +1228,20 @@ /// \brief Default traits class of BfsVisit class. /// /// Default traits class of BfsVisit class. - /// \tparam _Digraph Digraph type. + /// \tparam _Digraph The type of the digraph the algorithm runs on. template struct BfsVisitDefaultTraits { - /// \brief The digraph type the algorithm runs on. + /// \brief The type of the digraph the algorithm runs on. typedef _Digraph Digraph; /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// \todo named parameter to set this type, function to read and write. + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - /// \brief Instantiates a ReachedMap. + /// \brief Instantiates a \ref ReachedMap. /// /// This function instantiates a \ref ReachedMap. /// \param digraph is the digraph, to which @@ -1192,28 +1254,28 @@ /// \ingroup search /// - /// \brief %BFS Visit algorithm class. + /// \brief %BFS algorithm class with visitor interface. /// /// This class provides an efficient implementation of the %BFS algorithm /// with visitor interface. /// /// The %BfsVisit class provides an alternative interface to the Bfs /// class. It works with callback mechanism, the BfsVisit object calls - /// on every bfs event the \c Visitor class member functions. + /// the member functions of the \c Visitor class on every BFS event. /// - /// \tparam _Digraph The digraph type the algorithm runs on. + /// \tparam _Digraph The type of the digraph the algorithm runs on. /// The default value is - /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it - /// is only passed to \ref BfsDefaultTraits. - /// \tparam _Visitor The Visitor object for the algorithm. The - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which - /// does not observe the Bfs events. If you want to observe the bfs - /// events you should implement your own Visitor class. + /// \ref ListDigraph. The value of _Digraph is not used directly by + /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. + /// \tparam _Visitor The Visitor type that is used by the algorithm. + /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which + /// does not observe the BFS events. If you want to observe the BFS + /// events, you should implement your own visitor class. /// \tparam _Traits Traits class to set various data types used by the /// algorithm. The default traits class is /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". /// See \ref BfsVisitDefaultTraits for the documentation of - /// a Bfs visit traits class. + /// a BFS visit traits class. #ifdef DOXYGEN template #else @@ -1227,7 +1289,7 @@ /// \brief \ref Exception for uninitialized parameters. /// /// This error represents problems in the initialization - /// of the parameters of the algorithms. + /// of the parameters of the algorithm. class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() @@ -1236,13 +1298,16 @@ } }; + ///The traits class. typedef _Traits Traits; + ///The type of the digraph the algorithm runs on. typedef typename Traits::Digraph Digraph; + ///The visitor type used by the algorithm. typedef _Visitor Visitor; - ///The type of the map indicating which nodes are reached. + ///The type of the map that indicates which nodes are reached. typedef typename Traits::ReachedMap ReachedMap; private: @@ -1252,21 +1317,20 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - /// Pointer to the underlying digraph. + //Pointer to the underlying digraph. const Digraph *_digraph; - /// Pointer to the visitor object. + //Pointer to the visitor object. Visitor *_visitor; - ///Pointer to the map of reached status of the nodes. + //Pointer to the map of reached status of the nodes. ReachedMap *_reached; - ///Indicates if \ref _reached is locally allocated (\c true) or not. + //Indicates if _reached is locally allocated (true) or not. bool local_reached; std::vector _list; int _list_front, _list_back; - /// \brief Creates the maps if necessary. - /// - /// Creates the maps if necessary. + ///Creates the maps if necessary. + ///\todo Better memory allocation (instead of new). void create_maps() { if(!_reached) { local_reached = true; @@ -1293,9 +1357,9 @@ } }; /// \brief \ref named-templ-param "Named parameter" for setting - /// ReachedMap type + /// ReachedMap type. /// - /// \ref named-templ-param "Named parameter" for setting ReachedMap type + /// \ref named-templ-param "Named parameter" for setting ReachedMap type. template struct DefReachedMap : public BfsVisit< Digraph, Visitor, DefReachedMapTraits > { @@ -1309,25 +1373,22 @@ /// /// Constructor. /// - /// \param digraph the digraph the algorithm will run on. - /// \param visitor The visitor of the algorithm. - /// + /// \param digraph The digraph the algorithm runs on. + /// \param visitor The visitor object of the algorithm. BfsVisit(const Digraph& digraph, Visitor& visitor) : _digraph(&digraph), _visitor(&visitor), _reached(0), local_reached(false) {} /// \brief Destructor. - /// - /// Destructor. ~BfsVisit() { if(local_reached) delete _reached; } - /// \brief Sets the map indicating if a node is reached. + /// \brief Sets the map that indicates which nodes are reached. /// - /// Sets the map indicating if a node is reached. + /// Sets the map that indicates which nodes are reached. /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this + /// it will allocate one. The destructor deallocates this /// automatically allocated map, of course. /// \return (*this) BfsVisit &reachedMap(ReachedMap &m) { @@ -1340,21 +1401,23 @@ } public: + /// \name Execution control /// The simplest way to execute the algorithm is to use - /// one of the member functions called \c run(...). + /// one of the member functions called \ref lemon::BfsVisit::run() + /// "run()". /// \n - /// If you need more control on the execution, - /// first you must call \ref init(), then you can adda source node - /// with \ref addSource(). - /// Finally \ref start() will perform the actual path - /// computation. + /// If you need more control on the execution, first you must call + /// \ref lemon::BfsVisit::init() "init()", then you can add several + /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". + /// Finally \ref lemon::BfsVisit::start() "start()" will perform the + /// actual path computation. /// @{ + /// \brief Initializes the internal data structures. /// /// Initializes the internal data structures. - /// void init() { create_maps(); _list.resize(countNodes(*_digraph)); @@ -1382,7 +1445,7 @@ /// /// \return The processed node. /// - /// \pre The queue must not be empty! + /// \pre The queue must not be empty. Node processNextNode() { Node n = _list[++_list_front]; _visitor->process(n); @@ -1403,16 +1466,17 @@ /// \brief Processes the next node. /// - /// Processes the next node. And checks that the given target node + /// Processes the next node and checks if the given target node /// is reached. If the target node is reachable from the processed - /// node then the reached parameter will be set true. The reached - /// parameter should be initially false. + /// node, then the \c reach parameter will be set to \c true. /// /// \param target The target node. - /// \retval reach Indicates that the target node is reached. + /// \retval reach Indicates if the target node is reached. + /// It should be initially \c false. + /// /// \return The processed node. /// - /// \warning The queue must not be empty! + /// \pre The queue must not be empty. Node processNextNode(Node target, bool& reach) { Node n = _list[++_list_front]; _visitor->process(n); @@ -1434,16 +1498,19 @@ /// \brief Processes the next node. /// - /// Processes the next node. And checks that at least one of - /// reached node has true value in the \c nm node map. If one node - /// with true value is reachable from the processed node then the - /// rnode parameter will be set to the first of such nodes. + /// Processes the next node and checks if at least one of reached + /// nodes has \c true value in the \c nm node map. If one node + /// with \c true value is reachable from the processed node, then the + /// \c rnode parameter will be set to the first of such nodes. /// - /// \param nm The node map of possible targets. + /// \param nm A \c bool (or convertible) node map that indicates the + /// possible targets. /// \retval rnode The reached target node. + /// It should be initially \c INVALID. + /// /// \return The processed node. /// - /// \warning The queue must not be empty! + /// \pre The queue must not be empty. template Node processNextNode(const NM& nm, Node& rnode) { Node n = _list[++_list_front]; @@ -1464,44 +1531,71 @@ return n; } - /// \brief Next node to be processed. + /// \brief The next node to be processed. /// - /// Next node to be processed. - /// - /// \return The next node to be processed or INVALID if the stack is - /// empty. - Node nextNode() { + /// Returns the next node to be processed or \c INVALID if the queue + /// is empty. + Node nextNode() const { return _list_front != _list_back ? _list[_list_front + 1] : INVALID; } /// \brief Returns \c false if there are nodes - /// to be processed in the queue + /// to be processed. /// /// Returns \c false if there are nodes - /// to be processed in the queue - bool emptyQueue() { return _list_front == _list_back; } + /// to be processed in the queue. + bool emptyQueue() const { return _list_front == _list_back; } /// \brief Returns the number of the nodes to be processed. /// /// Returns the number of the nodes to be processed in the queue. - int queueSize() { return _list_back - _list_front; } + int queueSize() const { return _list_back - _list_front; } /// \brief Executes the algorithm. /// /// Executes the algorithm. /// - /// \pre init() must be called and at least one node should be added + /// This method runs the %BFS algorithm from the root node(s) + /// in order to compute the shortest path to each node. + /// + /// The algorithm computes + /// - the shortest path tree (forest), + /// - the distance of each node from the root(s). + /// + /// \pre init() must be called and at least one root node should be added /// with addSource() before using this function. + /// + /// \note b.start() is just a shortcut of the following code. + /// \code + /// while ( !b.emptyQueue() ) { + /// b.processNextNode(); + /// } + /// \endcode void start() { while ( !emptyQueue() ) processNextNode(); } - /// \brief Executes the algorithm until \c dest is reached. + /// \brief Executes the algorithm until the given target node is reached. /// - /// Executes the algorithm until \c dest is reached. + /// Executes the algorithm until the given target node is reached. /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. + /// This method runs the %BFS algorithm from the root node(s) + /// in order to compute the shortest path to \c dest. + /// + /// The algorithm computes + /// - the shortest path to \c dest, + /// - the distance of \c dest from the root(s). + /// + /// \pre init() must be called and at least one root node should be + /// added with addSource() before using this function. + /// + /// \note b.start(t) is just a shortcut of the following code. + /// \code + /// bool reach = false; + /// while ( !b.emptyQueue() && !reach ) { + /// b.processNextNode(t, reach); + /// } + /// \endcode void start(Node dest) { bool reach = false; while ( !emptyQueue() && !reach ) processNextNode(dest, reach); @@ -1511,15 +1605,28 @@ /// /// Executes the algorithm until a condition is met. /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. + /// This method runs the %BFS algorithm from the root node(s) in + /// order to compute the shortest path to a node \c v with + /// nm[v] true, if such a node can be found. /// - ///\param nm must be a bool (or convertible) node map. The - ///algorithm will stop when it reaches a node \c v with + /// \param nm must be a bool (or convertible) node map. The + /// algorithm will stop when it reaches a node \c v with /// nm[v] true. /// - ///\return The reached node \c v with nm[v] true or - ///\c INVALID if no such node was found. + /// \return The reached node \c v with nm[v] true or + /// \c INVALID if no such node was found. + /// + /// \pre init() must be called and at least one root node should be + /// added with addSource() before using this function. + /// + /// \note b.start(nm) is just a shortcut of the following code. + /// \code + /// Node rnode = INVALID; + /// while ( !b.emptyQueue() && rnode == INVALID ) { + /// b.processNextNode(nm, rnode); + /// } + /// return rnode; + /// \endcode template Node start(const NM &nm) { Node rnode = INVALID; @@ -1529,10 +1636,16 @@ return rnode; } - /// \brief Runs %BFSVisit algorithm from node \c s. + /// \brief Runs the algorithm from the given node. /// - /// This method runs the %BFS algorithm from a root node \c s. - /// \note b.run(s) is just a shortcut of the following code. + /// This method runs the %BFS algorithm from node \c s + /// in order to compute the shortest path to each node. + /// + /// The algorithm computes + /// - the shortest path tree, + /// - the distance of each node from the root. + /// + /// \note b.run(s) is just a shortcut of the following code. ///\code /// b.init(); /// b.addSource(s); @@ -1544,19 +1657,21 @@ start(); } - /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph. + /// \brief Runs the algorithm to visit all nodes in the digraph. /// /// This method runs the %BFS algorithm in order to - /// compute the %BFS path to each node. The algorithm computes - /// - The %BFS tree. - /// - The distance of each node from the root in the %BFS tree. + /// compute the shortest path to each node. /// - ///\note b.run() is just a shortcut of the following code. + /// The algorithm computes + /// - the shortest path tree (forest), + /// - the distance of each node from the root(s). + /// + /// \note b.run(s) is just a shortcut of the following code. ///\code /// b.init(); - /// for (NodeIt it(digraph); it != INVALID; ++it) { - /// if (!b.reached(it)) { - /// b.addSource(it); + /// for (NodeIt n(gr); n != INVALID; ++n) { + /// if (!b.reached(n)) { + /// b.addSource(n); /// b.start(); /// } /// } @@ -1570,27 +1685,28 @@ } } } + ///@} /// \name Query Functions /// The result of the %BFS algorithm can be obtained using these /// functions.\n - /// Before the use of these functions, - /// either run() or start() must be called. + /// Either \ref lemon::BfsVisit::run() "run()" or + /// \ref lemon::BfsVisit::start() "start()" must be called before + /// using them. ///@{ - /// \brief Checks if a node is reachable from the root. + /// \brief Checks if a node is reachable from the root(s). /// /// Returns \c true if \c v is reachable from the root(s). - /// \warning The source nodes are inditated as unreachable. /// \pre Either \ref run() or \ref start() /// must be called before using this function. - /// bool reached(Node v) { return (*_reached)[v]; } + ///@} + }; } //END OF NAMESPACE LEMON #endif - diff --git a/lemon/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -21,20 +21,18 @@ ///\ingroup search ///\file -///\brief Dfs algorithm. +///\brief DFS algorithm. #include #include #include #include #include +#include #include -#include - namespace lemon { - ///Default traits class of Dfs class. ///Default traits class of Dfs class. @@ -42,74 +40,75 @@ template struct DfsDefaultTraits { - ///The digraph type the algorithm runs on. + ///The type of the digraph the algorithm runs on. typedef GR Digraph; - ///\brief The type of the map that stores the last + + ///\brief The type of the map that stores the predecessor ///arcs of the %DFS paths. /// - ///The type of the map that stores the last + ///The type of the map that stores the predecessor ///arcs of the %DFS paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef typename Digraph::template NodeMap PredMap; - ///Instantiates a PredMap. + typedef typename Digraph::template NodeMap PredMap; + ///Instantiates a \ref PredMap. ///This function instantiates a \ref PredMap. - ///\param G is the digraph, to which we would like to define the PredMap. + ///\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 GR &G) + static PredMap *createPredMap(const Digraph &g) { - return new PredMap(G); + return new PredMap(g); } ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. + ///By default it is a NullMap. typedef NullMap ProcessedMap; - ///Instantiates a ProcessedMap. + ///Instantiates a \ref ProcessedMap. ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which ///we would like to define the \ref ProcessedMap #ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const GR &g) + static ProcessedMap *createProcessedMap(const Digraph &g) #else - static ProcessedMap *createProcessedMap(const GR &) + static ProcessedMap *createProcessedMap(const Digraph &) #endif { return new ProcessedMap(); } + ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - ///Instantiates a ReachedMap. + ///Instantiates a \ref ReachedMap. ///This function instantiates a \ref ReachedMap. - ///\param G is the digraph, to which + ///\param g is the digraph, to which ///we would like to define the \ref ReachedMap. - static ReachedMap *createReachedMap(const GR &G) + static ReachedMap *createReachedMap(const Digraph &g) { - return new ReachedMap(G); + return new ReachedMap(g); } - ///The type of the map that stores the dists of the nodes. - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. + + ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// typedef typename Digraph::template NodeMap DistMap; - ///Instantiates a DistMap. + ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. - ///\param G is the digraph, to which we would like to define - ///the \ref DistMap - static DistMap *createDistMap(const GR &G) + ///\param g is the digraph, to which we would like to define the + ///\ref DistMap. + static DistMap *createDistMap(const Digraph &g) { - return new DistMap(G); + return new DistMap(g); } }; @@ -118,9 +117,13 @@ ///\ingroup search ///This class provides an efficient implementation of the %DFS algorithm. /// - ///\tparam GR The digraph type the algorithm runs on. The default value is - ///\ref ListDigraph. The value of GR is not used directly by Dfs, it - ///is only passed to \ref DfsDefaultTraits. + ///There is also a \ref dfs() "function type interface" for the DFS + ///algorithm, which is convenient in the simplier cases and it can be + ///used easier. + /// + ///\tparam GR The type of the digraph the algorithm runs on. + ///The default value is \ref ListDigraph. The value of GR is not used + ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. ///\tparam TR Traits class to set various data types used by the algorithm. ///The default traits class is ///\ref DfsDefaultTraits "DfsDefaultTraits". @@ -135,12 +138,10 @@ #endif class Dfs { public: - /** - * \brief \ref Exception for uninitialized parameters. - * - * This error represents problems in the initialization - * of the parameters of the algorithms. - */ + ///\ref Exception for uninitialized parameters. + + ///This error represents problems in the initialization of the + ///parameters of the algorithm. class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() { @@ -148,52 +149,54 @@ } }; + ///The type of the digraph the algorithm runs on. + typedef typename TR::Digraph Digraph; + + ///\brief The type of the map that stores the predecessor arcs of the + ///DFS paths. + typedef typename TR::PredMap PredMap; + ///The type of the map that stores the distances of the nodes. + typedef typename TR::DistMap DistMap; + ///The type of the map that indicates which nodes are reached. + typedef typename TR::ReachedMap ReachedMap; + ///The type of the map that indicates which nodes are processed. + typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the paths. + typedef PredMapPath Path; + + ///The traits class. typedef TR Traits; - ///The type of the underlying digraph. - typedef typename TR::Digraph Digraph; - ///\e + + private: + typedef typename Digraph::Node Node; - ///\e typedef typename Digraph::NodeIt NodeIt; - ///\e typedef typename Digraph::Arc Arc; - ///\e typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the last - ///arcs of the %DFS paths. - typedef typename TR::PredMap PredMap; - ///The type of the map indicating which nodes are reached. - typedef typename TR::ReachedMap ReachedMap; - ///The type of the map indicating which nodes are processed. - typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the map that stores the dists of the nodes. - typedef typename TR::DistMap DistMap; - private: - /// Pointer to the underlying digraph. + //Pointer to the underlying digraph. const Digraph *G; - ///Pointer to the map of predecessors arcs. + //Pointer to the map of predecessor arcs. PredMap *_pred; - ///Indicates if \ref _pred is locally allocated (\c true) or not. + //Indicates if _pred is locally allocated (true) or not. bool local_pred; - ///Pointer to the map of distances. + //Pointer to the map of distances. DistMap *_dist; - ///Indicates if \ref _dist is locally allocated (\c true) or not. + //Indicates if _dist is locally allocated (true) or not. bool local_dist; - ///Pointer to the map of reached status of the nodes. + //Pointer to the map of reached status of the nodes. ReachedMap *_reached; - ///Indicates if \ref _reached is locally allocated (\c true) or not. + //Indicates if _reached is locally allocated (true) or not. bool local_reached; - ///Pointer to the map of processed status of the nodes. + //Pointer to the map of processed status of the nodes. ProcessedMap *_processed; - ///Indicates if \ref _processed is locally allocated (\c true) or not. + //Indicates if _processed is locally allocated (true) or not. bool local_processed; std::vector _stack; int _stack_head; ///Creates the maps if necessary. - ///\todo Better memory allocation (instead of new). void create_maps() { @@ -230,22 +233,21 @@ template struct DefPredMapTraits : public Traits { typedef T PredMap; - static PredMap *createPredMap(const Digraph &G) + static PredMap *createPredMap(const Digraph &) { throw UninitializedParameter(); } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///PredMap type + ///\ref PredMap type. /// - ///\ref named-templ-param "Named parameter" for setting PredMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref PredMap type. template struct DefPredMap : public Dfs > { typedef Dfs > Create; }; - template struct DefDistMapTraits : public Traits { typedef T DistMap; @@ -255,12 +257,12 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///DistMap type + ///\ref DistMap type. /// - ///\ref named-templ-param "Named parameter" for setting DistMap - ///type + ///\ref named-templ-param "Named parameter" for setting + ///\ref DistMap type. template - struct DefDistMap { + struct DefDistMap : public Dfs< Digraph, DefDistMapTraits > { typedef Dfs > Create; }; @@ -273,10 +275,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ReachedMap type + ///\ref ReachedMap type. /// - ///\ref named-templ-param "Named parameter" for setting ReachedMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref ReachedMap type. template struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits > { typedef Dfs< Digraph, DefReachedMapTraits > Create; @@ -291,10 +293,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ProcessedMap type + ///\ref ProcessedMap type. /// - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type - /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type. template struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits > { typedef Dfs< Digraph, DefProcessedMapTraits > Create; @@ -302,19 +304,19 @@ struct DefDigraphProcessedMapTraits : public Traits { typedef typename Digraph::template NodeMap ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &G) + static ProcessedMap *createProcessedMap(const Digraph &g) { - return new ProcessedMap(G); + return new ProcessedMap(g); } }; - ///\brief \ref named-templ-param "Named parameter" - ///for setting the ProcessedMap type to be Digraph::NodeMap. + ///\brief \ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type to be Digraph::NodeMap. /// - ///\ref named-templ-param "Named parameter" - ///for setting the ProcessedMap type to be Digraph::NodeMap. - ///If you don't set it explicitely, it will be automatically allocated. + ///\ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type to be Digraph::NodeMap. + ///If you don't set it explicitly, it will be automatically allocated. template - class DefProcessedMapToBeDefaultMap : + struct DefProcessedMapToBeDefaultMap : public Dfs< Digraph, DefDigraphProcessedMapTraits> { typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; }; @@ -325,10 +327,10 @@ ///Constructor. - ///\param _G the digraph the algorithm will run on. - /// - Dfs(const Digraph& _G) : - G(&_G), + ///Constructor. + ///\param g The digraph the algorithm runs on. + Dfs(const Digraph &g) : + G(&g), _pred(NULL), local_pred(false), _dist(NULL), local_dist(false), _reached(NULL), local_reached(false), @@ -344,11 +346,11 @@ if(local_processed) delete _processed; } - ///Sets the map storing the predecessor arcs. + ///Sets the map that stores the predecessor arcs. - ///Sets the map storing the predecessor arcs. + ///Sets the map that stores the predecessor arcs. ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this + ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) Dfs &predMap(PredMap &m) @@ -361,11 +363,46 @@ return *this; } - ///Sets the map storing the distances calculated by the algorithm. + ///Sets the map that indicates which nodes are reached. - ///Sets the map storing the distances calculated by the algorithm. + ///Sets the map that indicates which nodes are reached. ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this + ///it will allocate one. The destructor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dfs &reachedMap(ReachedMap &m) + { + if(local_reached) { + delete _reached; + local_reached=false; + } + _reached = &m; + return *this; + } + + ///Sets the map that indicates which nodes are processed. + + ///Sets the map that indicates which nodes are processed. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destructor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dfs &processedMap(ProcessedMap &m) + { + if(local_processed) { + delete _processed; + local_processed=false; + } + _processed = &m; + return *this; + } + + ///Sets the map that stores the distances of the nodes. + + ///Sets the map that stores the distances of the nodes calculated by + ///the algorithm. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) Dfs &distMap(DistMap &m) @@ -378,50 +415,17 @@ return *this; } - ///Sets the map indicating if a node is reached. + public: - ///Sets the map indicating if a node is reached. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dfs &reachedMap(ReachedMap &m) - { - if(local_reached) { - delete _reached; - local_reached=false; - } - _reached = &m; - return *this; - } - - ///Sets the map indicating if a node is processed. - - ///Sets the map indicating if a node is processed. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dfs &processedMap(ProcessedMap &m) - { - if(local_processed) { - delete _processed; - local_processed=false; - } - _processed = &m; - return *this; - } - - public: ///\name Execution control ///The simplest way to execute the algorithm is to use - ///one of the member functions called \c run(...). + ///one of the member functions called \ref lemon::Dfs::run() "run()". ///\n - ///If you need more control on the execution, - ///first you must call \ref init(), then you can add a source node - ///with \ref addSource(). - ///Finally \ref start() will perform the actual path - ///computation. + ///If you need more control on the execution, first you must call + ///\ref lemon::Dfs::init() "init()", then you can add a source node + ///with \ref lemon::Dfs::addSource() "addSource()". + ///Finally \ref lemon::Dfs::start() "start()" will perform the + ///actual path computation. ///@{ @@ -436,7 +440,6 @@ _stack_head=-1; for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); - // _predNode->set(u,INVALID); _reached->set(u,false); _processed->set(u,false); } @@ -446,10 +449,14 @@ ///Adds a new source node to the set of nodes to be processed. /// - ///\warning dists are wrong (or at least strange) - ///in case of multiple sources. + ///\pre The stack must be empty. (Otherwise the algorithm gives + ///false results.) + /// + ///\warning Distances will be wrong (or at least strange) in case of + ///multiple sources. void addSource(Node s) { + LEMON_DEBUG(emptyQueue(), "The stack is not empty."); if(!(*_reached)[s]) { _reached->set(s,true); @@ -472,7 +479,7 @@ /// ///\return The processed arc. /// - ///\pre The stack must not be empty! + ///\pre The stack must not be empty. Arc processNextArc() { Node m; @@ -498,61 +505,68 @@ } return e; } + ///Next arc to be processed. ///Next arc to be processed. /// - ///\return The next arc to be processed or INVALID if the stack is - /// empty. - OutArcIt nextArc() + ///\return The next arc to be processed or \c INVALID if the stack + ///is empty. + OutArcIt nextArc() const { return _stack_head>=0?_stack[_stack_head]:INVALID; } ///\brief Returns \c false if there are nodes - ///to be processed in the queue + ///to be processed. /// ///Returns \c false if there are nodes - ///to be processed in the queue - bool emptyQueue() { return _stack_head<0; } + ///to be processed in the queue (stack). + bool emptyQueue() const { return _stack_head<0; } + ///Returns the number of the nodes to be processed. - ///Returns the number of the nodes to be processed in the queue. - int queueSize() { return _stack_head+1; } + ///Returns the number of the nodes to be processed in the queue (stack). + int queueSize() const { return _stack_head+1; } ///Executes the algorithm. ///Executes the algorithm. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %DFS algorithm from the root node + ///in order to compute the DFS path to each node. /// - ///This method runs the %DFS algorithm from the root node(s) - ///in order to - ///compute the - ///%DFS path to each node. The algorithm computes - ///- The %DFS tree. - ///- The distance of each node from the root(s) in the %DFS tree. + /// The algorithm computes + ///- the %DFS tree, + ///- the distance of each node 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. + /// + ///\note d.start() is just a shortcut of the following code. + ///\code + /// while ( !d.emptyQueue() ) { + /// d.processNextArc(); + /// } + ///\endcode void start() { while ( !emptyQueue() ) processNextArc(); } - ///Executes the algorithm until \c dest is reached. + ///Executes the algorithm until the given target node is reached. - ///Executes the algorithm until \c dest is reached. + ///Executes the algorithm until the given target node is reached. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %DFS algorithm from the root node + ///in order to compute the DFS path to \c dest. /// - ///This method runs the %DFS algorithm from the root node(s) - ///in order to - ///compute the - ///%DFS path to \c dest. The algorithm computes - ///- The %DFS path to \c dest. - ///- The distance of \c dest from the root(s) in the %DFS tree. + ///The algorithm computes + ///- the %DFS path to \c dest, + ///- the distance of \c dest 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 ) @@ -563,39 +577,86 @@ ///Executes the algorithm until a condition is met. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %DFS algorithm from the root node + ///until an arc \c a with am[a] true is found. /// - ///\param em must be a bool (or convertible) arc map. The algorithm - ///will stop when it reaches an arc \c e with em[e] true. + ///\param am A \c bool (or convertible) arc map. The algorithm + ///will stop when it reaches an arc \c a with am[a] true. /// - ///\return The reached arc \c e with em[e] true or + ///\return The reached arc \c a with am[a] true or ///\c INVALID if no such arc was found. /// - ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, + ///\pre init() must be called and a root node should be + ///added with addSource() before using this function. + /// + ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, ///not a node map. - template - Arc start(const EM &em) + template + Arc start(const ArcBoolMap &am) { - while ( !emptyQueue() && !em[_stack[_stack_head]] ) + while ( !emptyQueue() && !am[_stack[_stack_head]] ) processNextArc(); return emptyQueue() ? INVALID : _stack[_stack_head]; } - ///Runs %DFS algorithm to visit all nodes in the digraph. + ///Runs the algorithm from the given node. - ///This method runs the %DFS algorithm in order to - ///compute the - ///%DFS path to each node. The algorithm computes - ///- The %DFS tree. - ///- The distance of each node from the root in the %DFS tree. + ///This method runs the %DFS algorithm from node \c s + ///in order to compute the DFS path to each node. /// - ///\note d.run() is just a shortcut of the following code. + ///The algorithm computes + ///- the %DFS tree, + ///- the distance of each node from the root in the %DFS tree. + /// + ///\note d.run(s) is just a shortcut of the following code. ///\code /// d.init(); - /// for (NodeIt it(digraph); it != INVALID; ++it) { - /// if (!d.reached(it)) { - /// d.addSource(it); + /// d.addSource(s); + /// d.start(); + ///\endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + ///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. + /// + ///\return The length of the s--t DFS path, + ///if \c t is reachable form \c s, \c 0 otherwise. + /// + ///\note Apart from the return value, d.run(s,t) is + ///just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(t); + ///\endcode + int run(Node s,Node t) { + init(); + addSource(s); + start(t); + return reached(t)?_stack_head+1:0; + } + + ///Runs the algorithm to visit all nodes in the digraph. + + ///This method runs the %DFS algorithm in order to compute the + ///%DFS path to each node. + /// + ///The algorithm computes + ///- the %DFS tree, + ///- the distance of each node from the root in the %DFS tree. + /// + ///\note d.run() is just a shortcut of the following code. + ///\code + /// d.init(); + /// for (NodeIt n(digraph); n != INVALID; ++n) { + /// if (!d.reached(n)) { + /// d.addSource(n); /// d.start(); /// } /// } @@ -610,157 +671,124 @@ } } - ///Runs %DFS algorithm from node \c s. - - ///This method runs the %DFS algorithm from a root node \c s - ///in order to - ///compute the - ///%DFS path to each node. The algorithm computes - ///- The %DFS tree. - ///- The distance of each node from the root in the %DFS tree. - /// - ///\note d.run(s) is just a shortcut of the following code. - ///\code - /// d.init(); - /// d.addSource(s); - /// d.start(); - ///\endcode - void run(Node s) { - init(); - addSource(s); - start(); - } - - ///Finds the %DFS path between \c s and \c t. - - ///Finds the %DFS path between \c s and \c t. - /// - ///\return The length of the %DFS s---t path if there exists one, - ///0 otherwise. - ///\note Apart from the return value, d.run(s,t) is - ///just a shortcut of the following code. - ///\code - /// d.init(); - /// d.addSource(s); - /// d.start(t); - ///\endcode - int run(Node s,Node t) { - init(); - addSource(s); - start(t); - return reached(t)?_stack_head+1:0; - } - ///@} ///\name Query Functions ///The result of the %DFS algorithm can be obtained using these ///functions.\n - ///Before the use of these functions, - ///either run() or start() must be called. + ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start() + ///"start()" must be called before using them. ///@{ - typedef PredMapPath Path; + ///The DFS path to a node. - ///Gives back the shortest path. + ///Returns the DFS path to a node. + /// + ///\warning \c t should be reachable from the root. + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. + Path path(Node t) const { return Path(*G, *_pred, t); } - ///Gives back the shortest path. - ///\pre The \c t should be reachable from the source. - Path path(Node t) - { - return Path(*G, *_pred, t); - } + ///The distance of a node from the root. - ///The distance of a node from the root(s). - - ///Returns the distance of a node from the root(s). - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v is unreachable from the root(s) then the return - ///value of this funcion is undefined. + ///Returns the distance of a node from the root. + /// + ///\warning If node \c v is not reachable from the root, then + ///the return value of this function is undefined. + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the %DFS tree. + ///Returns the 'previous arc' of the %DFS tree for a node. - ///For a node \c v it returns the 'previous arc' - ///of the %DFS path, - ///i.e. it returns the last arc of a %DFS path from the root(s) to \c - ///v. It is \ref INVALID - ///if \c v is unreachable from the root(s) or \c v is a root. The - ///%DFS tree used here is equal to the %DFS tree used in + ///This function returns the 'previous arc' of the %DFS tree for the + ///node \c v, i.e. it returns the last arc of a %DFS path from the + ///root to \c v. It is \c INVALID + ///if \c v is not reachable from the root(s) or if \c v is a root. + /// + ///The %DFS tree used here is equal to the %DFS tree used in ///\ref predNode(). + /// ///\pre Either \ref run() or \ref start() must be called before using ///this function. Arc predArc(Node v) const { return (*_pred)[v];} ///Returns the 'previous node' of the %DFS tree. - ///For a node \c v it returns the 'previous node' - ///of the %DFS tree, - ///i.e. it returns the last but one node from a %DFS path from the - ///root(s) to \c v. - ///It is INVALID if \c v is unreachable from the root(s) or - ///if \c v itself a root. - ///The %DFS tree used here is equal to the %DFS - ///tree used in \ref predArc(). + ///This function returns the 'previous node' of the %DFS + ///tree for the node \c v, i.e. it returns the last but one node + ///from a %DFS path from the root to \c v. It is \c INVALID + ///if \c v is not reachable from the root(s) or if \c v is a root. + /// + ///The %DFS tree used here is equal to the %DFS tree used in + ///\ref predArc(). + /// ///\pre Either \ref run() or \ref start() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } - ///Returns a reference to the NodeMap of distances. - - ///Returns a reference to the NodeMap of distances. - ///\pre Either \ref run() or \ref init() must - ///be called before using this function. + ///\brief Returns a const reference to the node map that stores the + ///distances of the nodes. + /// + ///Returns a const reference to the node map that stores the + ///distances of the nodes calculated by the algorithm. + /// + ///\pre Either \ref run() or \ref init() + ///must be called before using this function. const DistMap &distMap() const { return *_dist;} - ///Returns a reference to the %DFS arc-tree map. - - ///Returns a reference to the NodeMap of the arcs of the - ///%DFS tree. + ///\brief Returns a const reference to the node map that stores the + ///predecessor arcs. + /// + ///Returns a const reference to the node map that stores the predecessor + ///arcs, which form the DFS tree. + /// ///\pre Either \ref run() or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reachable from the root. + ///Checks if a node is reachable from the root(s). ///Returns \c true if \c v is reachable from the root(s). - ///\warning The source nodes are inditated as unreachable. ///\pre Either \ref run() or \ref start() ///must be called before using this function. - /// - bool reached(Node v) { return (*_reached)[v]; } + bool reached(Node v) const { return (*_reached)[v]; } ///@} }; - ///Default traits class of Dfs function. + ///Default traits class of dfs() function. - ///Default traits class of Dfs function. + ///Default traits class of dfs() function. ///\tparam GR Digraph type. template struct DfsWizardDefaultTraits { - ///The digraph type the algorithm runs on. + ///The type of the digraph the algorithm runs on. typedef GR Digraph; - ///\brief The type of the map that stores the last + + ///\brief The type of the map that stores the predecessor ///arcs of the %DFS paths. /// - ///The type of the map that stores the last + ///The type of the map that stores the predecessor ///arcs of the %DFS paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// - typedef NullMap PredMap; - ///Instantiates a PredMap. + typedef NullMap PredMap; + ///Instantiates a \ref PredMap. ///This function instantiates a \ref PredMap. - ///\param g is the digraph, to which we would like to define the PredMap. + ///\param g is the digraph, to which we would like to define the + ///\ref PredMap. ///\todo The digraph alone may be insufficient to initialize #ifdef DOXYGEN - static PredMap *createPredMap(const GR &g) + static PredMap *createPredMap(const Digraph &g) #else - static PredMap *createPredMap(const GR &) + static PredMap *createPredMap(const Digraph &) #endif { return new PredMap(); @@ -770,63 +798,63 @@ ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. typedef NullMap ProcessedMap; - ///Instantiates a ProcessedMap. + ///Instantiates a \ref ProcessedMap. ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which - ///we would like to define the \ref ProcessedMap + ///we would like to define the \ref ProcessedMap. #ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const GR &g) + static ProcessedMap *createProcessedMap(const Digraph &g) #else - static ProcessedMap *createProcessedMap(const GR &) + static ProcessedMap *createProcessedMap(const Digraph &) #endif { return new ProcessedMap(); } + ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - ///\todo named parameter to set this type, function to read and write. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - ///Instantiates a ReachedMap. + ///Instantiates a \ref ReachedMap. ///This function instantiates a \ref ReachedMap. - ///\param G is the digraph, to which + ///\param g is the digraph, to which ///we would like to define the \ref ReachedMap. - static ReachedMap *createReachedMap(const GR &G) + static ReachedMap *createReachedMap(const Digraph &g) { - return new ReachedMap(G); + return new ReachedMap(g); } - ///The type of the map that stores the dists of the nodes. - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. + + ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// typedef NullMap DistMap; - ///Instantiates a DistMap. + ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define ///the \ref DistMap #ifdef DOXYGEN - static DistMap *createDistMap(const GR &g) + static DistMap *createDistMap(const Digraph &g) #else - static DistMap *createDistMap(const GR &) + static DistMap *createDistMap(const Digraph &) #endif { return new DistMap(); } }; - /// Default traits used by \ref DfsWizard + /// Default traits class used by \ref DfsWizard /// To make it easier to use Dfs algorithm - ///we have created a wizard class. + /// we have created a wizard class. /// This \ref DfsWizard class needs default traits, - ///as well as the \ref Dfs class. + /// as well as the \ref Dfs class. /// The \ref DfsWizardBase is a class to be the default traits of the /// \ref DfsWizard class. template @@ -835,20 +863,20 @@ typedef DfsWizardDefaultTraits Base; protected: - /// Type of the nodes in the digraph. + //The type of the nodes in the digraph. typedef typename Base::Digraph::Node Node; - /// Pointer to the underlying digraph. + //Pointer to the digraph the algorithm runs on. void *_g; - ///Pointer to the map of reached nodes. + //Pointer to the map of reached nodes. void *_reached; - ///Pointer to the map of processed nodes. + //Pointer to the map of processed nodes. void *_processed; - ///Pointer to the map of predecessors arcs. + //Pointer to the map of predecessors arcs. void *_pred; - ///Pointer to the map of distances. + //Pointer to the map of distances. void *_dist; - ///Pointer to the source node. + //Pointer to the source node. Node _source; public: @@ -857,26 +885,28 @@ /// This constructor does not require parameters, therefore it initiates /// all of the attributes to default values (0, INVALID). DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), - _dist(0), _source(INVALID) {} + _dist(0), _source(INVALID) {} /// Constructor. /// This constructor requires some parameters, /// listed in the parameters list. /// Others are initiated to 0. - /// \param g is the initial value of \ref _g - /// \param s is the initial value of \ref _source + /// \param g The digraph the algorithm runs on. + /// \param s The source node. DfsWizardBase(const GR &g, Node s=INVALID) : _g(reinterpret_cast(const_cast(&g))), _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} }; - /// A class to make the usage of the Dfs algorithm easier + /// Auxiliary class for the function type interface of DFS algorithm. - /// This class is created to make it easier to use the Dfs algorithm. - /// It uses the functions and features of the plain \ref Dfs, - /// but it is much simpler to use it. + /// This auxiliary class is created to implement the function type + /// interface of \ref Dfs algorithm. It uses the functions and features + /// of the plain \ref Dfs, but it is much simpler to use it. + /// It should only be used through the \ref dfs() function, which makes + /// it easier to use the algorithm. /// /// Simplicity means that the way to change the types defined /// in the traits class is based on functions that returns the new class @@ -885,41 +915,37 @@ /// the new class with the modified type comes from /// the original class by using the :: /// operator. In the case of \ref DfsWizard only - /// a function have to be called and it will + /// a function have to be called, and it will /// return the needed class. /// - /// It does not have own \ref run method. When its \ref run method is called - /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run - /// method of it. + /// It does not have own \ref run() method. When its \ref run() method + /// is called, it initiates a plain \ref Dfs object, and calls the + /// \ref Dfs::run() method of it. template class DfsWizard : public TR { typedef TR Base; - ///The type of the underlying digraph. + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - //\e + typedef typename Digraph::Node Node; - //\e typedef typename Digraph::NodeIt NodeIt; - //\e typedef typename Digraph::Arc Arc; - //\e typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores - ///the reached nodes + ///\brief The type of the map that stores the predecessor + ///arcs of the shortest paths. + typedef typename TR::PredMap PredMap; + ///\brief The type of the map that stores the distances of the nodes. + typedef typename TR::DistMap DistMap; + ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that stores - ///the processed nodes + ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///\brief The type of the map that stores the last - ///arcs of the %DFS paths. - typedef typename TR::PredMap PredMap; - ///The type of the map that stores the distances of the nodes. - typedef typename TR::DistMap DistMap; public: + /// Constructor. DfsWizard() : TR() {} @@ -935,10 +961,10 @@ ~DfsWizard() {} - ///Runs Dfs algorithm from a given node. + ///Runs DFS algorithm from a source node. - ///Runs Dfs algorithm from a given node. - ///The node can be given by the \ref source function. + ///Runs DFS algorithm from a source node. + ///The node can be given with the \ref source() function. void run() { if(Base::_source==INVALID) throw UninitializedParameter(); @@ -954,9 +980,9 @@ alg.run(Base::_source); } - ///Runs Dfs algorithm from the given node. + ///Runs DFS algorithm from the given node. - ///Runs Dfs algorithm from the given node. + ///Runs DFS algorithm from the given node. ///\param s is the given source. void run(Node s) { @@ -964,19 +990,27 @@ run(); } + /// Sets the source node, from which the Dfs algorithm runs. + + /// Sets the source node, from which the Dfs algorithm runs. + /// \param s is the source node. + DfsWizard &source(Node s) + { + Base::_source=s; + return *this; + } + template struct DefPredMapBase : public Base { typedef T PredMap; static PredMap *createPredMap(const Digraph &) { return 0; }; DefPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting PredMap type + ///for setting \ref PredMap object. /// - /// \ref named-templ-param "Named parameter" - ///function for setting PredMap type - /// + ///\ref named-templ-param "Named parameter" + ///for setting \ref PredMap object. template DfsWizard > predMap(const T &t) { @@ -984,20 +1018,17 @@ return DfsWizard >(*this); } - template struct DefReachedMapBase : public Base { typedef T ReachedMap; static ReachedMap *createReachedMap(const Digraph &) { return 0; }; DefReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting ReachedMap + ///for setting \ref ReachedMap object. /// /// \ref named-templ-param "Named parameter" - ///function for setting ReachedMap - /// + ///for setting \ref ReachedMap object. template DfsWizard > reachedMap(const T &t) { @@ -1005,20 +1036,17 @@ return DfsWizard >(*this); } - template struct DefProcessedMapBase : public Base { typedef T ProcessedMap; static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; DefProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting ProcessedMap + ///for setting \ref ProcessedMap object. /// /// \ref named-templ-param "Named parameter" - ///function for setting ProcessedMap - /// + ///for setting \ref ProcessedMap object. template DfsWizard > processedMap(const T &t) { @@ -1032,13 +1060,11 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; DefDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting DistMap type + ///for setting \ref DistMap object. /// - /// \ref named-templ-param "Named parameter" - ///function for setting DistMap type - /// + ///\ref named-templ-param "Named parameter" + ///for setting \ref DistMap object. template DfsWizard > distMap(const T &t) { @@ -1046,16 +1072,6 @@ return DfsWizard >(*this); } - /// Sets the source node, from which the Dfs algorithm runs. - - /// Sets the source node, from which the Dfs algorithm runs. - /// \param s is the source node. - DfsWizard &source(Node s) - { - Base::_source=s; - return *this; - } - }; ///Function type interface for Dfs algorithm. @@ -1083,47 +1099,46 @@ } #ifdef DOXYGEN - /// \brief Visitor class for dfs. + /// \brief Visitor class for DFS. /// - /// It gives a simple interface for a functional interface for dfs - /// traversal. The traversal on a linear data structure. + /// This class defines the interface of the DfsVisit events, and + /// it could be the base of a real visitor class. template struct DfsVisitor { typedef _Digraph Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; - /// \brief Called when the arc reach a node. + /// \brief Called for the source node of the DFS. /// - /// It is called when the dfs find an arc which target is not - /// reached yet. + /// This function is called for the source node of the DFS. + void start(const Node& node) {} + /// \brief Called when the source node is leaved. + /// + /// This function is called when the source node is leaved. + void stop(const Node& node) {} + /// \brief Called when a node is reached first time. + /// + /// This function is called when a node is reached first time. + void reach(const Node& node) {} + /// \brief Called when an arc reaches a new node. + /// + /// This function is called when the DFS finds an arc whose target node + /// is not reached yet. void discover(const Arc& arc) {} - /// \brief Called when the node reached first time. - /// - /// It is Called when the node reached first time. - void reach(const Node& node) {} - /// \brief Called when we step back on an arc. - /// - /// It is called when the dfs should step back on the arc. - void backtrack(const Arc& arc) {} - /// \brief Called when we step back from the node. - /// - /// It is called when we step back from the node. - void leave(const Node& node) {} - /// \brief Called when the arc examined but target of the arc + /// \brief Called when an arc is examined but its target node is /// already discovered. /// - /// It called when the arc examined but the target of the arc + /// This function is called when an arc is examined but its target node is /// already discovered. void examine(const Arc& arc) {} - /// \brief Called for the source node of the dfs. + /// \brief Called when the DFS steps back from a node. /// - /// It is called for the source node of the dfs. - void start(const Node& node) {} - /// \brief Called when we leave the source node of the dfs. + /// This function is called when the DFS steps back from a node. + void leave(const Node& node) {} + /// \brief Called when the DFS steps back on an arc. /// - /// It is called when we leave the source node of the dfs. - void stop(const Node& node) {} - + /// This function is called when the DFS steps back on an arc. + void backtrack(const Arc& arc) {} }; #else template @@ -1131,26 +1146,26 @@ typedef _Digraph Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; - void discover(const Arc&) {} - void reach(const Node&) {} - void backtrack(const Arc&) {} - void leave(const Node&) {} - void examine(const Arc&) {} void start(const Node&) {} void stop(const Node&) {} + void reach(const Node&) {} + void discover(const Arc&) {} + void examine(const Arc&) {} + void leave(const Node&) {} + void backtrack(const Arc&) {} template struct Constraints { void constraints() { Arc arc; Node node; - visitor.discover(arc); - visitor.reach(node); - visitor.backtrack(arc); - visitor.leave(node); - visitor.examine(arc); visitor.start(node); visitor.stop(arc); + visitor.reach(node); + visitor.discover(arc); + visitor.examine(arc); + visitor.leave(node); + visitor.backtrack(arc); } _Visitor& visitor; }; @@ -1160,21 +1175,20 @@ /// \brief Default traits class of DfsVisit class. /// /// Default traits class of DfsVisit class. - /// \tparam _Digraph Digraph type. + /// \tparam _Digraph The type of the digraph the algorithm runs on. template struct DfsVisitDefaultTraits { - /// \brief The digraph type the algorithm runs on. + /// \brief The type of the digraph the algorithm runs on. typedef _Digraph Digraph; /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// \todo named parameter to set this type, function to read and write. + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - /// \brief Instantiates a ReachedMap. + /// \brief Instantiates a \ref ReachedMap. /// /// This function instantiates a \ref ReachedMap. /// \param digraph is the digraph, to which @@ -1185,31 +1199,30 @@ }; - /// %DFS Visit algorithm class. - /// \ingroup search + /// + /// \brief %DFS algorithm class with visitor interface. + /// /// This class provides an efficient implementation of the %DFS algorithm /// with visitor interface. /// /// The %DfsVisit class provides an alternative interface to the Dfs /// class. It works with callback mechanism, the DfsVisit object calls - /// on every dfs event the \c Visitor class member functions. + /// the member functions of the \c Visitor class on every DFS event. /// - /// \tparam _Digraph The digraph type the algorithm runs on. + /// \tparam _Digraph The type of the digraph the algorithm runs on. /// The default value is - /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it - /// is only passed to \ref DfsDefaultTraits. - /// \tparam _Visitor The Visitor object for the algorithm. The - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which - /// does not observe the Dfs events. If you want to observe the dfs - /// events you should implement your own Visitor class. + /// \ref ListDigraph. The value of _Digraph is not used directly by + /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits. + /// \tparam _Visitor The Visitor type that is used by the algorithm. + /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which + /// does not observe the DFS events. If you want to observe the DFS + /// events, you should implement your own visitor class. /// \tparam _Traits Traits class to set various data types used by the /// algorithm. The default traits class is /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". /// See \ref DfsVisitDefaultTraits for the documentation of - /// a Dfs visit traits class. - /// - /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso + /// a DFS visit traits class. #ifdef DOXYGEN template #else @@ -1223,7 +1236,7 @@ /// \brief \ref Exception for uninitialized parameters. /// /// This error represents problems in the initialization - /// of the parameters of the algorithms. + /// of the parameters of the algorithm. class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() @@ -1232,13 +1245,16 @@ } }; + ///The traits class. typedef _Traits Traits; + ///The type of the digraph the algorithm runs on. typedef typename Traits::Digraph Digraph; + ///The visitor type used by the algorithm. typedef _Visitor Visitor; - ///The type of the map indicating which nodes are reached. + ///The type of the map that indicates which nodes are reached. typedef typename Traits::ReachedMap ReachedMap; private: @@ -1248,21 +1264,20 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - /// Pointer to the underlying digraph. + //Pointer to the underlying digraph. const Digraph *_digraph; - /// Pointer to the visitor object. + //Pointer to the visitor object. Visitor *_visitor; - ///Pointer to the map of reached status of the nodes. + //Pointer to the map of reached status of the nodes. ReachedMap *_reached; - ///Indicates if \ref _reached is locally allocated (\c true) or not. + //Indicates if _reached is locally allocated (true) or not. bool local_reached; std::vector _stack; int _stack_head; - /// \brief Creates the maps if necessary. - /// - /// Creates the maps if necessary. + ///Creates the maps if necessary. + ///\todo Better memory allocation (instead of new). void create_maps() { if(!_reached) { local_reached = true; @@ -1289,9 +1304,9 @@ } }; /// \brief \ref named-templ-param "Named parameter" for setting - /// ReachedMap type + /// ReachedMap type. /// - /// \ref named-templ-param "Named parameter" for setting ReachedMap type + /// \ref named-templ-param "Named parameter" for setting ReachedMap type. template struct DefReachedMap : public DfsVisit< Digraph, Visitor, DefReachedMapTraits > { @@ -1305,25 +1320,22 @@ /// /// Constructor. /// - /// \param digraph the digraph the algorithm will run on. - /// \param visitor The visitor of the algorithm. - /// + /// \param digraph The digraph the algorithm runs on. + /// \param visitor The visitor object of the algorithm. DfsVisit(const Digraph& digraph, Visitor& visitor) : _digraph(&digraph), _visitor(&visitor), _reached(0), local_reached(false) {} /// \brief Destructor. - /// - /// Destructor. ~DfsVisit() { if(local_reached) delete _reached; } - /// \brief Sets the map indicating if a node is reached. + /// \brief Sets the map that indicates which nodes are reached. /// - /// Sets the map indicating if a node is reached. + /// Sets the map that indicates which nodes are reached. /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this + /// it will allocate one. The destructor deallocates this /// automatically allocated map, of course. /// \return (*this) DfsVisit &reachedMap(ReachedMap &m) { @@ -1336,21 +1348,23 @@ } public: + /// \name Execution control /// The simplest way to execute the algorithm is to use - /// one of the member functions called \c run(...). + /// one of the member functions called \ref lemon::DfsVisit::run() + /// "run()". /// \n - /// If you need more control on the execution, - /// first you must call \ref init(), then you can adda source node - /// with \ref addSource(). - /// Finally \ref start() will perform the actual path - /// computation. + /// If you need more control on the execution, first you must call + /// \ref lemon::DfsVisit::init() "init()", then you can add several + /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". + /// Finally \ref lemon::DfsVisit::start() "start()" will perform the + /// actual path computation. /// @{ + /// \brief Initializes the internal data structures. /// /// Initializes the internal data structures. - /// void init() { create_maps(); _stack.resize(countNodes(*_digraph)); @@ -1360,10 +1374,18 @@ } } - /// \brief Adds a new source node. + ///Adds a new source node. + + ///Adds a new source node to the set of nodes to be processed. /// - /// Adds a new source node to the set of nodes to be processed. - void addSource(Node s) { + ///\pre The stack must be empty. (Otherwise the algorithm gives + ///false results.) + /// + ///\warning Distances will be wrong (or at least strange) in case of + ///multiple sources. + void addSource(Node s) + { + LEMON_DEBUG(emptyQueue(), "The stack is not empty."); if(!(*_reached)[s]) { _reached->set(s,true); _visitor->start(s); @@ -1384,7 +1406,7 @@ /// /// \return The processed arc. /// - /// \pre The stack must not be empty! + /// \pre The stack must not be empty. Arc processNextArc() { Arc e = _stack[_stack_head]; Node m = _digraph->target(e); @@ -1418,37 +1440,58 @@ /// /// \return The next arc to be processed or INVALID if the stack is /// empty. - Arc nextArc() { + Arc nextArc() const { return _stack_head >= 0 ? _stack[_stack_head] : INVALID; } /// \brief Returns \c false if there are nodes - /// to be processed in the queue + /// to be processed. /// /// Returns \c false if there are nodes - /// to be processed in the queue - bool emptyQueue() { return _stack_head < 0; } + /// to be processed in the queue (stack). + bool emptyQueue() const { return _stack_head < 0; } /// \brief Returns the number of the nodes to be processed. /// - /// Returns the number of the nodes to be processed in the queue. - int queueSize() { return _stack_head + 1; } + /// Returns the number of the nodes to be processed in the queue (stack). + int queueSize() const { return _stack_head + 1; } /// \brief Executes the algorithm. /// /// Executes the algorithm. /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. + /// This method runs the %DFS algorithm from the root node + /// in order to compute the %DFS path to each node. + /// + /// The algorithm computes + /// - the %DFS tree, + /// - the distance of each node 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. + /// + /// \note d.start() is just a shortcut of the following code. + /// \code + /// while ( !d.emptyQueue() ) { + /// d.processNextArc(); + /// } + /// \endcode void start() { while ( !emptyQueue() ) processNextArc(); } - /// \brief Executes the algorithm until \c dest is reached. + /// \brief Executes the algorithm until the given target node is reached. /// - /// Executes the algorithm until \c dest is reached. + /// Executes the algorithm until the given target node is reached. /// - /// \pre init() must be called and at least one node should be added + /// This method runs the %DFS algorithm from the root node + /// in order to compute the DFS path to \c dest. + /// + /// The algorithm computes + /// - the %DFS path to \c dest, + /// - the distance of \c dest 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 ) @@ -1459,28 +1502,37 @@ /// /// Executes the algorithm until a condition is met. /// - /// \pre init() must be called and at least one node should be added + /// This method runs the %DFS algorithm from the root node + /// until an arc \c a with am[a] true is found. + /// + /// \param am A \c bool (or convertible) arc map. The algorithm + /// will stop when it reaches an arc \c a with am[a] true. + /// + /// \return The reached arc \c a with am[a] true or + /// \c INVALID if no such arc was found. + /// + /// \pre init() must be called and a root node should be added /// with addSource() before using this function. /// - /// \param em must be a bool (or convertible) arc map. The algorithm - /// will stop when it reaches an arc \c e with em[e] true. - /// - ///\return The reached arc \c e with em[e] true or - ///\c INVALID if no such arc was found. - /// - /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, + /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, /// not a node map. - template - Arc start(const EM &em) { - while ( !emptyQueue() && !em[_stack[_stack_head]] ) + template + Arc start(const AM &am) { + while ( !emptyQueue() && !am[_stack[_stack_head]] ) processNextArc(); return emptyQueue() ? INVALID : _stack[_stack_head]; } - /// \brief Runs %DFSVisit algorithm from node \c s. + /// \brief Runs the algorithm from the given node. /// - /// This method runs the %DFS algorithm from a root node \c s. - /// \note d.run(s) is just a shortcut of the following code. + /// This method runs the %DFS algorithm from node \c s. + /// in order to compute the DFS path to each node. + /// + /// The algorithm computes + /// - the %DFS tree, + /// - the distance of each node from the root in the %DFS tree. + /// + /// \note d.run(s) is just a shortcut of the following code. ///\code /// d.init(); /// d.addSource(s); @@ -1492,22 +1544,46 @@ start(); } - /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph. + /// \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. + /// + /// \return The length of the s--t DFS path, + /// if \c t is reachable form \c s, \c 0 otherwise. + /// + /// \note Apart from the return value, d.run(s,t) is + /// just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(t); + ///\endcode + int run(Node s,Node t) { + init(); + addSource(s); + start(t); + return reached(t)?_stack_head+1:0; + } + + /// \brief Runs the algorithm to visit all nodes in the digraph. /// This method runs the %DFS algorithm in order to - /// compute the %DFS path to each node. The algorithm computes - /// - The %DFS tree. - /// - The distance of each node from the root in the %DFS tree. + /// compute the %DFS path to each node. /// - ///\note d.run() is just a shortcut of the following code. + /// The algorithm computes + /// - the %DFS tree, + /// - the distance of each node from the root in the %DFS tree. + /// + /// \note d.run() is just a shortcut of the following code. ///\code - /// d.init(); - /// for (NodeIt it(digraph); it != INVALID; ++it) { - /// if (!d.reached(it)) { - /// d.addSource(it); - /// d.start(); - /// } - /// } + /// d.init(); + /// for (NodeIt n(digraph); n != INVALID; ++n) { + /// if (!d.reached(n)) { + /// d.addSource(n); + /// d.start(); + /// } + /// } ///\endcode void run() { init(); @@ -1518,27 +1594,28 @@ } } } + ///@} /// \name Query Functions /// The result of the %DFS algorithm can be obtained using these /// functions.\n - /// Before the use of these functions, - /// either run() or start() must be called. + /// Either \ref lemon::DfsVisit::run() "run()" or + /// \ref lemon::DfsVisit::start() "start()" must be called before + /// using them. ///@{ - /// \brief Checks if a node is reachable from the root. + + /// \brief Checks if a node is reachable from the root(s). /// /// Returns \c true if \c v is reachable from the root(s). - /// \warning The source nodes are inditated as unreachable. /// \pre Either \ref run() or \ref start() /// must be called before using this function. - /// bool reached(Node v) { return (*_reached)[v]; } + ///@} + }; - } //END OF NAMESPACE LEMON #endif - diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -33,10 +33,10 @@ namespace lemon { - /// \brief Default OperationTraits for the Dijkstra algorithm class. + /// \brief Default operation traits for the Dijkstra algorithm class. /// - /// It defines all computational operations and constants which are - /// used in the Dijkstra algorithm. + /// This operation traits class defines all computational operations and + /// constants which are used in the Dijkstra algorithm. template struct DijkstraDefaultOperationTraits { /// \brief Gives back the zero value of the type. @@ -47,16 +47,19 @@ static Value plus(const Value& left, const Value& right) { return left + right; } - /// \brief Gives back true only if the first value less than the second. + /// \brief Gives back true only if the first value is less than the second. static bool less(const Value& left, const Value& right) { return left < right; } }; - /// \brief Widest path OperationTraits for the Dijkstra algorithm class. + /// \brief Widest path operation traits for the Dijkstra algorithm class. /// - /// It defines all computational operations and constants which are - /// used in the Dijkstra algorithm for widest path computation. + /// This operation traits class defines all computational operations and + /// constants which are used in the Dijkstra algorithm for widest path + /// computation. + /// + /// \see DijkstraDefaultOperationTraits template struct DijkstraWidestPathOperationTraits { /// \brief Gives back the maximum value of the type. @@ -67,7 +70,7 @@ static Value plus(const Value& left, const Value& right) { return std::min(left, right); } - /// \brief Gives back true only if the first value less than the second. + /// \brief Gives back true only if the first value is less than the second. static bool less(const Value& left, const Value& right) { return left < right; } @@ -76,141 +79,145 @@ ///Default traits class of Dijkstra class. ///Default traits class of Dijkstra class. - ///\tparam GR Digraph type. - ///\tparam LM Type of length map. + ///\tparam GR The type of the digraph. + ///\tparam LM The type of the length map. template struct DijkstraDefaultTraits { - ///The digraph type the algorithm runs on. + ///The type of the digraph the algorithm runs on. typedef GR Digraph; + ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. ///It must meet the \ref concepts::ReadMap "ReadMap" concept. typedef LM LengthMap; - //The type of the length of the arcs. + ///The type of the length of the arcs. typedef typename LM::Value Value; + /// Operation traits for Dijkstra algorithm. - /// It defines the used operation by the algorithm. + /// This class defines the operations that are used in the algorithm. /// \see DijkstraDefaultOperationTraits typedef DijkstraDefaultOperationTraits OperationTraits; - /// The cross reference type used by heap. + /// The cross reference type used by the heap. - /// The cross reference type used by heap. + /// The cross reference type used by the heap. /// Usually it is \c Digraph::NodeMap. typedef typename Digraph::template NodeMap HeapCrossRef; - ///Instantiates a HeapCrossRef. + ///Instantiates a \ref HeapCrossRef. - ///This function instantiates a \c HeapCrossRef. - /// \param G is the digraph, to which we would like to define the - /// HeapCrossRef. - static HeapCrossRef *createHeapCrossRef(const GR &G) + ///This function instantiates a \ref HeapCrossRef. + /// \param g is the digraph, to which we would like to define the + /// \ref HeapCrossRef. + static HeapCrossRef *createHeapCrossRef(const Digraph &g) { - return new HeapCrossRef(G); + return new HeapCrossRef(g); } - ///The heap type used by Dijkstra algorithm. + ///The heap type used by the Dijkstra algorithm. - ///The heap type used by Dijkstra algorithm. + ///The heap type used by the Dijkstra algorithm. /// ///\sa BinHeap ///\sa Dijkstra typedef BinHeap > Heap; + ///Instantiates a \ref Heap. - static Heap *createHeap(HeapCrossRef& R) + ///This function instantiates a \ref Heap. + static Heap *createHeap(HeapCrossRef& r) { - return new Heap(R); + return new Heap(r); } - ///\brief The type of the map that stores the last + ///\brief The type of the map that stores the predecessor ///arcs of the shortest paths. /// - ///The type of the map that stores the last + ///The type of the map that stores the predecessor ///arcs of the shortest paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef typename Digraph::template NodeMap PredMap; - ///Instantiates a PredMap. + typedef typename Digraph::template NodeMap PredMap; + ///Instantiates a \ref PredMap. - ///This function instantiates a \c PredMap. - ///\param G is the digraph, to which we would like to define the PredMap. + ///This function instantiates a \ref PredMap. + ///\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 GR &G) + static PredMap *createPredMap(const Digraph &g) { - return new PredMap(G); + return new PredMap(g); } - ///The type of the map that stores whether a nodes is processed. + ///The type of the map that indicates which nodes are processed. - ///The type of the map that stores whether a nodes is processed. + ///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. ///\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 ProcessedMap. + ///Instantiates a \ref ProcessedMap. - ///This function instantiates a \c ProcessedMap. + ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which - ///we would like to define the \c ProcessedMap + ///we would like to define the \ref ProcessedMap #ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const GR &g) + static ProcessedMap *createProcessedMap(const Digraph &g) #else - static ProcessedMap *createProcessedMap(const GR &) + static ProcessedMap *createProcessedMap(const Digraph &) #endif { return new ProcessedMap(); } - ///The type of the map that stores the dists of the nodes. - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. + + ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// typedef typename Digraph::template NodeMap DistMap; - ///Instantiates a DistMap. + ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. - ///\param G is the digraph, to which we would like to define + ///\param g is the digraph, to which we would like to define ///the \ref DistMap - static DistMap *createDistMap(const GR &G) + static DistMap *createDistMap(const Digraph &g) { - return new DistMap(G); + return new DistMap(g); } }; ///%Dijkstra algorithm class. /// \ingroup shortest_path - ///This class provides an efficient implementation of %Dijkstra algorithm. + ///This class provides an efficient implementation of the %Dijkstra algorithm. + /// ///The arc lengths are passed to the algorithm using a ///\ref concepts::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. - /// ///The type of the length is determined by the ///\ref concepts::ReadMap::Value "Value" of the length map. - /// ///It is also possible to change the underlying priority heap. /// - ///\tparam GR The digraph type the algorithm runs on. The default value - ///is \ref ListDigraph. The value of GR is not used directly by - ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. - ///\tparam LM This read-only ArcMap determines the lengths of the + ///There is also a \ref dijkstra() "function type interface" for the + ///%Dijkstra algorithm, which is convenient in the simplier cases and + ///it can be used easier. + /// + ///\tparam GR The type of the digraph the algorithm runs on. + ///The default value is \ref ListDigraph. + ///The value of GR is not used directly by \ref Dijkstra, it is only + ///passed to \ref DijkstraDefaultTraits. + ///\tparam LM A readable arc map that determines the lengths of the ///arcs. It is read once for each arc, so the map may involve in - ///relatively time consuming process to compute the arc length if + ///relatively time consuming process to compute the arc lengths if ///it is necessary. The default map type is \ref - ///concepts::Digraph::ArcMap "Digraph::ArcMap". The value - ///of LM is not used directly by Dijkstra, it is only passed to \ref - ///DijkstraDefaultTraits. - ///\tparam TR Traits class to set - ///various data types used by the algorithm. The default traits - ///class is \ref DijkstraDefaultTraits - ///"DijkstraDefaultTraits". See \ref - ///DijkstraDefaultTraits for the documentation of a Dijkstra traits - ///class. - + ///concepts::Digraph::ArcMap "Digraph::ArcMap". + ///The value of LM is not used directly by \ref Dijkstra, it is only + ///passed to \ref DijkstraDefaultTraits. + ///\tparam TR Traits class to set various data types used by the algorithm. + ///The default traits class is \ref DijkstraDefaultTraits + ///"DijkstraDefaultTraits". See \ref DijkstraDefaultTraits + ///for the documentation of a Dijkstra traits class. #ifdef DOXYGEN template #else @@ -220,12 +227,10 @@ #endif class Dijkstra { public: - /** - * \brief \ref Exception for uninitialized parameters. - * - * This error represents problems in the initialization - * of the parameters of the algorithms. - */ + ///\ref Exception for uninitialized parameters. + + ///This error represents problems in the initialization of the + ///parameters of the algorithm. class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() { @@ -233,63 +238,65 @@ } }; - typedef TR Traits; - ///The type of the underlying digraph. + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - ///\e - typedef typename Digraph::Node Node; - ///\e - typedef typename Digraph::NodeIt NodeIt; - ///\e - typedef typename Digraph::Arc Arc; - ///\e - typedef typename Digraph::OutArcIt OutArcIt; ///The type of the length of the arcs. typedef typename TR::LengthMap::Value Value; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; - ///\brief The type of the map that stores the last - ///arcs of the shortest paths. + ///\brief The type of the map that stores the predecessor arcs of the + ///shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map indicating if a node is processed. + ///The type of the map that stores the distances of the nodes. + typedef typename TR::DistMap DistMap; + ///The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the map that stores the dists of the nodes. - typedef typename TR::DistMap DistMap; + ///The type of the paths. + typedef PredMapPath Path; ///The cross reference type used for the current heap. typedef typename TR::HeapCrossRef HeapCrossRef; - ///The heap type used by the dijkstra algorithm. + ///The heap type used by the algorithm. typedef typename TR::Heap Heap; - ///The operation traits. + ///The operation traits class. typedef typename TR::OperationTraits OperationTraits; + + ///The traits class. + typedef TR Traits; + private: - /// Pointer to the underlying digraph. + + typedef typename Digraph::Node Node; + typedef typename Digraph::NodeIt NodeIt; + typedef typename Digraph::Arc Arc; + typedef typename Digraph::OutArcIt OutArcIt; + + //Pointer to the underlying digraph. const Digraph *G; - /// Pointer to the length map + //Pointer to the length map. const LengthMap *length; - ///Pointer to the map of predecessors arcs. + //Pointer to the map of predecessors arcs. PredMap *_pred; - ///Indicates if \ref _pred is locally allocated (\c true) or not. + //Indicates if _pred is locally allocated (true) or not. bool local_pred; - ///Pointer to the map of distances. + //Pointer to the map of distances. DistMap *_dist; - ///Indicates if \ref _dist is locally allocated (\c true) or not. + //Indicates if _dist is locally allocated (true) or not. bool local_dist; - ///Pointer to the map of processed status of the nodes. + //Pointer to the map of processed status of the nodes. ProcessedMap *_processed; - ///Indicates if \ref _processed is locally allocated (\c true) or not. + //Indicates if _processed is locally allocated (true) or not. bool local_processed; - ///Pointer to the heap cross references. + //Pointer to the heap cross references. HeapCrossRef *_heap_cross_ref; - ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. + //Indicates if _heap_cross_ref is locally allocated (true) or not. bool local_heap_cross_ref; - ///Pointer to the heap. + //Pointer to the heap. Heap *_heap; - ///Indicates if \ref _heap is locally allocated (\c true) or not. + //Indicates if _heap is locally allocated (true) or not. bool local_heap; ///Creates the maps if necessary. - ///\todo Better memory allocation (instead of new). void create_maps() { @@ -315,7 +322,7 @@ } } - public : + public: typedef Dijkstra Create; @@ -331,10 +338,11 @@ throw UninitializedParameter(); } }; - ///\ref named-templ-param "Named parameter" for setting PredMap type - - ///\ref named-templ-param "Named parameter" for setting PredMap type + ///\brief \ref named-templ-param "Named parameter" for setting + ///\ref PredMap type. /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref PredMap type. template struct DefPredMap : public Dijkstra< Digraph, LengthMap, DefPredMapTraits > { @@ -349,10 +357,11 @@ throw UninitializedParameter(); } }; - ///\ref named-templ-param "Named parameter" for setting DistMap type - - ///\ref named-templ-param "Named parameter" for setting DistMap type + ///\brief \ref named-templ-param "Named parameter" for setting + ///\ref DistMap type. /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref DistMap type. template struct DefDistMap : public Dijkstra< Digraph, LengthMap, DefDistMapTraits > { @@ -362,15 +371,16 @@ template struct DefProcessedMapTraits : public Traits { typedef T ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &G) + static ProcessedMap *createProcessedMap(const Digraph &) { throw UninitializedParameter(); } }; - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type - - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + ///\brief \ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type. /// + ///\ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type. template struct DefProcessedMap : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits > { @@ -379,17 +389,17 @@ struct DefDigraphProcessedMapTraits : public Traits { typedef typename Digraph::template NodeMap ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &G) + static ProcessedMap *createProcessedMap(const Digraph &g) { - return new ProcessedMap(G); + return new ProcessedMap(g); } }; - ///\brief \ref named-templ-param "Named parameter" - ///for setting the ProcessedMap type to be Digraph::NodeMap. + ///\brief \ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type to be Digraph::NodeMap. /// - ///\ref named-templ-param "Named parameter" - ///for setting the ProcessedMap type to be Digraph::NodeMap. - ///If you don't set it explicitely, it will be automatically allocated. + ///\ref named-templ-param "Named parameter" for setting + ///\ref ProcessedMap type to be Digraph::NodeMap. + ///If you don't set it explicitly, it will be automatically allocated. template struct DefProcessedMapToBeDefaultMap : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> { @@ -413,8 +423,7 @@ ///heap and cross reference type /// ///\ref named-templ-param "Named parameter" for setting heap and cross - ///reference type - /// + ///reference type. template > struct DefHeap : public Dijkstra< Digraph, LengthMap, DefHeapTraits > { @@ -453,10 +462,10 @@ }; /// \brief \ref named-templ-param "Named parameter" for setting - /// OperationTraits type + ///\ref OperationTraits type /// - /// \ref named-templ-param "Named parameter" for setting OperationTraits - /// type + ///\ref named-templ-param "Named parameter" for setting + ///\ref OperationTraits type. template struct DefOperationTraits : public Dijkstra > { @@ -466,7 +475,6 @@ ///@} - protected: Dijkstra() {} @@ -475,10 +483,11 @@ ///Constructor. - ///\param _G the digraph the algorithm will run on. - ///\param _length the length map used by the algorithm. - Dijkstra(const Digraph& _G, const LengthMap& _length) : - G(&_G), length(&_length), + ///Constructor. + ///\param _g The digraph the algorithm runs on. + ///\param _length The length map used by the algorithm. + Dijkstra(const Digraph& _g, const LengthMap& _length) : + G(&_g), length(&_length), _pred(NULL), local_pred(false), _dist(NULL), local_dist(false), _processed(NULL), local_processed(false), @@ -506,11 +515,11 @@ return *this; } - ///Sets the map storing the predecessor arcs. + ///Sets the map that stores the predecessor arcs. - ///Sets the map storing the predecessor arcs. + ///Sets the map that stores the predecessor arcs. ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this + ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) Dijkstra &predMap(PredMap &m) @@ -523,11 +532,29 @@ return *this; } - ///Sets the map storing the distances calculated by the algorithm. + ///Sets the map that indicates which nodes are processed. - ///Sets the map storing the distances calculated by the algorithm. + ///Sets the map that indicates which nodes are processed. ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this + ///it will allocate one. The destructor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dijkstra &processedMap(ProcessedMap &m) + { + if(local_processed) { + delete _processed; + local_processed=false; + } + _processed = &m; + return *this; + } + + ///Sets the map that stores the distances of the nodes. + + ///Sets the map that stores the distances of the nodes calculated by the + ///algorithm. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) Dijkstra &distMap(DistMap &m) @@ -544,7 +571,7 @@ ///Sets the heap and the cross reference used by algorithm. ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this + ///it will allocate one. The destructor deallocates this ///automatically allocated heap and cross reference, of course. ///\return (*this) Dijkstra &heap(Heap& hp, HeapCrossRef &cr) @@ -563,6 +590,7 @@ } private: + void finalizeNodeData(Node v,Value dst) { _processed->set(v,true); @@ -571,17 +599,15 @@ public: - typedef PredMapPath Path; - ///\name Execution control - ///The simplest way to execute the algorithm is to use - ///one of the member functions called \c run(...). + ///The simplest way to execute the algorithm is to use one of the + ///member functions called \ref lemon::Dijkstra::run() "run()". ///\n - ///If you need more control on the execution, - ///first you must call \ref init(), then you can add several source nodes - ///with \ref addSource(). - ///Finally \ref start() will perform the actual path - ///computation. + ///If you need more control on the execution, first you must call + ///\ref lemon::Dijkstra::init() "init()", then you can add several + ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". + ///Finally \ref lemon::Dijkstra::start() "start()" will perform the + ///actual path computation. ///@{ @@ -603,10 +629,9 @@ ///Adds a new source node. ///Adds a new source node to the priority heap. - /// ///The optional second parameter is the initial distance of the node. /// - ///It checks if the node has already been added to the heap and + ///The function checks if the node has already been added to the heap and ///it is pushed to the heap only if either it was not in the heap ///or the shortest path found till then is shorter than \c dst. void addSource(Node s,Value dst=OperationTraits::zero()) @@ -625,7 +650,7 @@ /// ///\return The processed node. /// - ///\warning The priority heap must not be empty! + ///\warning The priority heap must not be empty. Node processNextNode() { Node v=_heap->top(); @@ -656,62 +681,66 @@ return v; } - ///Next node to be processed. + ///The next node to be processed. - ///Next node to be processed. - /// - ///\return The next node to be processed or INVALID if the priority heap - /// is empty. - Node nextNode() + ///Returns the next node to be processed or \c INVALID if the + ///priority heap is empty. + Node nextNode() const { return !_heap->empty()?_heap->top():INVALID; } ///\brief Returns \c false if there are nodes - ///to be processed in the priority heap + ///to be processed. /// ///Returns \c false if there are nodes - ///to be processed in the priority heap - bool emptyQueue() { return _heap->empty(); } + ///to be processed in the priority heap. + bool emptyQueue() const { return _heap->empty(); } + ///Returns the number of the nodes to be processed in the priority heap - ///Returns the number of the nodes to be processed in the priority heap + ///Returns the number of the nodes to be processed in the priority heap. /// - int queueSize() { return _heap->size(); } + int queueSize() const { return _heap->size(); } ///Executes the algorithm. ///Executes the algorithm. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %Dijkstra algorithm from the root node(s) + ///in order to compute the shortest path to each node. + /// + ///The algorithm computes + ///- the shortest path tree (forest), + ///- the distance of each node from the root(s). + /// + ///\pre init() must be called and at least one root node should be + ///added with addSource() before using this function. + /// + ///\note d.start() is just a shortcut of the following code. + ///\code + /// while ( !d.emptyQueue() ) { + /// d.processNextNode(); + /// } + ///\endcode + void start() + { + while ( !emptyQueue() ) processNextNode(); + } + + ///Executes the algorithm until the given target node is reached. + + ///Executes the algorithm until the given target node is reached. /// ///This method runs the %Dijkstra algorithm from the root node(s) - ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the root(s). + ///in order to compute the shortest path to \c dest. /// - void start() - { - while ( !_heap->empty() ) processNextNode(); - } - - ///Executes the algorithm until \c dest is reached. - - ///Executes the algorithm until \c dest is reached. + ///The algorithm computes + ///- the shortest path to \c dest, + ///- the distance of \c dest from the root(s). /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. - /// - ///This method runs the %Dijkstra algorithm from the root node(s) - ///in order to - ///compute the - ///shortest path to \c dest. The algorithm computes - ///- The shortest path to \c dest. - ///- The distance of \c dest 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(); @@ -722,14 +751,18 @@ ///Executes the algorithm until a condition is met. /// - ///\pre init() must be called and at least one node should be added - ///with addSource() before using this function. + ///This method runs the %Dijkstra algorithm from the root node(s) in + ///order to compute the shortest path to a node \c v with + /// nm[v] true, if such a node can be found. /// - ///\param nm must be a bool (or convertible) node map. The algorithm + ///\param nm A \c bool (or convertible) node map. The algorithm ///will stop when it reaches a node \c v with nm[v] true. /// ///\return The reached node \c v with nm[v] true or ///\c INVALID if no such node was found. + /// + ///\pre init() must be called and at least one root node should be + ///added with addSource() before using this function. template Node start(const NodeBoolMap &nm) { @@ -739,16 +772,16 @@ return _heap->top(); } - ///Runs %Dijkstra algorithm from node \c s. + ///Runs the algorithm from the given node. - ///This method runs the %Dijkstra algorithm from a root node \c s - ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the root. + ///This method runs the %Dijkstra algorithm from node \c s + ///in order to compute the shortest path to each node. /// - ///\note d.run(s) is just a shortcut of the following code. + ///The algorithm computes + ///- the shortest path tree, + ///- the distance of each node from the root. + /// + ///\note d.run(s) is just a shortcut of the following code. ///\code /// d.init(); /// d.addSource(s); @@ -762,12 +795,14 @@ ///Finds the shortest path between \c s and \c t. - ///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. /// - ///\return The length of the shortest s---t path if there exists one, - ///0 otherwise. - ///\note Apart from the return value, d.run(s) is - ///just a shortcut of the following code. + ///\return The length of the shortest s--t path, + ///if \c t is reachable form \c s, \c 0 otherwise. + /// + ///\note Apart from the return value, d.run(s,t) is just a + ///shortcut of the following code. ///\code /// d.init(); /// d.addSource(s); @@ -785,241 +820,262 @@ ///\name Query Functions ///The result of the %Dijkstra algorithm can be obtained using these ///functions.\n - ///Before the use of these functions, - ///either run() or start() must be called. + ///Either \ref lemon::Dijkstra::run() "run()" or + ///\ref lemon::Dijkstra::start() "start()" must be called before + ///using them. ///@{ - ///Gives back the shortest path. + ///The shortest path to a node. - ///Gives back the shortest path. - ///\pre The \c t should be reachable from the source. - Path path(Node t) - { - return Path(*G, *_pred, t); - } + ///Returns the shortest path to a node. + /// + ///\warning \c t should be reachable from the root(s). + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. + Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root. + ///The distance of a node from the root(s). - ///Returns the distance of a node from the root. - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root the return value - ///of this funcion is undefined. + ///Returns the distance of a node from the root(s). + /// + ///\warning If node \c v is not reachable from the root(s), then + ///the return value of this function is undefined. + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. Value dist(Node v) const { return (*_dist)[v]; } - ///The current distance of a node from the root. + ///Returns the 'previous arc' of the shortest path tree for a node. - ///Returns the current distance of a node from the root. - ///It may be decreased in the following processes. - ///\pre \c node should be reached but not processed - Value currentDist(Node v) const { return (*_heap)[v]; } - - ///Returns the 'previous arc' of the shortest path tree. - - ///For a node \c v it returns the 'previous arc' of the shortest path tree, - ///i.e. it returns the last arc of a shortest path from the root to \c - ///v. It is \ref INVALID - ///if \c v is unreachable from the root or if \c v=s. The - ///shortest path tree used here is equal to the shortest path tree used in - ///\ref predNode(). \pre \ref run() must be called before using - ///this function. + ///This function returns the 'previous arc' of the shortest path + ///tree for the node \c v, i.e. it returns the last arc of a + ///shortest path from the root(s) to \c v. It is \c INVALID if \c v + ///is not reachable from the root(s) or if \c v is a root. + /// + ///The shortest path tree used here is equal to the shortest path + ///tree used in \ref predNode(). + /// + ///\pre Either \ref run() or \ref start() must be called before + ///using this function. Arc predArc(Node v) const { return (*_pred)[v]; } - ///Returns the 'previous node' of the shortest path tree. + ///Returns the 'previous node' of the shortest path tree for a node. - ///For a node \c v it returns the 'previous node' of the shortest path tree, - ///i.e. it returns the last but one node from a shortest path from the - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if - ///\c v=s. The shortest path tree used here is equal to the shortest path - ///tree used in \ref predArc(). \pre \ref run() must be called before + ///This function returns the 'previous node' of the shortest path + ///tree for the node \c v, i.e. it returns the last but one node + ///from a shortest path from the root(s) to \c v. It is \c INVALID + ///if \c v is not reachable from the root(s) or if \c v is a root. + /// + ///The shortest path tree used here is equal to the shortest path + ///tree used in \ref predArc(). + /// + ///\pre Either \ref run() or \ref start() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } - ///Returns a reference to the NodeMap of distances. - - ///Returns a reference to the NodeMap of distances. \pre \ref run() must - ///be called before using this function. + ///\brief Returns a const reference to the node map that stores the + ///distances of the nodes. + /// + ///Returns a const reference to the node map that stores the distances + ///of the nodes calculated by the algorithm. + /// + ///\pre Either \ref run() or \ref init() + ///must be called before using this function. const DistMap &distMap() const { return *_dist;} - ///Returns a reference to the shortest path tree map. - - ///Returns a reference to the NodeMap of the arcs of the - ///shortest path tree. - ///\pre \ref run() must be called before using this function. + ///\brief Returns a const reference to the node map that stores the + ///predecessor arcs. + /// + ///Returns a const reference to the node map that stores the predecessor + ///arcs, which form the shortest path tree. + /// + ///\pre Either \ref run() or \ref init() + ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reachable from the root. + ///Checks if a node is reachable from the root(s). - ///Returns \c true if \c v is reachable from the root. - ///\warning The source nodes are inditated as unreached. - ///\pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } + ///Returns \c true if \c v is reachable from the root(s). + ///\pre Either \ref run() or \ref start() + ///must be called before using this function. + bool reached(Node v) const { return (*_heap_cross_ref)[v] != + Heap::PRE_HEAP; } ///Checks if a node is processed. ///Returns \c true if \c v is processed, i.e. the shortest ///path to \c v has already found. - ///\pre \ref run() must be called before using this function. - /// - bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } + ///\pre Either \ref run() or \ref start() + ///must be called before using this function. + bool processed(Node v) const { return (*_heap_cross_ref)[v] == + Heap::POST_HEAP; } + + ///The current distance of a node from the root(s). + + ///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]; } ///@} }; + ///Default traits class of dijkstra() function. - - - ///Default traits class of Dijkstra function. - - ///Default traits class of Dijkstra function. - ///\tparam GR Digraph type. - ///\tparam LM Type of length map. + ///Default traits class of dijkstra() function. + ///\tparam GR The type of the digraph. + ///\tparam LM The type of the length map. template struct DijkstraWizardDefaultTraits { - ///The digraph type the algorithm runs on. + ///The type of the digraph the algorithm runs on. typedef GR Digraph; ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. ///It must meet the \ref concepts::ReadMap "ReadMap" concept. typedef LM LengthMap; - //The type of the length of the arcs. + ///The type of the length of the arcs. typedef typename LM::Value Value; + /// Operation traits for Dijkstra algorithm. - /// It defines the used operation by the algorithm. + /// This class defines the operations that are used in the algorithm. /// \see DijkstraDefaultOperationTraits typedef DijkstraDefaultOperationTraits OperationTraits; - ///The heap type used by Dijkstra algorithm. - /// The cross reference type used by heap. + /// The cross reference type used by the heap. - /// The cross reference type used by heap. + /// The cross reference type used by the heap. /// Usually it is \c Digraph::NodeMap. typedef typename Digraph::template NodeMap HeapCrossRef; - ///Instantiates a HeapCrossRef. + ///Instantiates a \ref HeapCrossRef. ///This function instantiates a \ref HeapCrossRef. - /// \param G is the digraph, to which we would like to define the + /// \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 GR &G) + static HeapCrossRef *createHeapCrossRef(const Digraph &g) { - return new HeapCrossRef(G); + return new HeapCrossRef(g); } - ///The heap type used by Dijkstra algorithm. + ///The heap type used by the Dijkstra algorithm. - ///The heap type used by Dijkstra algorithm. + ///The heap type used by the Dijkstra algorithm. /// ///\sa BinHeap ///\sa Dijkstra - typedef BinHeap, + typedef BinHeap, std::less > Heap; - static Heap *createHeap(HeapCrossRef& R) + ///Instantiates a \ref Heap. + + ///This function instantiates a \ref Heap. + /// \param r is the HeapCrossRef which is used. + static Heap *createHeap(HeapCrossRef& r) { - return new Heap(R); + return new Heap(r); } - ///\brief The type of the map that stores the last + ///\brief The type of the map that stores the predecessor ///arcs of the shortest paths. /// - ///The type of the map that stores the last + ///The type of the map that stores the predecessor ///arcs of the shortest paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef NullMap PredMap; - ///Instantiates a PredMap. + typedef NullMap PredMap; + ///Instantiates a \ref PredMap. ///This function instantiates a \ref PredMap. - ///\param g is the digraph, to which we would like to define the PredMap. - ///\todo The digraph alone may be insufficient for the initialization + ///\param g is the digraph, to which we would like to define the + ///\ref PredMap. + ///\todo The digraph alone may be insufficient to initialize #ifdef DOXYGEN - static PredMap *createPredMap(const GR &g) + static PredMap *createPredMap(const Digraph &g) #else - static PredMap *createPredMap(const GR &) + static PredMap *createPredMap(const Digraph &) #endif { return new PredMap(); } - ///The type of the map that stores whether a nodes is processed. - ///The type of the map that stores whether a nodes is processed. + ///The type of the map that indicates which nodes are processed. + + ///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. ///\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 ProcessedMap. + ///Instantiates a \ref ProcessedMap. ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which - ///we would like to define the \ref ProcessedMap + ///we would like to define the \ref ProcessedMap. #ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const GR &g) + static ProcessedMap *createProcessedMap(const Digraph &g) #else - static ProcessedMap *createProcessedMap(const GR &) + static ProcessedMap *createProcessedMap(const Digraph &) #endif { return new ProcessedMap(); } - ///The type of the map that stores the dists of the nodes. - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. + + ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - /// - typedef NullMap DistMap; - ///Instantiates a DistMap. + typedef NullMap DistMap; + ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define ///the \ref DistMap #ifdef DOXYGEN - static DistMap *createDistMap(const GR &g) + static DistMap *createDistMap(const Digraph &g) #else - static DistMap *createDistMap(const GR &) + static DistMap *createDistMap(const Digraph &) #endif { return new DistMap(); } }; - /// Default traits used by \ref DijkstraWizard + /// Default traits class used by \ref DijkstraWizard /// To make it easier to use Dijkstra algorithm - ///we have created a wizard class. + /// we have created a wizard class. /// This \ref DijkstraWizard class needs default traits, - ///as well as the \ref Dijkstra class. + /// as well as the \ref Dijkstra class. /// 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 { - typedef DijkstraWizardDefaultTraits Base; protected: - /// Type of the nodes in the digraph. + //The type of the nodes in the digraph. typedef typename Base::Digraph::Node Node; - /// Pointer to the underlying digraph. + //Pointer to the digraph the algorithm runs on. void *_g; - /// Pointer to the length map + //Pointer to the length map void *_length; - ///Pointer to the map of predecessors arcs. + //Pointer to the map of predecessors arcs. void *_pred; - ///Pointer to the map of distances. + //Pointer to the map of distances. void *_dist; - ///Pointer to the source node. + //Pointer to the source node. Node _source; - public: + public: /// Constructor. /// This constructor does not require parameters, therefore it initiates @@ -1032,9 +1088,9 @@ /// This constructor requires some parameters, /// listed in the parameters list. /// Others are initiated to 0. - /// \param g is the initial value of \ref _g - /// \param l is the initial value of \ref _length - /// \param s is the initial value of \ref _source + /// \param g The digraph the algorithm runs on. + /// \param l The length map. + /// \param s The source node. DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : _g(reinterpret_cast(const_cast(&g))), _length(reinterpret_cast(const_cast(&l))), @@ -1042,11 +1098,13 @@ }; - /// A class to make the usage of Dijkstra algorithm easier + /// Auxiliary class for the function type interface of Dijkstra algorithm. - /// This class is created to make it easier to use Dijkstra algorithm. - /// It uses the functions and features of the plain \ref Dijkstra, - /// but it is much simpler to use it. + /// This auxiliary class is created to implement the function type + /// interface of \ref Dijkstra algorithm. It uses the functions and features + /// of the plain \ref Dijkstra, but it is much simpler to use it. + /// It should only be used through the \ref dijkstra() function, which makes + /// it easier to use the algorithm. /// /// Simplicity means that the way to change the types defined /// in the traits class is based on functions that returns the new class @@ -1055,40 +1113,41 @@ /// the new class with the modified type comes from /// the original class by using the :: /// operator. In the case of \ref DijkstraWizard only - /// a function have to be called and it will + /// a function have to be called, and it will /// return the needed class. /// - /// It does not have own \ref run method. When its \ref run method is called - /// it initiates a plain \ref Dijkstra class, and calls the \ref - /// Dijkstra::run method of it. + /// It does not have own \ref run() method. When its \ref run() method + /// is called, it initiates a plain \ref Dijkstra object, and calls the + /// \ref Dijkstra::run() method of it. template class DijkstraWizard : public TR { typedef TR Base; - ///The type of the underlying digraph. + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - //\e + typedef typename Digraph::Node Node; - //\e typedef typename Digraph::NodeIt NodeIt; - //\e typedef typename Digraph::Arc Arc; - //\e typedef typename Digraph::OutArcIt OutArcIt; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; ///The type of the length of the arcs. typedef typename LengthMap::Value Value; - ///\brief The type of the map that stores the last + ///\brief The type of the map that stores the predecessor ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; + ///The type of the map that indicates which nodes are processed. + typedef typename TR::ProcessedMap ProcessedMap; ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; + public: + /// Constructor. DijkstraWizard() : TR() {} @@ -1104,10 +1163,10 @@ ~DijkstraWizard() {} - ///Runs Dijkstra algorithm from a given node. + ///Runs Dijkstra algorithm from a source node. - ///Runs Dijkstra algorithm from a given node. - ///The node can be given by the \ref source function. + ///Runs Dijkstra algorithm from a source node. + ///The node can be given with the \ref source() function. void run() { if(Base::_source==INVALID) throw UninitializedParameter(); @@ -1129,19 +1188,27 @@ run(); } + /// Sets the source node, from which the Dijkstra algorithm runs. + + /// Sets the source node, from which the Dijkstra algorithm runs. + /// \param s is the source node. + DijkstraWizard &source(Node s) + { + Base::_source=s; + return *this; + } + template struct DefPredMapBase : public Base { typedef T PredMap; static PredMap *createPredMap(const Digraph &) { return 0; }; DefPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting PredMap type + ///for setting \ref PredMap object. /// - /// \ref named-templ-param "Named parameter" - ///function for setting PredMap type - /// + ///\ref named-templ-param "Named parameter" + ///for setting \ref PredMap object. template DijkstraWizard > predMap(const T &t) { @@ -1150,18 +1217,34 @@ } template + struct DefProcessedMapBase : public Base { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; + DefProcessedMapBase(const TR &b) : TR(b) {} + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting \ref ProcessedMap object. + /// + /// \ref named-templ-param "Named parameter" + ///for setting \ref ProcessedMap object. + template + DijkstraWizard > processedMap(const T &t) + { + Base::_processed=reinterpret_cast(const_cast(&t)); + return DijkstraWizard >(*this); + } + + template struct DefDistMapBase : public Base { typedef T DistMap; static DistMap *createDistMap(const Digraph &) { return 0; }; DefDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting DistMap type + ///for setting \ref DistMap object. /// - /// \ref named-templ-param "Named parameter" - ///function for setting DistMap type - /// + ///\ref named-templ-param "Named parameter" + ///for setting \ref DistMap object. template DijkstraWizard > distMap(const T &t) { @@ -1169,16 +1252,6 @@ return DijkstraWizard >(*this); } - /// Sets the source node, from which the Dijkstra algorithm runs. - - /// Sets the source node, from which the Dijkstra algorithm runs. - /// \param s is the source node. - DijkstraWizard &source(Node s) - { - Base::_source=s; - return *this; - } - }; ///Function type interface for Dijkstra algorithm.