COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 244:c30731a37f91 in lemon-1.2 for lemon/dfs.h


Ignore:
Timestamp:
08/03/08 13:34:57 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/dfs.h

    r210 r244  
    2222///\ingroup search
    2323///\file
    24 ///\brief Dfs algorithm.
     24///\brief DFS algorithm.
    2525
    2626#include <lemon/list_graph.h>
    … …  
    2929#include <lemon/bits/invalid.h>
    3030#include <lemon/error.h>
     31#include <lemon/assert.h>
    3132#include <lemon/maps.h>
    3233
    33 #include <lemon/concept_check.h>
    34 
    3534namespace lemon {
    36 
    3735
    3836  ///Default traits class of Dfs class.
    … …  
    4341  struct DfsDefaultTraits
    4442  {
    45     ///The digraph type the algorithm runs on.
     43    ///The type of the digraph the algorithm runs on.
    4644    typedef GR Digraph;
    47     ///\brief The type of the map that stores the last
     45
     46    ///\brief The type of the map that stores the predecessor
    4847    ///arcs of the %DFS paths.
    4948    ///
    50     ///The type of the map that stores the last
     49    ///The type of the map that stores the predecessor
    5150    ///arcs of the %DFS paths.
    5251    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    53     ///
    54     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    55     ///Instantiates a PredMap.
     52    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     53    ///Instantiates a \ref PredMap.
    5654
    5755    ///This function instantiates a \ref PredMap.
    58     ///\param G is the digraph, to which we would like to define the PredMap.
     56    ///\param g is the digraph, to which we would like to define the
     57    ///\ref PredMap.
    5958    ///\todo The digraph alone may be insufficient to initialize
    60     static PredMap *createPredMap(const GR &G)
    61     {
    62       return new PredMap(G);
     59    static PredMap *createPredMap(const Digraph &g)
     60    {
     61      return new PredMap(g);
    6362    }
    6463
    … …  
    6766    ///The type of the map that indicates which nodes are processed.
    6867    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    69     ///\todo named parameter to set this type, function to read and write.
     68    ///By default it is a NullMap.
    7069    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    71     ///Instantiates a ProcessedMap.
     70    ///Instantiates a \ref ProcessedMap.
    7271
    7372    ///This function instantiates a \ref ProcessedMap.
    … …  
    7574    ///we would like to define the \ref ProcessedMap
    7675#ifdef DOXYGEN
    77     static ProcessedMap *createProcessedMap(const GR &g)
     76    static ProcessedMap *createProcessedMap(const Digraph &g)
    7877#else
    79     static ProcessedMap *createProcessedMap(const GR &)
     78    static ProcessedMap *createProcessedMap(const Digraph &)
    8079#endif
    8180    {
    8281      return new ProcessedMap();
    8382    }
     83
    8484    ///The type of the map that indicates which nodes are reached.
    8585
    8686    ///The type of the map that indicates which nodes are reached.
     87    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     88    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     89    ///Instantiates a \ref ReachedMap.
     90
     91    ///This function instantiates a \ref ReachedMap.
     92    ///\param g is the digraph, to which
     93    ///we would like to define the \ref ReachedMap.
     94    static ReachedMap *createReachedMap(const Digraph &g)
     95    {
     96      return new ReachedMap(g);
     97    }
     98
     99    ///The type of the map that stores the distances of the nodes.
     100
     101    ///The type of the map that stores the distances of the nodes.
    87102    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    88     ///\todo named parameter to set this type, function to read and write.
    89     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    90     ///Instantiates a ReachedMap.
    91 
    92     ///This function instantiates a \ref ReachedMap.
    93     ///\param G is the digraph, to which
    94     ///we would like to define the \ref ReachedMap.
    95     static ReachedMap *createReachedMap(const GR &G)
    96     {
    97       return new ReachedMap(G);
    98     }
    99     ///The type of the map that stores the dists of the nodes.
    100 
    101     ///The type of the map that stores the dists of the nodes.
    102     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    103     ///
    104103    typedef typename Digraph::template NodeMap<int> DistMap;
    105     ///Instantiates a DistMap.
     104    ///Instantiates a \ref DistMap.
    106105
    107106    ///This function instantiates a \ref DistMap.
    108     ///\param G is the digraph, to which we would like to define
    109     ///the \ref DistMap
    110     static DistMap *createDistMap(const GR &G)
    111     {
    112       return new DistMap(G);
     107    ///\param g is the digraph, to which we would like to define the
     108    ///\ref DistMap.
     109    static DistMap *createDistMap(const Digraph &g)
     110    {
     111      return new DistMap(g);
    113112    }
    114113  };
    … …  
    119118  ///This class provides an efficient implementation of the %DFS algorithm.
    120119  ///
    121   ///\tparam GR The digraph type the algorithm runs on. The default value is
    122   ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
    123   ///is only passed to \ref DfsDefaultTraits.
     120  ///There is also a \ref dfs() "function type interface" for the DFS
     121  ///algorithm, which is convenient in the simplier cases and it can be
     122  ///used easier.
     123  ///
     124  ///\tparam GR The type of the digraph the algorithm runs on.
     125  ///The default value is \ref ListDigraph. The value of GR is not used
     126  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
    124127  ///\tparam TR Traits class to set various data types used by the algorithm.
    125128  ///The default traits class is
    … …  
    136139  class Dfs {
    137140  public:
    138     /**
    139      * \brief \ref Exception for uninitialized parameters.
    140      *
    141      * This error represents problems in the initialization
    142      * of the parameters of the algorithms.
    143      */
     141    ///\ref Exception for uninitialized parameters.
     142
     143    ///This error represents problems in the initialization of the
     144    ///parameters of the algorithm.
    144145    class UninitializedParameter : public lemon::UninitializedParameter {
    145146    public:
    … …  
    149150    };
    150151
     152    ///The type of the digraph the algorithm runs on.
     153    typedef typename TR::Digraph Digraph;
     154
     155    ///\brief The type of the map that stores the predecessor arcs of the
     156    ///DFS paths.
     157    typedef typename TR::PredMap PredMap;
     158    ///The type of the map that stores the distances of the nodes.
     159    typedef typename TR::DistMap DistMap;
     160    ///The type of the map that indicates which nodes are reached.
     161    typedef typename TR::ReachedMap ReachedMap;
     162    ///The type of the map that indicates which nodes are processed.
     163    typedef typename TR::ProcessedMap ProcessedMap;
     164    ///The type of the paths.
     165    typedef PredMapPath<Digraph, PredMap> Path;
     166
     167    ///The traits class.
    151168    typedef TR Traits;
    152     ///The type of the underlying digraph.
    153     typedef typename TR::Digraph Digraph;
    154     ///\e
     169
     170  private:
     171
    155172    typedef typename Digraph::Node Node;
    156     ///\e
    157173    typedef typename Digraph::NodeIt NodeIt;
    158     ///\e
    159174    typedef typename Digraph::Arc Arc;
    160     ///\e
    161175    typedef typename Digraph::OutArcIt OutArcIt;
    162176
    163     ///\brief The type of the map that stores the last
    164     ///arcs of the %DFS paths.
    165     typedef typename TR::PredMap PredMap;
    166     ///The type of the map indicating which nodes are reached.
    167     typedef typename TR::ReachedMap ReachedMap;
    168     ///The type of the map indicating which nodes are processed.
    169     typedef typename TR::ProcessedMap ProcessedMap;
    170     ///The type of the map that stores the dists of the nodes.
    171     typedef typename TR::DistMap DistMap;
    172   private:
    173     /// Pointer to the underlying digraph.
     177    //Pointer to the underlying digraph.
    174178    const Digraph *G;
    175     ///Pointer to the map of predecessors arcs.
     179    //Pointer to the map of predecessor arcs.
    176180    PredMap *_pred;
    177     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     181    //Indicates if _pred is locally allocated (true) or not.
    178182    bool local_pred;
    179     ///Pointer to the map of distances.
     183    //Pointer to the map of distances.
    180184    DistMap *_dist;
    181     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     185    //Indicates if _dist is locally allocated (true) or not.
    182186    bool local_dist;
    183     ///Pointer to the map of reached status of the nodes.
     187    //Pointer to the map of reached status of the nodes.
    184188    ReachedMap *_reached;
    185     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     189    //Indicates if _reached is locally allocated (true) or not.
    186190    bool local_reached;
    187     ///Pointer to the map of processed status of the nodes.
     191    //Pointer to the map of processed status of the nodes.
    188192    ProcessedMap *_processed;
    189     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     193    //Indicates if _processed is locally allocated (true) or not.
    190194    bool local_processed;
    191195
    … …  
    194198
    195199    ///Creates the maps if necessary.
    196 
    197200    ///\todo Better memory allocation (instead of new).
    198201    void create_maps()
    … …  
    231234    struct DefPredMapTraits : public Traits {
    232235      typedef T PredMap;
    233       static PredMap *createPredMap(const Digraph &G)
     236      static PredMap *createPredMap(const Digraph &)
    234237      {
    235238        throw UninitializedParameter();
    … …  
    237240    };
    238241    ///\brief \ref named-templ-param "Named parameter" for setting
    239     ///PredMap type
    240     ///
    241     ///\ref named-templ-param "Named parameter" for setting PredMap type
    242     ///
     242    ///\ref PredMap type.
     243    ///
     244    ///\ref named-templ-param "Named parameter" for setting
     245    ///\ref PredMap type.
    243246    template <class T>
    244247    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
    245248      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
    246249    };
    247 
    248250
    249251    template <class T>
    … …  
    256258    };
    257259    ///\brief \ref named-templ-param "Named parameter" for setting
    258     ///DistMap type
    259     ///
    260     ///\ref named-templ-param "Named parameter" for setting DistMap
    261     ///type
     260    ///\ref DistMap type.
     261    ///
     262    ///\ref named-templ-param "Named parameter" for setting
     263    ///\ref DistMap type.
    262264    template <class T>
    263     struct DefDistMap {
     265    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
    264266      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
    265267    };
    … …  
    274276    };
    275277    ///\brief \ref named-templ-param "Named parameter" for setting
    276     ///ReachedMap type
    277     ///
    278     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    279     ///
     278    ///\ref ReachedMap type.
     279    ///
     280    ///\ref named-templ-param "Named parameter" for setting
     281    ///\ref ReachedMap type.
    280282    template <class T>
    281283    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
    … …  
    292294    };
    293295    ///\brief \ref named-templ-param "Named parameter" for setting
    294     ///ProcessedMap type
    295     ///
    296     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    297     ///
     296    ///\ref ProcessedMap type.
     297    ///
     298    ///\ref named-templ-param "Named parameter" for setting
     299    ///\ref ProcessedMap type.
    298300    template <class T>
    299301    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
    … …  
    303305    struct DefDigraphProcessedMapTraits : public Traits {
    304306      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    305       static ProcessedMap *createProcessedMap(const Digraph &G)
     307      static ProcessedMap *createProcessedMap(const Digraph &g)
    306308      {
    307         return new ProcessedMap(G);
    308       }
    309     };
    310     ///\brief \ref named-templ-param "Named parameter"
    311     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    312     ///
    313     ///\ref named-templ-param "Named parameter"
    314     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    315     ///If you don't set it explicitely, it will be automatically allocated.
     309        return new ProcessedMap(g);
     310      }
     311    };
     312    ///\brief \ref named-templ-param "Named parameter" for setting
     313    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     314    ///
     315    ///\ref named-templ-param "Named parameter" for setting
     316    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     317    ///If you don't set it explicitly, it will be automatically allocated.
    316318    template <class T>
    317     class DefProcessedMapToBeDefaultMap :
     319    struct DefProcessedMapToBeDefaultMap :
    318320      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
    319321      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
    … …  
    326328    ///Constructor.
    327329
    328     ///\param _G the digraph the algorithm will run on.
    329     ///
    330     Dfs(const Digraph& _G) :
    331       G(&_G),
     330    ///Constructor.
     331    ///\param g The digraph the algorithm runs on.
     332    Dfs(const Digraph &g) :
     333      G(&g),
    332334      _pred(NULL), local_pred(false),
    333335      _dist(NULL), local_dist(false),
    … …  
    345347    }
    346348
    347     ///Sets the map storing the predecessor arcs.
    348 
    349     ///Sets the map storing the predecessor arcs.
     349    ///Sets the map that stores the predecessor arcs.
     350
     351    ///Sets the map that stores the predecessor arcs.
    350352    ///If you don't use this function before calling \ref run(),
    351     ///it will allocate one. The destuctor deallocates this
     353    ///it will allocate one. The destructor deallocates this
    352354    ///automatically allocated map, of course.
    353355    ///\return <tt> (*this) </tt>
    … …  
    362364    }
    363365
    364     ///Sets the map storing the distances calculated by the algorithm.
    365 
    366     ///Sets the map storing the distances calculated by the algorithm.
     366    ///Sets the map that indicates which nodes are reached.
     367
     368    ///Sets the map that indicates which nodes are reached.
    367369    ///If you don't use this function before calling \ref run(),
    368     ///it will allocate one. The destuctor deallocates this
     370    ///it will allocate one. The destructor deallocates this
     371    ///automatically allocated map, of course.
     372    ///\return <tt> (*this) </tt>
     373    Dfs &reachedMap(ReachedMap &m)
     374    {
     375      if(local_reached) {
     376        delete _reached;
     377        local_reached=false;
     378      }
     379      _reached = &m;
     380      return *this;
     381    }
     382
     383    ///Sets the map that indicates which nodes are processed.
     384
     385    ///Sets the map that indicates which nodes are processed.
     386    ///If you don't use this function before calling \ref run(),
     387    ///it will allocate one. The destructor deallocates this
     388    ///automatically allocated map, of course.
     389    ///\return <tt> (*this) </tt>
     390    Dfs &processedMap(ProcessedMap &m)
     391    {
     392      if(local_processed) {
     393        delete _processed;
     394        local_processed=false;
     395      }
     396      _processed = &m;
     397      return *this;
     398    }
     399
     400    ///Sets the map that stores the distances of the nodes.
     401
     402    ///Sets the map that stores the distances of the nodes calculated by
     403    ///the algorithm.
     404    ///If you don't use this function before calling \ref run(),
     405    ///it will allocate one. The destructor deallocates this
    369406    ///automatically allocated map, of course.
    370407    ///\return <tt> (*this) </tt>
    … …  
    379416    }
    380417
    381     ///Sets the map indicating if a node is reached.
    382 
    383     ///Sets the map indicating if a node is reached.
    384     ///If you don't use this function before calling \ref run(),
    385     ///it will allocate one. The destuctor deallocates this
    386     ///automatically allocated map, of course.
    387     ///\return <tt> (*this) </tt>
    388     Dfs &reachedMap(ReachedMap &m)
    389     {
    390       if(local_reached) {
    391         delete _reached;
    392         local_reached=false;
    393       }
    394       _reached = &m;
    395       return *this;
    396     }
    397 
    398     ///Sets the map indicating if a node is processed.
    399 
    400     ///Sets the map indicating if a node is processed.
    401     ///If you don't use this function before calling \ref run(),
    402     ///it will allocate one. The destuctor deallocates this
    403     ///automatically allocated map, of course.
    404     ///\return <tt> (*this) </tt>
    405     Dfs &processedMap(ProcessedMap &m)
    406     {
    407       if(local_processed) {
    408         delete _processed;
    409         local_processed=false;
    410       }
    411       _processed = &m;
    412       return *this;
    413     }
    414 
    415418  public:
     419
    416420    ///\name Execution control
    417421    ///The simplest way to execute the algorithm is to use
    418     ///one of the member functions called \c run(...).
     422    ///one of the member functions called \ref lemon::Dfs::run() "run()".
    419423    ///\n
    420     ///If you need more control on the execution,
    421     ///first you must call \ref init(), then you can add a source node
    422     ///with \ref addSource().
    423     ///Finally \ref start() will perform the actual path
    424     ///computation.
     424    ///If you need more control on the execution, first you must call
     425    ///\ref lemon::Dfs::init() "init()", then you can add a source node
     426    ///with \ref lemon::Dfs::addSource() "addSource()".
     427    ///Finally \ref lemon::Dfs::start() "start()" will perform the
     428    ///actual path computation.
    425429
    426430    ///@{
    … …  
    437441      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    438442        _pred->set(u,INVALID);
    439         // _predNode->set(u,INVALID);
    440443        _reached->set(u,false);
    441444        _processed->set(u,false);
    … …  
    447450    ///Adds a new source node to the set of nodes to be processed.
    448451    ///
    449     ///\warning dists are wrong (or at least strange)
    450     ///in case of multiple sources.
     452    ///\pre The stack must be empty. (Otherwise the algorithm gives
     453    ///false results.)
     454    ///
     455    ///\warning Distances will be wrong (or at least strange) in case of
     456    ///multiple sources.
    451457    void addSource(Node s)
    452458    {
     459      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
    453460      if(!(*_reached)[s])
    454461        {
    … …  
    473480    ///\return The processed arc.
    474481    ///
    475     ///\pre The stack must not be empty!
     482    ///\pre The stack must not be empty.
    476483    Arc processNextArc()
    477484    {
    … …  
    499506      return e;
    500507    }
     508
    501509    ///Next arc to be processed.
    502510
    503511    ///Next arc to be processed.
    504512    ///
    505     ///\return The next arc to be processed or INVALID if the stack is
    506     /// empty.
    507     OutArcIt nextArc()
     513    ///\return The next arc to be processed or \c INVALID if the stack
     514    ///is empty.
     515    OutArcIt nextArc() const
    508516    {
    509517      return _stack_head>=0?_stack[_stack_head]:INVALID;
    … …  
    511519
    512520    ///\brief Returns \c false if there are nodes
    513     ///to be processed in the queue
     521    ///to be processed.
    514522    ///
    515523    ///Returns \c false if there are nodes
    516     ///to be processed in the queue
    517     bool emptyQueue() { return _stack_head<0; }
     524    ///to be processed in the queue (stack).
     525    bool emptyQueue() const { return _stack_head<0; }
     526
    518527    ///Returns the number of the nodes to be processed.
    519528
    520     ///Returns the number of the nodes to be processed in the queue.
    521     int queueSize() { return _stack_head+1; }
     529    ///Returns the number of the nodes to be processed in the queue (stack).
     530    int queueSize() const { return _stack_head+1; }
    522531
    523532    ///Executes the algorithm.
    … …  
    525534    ///Executes the algorithm.
    526535    ///
    527     ///\pre init() must be called and at least one node should be added
    528     ///with addSource() before using this function.
    529     ///
    530     ///This method runs the %DFS algorithm from the root node(s)
    531     ///in order to
    532     ///compute the
    533     ///%DFS path to each node. The algorithm computes
    534     ///- The %DFS tree.
    535     ///- The distance of each node from the root(s) in the %DFS tree.
    536     ///
     536    ///This method runs the %DFS algorithm from the root node
     537    ///in order to compute the DFS path to each node.
     538    ///
     539    /// The algorithm computes
     540    ///- the %DFS tree,
     541    ///- the distance of each node from the root in the %DFS tree.
     542    ///
     543    ///\pre init() must be called and a root node should be
     544    ///added with addSource() before using this function.
     545    ///
     546    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
     547    ///\code
     548    ///  while ( !d.emptyQueue() ) {
     549    ///    d.processNextArc();
     550    ///  }
     551    ///\endcode
    537552    void start()
    538553    {
    … …  
    540555    }
    541556
    542     ///Executes the algorithm until \c dest is reached.
    543 
    544     ///Executes the algorithm until \c dest is reached.
    545     ///
    546     ///\pre init() must be called and at least one node should be added
    547     ///with addSource() before using this function.
    548     ///
    549     ///This method runs the %DFS algorithm from the root node(s)
    550     ///in order to
    551     ///compute the
    552     ///%DFS path to \c dest. The algorithm computes
    553     ///- The %DFS path to \c  dest.
    554     ///- The distance of \c dest from the root(s) in the %DFS tree.
    555     ///
     557    ///Executes the algorithm until the given target node is reached.
     558
     559    ///Executes the algorithm until the given target node is reached.
     560    ///
     561    ///This method runs the %DFS algorithm from the root node
     562    ///in order to compute the DFS path to \c dest.
     563    ///
     564    ///The algorithm computes
     565    ///- the %DFS path to \c dest,
     566    ///- the distance of \c dest from the root in the %DFS tree.
     567    ///
     568    ///\pre init() must be called and a root node should be
     569    ///added with addSource() before using this function.
    556570    void start(Node dest)
    557571    {
    … …  
    564578    ///Executes the algorithm until a condition is met.
    565579    ///
    566     ///\pre init() must be called and at least one node should be added
    567     ///with addSource() before using this function.
    568     ///
    569     ///\param em must be a bool (or convertible) arc map. The algorithm
    570     ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
    571     ///
    572     ///\return The reached arc \c e with <tt>em[e]</tt> true or
     580    ///This method runs the %DFS algorithm from the root node
     581    ///until an arc \c a with <tt>am[a]</tt> true is found.
     582    ///
     583    ///\param am A \c bool (or convertible) arc map. The algorithm
     584    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
     585    ///
     586    ///\return The reached arc \c a with <tt>am[a]</tt> true or
    573587    ///\c INVALID if no such arc was found.
    574588    ///
    575     ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
     589    ///\pre init() must be called and a root node should be
     590    ///added with addSource() before using this function.
     591    ///
     592    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
    576593    ///not a node map.
    577     template<class EM>
    578     Arc start(const EM &em)
    579     {
    580       while ( !emptyQueue() && !em[_stack[_stack_head]] )
     594    template<class ArcBoolMap>
     595    Arc start(const ArcBoolMap &am)
     596    {
     597      while ( !emptyQueue() && !am[_stack[_stack_head]] )
    581598        processNextArc();
    582599      return emptyQueue() ? INVALID : _stack[_stack_head];
    583600    }
    584601
    585     ///Runs %DFS algorithm to visit all nodes in the digraph.
    586 
    587     ///This method runs the %DFS algorithm in order to
    588     ///compute the
    589     ///%DFS path to each node. The algorithm computes
    590     ///- The %DFS tree.
    591     ///- The distance of each node from the root in the %DFS tree.
    592     ///
    593     ///\note d.run() is just a shortcut of the following code.
     602    ///Runs the algorithm from the given node.
     603
     604    ///This method runs the %DFS algorithm from node \c s
     605    ///in order to compute the DFS path to each node.
     606    ///
     607    ///The algorithm computes
     608    ///- the %DFS tree,
     609    ///- the distance of each node from the root in the %DFS tree.
     610    ///
     611    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
    594612    ///\code
    595613    ///  d.init();
    596     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    597     ///    if (!d.reached(it)) {
    598     ///      d.addSource(it);
     614    ///  d.addSource(s);
     615    ///  d.start();
     616    ///\endcode
     617    void run(Node s) {
     618      init();
     619      addSource(s);
     620      start();
     621    }
     622
     623    ///Finds the %DFS path between \c s and \c t.
     624
     625    ///This method runs the %DFS algorithm from node \c s
     626    ///in order to compute the DFS path to \c t.
     627    ///
     628    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
     629    ///if \c t is reachable form \c s, \c 0 otherwise.
     630    ///
     631    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
     632    ///just a shortcut of the following code.
     633    ///\code
     634    ///  d.init();
     635    ///  d.addSource(s);
     636    ///  d.start(t);
     637    ///\endcode
     638    int run(Node s,Node t) {
     639      init();
     640      addSource(s);
     641      start(t);
     642      return reached(t)?_stack_head+1:0;
     643    }
     644
     645    ///Runs the algorithm to visit all nodes in the digraph.
     646
     647    ///This method runs the %DFS algorithm in order to compute the
     648    ///%DFS path to each node.
     649    ///
     650    ///The algorithm computes
     651    ///- the %DFS tree,
     652    ///- the distance of each node from the root in the %DFS tree.
     653    ///
     654    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     655    ///\code
     656    ///  d.init();
     657    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
     658    ///    if (!d.reached(n)) {
     659    ///      d.addSource(n);
    599660    ///      d.start();
    600661    ///    }
    … …  
    611672    }
    612673
    613     ///Runs %DFS algorithm from node \c s.
    614 
    615     ///This method runs the %DFS algorithm from a root node \c s
    616     ///in order to
    617     ///compute the
    618     ///%DFS path to each node. The algorithm computes
    619     ///- The %DFS tree.
    620     ///- The distance of each node from the root in the %DFS tree.
    621     ///
    622     ///\note d.run(s) is just a shortcut of the following code.
    623     ///\code
    624     ///  d.init();
    625     ///  d.addSource(s);
    626     ///  d.start();
    627     ///\endcode
    628     void run(Node s) {
    629       init();
    630       addSource(s);
    631       start();
    632     }
    633 
    634     ///Finds the %DFS path between \c s and \c t.
    635 
    636     ///Finds the %DFS path between \c s and \c t.
    637     ///
    638     ///\return The length of the %DFS s---t path if there exists one,
    639     ///0 otherwise.
    640     ///\note Apart from the return value, d.run(s,t) is
    641     ///just a shortcut of the following code.
    642     ///\code
    643     ///  d.init();
    644     ///  d.addSource(s);
    645     ///  d.start(t);
    646     ///\endcode
    647     int run(Node s,Node t) {
    648       init();
    649       addSource(s);
    650       start(t);
    651       return reached(t)?_stack_head+1:0;
    652     }
    653 
    654674    ///@}
    655675
    … …  
    657677    ///The result of the %DFS algorithm can be obtained using these
    658678    ///functions.\n
    659     ///Before the use of these functions,
    660     ///either run() or start() must be called.
     679    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
     680    ///"start()" must be called before using them.
    661681
    662682    ///@{
    663683
    664     typedef PredMapPath<Digraph, PredMap> Path;
    665 
    666     ///Gives back the shortest path.
    667 
    668     ///Gives back the shortest path.
    669     ///\pre The \c t should be reachable from the source.
    670     Path path(Node t)
    671     {
    672       return Path(*G, *_pred, t);
    673     }
    674 
    675     ///The distance of a node from the root(s).
    676 
    677     ///Returns the distance of a node from the root(s).
    678     ///\pre \ref run() must be called before using this function.
    679     ///\warning If node \c v is unreachable from the root(s) then the return
    680     ///value of this funcion is undefined.
     684    ///The DFS path to a node.
     685
     686    ///Returns the DFS path to a node.
     687    ///
     688    ///\warning \c t should be reachable from the root.
     689    ///
     690    ///\pre Either \ref run() or \ref start() must be called before
     691    ///using this function.
     692    Path path(Node t) const { return Path(*G, *_pred, t); }
     693
     694    ///The distance of a node from the root.
     695
     696    ///Returns the distance of a node from the root.
     697    ///
     698    ///\warning If node \c v is not reachable from the root, then
     699    ///the return value of this function is undefined.
     700    ///
     701    ///\pre Either \ref run() or \ref start() must be called before
     702    ///using this function.
    681703    int dist(Node v) const { return (*_dist)[v]; }
    682704
    683     ///Returns the 'previous arc' of the %DFS tree.
    684 
    685     ///For a node \c v it returns the 'previous arc'
    686     ///of the %DFS path,
    687     ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
    688     ///v. It is \ref INVALID
    689     ///if \c v is unreachable from the root(s) or \c v is a root. The
    690     ///%DFS tree used here is equal to the %DFS tree used in
     705    ///Returns the 'previous arc' of the %DFS tree for a node.
     706
     707    ///This function returns the 'previous arc' of the %DFS tree for the
     708    ///node \c v, i.e. it returns the last arc of a %DFS path from the
     709    ///root to \c v. It is \c INVALID
     710    ///if \c v is not reachable from the root(s) or if \c v is a root.
     711    ///
     712    ///The %DFS tree used here is equal to the %DFS tree used in
    691713    ///\ref predNode().
     714    ///
    692715    ///\pre Either \ref run() or \ref start() must be called before using
    693716    ///this function.
    … …  
    696719    ///Returns the 'previous node' of the %DFS tree.
    697720
    698     ///For a node \c v it returns the 'previous node'
    699     ///of the %DFS tree,
    700     ///i.e. it returns the last but one node from a %DFS path from the
    701     ///root(s) to \c v.
    702     ///It is INVALID if \c v is unreachable from the root(s) or
    703     ///if \c v itself a root.
    704     ///The %DFS tree used here is equal to the %DFS
    705     ///tree used in \ref predArc().
     721    ///This function returns the 'previous node' of the %DFS
     722    ///tree for the node \c v, i.e. it returns the last but one node
     723    ///from a %DFS path from the root to \c v. It is \c INVALID
     724    ///if \c v is not reachable from the root(s) or if \c v is a root.
     725    ///
     726    ///The %DFS tree used here is equal to the %DFS tree used in
     727    ///\ref predArc().
     728    ///
    706729    ///\pre Either \ref run() or \ref start() must be called before
    707730    ///using this function.
    … …  
    709732                                  G->source((*_pred)[v]); }
    710733
    711     ///Returns a reference to the NodeMap of distances.
    712 
    713     ///Returns a reference to the NodeMap of distances.
    714     ///\pre Either \ref run() or \ref init() must
    715     ///be called before using this function.
     734    ///\brief Returns a const reference to the node map that stores the
     735    ///distances of the nodes.
     736    ///
     737    ///Returns a const reference to the node map that stores the
     738    ///distances of the nodes calculated by the algorithm.
     739    ///
     740    ///\pre Either \ref run() or \ref init()
     741    ///must be called before using this function.
    716742    const DistMap &distMap() const { return *_dist;}
    717743
    718     ///Returns a reference to the %DFS arc-tree map.
    719 
    720     ///Returns a reference to the NodeMap of the arcs of the
    721     ///%DFS tree.
     744    ///\brief Returns a const reference to the node map that stores the
     745    ///predecessor arcs.
     746    ///
     747    ///Returns a const reference to the node map that stores the predecessor
     748    ///arcs, which form the DFS tree.
     749    ///
    722750    ///\pre Either \ref run() or \ref init()
    723751    ///must be called before using this function.
    724752    const PredMap &predMap() const { return *_pred;}
    725753
    726     ///Checks if a node is reachable from the root.
     754    ///Checks if a node is reachable from the root(s).
    727755
    728756    ///Returns \c true if \c v is reachable from the root(s).
    729     ///\warning The source nodes are inditated as unreachable.
    730757    ///\pre Either \ref run() or \ref start()
    731758    ///must be called before using this function.
    732     ///
    733     bool reached(Node v) { return (*_reached)[v]; }
     759    bool reached(Node v) const { return (*_reached)[v]; }
    734760
    735761    ///@}
    736762  };
    737763
    738   ///Default traits class of Dfs function.
    739 
    740   ///Default traits class of Dfs function.
     764  ///Default traits class of dfs() function.
     765
     766  ///Default traits class of dfs() function.
    741767  ///\tparam GR Digraph type.
    742768  template<class GR>
    743769  struct DfsWizardDefaultTraits
    744770  {
    745     ///The digraph type the algorithm runs on.
     771    ///The type of the digraph the algorithm runs on.
    746772    typedef GR Digraph;
    747     ///\brief The type of the map that stores the last
     773
     774    ///\brief The type of the map that stores the predecessor
    748775    ///arcs of the %DFS paths.
    749776    ///
    750     ///The type of the map that stores the last
     777    ///The type of the map that stores the predecessor
    751778    ///arcs of the %DFS paths.
    752779    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    753780    ///
    754     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
    755     ///Instantiates a PredMap.
     781    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     782    ///Instantiates a \ref PredMap.
    756783
    757784    ///This function instantiates a \ref PredMap.
    758     ///\param g is the digraph, to which we would like to define the PredMap.
     785    ///\param g is the digraph, to which we would like to define the
     786    ///\ref PredMap.
    759787    ///\todo The digraph alone may be insufficient to initialize
    760788#ifdef DOXYGEN
    761     static PredMap *createPredMap(const GR &g)
     789    static PredMap *createPredMap(const Digraph &g)
    762790#else
    763     static PredMap *createPredMap(const GR &)
     791    static PredMap *createPredMap(const Digraph &)
    764792#endif
    765793    {
    … …  
    771799    ///The type of the map that indicates which nodes are processed.
    772800    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    773     ///\todo named parameter to set this type, function to read and write.
    774801    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    775     ///Instantiates a ProcessedMap.
     802    ///Instantiates a \ref ProcessedMap.
    776803
    777804    ///This function instantiates a \ref ProcessedMap.
    778805    ///\param g is the digraph, to which
    779     ///we would like to define the \ref ProcessedMap
     806    ///we would like to define the \ref ProcessedMap.
    780807#ifdef DOXYGEN
    781     static ProcessedMap *createProcessedMap(const GR &g)
     808    static ProcessedMap *createProcessedMap(const Digraph &g)
    782809#else
    783     static ProcessedMap *createProcessedMap(const GR &)
     810    static ProcessedMap *createProcessedMap(const Digraph &)
    784811#endif
    785812    {
    786813      return new ProcessedMap();
    787814    }
     815
    788816    ///The type of the map that indicates which nodes are reached.
    789817
    790818    ///The type of the map that indicates which nodes are reached.
     819    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     820    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     821    ///Instantiates a \ref ReachedMap.
     822
     823    ///This function instantiates a \ref ReachedMap.
     824    ///\param g is the digraph, to which
     825    ///we would like to define the \ref ReachedMap.
     826    static ReachedMap *createReachedMap(const Digraph &g)
     827    {
     828      return new ReachedMap(g);
     829    }
     830
     831    ///The type of the map that stores the distances of the nodes.
     832
     833    ///The type of the map that stores the distances of the nodes.
    791834    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    792     ///\todo named parameter to set this type, function to read and write.
    793     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    794     ///Instantiates a ReachedMap.
    795 
    796     ///This function instantiates a \ref ReachedMap.
    797     ///\param G is the digraph, to which
    798     ///we would like to define the \ref ReachedMap.
    799     static ReachedMap *createReachedMap(const GR &G)
    800     {
    801       return new ReachedMap(G);
    802     }
    803     ///The type of the map that stores the dists of the nodes.
    804 
    805     ///The type of the map that stores the dists of the nodes.
    806     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    807835    ///
    808836    typedef NullMap<typename Digraph::Node,int> DistMap;
    809     ///Instantiates a DistMap.
     837    ///Instantiates a \ref DistMap.
    810838
    811839    ///This function instantiates a \ref DistMap.
    … …  
    813841    ///the \ref DistMap
    814842#ifdef DOXYGEN
    815     static DistMap *createDistMap(const GR &g)
     843    static DistMap *createDistMap(const Digraph &g)
    816844#else
    817     static DistMap *createDistMap(const GR &)
     845    static DistMap *createDistMap(const Digraph &)
    818846#endif
    819847    {
    … …  
    822850  };
    823851
    824   /// Default traits used by \ref DfsWizard
     852  /// Default traits class used by \ref DfsWizard
    825853
    826854  /// To make it easier to use Dfs algorithm
    827   ///we have created a wizard class.
     855  /// we have created a wizard class.
    828856  /// This \ref DfsWizard class needs default traits,
    829   ///as well as the \ref Dfs class.
     857  /// as well as the \ref Dfs class.
    830858  /// The \ref DfsWizardBase is a class to be the default traits of the
    831859  /// \ref DfsWizard class.
    … …  
    836864    typedef DfsWizardDefaultTraits<GR> Base;
    837865  protected:
    838     /// Type of the nodes in the digraph.
     866    //The type of the nodes in the digraph.
    839867    typedef typename Base::Digraph::Node Node;
    840868
    841     /// Pointer to the underlying digraph.
     869    //Pointer to the digraph the algorithm runs on.
    842870    void *_g;
    843     ///Pointer to the map of reached nodes.
     871    //Pointer to the map of reached nodes.
    844872    void *_reached;
    845     ///Pointer to the map of processed nodes.
     873    //Pointer to the map of processed nodes.
    846874    void *_processed;
    847     ///Pointer to the map of predecessors arcs.
     875    //Pointer to the map of predecessors arcs.
    848876    void *_pred;
    849     ///Pointer to the map of distances.
     877    //Pointer to the map of distances.
    850878    void *_dist;
    851     ///Pointer to the source node.
     879    //Pointer to the source node.
    852880    Node _source;
    853881
    … …  
    858886    /// all of the attributes to default values (0, INVALID).
    859887    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    860                            _dist(0), _source(INVALID) {}
     888                      _dist(0), _source(INVALID) {}
    861889
    862890    /// Constructor.
    … …  
    865893    /// listed in the parameters list.
    866894    /// Others are initiated to 0.
    867     /// \param g is the initial value of  \ref _g
    868     /// \param s is the initial value of  \ref _source
     895    /// \param g The digraph the algorithm runs on.
     896    /// \param s The source node.
    869897    DfsWizardBase(const GR &g, Node s=INVALID) :
    870898      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    … …  
    873901  };
    874902
    875   /// A class to make the usage of the Dfs algorithm easier
    876 
    877   /// This class is created to make it easier to use the Dfs algorithm.
    878   /// It uses the functions and features of the plain \ref Dfs,
    879   /// but it is much simpler to use it.
     903  /// Auxiliary class for the function type interface of DFS algorithm.
     904
     905  /// This auxiliary class is created to implement the function type
     906  /// interface of \ref Dfs algorithm. It uses the functions and features
     907  /// of the plain \ref Dfs, but it is much simpler to use it.
     908  /// It should only be used through the \ref dfs() function, which makes
     909  /// it easier to use the algorithm.
    880910  ///
    881911  /// Simplicity means that the way to change the types defined
    … …  
    886916  /// the original class by using the ::
    887917  /// operator. In the case of \ref DfsWizard only
    888   /// a function have to be called and it will
     918  /// a function have to be called, and it will
    889919  /// return the needed class.
    890920  ///
    891   /// It does not have own \ref run method. When its \ref run method is called
    892   /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
    893   /// method of it.
     921  /// It does not have own \ref run() method. When its \ref run() method
     922  /// is called, it initiates a plain \ref Dfs object, and calls the
     923  /// \ref Dfs::run() method of it.
    894924  template<class TR>
    895925  class DfsWizard : public TR
    … …  
    897927    typedef TR Base;
    898928
    899     ///The type of the underlying digraph.
     929    ///The type of the digraph the algorithm runs on.
    900930    typedef typename TR::Digraph Digraph;
    901     //\e
     931
    902932    typedef typename Digraph::Node Node;
    903     //\e
    904933    typedef typename Digraph::NodeIt NodeIt;
    905     //\e
    906934    typedef typename Digraph::Arc Arc;
    907     //\e
    908935    typedef typename Digraph::OutArcIt OutArcIt;
    909936
    910     ///\brief The type of the map that stores
    911     ///the reached nodes
     937    ///\brief The type of the map that stores the predecessor
     938    ///arcs of the shortest paths.
     939    typedef typename TR::PredMap PredMap;
     940    ///\brief The type of the map that stores the distances of the nodes.
     941    typedef typename TR::DistMap DistMap;
     942    ///\brief The type of the map that indicates which nodes are reached.
    912943    typedef typename TR::ReachedMap ReachedMap;
    913     ///\brief The type of the map that stores
    914     ///the processed nodes
     944    ///\brief The type of the map that indicates which nodes are processed.
    915945    typedef typename TR::ProcessedMap ProcessedMap;
    916     ///\brief The type of the map that stores the last
    917     ///arcs of the %DFS paths.
    918     typedef typename TR::PredMap PredMap;
    919     ///The type of the map that stores the distances of the nodes.
    920     typedef typename TR::DistMap DistMap;
    921946
    922947  public:
     948
    923949    /// Constructor.
    924950    DfsWizard() : TR() {}
    … …  
    936962    ~DfsWizard() {}
    937963
    938     ///Runs Dfs algorithm from a given node.
    939 
    940     ///Runs Dfs algorithm from a given node.
    941     ///The node can be given by the \ref source function.
     964    ///Runs DFS algorithm from a source node.
     965
     966    ///Runs DFS algorithm from a source node.
     967    ///The node can be given with the \ref source() function.
    942968    void run()
    943969    {
    … …  
    955981    }
    956982
    957     ///Runs Dfs algorithm from the given node.
    958 
    959     ///Runs Dfs algorithm from the given node.
     983    ///Runs DFS algorithm from the given node.
     984
     985    ///Runs DFS algorithm from the given node.
    960986    ///\param s is the given source.
    961987    void run(Node s)
    … …  
    963989      Base::_source=s;
    964990      run();
     991    }
     992
     993    /// Sets the source node, from which the Dfs algorithm runs.
     994
     995    /// Sets the source node, from which the Dfs algorithm runs.
     996    /// \param s is the source node.
     997    DfsWizard<TR> &source(Node s)
     998    {
     999      Base::_source=s;
     1000      return *this;
    9651001    }
    9661002
    … …  
    9711007      DefPredMapBase(const TR &b) : TR(b) {}
    9721008    };
    973 
    9741009    ///\brief \ref named-templ-param "Named parameter"
    975     ///function for setting PredMap type
    976     ///
    977     /// \ref named-templ-param "Named parameter"
    978     ///function for setting PredMap type
    979     ///
     1010    ///for setting \ref PredMap object.
     1011    ///
     1012    ///\ref named-templ-param "Named parameter"
     1013    ///for setting \ref PredMap object.
    9801014    template<class T>
    9811015    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
    … …  
    9841018      return DfsWizard<DefPredMapBase<T> >(*this);
    9851019    }
    986 
    9871020
    9881021    template<class T>
    … …  
    9921025      DefReachedMapBase(const TR &b) : TR(b) {}
    9931026    };
    994 
    9951027    ///\brief \ref named-templ-param "Named parameter"
    996     ///function for setting ReachedMap
     1028    ///for setting \ref ReachedMap object.
    9971029    ///
    9981030    /// \ref named-templ-param "Named parameter"
    999     ///function for setting ReachedMap
    1000     ///
     1031    ///for setting \ref ReachedMap object.
    10011032    template<class T>
    10021033    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
    … …  
    10051036      return DfsWizard<DefReachedMapBase<T> >(*this);
    10061037    }
    1007 
    10081038
    10091039    template<class T>
    … …  
    10131043      DefProcessedMapBase(const TR &b) : TR(b) {}
    10141044    };
    1015 
    10161045    ///\brief \ref named-templ-param "Named parameter"
    1017     ///function for setting ProcessedMap
     1046    ///for setting \ref ProcessedMap object.
    10181047    ///
    10191048    /// \ref named-templ-param "Named parameter"
    1020     ///function for setting ProcessedMap
    1021     ///
     1049    ///for setting \ref ProcessedMap object.
    10221050    template<class T>
    10231051    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
    … …  
    10331061      DefDistMapBase(const TR &b) : TR(b) {}
    10341062    };
    1035 
    10361063    ///\brief \ref named-templ-param "Named parameter"
    1037     ///function for setting DistMap type
    1038     ///
    1039     /// \ref named-templ-param "Named parameter"
    1040     ///function for setting DistMap type
    1041     ///
     1064    ///for setting \ref DistMap object.
     1065    ///
     1066    ///\ref named-templ-param "Named parameter"
     1067    ///for setting \ref DistMap object.
    10421068    template<class T>
    10431069    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
    … …  
    10451071      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    10461072      return DfsWizard<DefDistMapBase<T> >(*this);
    1047     }
    1048 
    1049     /// Sets the source node, from which the Dfs algorithm runs.
    1050 
    1051     /// Sets the source node, from which the Dfs algorithm runs.
    1052     /// \param s is the source node.
    1053     DfsWizard<TR> &source(Node s)
    1054     {
    1055       Base::_source=s;
    1056       return *this;
    10571073    }
    10581074
    … …  
    10841100
    10851101#ifdef DOXYGEN
    1086   /// \brief Visitor class for dfs.
     1102  /// \brief Visitor class for DFS.
    10871103  ///
    1088   /// It gives a simple interface for a functional interface for dfs
    1089   /// traversal. The traversal on a linear data structure.
     1104  /// This class defines the interface of the DfsVisit events, and
     1105  /// it could be the base of a real visitor class.
    10901106  template <typename _Digraph>
    10911107  struct DfsVisitor {
    … …  
    10931109    typedef typename Digraph::Arc Arc;
    10941110    typedef typename Digraph::Node Node;
    1095     /// \brief Called when the arc reach a node.
    1096     ///
    1097     /// It is called when the dfs find an arc which target is not
    1098     /// reached yet.
     1111    /// \brief Called for the source node of the DFS.
     1112    ///
     1113    /// This function is called for the source node of the DFS.
     1114    void start(const Node& node) {}
     1115    /// \brief Called when the source node is leaved.
     1116    ///
     1117    /// This function is called when the source node is leaved.
     1118    void stop(const Node& node) {}
     1119    /// \brief Called when a node is reached first time.
     1120    ///
     1121    /// This function is called when a node is reached first time.
     1122    void reach(const Node& node) {}
     1123    /// \brief Called when an arc reaches a new node.
     1124    ///
     1125    /// This function is called when the DFS finds an arc whose target node
     1126    /// is not reached yet.
    10991127    void discover(const Arc& arc) {}
    1100     /// \brief Called when the node reached first time.
    1101     ///
    1102     /// It is Called when the node reached first time.
    1103     void reach(const Node& node) {}
    1104     /// \brief Called when we step back on an arc.
    1105     ///
    1106     /// It is called when the dfs should step back on the arc.
    1107     void backtrack(const Arc& arc) {}
    1108     /// \brief Called when we step back from the node.
    1109     ///
    1110     /// It is called when we step back from the node.
    1111     void leave(const Node& node) {}
    1112     /// \brief Called when the arc examined but target of the arc
     1128    /// \brief Called when an arc is examined but its target node is
    11131129    /// already discovered.
    11141130    ///
    1115     /// It called when the arc examined but the target of the arc
     1131    /// This function is called when an arc is examined but its target node is
    11161132    /// already discovered.
    11171133    void examine(const Arc& arc) {}
    1118     /// \brief Called for the source node of the dfs.
    1119     ///
    1120     /// It is called for the source node of the dfs.
    1121     void start(const Node& node) {}
    1122     /// \brief Called when we leave the source node of the dfs.
    1123     ///
    1124     /// It is called when we leave the source node of the dfs.
    1125     void stop(const Node& node) {}
    1126 
     1134    /// \brief Called when the DFS steps back from a node.
     1135    ///
     1136    /// This function is called when the DFS steps back from a node.
     1137    void leave(const Node& node) {}
     1138    /// \brief Called when the DFS steps back on an arc.
     1139    ///
     1140    /// This function is called when the DFS steps back on an arc.
     1141    void backtrack(const Arc& arc) {}
    11271142  };
    11281143#else
    … …  
    11321147    typedef typename Digraph::Arc Arc;
    11331148    typedef typename Digraph::Node Node;
    1134     void discover(const Arc&) {}
    1135     void reach(const Node&) {}
    1136     void backtrack(const Arc&) {}
    1137     void leave(const Node&) {}
    1138     void examine(const Arc&) {}
    11391149    void start(const Node&) {}
    11401150    void stop(const Node&) {}
     1151    void reach(const Node&) {}
     1152    void discover(const Arc&) {}
     1153    void examine(const Arc&) {}
     1154    void leave(const Node&) {}
     1155    void backtrack(const Arc&) {}
    11411156
    11421157    template <typename _Visitor>
    … …  
    11451160        Arc arc;
    11461161        Node node;
    1147         visitor.discover(arc);
    1148         visitor.reach(node);
    1149         visitor.backtrack(arc);
    1150         visitor.leave(node);
    1151         visitor.examine(arc);
    11521162        visitor.start(node);
    11531163        visitor.stop(arc);
     1164        visitor.reach(node);
     1165        visitor.discover(arc);
     1166        visitor.examine(arc);
     1167        visitor.leave(node);
     1168        visitor.backtrack(arc);
    11541169      }
    11551170      _Visitor& visitor;
    … …  
    11611176  ///
    11621177  /// Default traits class of DfsVisit class.
    1163   /// \tparam _Digraph Digraph type.
     1178  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11641179  template<class _Digraph>
    11651180  struct DfsVisitDefaultTraits {
    11661181
    1167     /// \brief The digraph type the algorithm runs on.
     1182    /// \brief The type of the digraph the algorithm runs on.
    11681183    typedef _Digraph Digraph;
    11691184
    … …  
    11711186    ///
    11721187    /// The type of the map that indicates which nodes are reached.
    1173     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1174     /// \todo named parameter to set this type, function to read and write.
     1188    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    11751189    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    11761190
    1177     /// \brief Instantiates a ReachedMap.
     1191    /// \brief Instantiates a \ref ReachedMap.
    11781192    ///
    11791193    /// This function instantiates a \ref ReachedMap.
    … …  
    11861200  };
    11871201
    1188   /// %DFS Visit algorithm class.
    1189 
    11901202  /// \ingroup search
     1203  ///
     1204  /// \brief %DFS algorithm class with visitor interface.
     1205  ///
    11911206  /// This class provides an efficient implementation of the %DFS algorithm
    11921207  /// with visitor interface.
    … …  
    11941209  /// The %DfsVisit class provides an alternative interface to the Dfs
    11951210  /// class. It works with callback mechanism, the DfsVisit object calls
    1196   /// on every dfs event the \c Visitor class member functions.
     1211  /// the member functions of the \c Visitor class on every DFS event.
    11971212  ///
    1198   /// \tparam _Digraph The digraph type the algorithm runs on.
     1213  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11991214  /// The default value is
    1200   /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
    1201   /// is only passed to \ref DfsDefaultTraits.
    1202   /// \tparam _Visitor The Visitor object for the algorithm. The
    1203   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
    1204   /// does not observe the Dfs events. If you want to observe the dfs
    1205   /// events you should implement your own Visitor class.
     1215  /// \ref ListDigraph. The value of _Digraph is not used directly by
     1216  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
     1217  /// \tparam _Visitor The Visitor type that is used by the algorithm.
     1218  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
     1219  /// does not observe the DFS events. If you want to observe the DFS
     1220  /// events, you should implement your own visitor class.
    12061221  /// \tparam _Traits Traits class to set various data types used by the
    12071222  /// algorithm. The default traits class is
    12081223  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
    12091224  /// See \ref DfsVisitDefaultTraits for the documentation of
    1210   /// a Dfs visit traits class.
    1211   ///
    1212   /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
     1225  /// a DFS visit traits class.
    12131226#ifdef DOXYGEN
    12141227  template <typename _Digraph, typename _Visitor, typename _Traits>
    … …  
    12241237    ///
    12251238    /// This error represents problems in the initialization
    1226     /// of the parameters of the algorithms.
     1239    /// of the parameters of the algorithm.
    12271240    class UninitializedParameter : public lemon::UninitializedParameter {
    12281241    public:
    … …  
    12331246    };
    12341247
     1248    ///The traits class.
    12351249    typedef _Traits Traits;
    12361250
     1251    ///The type of the digraph the algorithm runs on.
    12371252    typedef typename Traits::Digraph Digraph;
    12381253
     1254    ///The visitor type used by the algorithm.
    12391255    typedef _Visitor Visitor;
    12401256
    1241     ///The type of the map indicating which nodes are reached.
     1257    ///The type of the map that indicates which nodes are reached.
    12421258    typedef typename Traits::ReachedMap ReachedMap;
    12431259
    … …  
    12491265    typedef typename Digraph::OutArcIt OutArcIt;
    12501266
    1251     /// Pointer to the underlying digraph.
     1267    //Pointer to the underlying digraph.
    12521268    const Digraph *_digraph;
    1253     /// Pointer to the visitor object.
     1269    //Pointer to the visitor object.
    12541270    Visitor *_visitor;
    1255     ///Pointer to the map of reached status of the nodes.
     1271    //Pointer to the map of reached status of the nodes.
    12561272    ReachedMap *_reached;
    1257     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1273    //Indicates if _reached is locally allocated (true) or not.
    12581274    bool local_reached;
    12591275
    … …  
    12611277    int _stack_head;
    12621278
    1263     /// \brief Creates the maps if necessary.
    1264     ///
    1265     /// Creates the maps if necessary.
     1279    ///Creates the maps if necessary.
     1280    ///\todo Better memory allocation (instead of new).
    12661281    void create_maps() {
    12671282      if(!_reached) {
    … …  
    12901305    };
    12911306    /// \brief \ref named-templ-param "Named parameter" for setting
    1292     /// ReachedMap type
    1293     ///
    1294     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1307    /// ReachedMap type.
     1308    ///
     1309    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    12951310    template <class T>
    12961311    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
    … …  
    13061321    /// Constructor.
    13071322    ///
    1308     /// \param digraph the digraph the algorithm will run on.
    1309     /// \param visitor The visitor of the algorithm.
    1310     ///
     1323    /// \param digraph The digraph the algorithm runs on.
     1324    /// \param visitor The visitor object of the algorithm.
    13111325    DfsVisit(const Digraph& digraph, Visitor& visitor)
    13121326      : _digraph(&digraph), _visitor(&visitor),
    … …  
    13141328
    13151329    /// \brief Destructor.
    1316     ///
    1317     /// Destructor.
    13181330    ~DfsVisit() {
    13191331      if(local_reached) delete _reached;
    13201332    }
    13211333
    1322     /// \brief Sets the map indicating if a node is reached.
    1323     ///
    1324     /// Sets the map indicating if a node is reached.
     1334    /// \brief Sets the map that indicates which nodes are reached.
     1335    ///
     1336    /// Sets the map that indicates which nodes are reached.
    13251337    /// If you don't use this function before calling \ref run(),
    1326     /// it will allocate one. The destuctor deallocates this
     1338    /// it will allocate one. The destructor deallocates this
    13271339    /// automatically allocated map, of course.
    13281340    /// \return <tt> (*this) </tt>
    … …  
    13371349
    13381350  public:
     1351
    13391352    /// \name Execution control
    13401353    /// The simplest way to execute the algorithm is to use
    1341     /// one of the member functions called \c run(...).
     1354    /// one of the member functions called \ref lemon::DfsVisit::run()
     1355    /// "run()".
    13421356    /// \n
    1343     /// If you need more control on the execution,
    1344     /// first you must call \ref init(), then you can adda source node
    1345     /// with \ref addSource().
    1346     /// Finally \ref start() will perform the actual path
    1347     /// computation.
     1357    /// If you need more control on the execution, first you must call
     1358    /// \ref lemon::DfsVisit::init() "init()", then you can add several
     1359    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
     1360    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
     1361    /// actual path computation.
    13481362
    13491363    /// @{
     1364
    13501365    /// \brief Initializes the internal data structures.
    13511366    ///
    13521367    /// Initializes the internal data structures.
    1353     ///
    13541368    void init() {
    13551369      create_maps();
    … …  
    13611375    }
    13621376
    1363     /// \brief Adds a new source node.
    1364     ///
    1365     /// Adds a new source node to the set of nodes to be processed.
    1366     void addSource(Node s) {
     1377    ///Adds a new source node.
     1378
     1379    ///Adds a new source node to the set of nodes to be processed.
     1380    ///
     1381    ///\pre The stack must be empty. (Otherwise the algorithm gives
     1382    ///false results.)
     1383    ///
     1384    ///\warning Distances will be wrong (or at least strange) in case of
     1385    ///multiple sources.
     1386    void addSource(Node s)
     1387    {
     1388      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
    13671389      if(!(*_reached)[s]) {
    13681390          _reached->set(s,true);
    … …  
    13851407    /// \return The processed arc.
    13861408    ///
    1387     /// \pre The stack must not be empty!
     1409    /// \pre The stack must not be empty.
    13881410    Arc processNextArc() {
    13891411      Arc e = _stack[_stack_head];
    … …  
    14191441    /// \return The next arc to be processed or INVALID if the stack is
    14201442    /// empty.
    1421     Arc nextArc() {
     1443    Arc nextArc() const {
    14221444      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
    14231445    }
    14241446
    14251447    /// \brief Returns \c false if there are nodes
    1426     /// to be processed in the queue
     1448    /// to be processed.
    14271449    ///
    14281450    /// Returns \c false if there are nodes
    1429     /// to be processed in the queue
    1430     bool emptyQueue() { return _stack_head < 0; }
     1451    /// to be processed in the queue (stack).
     1452    bool emptyQueue() const { return _stack_head < 0; }
    14311453
    14321454    /// \brief Returns the number of the nodes to be processed.
    14331455    ///
    1434     /// Returns the number of the nodes to be processed in the queue.
    1435     int queueSize() { return _stack_head + 1; }
     1456    /// Returns the number of the nodes to be processed in the queue (stack).
     1457    int queueSize() const { return _stack_head + 1; }
    14361458
    14371459    /// \brief Executes the algorithm.
    … …  
    14391461    /// Executes the algorithm.
    14401462    ///
    1441     /// \pre init() must be called and at least one node should be added
    1442     /// with addSource() before using this function.
     1463    /// This method runs the %DFS algorithm from the root node
     1464    /// in order to compute the %DFS path to each node.
     1465    ///
     1466    /// The algorithm computes
     1467    /// - the %DFS tree,
     1468    /// - the distance of each node from the root in the %DFS tree.
     1469    ///
     1470    /// \pre init() must be called and a root node should be
     1471    /// added with addSource() before using this function.
     1472    ///
     1473    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
     1474    /// \code
     1475    ///   while ( !d.emptyQueue() ) {
     1476    ///     d.processNextArc();
     1477    ///   }
     1478    /// \endcode
    14431479    void start() {
    14441480      while ( !emptyQueue() ) processNextArc();
    14451481    }
    14461482
    1447     /// \brief Executes the algorithm until \c dest is reached.
    1448     ///
    1449     /// Executes the algorithm until \c dest is reached.
    1450     ///
    1451     /// \pre init() must be called and at least one node should be added
     1483    /// \brief Executes the algorithm until the given target node is reached.
     1484    ///
     1485    /// Executes the algorithm until the given target node is reached.
     1486    ///
     1487    /// This method runs the %DFS algorithm from the root node
     1488    /// in order to compute the DFS path to \c dest.
     1489    ///
     1490    /// The algorithm computes
     1491    /// - the %DFS path to \c dest,
     1492    /// - the distance of \c dest from the root in the %DFS tree.
     1493    ///
     1494    /// \pre init() must be called and a root node should be added
    14521495    /// with addSource() before using this function.
    14531496    void start(Node dest) {
    … …  
    14601503    /// Executes the algorithm until a condition is met.
    14611504    ///
    1462     /// \pre init() must be called and at least one node should be added
     1505    /// This method runs the %DFS algorithm from the root node
     1506    /// until an arc \c a with <tt>am[a]</tt> true is found.
     1507    ///
     1508    /// \param am A \c bool (or convertible) arc map. The algorithm
     1509    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
     1510    ///
     1511    /// \return The reached arc \c a with <tt>am[a]</tt> true or
     1512    /// \c INVALID if no such arc was found.
     1513    ///
     1514    /// \pre init() must be called and a root node should be added
    14631515    /// with addSource() before using this function.
    14641516    ///
    1465     /// \param em must be a bool (or convertible) arc map. The algorithm
    1466     /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
    1467     ///
    1468     ///\return The reached arc \c e with <tt>em[e]</tt> true or
    1469     ///\c INVALID if no such arc was found.
    1470     ///
    1471     /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
     1517    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
    14721518    /// not a node map.
    1473     template <typename EM>
    1474     Arc start(const EM &em) {
    1475       while ( !emptyQueue() && !em[_stack[_stack_head]] )
     1519    template <typename AM>
     1520    Arc start(const AM &am) {
     1521      while ( !emptyQueue() && !am[_stack[_stack_head]] )
    14761522        processNextArc();
    14771523      return emptyQueue() ? INVALID : _stack[_stack_head];
    14781524    }
    14791525
    1480     /// \brief Runs %DFSVisit algorithm from node \c s.
    1481     ///
    1482     /// This method runs the %DFS algorithm from a root node \c s.
    1483     /// \note d.run(s) is just a shortcut of the following code.
     1526    /// \brief Runs the algorithm from the given node.
     1527    ///
     1528    /// This method runs the %DFS algorithm from node \c s.
     1529    /// in order to compute the DFS path to each node.
     1530    ///
     1531    /// The algorithm computes
     1532    /// - the %DFS tree,
     1533    /// - the distance of each node from the root in the %DFS tree.
     1534    ///
     1535    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
    14841536    ///\code
    14851537    ///   d.init();
    … …  
    14931545    }
    14941546
    1495     /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
     1547    /// \brief Finds the %DFS path between \c s and \c t.
     1548
     1549    /// This method runs the %DFS algorithm from node \c s
     1550    /// in order to compute the DFS path to \c t.
     1551    ///
     1552    /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
     1553    /// if \c t is reachable form \c s, \c 0 otherwise.
     1554    ///
     1555    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
     1556    /// just a shortcut of the following code.
     1557    ///\code
     1558    ///   d.init();
     1559    ///   d.addSource(s);
     1560    ///   d.start(t);
     1561    ///\endcode
     1562    int run(Node s,Node t) {
     1563      init();
     1564      addSource(s);
     1565      start(t);
     1566      return reached(t)?_stack_head+1:0;
     1567    }
     1568
     1569    /// \brief Runs the algorithm to visit all nodes in the digraph.
    14961570
    14971571    /// This method runs the %DFS algorithm in order to
    1498     /// compute the %DFS path to each node. The algorithm computes
    1499     /// - The %DFS tree.
    1500     /// - The distance of each node from the root in the %DFS tree.
    1501     ///
    1502     ///\note d.run() is just a shortcut of the following code.
     1572    /// compute the %DFS path to each node.
     1573    ///
     1574    /// The algorithm computes
     1575    /// - the %DFS tree,
     1576    /// - the distance of each node from the root in the %DFS tree.
     1577    ///
     1578    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
    15031579    ///\code
    1504     ///  d.init();
    1505     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    1506     ///    if (!d.reached(it)) {
    1507     ///      d.addSource(it);
    1508     ///      d.start();
    1509     ///    }
    1510     ///  }
     1580    ///   d.init();
     1581    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
     1582    ///     if (!d.reached(n)) {
     1583    ///       d.addSource(n);
     1584    ///       d.start();
     1585    ///     }
     1586    ///   }
    15111587    ///\endcode
    15121588    void run() {
    … …  
    15191595      }
    15201596    }
     1597
    15211598    ///@}
    15221599
    … …  
    15241601    /// The result of the %DFS algorithm can be obtained using these
    15251602    /// functions.\n
    1526     /// Before the use of these functions,
    1527     /// either run() or start() must be called.
     1603    /// Either \ref lemon::DfsVisit::run() "run()" or
     1604    /// \ref lemon::DfsVisit::start() "start()" must be called before
     1605    /// using them.
    15281606    ///@{
    1529     /// \brief Checks if a node is reachable from the root.
     1607
     1608    /// \brief Checks if a node is reachable from the root(s).
    15301609    ///
    15311610    /// Returns \c true if \c v is reachable from the root(s).
    1532     /// \warning The source nodes are inditated as unreachable.
    15331611    /// \pre Either \ref run() or \ref start()
    15341612    /// must be called before using this function.
    1535     ///
    15361613    bool reached(Node v) { return (*_reached)[v]; }
     1614
    15371615    ///@}
     1616
    15381617  };
    15391618
    1540 
    15411619} //END OF NAMESPACE LEMON
    15421620
    15431621#endif
    1544 
Note: See TracChangeset for help on using the changeset viewer.