lemon/dfs.h
changeset 408 69f33ef03334
parent 319 5e12d7734036
child 419 9afe81e4c543
child 420 6a2a33ad261b
     1.1 --- a/lemon/dfs.h	Tue Dec 02 10:30:52 2008 +0000
     1.2 +++ b/lemon/dfs.h	Tue Dec 02 10:31:20 2008 +0000
     1.3 @@ -119,13 +119,7 @@
     1.4    ///used easier.
     1.5    ///
     1.6    ///\tparam GR The type of the digraph the algorithm runs on.
     1.7 -  ///The default value is \ref ListDigraph. The value of GR is not used
     1.8 -  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
     1.9 -  ///\tparam TR Traits class to set various data types used by the algorithm.
    1.10 -  ///The default traits class is
    1.11 -  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
    1.12 -  ///See \ref DfsDefaultTraits for the documentation of
    1.13 -  ///a Dfs traits class.
    1.14 +  ///The default type is \ref ListDigraph.
    1.15  #ifdef DOXYGEN
    1.16    template <typename GR,
    1.17              typename TR>
    1.18 @@ -151,7 +145,7 @@
    1.19      ///The type of the paths.
    1.20      typedef PredMapPath<Digraph, PredMap> Path;
    1.21  
    1.22 -    ///The traits class.
    1.23 +    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    1.24      typedef TR Traits;
    1.25  
    1.26    private:
    1.27 @@ -230,6 +224,7 @@
    1.28      ///
    1.29      ///\ref named-templ-param "Named parameter" for setting
    1.30      ///PredMap type.
    1.31 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.32      template <class T>
    1.33      struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    1.34        typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
    1.35 @@ -249,6 +244,7 @@
    1.36      ///
    1.37      ///\ref named-templ-param "Named parameter" for setting
    1.38      ///DistMap type.
    1.39 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.40      template <class T>
    1.41      struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    1.42        typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
    1.43 @@ -268,6 +264,7 @@
    1.44      ///
    1.45      ///\ref named-templ-param "Named parameter" for setting
    1.46      ///ReachedMap type.
    1.47 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.48      template <class T>
    1.49      struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    1.50        typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
    1.51 @@ -287,6 +284,7 @@
    1.52      ///
    1.53      ///\ref named-templ-param "Named parameter" for setting
    1.54      ///ProcessedMap type.
    1.55 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.56      template <class T>
    1.57      struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    1.58        typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
    1.59 @@ -338,9 +336,10 @@
    1.60      ///Sets the map that stores the predecessor arcs.
    1.61  
    1.62      ///Sets the map that stores the predecessor arcs.
    1.63 -    ///If you don't use this function before calling \ref run(),
    1.64 -    ///it will allocate one. The destructor deallocates this
    1.65 -    ///automatically allocated map, of course.
    1.66 +    ///If you don't use this function before calling \ref run(Node) "run()"
    1.67 +    ///or \ref init(), an instance will be allocated automatically.
    1.68 +    ///The destructor deallocates this automatically allocated map,
    1.69 +    ///of course.
    1.70      ///\return <tt> (*this) </tt>
    1.71      Dfs &predMap(PredMap &m)
    1.72      {
    1.73 @@ -355,9 +354,10 @@
    1.74      ///Sets the map that indicates which nodes are reached.
    1.75  
    1.76      ///Sets the map that indicates which nodes are reached.
    1.77 -    ///If you don't use this function before calling \ref run(),
    1.78 -    ///it will allocate one. The destructor deallocates this
    1.79 -    ///automatically allocated map, of course.
    1.80 +    ///If you don't use this function before calling \ref run(Node) "run()"
    1.81 +    ///or \ref init(), an instance will be allocated automatically.
    1.82 +    ///The destructor deallocates this automatically allocated map,
    1.83 +    ///of course.
    1.84      ///\return <tt> (*this) </tt>
    1.85      Dfs &reachedMap(ReachedMap &m)
    1.86      {
    1.87 @@ -372,9 +372,10 @@
    1.88      ///Sets the map that indicates which nodes are processed.
    1.89  
    1.90      ///Sets the map that indicates which nodes are processed.
    1.91 -    ///If you don't use this function before calling \ref run(),
    1.92 -    ///it will allocate one. The destructor deallocates this
    1.93 -    ///automatically allocated map, of course.
    1.94 +    ///If you don't use this function before calling \ref run(Node) "run()"
    1.95 +    ///or \ref init(), an instance will be allocated automatically.
    1.96 +    ///The destructor deallocates this automatically allocated map,
    1.97 +    ///of course.
    1.98      ///\return <tt> (*this) </tt>
    1.99      Dfs &processedMap(ProcessedMap &m)
   1.100      {
   1.101 @@ -390,9 +391,10 @@
   1.102  
   1.103      ///Sets the map that stores the distances of the nodes calculated by
   1.104      ///the algorithm.
   1.105 -    ///If you don't use this function before calling \ref run(),
   1.106 -    ///it will allocate one. The destructor deallocates this
   1.107 -    ///automatically allocated map, of course.
   1.108 +    ///If you don't use this function before calling \ref run(Node) "run()"
   1.109 +    ///or \ref init(), an instance will be allocated automatically.
   1.110 +    ///The destructor deallocates this automatically allocated map,
   1.111 +    ///of course.
   1.112      ///\return <tt> (*this) </tt>
   1.113      Dfs &distMap(DistMap &m)
   1.114      {
   1.115 @@ -406,22 +408,20 @@
   1.116  
   1.117    public:
   1.118  
   1.119 -    ///\name Execution control
   1.120 -    ///The simplest way to execute the algorithm is to use
   1.121 -    ///one of the member functions called \ref lemon::Dfs::run() "run()".
   1.122 -    ///\n
   1.123 -    ///If you need more control on the execution, first you must call
   1.124 -    ///\ref lemon::Dfs::init() "init()", then you can add a source node
   1.125 -    ///with \ref lemon::Dfs::addSource() "addSource()".
   1.126 -    ///Finally \ref lemon::Dfs::start() "start()" will perform the
   1.127 -    ///actual path computation.
   1.128 +    ///\name Execution Control
   1.129 +    ///The simplest way to execute the DFS algorithm is to use one of the
   1.130 +    ///member functions called \ref run(Node) "run()".\n
   1.131 +    ///If you need more control on the execution, first you have to call
   1.132 +    ///\ref init(), then you can add a source node with \ref addSource()
   1.133 +    ///and perform the actual computation with \ref start().
   1.134 +    ///This procedure can be repeated if there are nodes that have not
   1.135 +    ///been reached.
   1.136  
   1.137      ///@{
   1.138  
   1.139 +    ///\brief Initializes the internal data structures.
   1.140 +    ///
   1.141      ///Initializes the internal data structures.
   1.142 -
   1.143 -    ///Initializes the internal data structures.
   1.144 -    ///
   1.145      void init()
   1.146      {
   1.147        create_maps();
   1.148 @@ -438,11 +438,10 @@
   1.149  
   1.150      ///Adds a new source node to the set of nodes to be processed.
   1.151      ///
   1.152 -    ///\pre The stack must be empty. (Otherwise the algorithm gives
   1.153 -    ///false results.)
   1.154 -    ///
   1.155 -    ///\warning Distances will be wrong (or at least strange) in case of
   1.156 -    ///multiple sources.
   1.157 +    ///\pre The stack must be empty. Otherwise the algorithm gives
   1.158 +    ///wrong results. (One of the outgoing arcs of all the source nodes
   1.159 +    ///except for the last one will not be visited and distances will
   1.160 +    ///also be wrong.)
   1.161      void addSource(Node s)
   1.162      {
   1.163        LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   1.164 @@ -506,16 +505,16 @@
   1.165        return _stack_head>=0?_stack[_stack_head]:INVALID;
   1.166      }
   1.167  
   1.168 -    ///\brief Returns \c false if there are nodes
   1.169 -    ///to be processed.
   1.170 -    ///
   1.171 -    ///Returns \c false if there are nodes
   1.172 -    ///to be processed in the queue (stack).
   1.173 +    ///Returns \c false if there are nodes to be processed.
   1.174 +
   1.175 +    ///Returns \c false if there are nodes to be processed
   1.176 +    ///in the queue (stack).
   1.177      bool emptyQueue() const { return _stack_head<0; }
   1.178  
   1.179      ///Returns the number of the nodes to be processed.
   1.180  
   1.181 -    ///Returns the number of the nodes to be processed in the queue (stack).
   1.182 +    ///Returns the number of the nodes to be processed
   1.183 +    ///in the queue (stack).
   1.184      int queueSize() const { return _stack_head+1; }
   1.185  
   1.186      ///Executes the algorithm.
   1.187 @@ -637,8 +636,8 @@
   1.188      ///%DFS path to each node.
   1.189      ///
   1.190      ///The algorithm computes
   1.191 -    ///- the %DFS tree,
   1.192 -    ///- the distance of each node from the root in the %DFS tree.
   1.193 +    ///- the %DFS tree (forest),
   1.194 +    ///- the distance of each node from the root(s) in the %DFS tree.
   1.195      ///
   1.196      ///\note <tt>d.run()</tt> is just a shortcut of the following code.
   1.197      ///\code
   1.198 @@ -663,10 +662,10 @@
   1.199      ///@}
   1.200  
   1.201      ///\name Query Functions
   1.202 -    ///The result of the %DFS algorithm can be obtained using these
   1.203 +    ///The results of the DFS algorithm can be obtained using these
   1.204      ///functions.\n
   1.205 -    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
   1.206 -    ///"start()" must be called before using them.
   1.207 +    ///Either \ref run(Node) "run()" or \ref start() should be called
   1.208 +    ///before using them.
   1.209  
   1.210      ///@{
   1.211  
   1.212 @@ -674,49 +673,49 @@
   1.213  
   1.214      ///Returns the DFS path to a node.
   1.215      ///
   1.216 -    ///\warning \c t should be reachable from the root.
   1.217 +    ///\warning \c t should be reached from the root(s).
   1.218      ///
   1.219 -    ///\pre Either \ref run() or \ref start() must be called before
   1.220 -    ///using this function.
   1.221 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.222 +    ///must be called before using this function.
   1.223      Path path(Node t) const { return Path(*G, *_pred, t); }
   1.224  
   1.225 -    ///The distance of a node from the root.
   1.226 +    ///The distance of a node from the root(s).
   1.227  
   1.228 -    ///Returns the distance of a node from the root.
   1.229 +    ///Returns the distance of a node from the root(s).
   1.230      ///
   1.231 -    ///\warning If node \c v is not reachable from the root, then
   1.232 +    ///\warning If node \c v is not reached from the root(s), then
   1.233      ///the return value of this function is undefined.
   1.234      ///
   1.235 -    ///\pre Either \ref run() or \ref start() must be called before
   1.236 -    ///using this function.
   1.237 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.238 +    ///must be called before using this function.
   1.239      int dist(Node v) const { return (*_dist)[v]; }
   1.240  
   1.241      ///Returns the 'previous arc' of the %DFS tree for a node.
   1.242  
   1.243      ///This function returns the 'previous arc' of the %DFS tree for the
   1.244 -    ///node \c v, i.e. it returns the last arc of a %DFS path from the
   1.245 -    ///root to \c v. It is \c INVALID
   1.246 -    ///if \c v is not reachable from the root(s) or if \c v is a root.
   1.247 +    ///node \c v, i.e. it returns the last arc of a %DFS path from a
   1.248 +    ///root to \c v. It is \c INVALID if \c v is not reached from the
   1.249 +    ///root(s) or if \c v is a root.
   1.250      ///
   1.251      ///The %DFS tree used here is equal to the %DFS tree used in
   1.252      ///\ref predNode().
   1.253      ///
   1.254 -    ///\pre Either \ref run() or \ref start() must be called before using
   1.255 -    ///this function.
   1.256 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.257 +    ///must be called before using this function.
   1.258      Arc predArc(Node v) const { return (*_pred)[v];}
   1.259  
   1.260      ///Returns the 'previous node' of the %DFS tree.
   1.261  
   1.262      ///This function returns the 'previous node' of the %DFS
   1.263      ///tree for the node \c v, i.e. it returns the last but one node
   1.264 -    ///from a %DFS path from the root to \c v. It is \c INVALID
   1.265 -    ///if \c v is not reachable from the root(s) or if \c v is a root.
   1.266 +    ///from a %DFS path from a root to \c v. It is \c INVALID
   1.267 +    ///if \c v is not reached from the root(s) or if \c v is a root.
   1.268      ///
   1.269      ///The %DFS tree used here is equal to the %DFS tree used in
   1.270      ///\ref predArc().
   1.271      ///
   1.272 -    ///\pre Either \ref run() or \ref start() must be called before
   1.273 -    ///using this function.
   1.274 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.275 +    ///must be called before using this function.
   1.276      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   1.277                                    G->source((*_pred)[v]); }
   1.278  
   1.279 @@ -726,7 +725,7 @@
   1.280      ///Returns a const reference to the node map that stores the
   1.281      ///distances of the nodes calculated by the algorithm.
   1.282      ///
   1.283 -    ///\pre Either \ref run() or \ref init()
   1.284 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.285      ///must be called before using this function.
   1.286      const DistMap &distMap() const { return *_dist;}
   1.287  
   1.288 @@ -736,14 +735,15 @@
   1.289      ///Returns a const reference to the node map that stores the predecessor
   1.290      ///arcs, which form the DFS tree.
   1.291      ///
   1.292 -    ///\pre Either \ref run() or \ref init()
   1.293 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.294      ///must be called before using this function.
   1.295      const PredMap &predMap() const { return *_pred;}
   1.296  
   1.297 -    ///Checks if a node is reachable from the root(s).
   1.298 +    ///Checks if a node is reached from the root(s).
   1.299  
   1.300 -    ///Returns \c true if \c v is reachable from the root(s).
   1.301 -    ///\pre Either \ref run() or \ref start()
   1.302 +    ///Returns \c true if \c v is reached from the root(s).
   1.303 +    ///
   1.304 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.305      ///must be called before using this function.
   1.306      bool reached(Node v) const { return (*_reached)[v]; }
   1.307  
   1.308 @@ -889,8 +889,8 @@
   1.309  
   1.310    /// This auxiliary class is created to implement the
   1.311    /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
   1.312 -  /// It does not have own \ref run() method, it uses the functions
   1.313 -  /// and features of the plain \ref Dfs.
   1.314 +  /// It does not have own \ref run(Node) "run()" method, it uses the
   1.315 +  /// functions and features of the plain \ref Dfs.
   1.316    ///
   1.317    /// This class should only be used through the \ref dfs() function,
   1.318    /// which makes it easier to use the algorithm.
   1.319 @@ -1110,8 +1110,7 @@
   1.320    ///  // Compute the DFS path from s to t
   1.321    ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
   1.322    ///\endcode
   1.323 -
   1.324 -  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
   1.325 +  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
   1.326    ///to the end of the parameter list.
   1.327    ///\sa DfsWizard
   1.328    ///\sa Dfs
   1.329 @@ -1309,7 +1308,7 @@
   1.330  
   1.331      typedef DfsVisit Create;
   1.332  
   1.333 -    /// \name Named template parameters
   1.334 +    /// \name Named Template Parameters
   1.335  
   1.336      ///@{
   1.337      template <class T>
   1.338 @@ -1351,9 +1350,10 @@
   1.339      /// \brief Sets the map that indicates which nodes are reached.
   1.340      ///
   1.341      /// Sets the map that indicates which nodes are reached.
   1.342 -    /// If you don't use this function before calling \ref run(),
   1.343 -    /// it will allocate one. The destructor deallocates this
   1.344 -    /// automatically allocated map, of course.
   1.345 +    /// If you don't use this function before calling \ref run(Node) "run()"
   1.346 +    /// or \ref init(), an instance will be allocated automatically.
   1.347 +    /// The destructor deallocates this automatically allocated map,
   1.348 +    /// of course.
   1.349      /// \return <tt> (*this) </tt>
   1.350      DfsVisit &reachedMap(ReachedMap &m) {
   1.351        if(local_reached) {
   1.352 @@ -1366,16 +1366,14 @@
   1.353  
   1.354    public:
   1.355  
   1.356 -    /// \name Execution control
   1.357 -    /// The simplest way to execute the algorithm is to use
   1.358 -    /// one of the member functions called \ref lemon::DfsVisit::run()
   1.359 -    /// "run()".
   1.360 -    /// \n
   1.361 -    /// If you need more control on the execution, first you must call
   1.362 -    /// \ref lemon::DfsVisit::init() "init()", then you can add several
   1.363 -    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
   1.364 -    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
   1.365 -    /// actual path computation.
   1.366 +    /// \name Execution Control
   1.367 +    /// The simplest way to execute the DFS algorithm is to use one of the
   1.368 +    /// member functions called \ref run(Node) "run()".\n
   1.369 +    /// If you need more control on the execution, first you have to call
   1.370 +    /// \ref init(), then you can add a source node with \ref addSource()
   1.371 +    /// and perform the actual computation with \ref start().
   1.372 +    /// This procedure can be repeated if there are nodes that have not
   1.373 +    /// been reached.
   1.374  
   1.375      /// @{
   1.376  
   1.377 @@ -1391,15 +1389,14 @@
   1.378        }
   1.379      }
   1.380  
   1.381 -    ///Adds a new source node.
   1.382 -
   1.383 -    ///Adds a new source node to the set of nodes to be processed.
   1.384 +    /// \brief Adds a new source node.
   1.385      ///
   1.386 -    ///\pre The stack must be empty. (Otherwise the algorithm gives
   1.387 -    ///false results.)
   1.388 +    /// Adds a new source node to the set of nodes to be processed.
   1.389      ///
   1.390 -    ///\warning Distances will be wrong (or at least strange) in case of
   1.391 -    ///multiple sources.
   1.392 +    /// \pre The stack must be empty. Otherwise the algorithm gives
   1.393 +    /// wrong results. (One of the outgoing arcs of all the source nodes
   1.394 +    /// except for the last one will not be visited and distances will
   1.395 +    /// also be wrong.)
   1.396      void addSource(Node s)
   1.397      {
   1.398        LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   1.399 @@ -1589,8 +1586,8 @@
   1.400      /// compute the %DFS path to each node.
   1.401      ///
   1.402      /// The algorithm computes
   1.403 -    /// - the %DFS tree,
   1.404 -    /// - the distance of each node from the root in the %DFS tree.
   1.405 +    /// - the %DFS tree (forest),
   1.406 +    /// - the distance of each node from the root(s) in the %DFS tree.
   1.407      ///
   1.408      /// \note <tt>d.run()</tt> is just a shortcut of the following code.
   1.409      ///\code
   1.410 @@ -1615,17 +1612,18 @@
   1.411      ///@}
   1.412  
   1.413      /// \name Query Functions
   1.414 -    /// The result of the %DFS algorithm can be obtained using these
   1.415 +    /// The results of the DFS algorithm can be obtained using these
   1.416      /// functions.\n
   1.417 -    /// Either \ref lemon::DfsVisit::run() "run()" or
   1.418 -    /// \ref lemon::DfsVisit::start() "start()" must be called before
   1.419 -    /// using them.
   1.420 +    /// Either \ref run(Node) "run()" or \ref start() should be called
   1.421 +    /// before using them.
   1.422 +
   1.423      ///@{
   1.424  
   1.425 -    /// \brief Checks if a node is reachable from the root(s).
   1.426 +    /// \brief Checks if a node is reached from the root(s).
   1.427      ///
   1.428 -    /// Returns \c true if \c v is reachable from the root(s).
   1.429 -    /// \pre Either \ref run() or \ref start()
   1.430 +    /// Returns \c true if \c v is reached from the root(s).
   1.431 +    ///
   1.432 +    /// \pre Either \ref run(Node) "run()" or \ref init()
   1.433      /// must be called before using this function.
   1.434      bool reached(Node v) { return (*_reached)[v]; }
   1.435