COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 247:f1158744a112 in lemon for lemon/dfs.h


Ignore:
Timestamp:
08/04/08 22:00:36 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
248:8fada33fc60a, 365:37557a46e298
Parents:
246:7c67988fca07 (diff), 244:c30731a37f91 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/dfs.h

    r244 r247  
    2525
    2626#include <lemon/list_graph.h>
    27 #include <lemon/graph_utils.h>
    2827#include <lemon/bits/path_dump.h>
    29 #include <lemon/bits/invalid.h>
     28#include <lemon/core.h>
    3029#include <lemon/error.h>
    3130#include <lemon/assert.h>

  • lemon/dfs.h

    r220 r247  
    2222///\ingroup search
    2323///\file
    24 ///\brief Dfs algorithm.
     24///\brief DFS algorithm.
    2525
    2626#include <lemon/list_graph.h>
    … …  
    2828#include <lemon/core.h>
    2929#include <lemon/error.h>
     30#include <lemon/assert.h>
    3031#include <lemon/maps.h>
    3132
    32 #include <lemon/concept_check.h>
    33 
    3433namespace lemon {
    35 
    3634
    3735  ///Default traits class of Dfs class.
    … …  
    4240  struct DfsDefaultTraits
    4341  {
    44     ///The digraph type the algorithm runs on.
     42    ///The type of the digraph the algorithm runs on.
    4543    typedef GR Digraph;
    46     ///\brief The type of the map that stores the last
     44
     45    ///\brief The type of the map that stores the predecessor
    4746    ///arcs of the %DFS paths.
    4847    ///
    49     ///The type of the map that stores the last
     48    ///The type of the map that stores the predecessor
    5049    ///arcs of the %DFS paths.
    5150    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    52     ///
    53     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    54     ///Instantiates a PredMap.
     51    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     52    ///Instantiates a \ref PredMap.
    5553
    5654    ///This function instantiates a \ref PredMap.
    57     ///\param G is the digraph, to which we would like to define the PredMap.
     55    ///\param g is the digraph, to which we would like to define the
     56    ///\ref PredMap.
    5857    ///\todo The digraph alone may be insufficient to initialize
    59     static PredMap *createPredMap(const GR &G)
    60     {
    61       return new PredMap(G);
     58    static PredMap *createPredMap(const Digraph &g)
     59    {
     60      return new PredMap(g);
    6261    }
    6362
    … …  
    6665    ///The type of the map that indicates which nodes are processed.
    6766    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    68     ///\todo named parameter to set this type, function to read and write.
     67    ///By default it is a NullMap.
    6968    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    70     ///Instantiates a ProcessedMap.
     69    ///Instantiates a \ref ProcessedMap.
    7170
    7271    ///This function instantiates a \ref ProcessedMap.
    … …  
    7473    ///we would like to define the \ref ProcessedMap
    7574#ifdef DOXYGEN
    76     static ProcessedMap *createProcessedMap(const GR &g)
     75    static ProcessedMap *createProcessedMap(const Digraph &g)
    7776#else
    78     static ProcessedMap *createProcessedMap(const GR &)
     77    static ProcessedMap *createProcessedMap(const Digraph &)
    7978#endif
    8079    {
    8180      return new ProcessedMap();
    8281    }
     82
    8383    ///The type of the map that indicates which nodes are reached.
    8484
    8585    ///The type of the map that indicates which nodes are reached.
     86    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     87    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     88    ///Instantiates a \ref ReachedMap.
     89
     90    ///This function instantiates a \ref ReachedMap.
     91    ///\param g is the digraph, to which
     92    ///we would like to define the \ref ReachedMap.
     93    static ReachedMap *createReachedMap(const Digraph &g)
     94    {
     95      return new ReachedMap(g);
     96    }
     97
     98    ///The type of the map that stores the distances of the nodes.
     99
     100    ///The type of the map that stores the distances of the nodes.
    86101    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    87     ///\todo named parameter to set this type, function to read and write.
    88     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    89     ///Instantiates a 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 GR &G)
    95     {
    96       return new ReachedMap(G);
    97     }
    98     ///The type of the map that stores the dists of the nodes.
    99 
    100     ///The type of the map that stores the dists of the nodes.
    101     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    102     ///
    103102    typedef typename Digraph::template NodeMap<int> DistMap;
    104     ///Instantiates a DistMap.
     103    ///Instantiates a \ref DistMap.
    105104
    106105    ///This function instantiates a \ref DistMap.
    107     ///\param G is the digraph, to which we would like to define
    108     ///the \ref DistMap
    109     static DistMap *createDistMap(const GR &G)
    110     {
    111       return new DistMap(G);
     106    ///\param g is the digraph, to which we would like to define the
     107    ///\ref DistMap.
     108    static DistMap *createDistMap(const Digraph &g)
     109    {
     110      return new DistMap(g);
    112111    }
    113112  };
    … …  
    118117  ///This class provides an efficient implementation of the %DFS algorithm.
    119118  ///
    120   ///\tparam GR The digraph type the algorithm runs on. The default value is
    121   ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
    122   ///is only passed to \ref DfsDefaultTraits.
     119  ///There is also a \ref dfs() "function type interface" for the DFS
     120  ///algorithm, which is convenient in the simplier cases and it can be
     121  ///used easier.
     122  ///
     123  ///\tparam GR The type of the digraph the algorithm runs on.
     124  ///The default value is \ref ListDigraph. The value of GR is not used
     125  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
    123126  ///\tparam TR Traits class to set various data types used by the algorithm.
    124127  ///The default traits class is
    … …  
    135138  class Dfs {
    136139  public:
    137     /**
    138      * \brief \ref Exception for uninitialized parameters.
    139      *
    140      * This error represents problems in the initialization
    141      * of the parameters of the algorithms.
    142      */
     140    ///\ref Exception for uninitialized parameters.
     141
     142    ///This error represents problems in the initialization of the
     143    ///parameters of the algorithm.
    143144    class UninitializedParameter : public lemon::UninitializedParameter {
    144145    public:
    … …  
    148149    };
    149150
     151    ///The type of the digraph the algorithm runs on.
     152    typedef typename TR::Digraph Digraph;
     153
     154    ///\brief The type of the map that stores the predecessor arcs of the
     155    ///DFS paths.
     156    typedef typename TR::PredMap PredMap;
     157    ///The type of the map that stores the distances of the nodes.
     158    typedef typename TR::DistMap DistMap;
     159    ///The type of the map that indicates which nodes are reached.
     160    typedef typename TR::ReachedMap ReachedMap;
     161    ///The type of the map that indicates which nodes are processed.
     162    typedef typename TR::ProcessedMap ProcessedMap;
     163    ///The type of the paths.
     164    typedef PredMapPath<Digraph, PredMap> Path;
     165
     166    ///The traits class.
    150167    typedef TR Traits;
    151     ///The type of the underlying digraph.
    152     typedef typename TR::Digraph Digraph;
    153     ///\e
     168
     169  private:
     170
    154171    typedef typename Digraph::Node Node;
    155     ///\e
    156172    typedef typename Digraph::NodeIt NodeIt;
    157     ///\e
    158173    typedef typename Digraph::Arc Arc;
    159     ///\e
    160174    typedef typename Digraph::OutArcIt OutArcIt;
    161175
    162     ///\brief The type of the map that stores the last
    163     ///arcs of the %DFS paths.
    164     typedef typename TR::PredMap PredMap;
    165     ///The type of the map indicating which nodes are reached.
    166     typedef typename TR::ReachedMap ReachedMap;
    167     ///The type of the map indicating which nodes are processed.
    168     typedef typename TR::ProcessedMap ProcessedMap;
    169     ///The type of the map that stores the dists of the nodes.
    170     typedef typename TR::DistMap DistMap;
    171   private:
    172     /// Pointer to the underlying digraph.
     176    //Pointer to the underlying digraph.
    173177    const Digraph *G;
    174     ///Pointer to the map of predecessors arcs.
     178    //Pointer to the map of predecessor arcs.
    175179    PredMap *_pred;
    176     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     180    //Indicates if _pred is locally allocated (true) or not.
    177181    bool local_pred;
    178     ///Pointer to the map of distances.
     182    //Pointer to the map of distances.
    179183    DistMap *_dist;
    180     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     184    //Indicates if _dist is locally allocated (true) or not.
    181185    bool local_dist;
    182     ///Pointer to the map of reached status of the nodes.
     186    //Pointer to the map of reached status of the nodes.
    183187    ReachedMap *_reached;
    184     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     188    //Indicates if _reached is locally allocated (true) or not.
    185189    bool local_reached;
    186     ///Pointer to the map of processed status of the nodes.
     190    //Pointer to the map of processed status of the nodes.
    187191    ProcessedMap *_processed;
    188     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     192    //Indicates if _processed is locally allocated (true) or not.
    189193    bool local_processed;
    190194
    … …  
    193197
    194198    ///Creates the maps if necessary.
    195 
    196199    ///\todo Better memory allocation (instead of new).
    197200    void create_maps()
    … …  
    230233    struct DefPredMapTraits : public Traits {
    231234      typedef T PredMap;
    232       static PredMap *createPredMap(const Digraph &G)
     235      static PredMap *createPredMap(const Digraph &)
    233236      {
    234237        throw UninitializedParameter();
    … …  
    236239    };
    237240    ///\brief \ref named-templ-param "Named parameter" for setting
    238     ///PredMap type
    239     ///
    240     ///\ref named-templ-param "Named parameter" for setting PredMap type
    241     ///
     241    ///\ref PredMap type.
     242    ///
     243    ///\ref named-templ-param "Named parameter" for setting
     244    ///\ref PredMap type.
    242245    template <class T>
    243246    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
    244247      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
    245248    };
    246 
    247249
    248250    template <class T>
    … …  
    255257    };
    256258    ///\brief \ref named-templ-param "Named parameter" for setting
    257     ///DistMap type
    258     ///
    259     ///\ref named-templ-param "Named parameter" for setting DistMap
    260     ///type
     259    ///\ref DistMap type.
     260    ///
     261    ///\ref named-templ-param "Named parameter" for setting
     262    ///\ref DistMap type.
    261263    template <class T>
    262     struct DefDistMap {
     264    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
    263265      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
    264266    };
    … …  
    273275    };
    274276    ///\brief \ref named-templ-param "Named parameter" for setting
    275     ///ReachedMap type
    276     ///
    277     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    278     ///
     277    ///\ref ReachedMap type.
     278    ///
     279    ///\ref named-templ-param "Named parameter" for setting
     280    ///\ref ReachedMap type.
    279281    template <class T>
    280282    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
    … …  
    291293    };
    292294    ///\brief \ref named-templ-param "Named parameter" for setting
    293     ///ProcessedMap type
    294     ///
    295     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    296     ///
     295    ///\ref ProcessedMap type.
     296    ///
     297    ///\ref named-templ-param "Named parameter" for setting
     298    ///\ref ProcessedMap type.
    297299    template <class T>
    298300    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
    … …  
    302304    struct DefDigraphProcessedMapTraits : public Traits {
    303305      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    304       static ProcessedMap *createProcessedMap(const Digraph &G)
     306      static ProcessedMap *createProcessedMap(const Digraph &g)
    305307      {
    306         return new ProcessedMap(G);
    307       }
    308     };
    309     ///\brief \ref named-templ-param "Named parameter"
    310     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    311     ///
    312     ///\ref named-templ-param "Named parameter"
    313     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    314     ///If you don't set it explicitely, it will be automatically allocated.
     308        return new ProcessedMap(g);
     309      }
     310    };
     311    ///\brief \ref named-templ-param "Named parameter" for setting
     312    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     313    ///
     314    ///\ref named-templ-param "Named parameter" for setting
     315    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     316    ///If you don't set it explicitly, it will be automatically allocated.
    315317    template <class T>
    316     class DefProcessedMapToBeDefaultMap :
     318    struct DefProcessedMapToBeDefaultMap :
    317319      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
    318320      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
    … …  
    325327    ///Constructor.
    326328
    327     ///\param _G the digraph the algorithm will run on.
    328     ///
    329     Dfs(const Digraph& _G) :
    330       G(&_G),
     329    ///Constructor.
     330    ///\param g The digraph the algorithm runs on.
     331    Dfs(const Digraph &g) :
     332      G(&g),
    331333      _pred(NULL), local_pred(false),
    332334      _dist(NULL), local_dist(false),
    … …  
    344346    }
    345347
    346     ///Sets the map storing the predecessor arcs.
    347 
    348     ///Sets the map storing the predecessor arcs.
     348    ///Sets the map that stores the predecessor arcs.
     349
     350    ///Sets the map that stores the predecessor arcs.
    349351    ///If you don't use this function before calling \ref run(),
    350     ///it will allocate one. The destuctor deallocates this
     352    ///it will allocate one. The destructor deallocates this
    351353    ///automatically allocated map, of course.
    352354    ///\return <tt> (*this) </tt>
    … …  
    361363    }
    362364
    363     ///Sets the map storing the distances calculated by the algorithm.
    364 
    365     ///Sets the map storing the distances calculated by the algorithm.
     365    ///Sets the map that indicates which nodes are reached.
     366
     367    ///Sets the map that indicates which nodes are reached.
    366368    ///If you don't use this function before calling \ref run(),
    367     ///it will allocate one. The destuctor deallocates this
     369    ///it will allocate one. The destructor deallocates this
     370    ///automatically allocated map, of course.
     371    ///\return <tt> (*this) </tt>
     372    Dfs &reachedMap(ReachedMap &m)
     373    {
     374      if(local_reached) {
     375        delete _reached;
     376        local_reached=false;
     377      }
     378      _reached = &m;
     379      return *this;
     380    }
     381
     382    ///Sets the map that indicates which nodes are processed.
     383
     384    ///Sets the map that indicates which nodes are processed.
     385    ///If you don't use this function before calling \ref run(),
     386    ///it will allocate one. The destructor deallocates this
     387    ///automatically allocated map, of course.
     388    ///\return <tt> (*this) </tt>
     389    Dfs &processedMap(ProcessedMap &m)
     390    {
     391      if(local_processed) {
     392        delete _processed;
     393        local_processed=false;
     394      }
     395      _processed = &m;
     396      return *this;
     397    }
     398
     399    ///Sets the map that stores the distances of the nodes.
     400
     401    ///Sets the map that stores the distances of the nodes calculated by
     402    ///the algorithm.
     403    ///If you don't use this function before calling \ref run(),
     404    ///it will allocate one. The destructor deallocates this
    368405    ///automatically allocated map, of course.
    369406    ///\return <tt> (*this) </tt>
    … …  
    378415    }
    379416
    380     ///Sets the map indicating if a node is reached.
    381 
    382     ///Sets the map indicating if a node is reached.
    383     ///If you don't use this function before calling \ref run(),
    384     ///it will allocate one. The destuctor deallocates this
    385     ///automatically allocated map, of course.
    386     ///\return <tt> (*this) </tt>
    387     Dfs &reachedMap(ReachedMap &m)
    388     {
    389       if(local_reached) {
    390         delete _reached;
    391         local_reached=false;
    392       }
    393       _reached = &m;
    394       return *this;
    395     }
    396 
    397     ///Sets the map indicating if a node is processed.
    398 
    399     ///Sets the map indicating if a node is processed.
    400     ///If you don't use this function before calling \ref run(),
    401     ///it will allocate one. The destuctor deallocates this
    402     ///automatically allocated map, of course.
    403     ///\return <tt> (*this) </tt>
    404     Dfs &processedMap(ProcessedMap &m)
    405     {
    406       if(local_processed) {
    407         delete _processed;
    408         local_processed=false;
    409       }
    410       _processed = &m;
    411       return *this;
    412     }
    413 
    414417  public:
     418
    415419    ///\name Execution control
    416420    ///The simplest way to execute the algorithm is to use
    417     ///one of the member functions called \c run(...).
     421    ///one of the member functions called \ref lemon::Dfs::run() "run()".
    418422    ///\n
    419     ///If you need more control on the execution,
    420     ///first you must call \ref init(), then you can add a source node
    421     ///with \ref addSource().
    422     ///Finally \ref start() will perform the actual path
    423     ///computation.
     423    ///If you need more control on the execution, first you must call
     424    ///\ref lemon::Dfs::init() "init()", then you can add a source node
     425    ///with \ref lemon::Dfs::addSource() "addSource()".
     426    ///Finally \ref lemon::Dfs::start() "start()" will perform the
     427    ///actual path computation.
    424428
    425429    ///@{
    … …  
    436440      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    437441        _pred->set(u,INVALID);
    438         // _predNode->set(u,INVALID);
    439442        _reached->set(u,false);
    440443        _processed->set(u,false);
    … …  
    446449    ///Adds a new source node to the set of nodes to be processed.
    447450    ///
    448     ///\warning dists are wrong (or at least strange)
    449     ///in case of multiple sources.
     451    ///\pre The stack must be empty. (Otherwise the algorithm gives
     452    ///false results.)
     453    ///
     454    ///\warning Distances will be wrong (or at least strange) in case of
     455    ///multiple sources.
    450456    void addSource(Node s)
    451457    {
     458      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
    452459      if(!(*_reached)[s])
    453460        {
    … …  
    472479    ///\return The processed arc.
    473480    ///
    474     ///\pre The stack must not be empty!
     481    ///\pre The stack must not be empty.
    475482    Arc processNextArc()
    476483    {
    … …  
    498505      return e;
    499506    }
     507
    500508    ///Next arc to be processed.
    501509
    502510    ///Next arc to be processed.
    503511    ///
    504     ///\return The next arc to be processed or INVALID if the stack is
    505     /// empty.
    506     OutArcIt nextArc()
     512    ///\return The next arc to be processed or \c INVALID if the stack
     513    ///is empty.
     514    OutArcIt nextArc() const
    507515    {
    508516      return _stack_head>=0?_stack[_stack_head]:INVALID;
    … …  
    510518
    511519    ///\brief Returns \c false if there are nodes
    512     ///to be processed in the queue
     520    ///to be processed.
    513521    ///
    514522    ///Returns \c false if there are nodes
    515     ///to be processed in the queue
    516     bool emptyQueue() { return _stack_head<0; }
     523    ///to be processed in the queue (stack).
     524    bool emptyQueue() const { return _stack_head<0; }
     525
    517526    ///Returns the number of the nodes to be processed.
    518527
    519     ///Returns the number of the nodes to be processed in the queue.
    520     int queueSize() { return _stack_head+1; }
     528    ///Returns the number of the nodes to be processed in the queue (stack).
     529    int queueSize() const { return _stack_head+1; }
    521530
    522531    ///Executes the algorithm.
    … …  
    524533    ///Executes the algorithm.
    525534    ///
    526     ///\pre init() must be called and at least one node should be added
    527     ///with addSource() before using this function.
    528     ///
    529     ///This method runs the %DFS algorithm from the root node(s)
    530     ///in order to
    531     ///compute the
    532     ///%DFS path to each node. The algorithm computes
    533     ///- The %DFS tree.
    534     ///- The distance of each node from the root(s) in the %DFS tree.
    535     ///
     535    ///This method runs the %DFS algorithm from the root node
     536    ///in order to compute the DFS path to each node.
     537    ///
     538    /// The algorithm computes
     539    ///- the %DFS tree,
     540    ///- the distance of each node from the root in the %DFS tree.
     541    ///
     542    ///\pre init() must be called and a root node should be
     543    ///added with addSource() before using this function.
     544    ///
     545    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
     546    ///\code
     547    ///  while ( !d.emptyQueue() ) {
     548    ///    d.processNextArc();
     549    ///  }
     550    ///\endcode
    536551    void start()
    537552    {
    … …  
    539554    }
    540555
    541     ///Executes the algorithm until \c dest is reached.
    542 
    543     ///Executes the algorithm until \c dest is reached.
    544     ///
    545     ///\pre init() must be called and at least one node should be added
    546     ///with addSource() before using this function.
    547     ///
    548     ///This method runs the %DFS algorithm from the root node(s)
    549     ///in order to
    550     ///compute the
    551     ///%DFS path to \c dest. The algorithm computes
    552     ///- The %DFS path to \c  dest.
    553     ///- The distance of \c dest from the root(s) in the %DFS tree.
    554     ///
     556    ///Executes the algorithm until the given target node is reached.
     557
     558    ///Executes the algorithm until the given target node is reached.
     559    ///
     560    ///This method runs the %DFS algorithm from the root node
     561    ///in order to compute the DFS path to \c dest.
     562    ///
     563    ///The algorithm computes
     564    ///- the %DFS path to \c dest,
     565    ///- the distance of \c dest from the root in the %DFS tree.
     566    ///
     567    ///\pre init() must be called and a root node should be
     568    ///added with addSource() before using this function.
    555569    void start(Node dest)
    556570    {
    … …  
    563577    ///Executes the algorithm until a condition is met.
    564578    ///
    565     ///\pre init() must be called and at least one node should be added
    566     ///with addSource() before using this function.
    567     ///
    568     ///\param em must be a bool (or convertible) arc map. The algorithm
    569     ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
    570     ///
    571     ///\return The reached arc \c e with <tt>em[e]</tt> true or
     579    ///This method runs the %DFS algorithm from the root node
     580    ///until an arc \c a with <tt>am[a]</tt> true is found.
     581    ///
     582    ///\param am A \c bool (or convertible) arc map. The algorithm
     583    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
     584    ///
     585    ///\return The reached arc \c a with <tt>am[a]</tt> true or
    572586    ///\c INVALID if no such arc was found.
    573587    ///
    574     ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
     588    ///\pre init() must be called and a root node should be
     589    ///added with addSource() before using this function.
     590    ///
     591    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
    575592    ///not a node map.
    576     template<class EM>
    577     Arc start(const EM &em)
    578     {
    579       while ( !emptyQueue() && !em[_stack[_stack_head]] )
     593    template<class ArcBoolMap>
     594    Arc start(const ArcBoolMap &am)
     595    {
     596      while ( !emptyQueue() && !am[_stack[_stack_head]] )
    580597        processNextArc();
    581598      return emptyQueue() ? INVALID : _stack[_stack_head];
    582599    }
    583600
    584     ///Runs %DFS algorithm to visit all nodes in the digraph.
    585 
    586     ///This method runs the %DFS algorithm in order to
    587     ///compute the
    588     ///%DFS path to each node. The algorithm computes
    589     ///- The %DFS tree.
    590     ///- The distance of each node from the root in the %DFS tree.
    591     ///
    592     ///\note d.run() is just a shortcut of the following code.
     601    ///Runs the algorithm from the given node.
     602
     603    ///This method runs the %DFS algorithm from node \c s
     604    ///in order to compute the DFS path to each node.
     605    ///
     606    ///The algorithm computes
     607    ///- the %DFS tree,
     608    ///- the distance of each node from the root in the %DFS tree.
     609    ///
     610    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
    593611    ///\code
    594612    ///  d.init();
    595     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    596     ///    if (!d.reached(it)) {
    597     ///      d.addSource(it);
     613    ///  d.addSource(s);
     614    ///  d.start();
     615    ///\endcode
     616    void run(Node s) {
     617      init();
     618      addSource(s);
     619      start();
     620    }
     621
     622    ///Finds the %DFS path between \c s and \c t.
     623
     624    ///This method runs the %DFS algorithm from node \c s
     625    ///in order to compute the DFS path to \c t.
     626    ///
     627    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
     628    ///if \c t is reachable form \c s, \c 0 otherwise.
     629    ///
     630    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
     631    ///just a shortcut of the following code.
     632    ///\code
     633    ///  d.init();
     634    ///  d.addSource(s);
     635    ///  d.start(t);
     636    ///\endcode
     637    int run(Node s,Node t) {
     638      init();
     639      addSource(s);
     640      start(t);
     641      return reached(t)?_stack_head+1:0;
     642    }
     643
     644    ///Runs the algorithm to visit all nodes in the digraph.
     645
     646    ///This method runs the %DFS algorithm in order to compute the
     647    ///%DFS path to each node.
     648    ///
     649    ///The algorithm computes
     650    ///- the %DFS tree,
     651    ///- the distance of each node from the root in the %DFS tree.
     652    ///
     653    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     654    ///\code
     655    ///  d.init();
     656    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
     657    ///    if (!d.reached(n)) {
     658    ///      d.addSource(n);
    598659    ///      d.start();
    599660    ///    }
    … …  
    610671    }
    611672
    612     ///Runs %DFS algorithm from node \c s.
    613 
    614     ///This method runs the %DFS algorithm from a root node \c s
    615     ///in order to
    616     ///compute the
    617     ///%DFS path to each node. The algorithm computes
    618     ///- The %DFS tree.
    619     ///- The distance of each node from the root in the %DFS tree.
    620     ///
    621     ///\note d.run(s) is just a shortcut of the following code.
    622     ///\code
    623     ///  d.init();
    624     ///  d.addSource(s);
    625     ///  d.start();
    626     ///\endcode
    627     void run(Node s) {
    628       init();
    629       addSource(s);
    630       start();
    631     }
    632 
    633     ///Finds the %DFS path between \c s and \c t.
    634 
    635     ///Finds the %DFS path between \c s and \c t.
    636     ///
    637     ///\return The length of the %DFS s---t path if there exists one,
    638     ///0 otherwise.
    639     ///\note Apart from the return value, d.run(s,t) is
    640     ///just a shortcut of the following code.
    641     ///\code
    642     ///  d.init();
    643     ///  d.addSource(s);
    644     ///  d.start(t);
    645     ///\endcode
    646     int run(Node s,Node t) {
    647       init();
    648       addSource(s);
    649       start(t);
    650       return reached(t)?_stack_head+1:0;
    651     }
    652 
    653673    ///@}
    654674
    … …  
    656676    ///The result of the %DFS algorithm can be obtained using these
    657677    ///functions.\n
    658     ///Before the use of these functions,
    659     ///either run() or start() must be called.
     678    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
     679    ///"start()" must be called before using them.
    660680
    661681    ///@{
    662682
    663     typedef PredMapPath<Digraph, PredMap> Path;
    664 
    665     ///Gives back the shortest path.
    666 
    667     ///Gives back the shortest path.
    668     ///\pre The \c t should be reachable from the source.
    669     Path path(Node t)
    670     {
    671       return Path(*G, *_pred, t);
    672     }
    673 
    674     ///The distance of a node from the root(s).
    675 
    676     ///Returns the distance of a node from the root(s).
    677     ///\pre \ref run() must be called before using this function.
    678     ///\warning If node \c v is unreachable from the root(s) then the return
    679     ///value of this funcion is undefined.
     683    ///The DFS path to a node.
     684
     685    ///Returns the DFS path to a node.
     686    ///
     687    ///\warning \c t should be reachable from the root.
     688    ///
     689    ///\pre Either \ref run() or \ref start() must be called before
     690    ///using this function.
     691    Path path(Node t) const { return Path(*G, *_pred, t); }
     692
     693    ///The distance of a node from the root.
     694
     695    ///Returns the distance of a node from the root.
     696    ///
     697    ///\warning If node \c v is not reachable from the root, then
     698    ///the return value of this function is undefined.
     699    ///
     700    ///\pre Either \ref run() or \ref start() must be called before
     701    ///using this function.
    680702    int dist(Node v) const { return (*_dist)[v]; }
    681703
    682     ///Returns the 'previous arc' of the %DFS tree.
    683 
    684     ///For a node \c v it returns the 'previous arc'
    685     ///of the %DFS path,
    686     ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
    687     ///v. It is \ref INVALID
    688     ///if \c v is unreachable from the root(s) or \c v is a root. The
    689     ///%DFS tree used here is equal to the %DFS tree used in
     704    ///Returns the 'previous arc' of the %DFS tree for a node.
     705
     706    ///This function returns the 'previous arc' of the %DFS tree for the
     707    ///node \c v, i.e. it returns the last arc of a %DFS path from the
     708    ///root to \c v. It is \c INVALID
     709    ///if \c v is not reachable from the root(s) or if \c v is a root.
     710    ///
     711    ///The %DFS tree used here is equal to the %DFS tree used in
    690712    ///\ref predNode().
     713    ///
    691714    ///\pre Either \ref run() or \ref start() must be called before using
    692715    ///this function.
    … …  
    695718    ///Returns the 'previous node' of the %DFS tree.
    696719
    697     ///For a node \c v it returns the 'previous node'
    698     ///of the %DFS tree,
    699     ///i.e. it returns the last but one node from a %DFS path from the
    700     ///root(s) to \c v.
    701     ///It is INVALID if \c v is unreachable from the root(s) or
    702     ///if \c v itself a root.
    703     ///The %DFS tree used here is equal to the %DFS
    704     ///tree used in \ref predArc().
     720    ///This function returns the 'previous node' of the %DFS
     721    ///tree for the node \c v, i.e. it returns the last but one node
     722    ///from a %DFS path from the root to \c v. It is \c INVALID
     723    ///if \c v is not reachable from the root(s) or if \c v is a root.
     724    ///
     725    ///The %DFS tree used here is equal to the %DFS tree used in
     726    ///\ref predArc().
     727    ///
    705728    ///\pre Either \ref run() or \ref start() must be called before
    706729    ///using this function.
    … …  
    708731                                  G->source((*_pred)[v]); }
    709732
    710     ///Returns a reference to the NodeMap of distances.
    711 
    712     ///Returns a reference to the NodeMap of distances.
    713     ///\pre Either \ref run() or \ref init() must
    714     ///be called before using this function.
     733    ///\brief Returns a const reference to the node map that stores the
     734    ///distances of the nodes.
     735    ///
     736    ///Returns a const reference to the node map that stores the
     737    ///distances of the nodes calculated by the algorithm.
     738    ///
     739    ///\pre Either \ref run() or \ref init()
     740    ///must be called before using this function.
    715741    const DistMap &distMap() const { return *_dist;}
    716742
    717     ///Returns a reference to the %DFS arc-tree map.
    718 
    719     ///Returns a reference to the NodeMap of the arcs of the
    720     ///%DFS tree.
     743    ///\brief Returns a const reference to the node map that stores the
     744    ///predecessor arcs.
     745    ///
     746    ///Returns a const reference to the node map that stores the predecessor
     747    ///arcs, which form the DFS tree.
     748    ///
    721749    ///\pre Either \ref run() or \ref init()
    722750    ///must be called before using this function.
    723751    const PredMap &predMap() const { return *_pred;}
    724752
    725     ///Checks if a node is reachable from the root.
     753    ///Checks if a node is reachable from the root(s).
    726754
    727755    ///Returns \c true if \c v is reachable from the root(s).
    728     ///\warning The source nodes are inditated as unreachable.
    729756    ///\pre Either \ref run() or \ref start()
    730757    ///must be called before using this function.
    731     ///
    732     bool reached(Node v) { return (*_reached)[v]; }
     758    bool reached(Node v) const { return (*_reached)[v]; }
    733759
    734760    ///@}
    735761  };
    736762
    737   ///Default traits class of Dfs function.
    738 
    739   ///Default traits class of Dfs function.
     763  ///Default traits class of dfs() function.
     764
     765  ///Default traits class of dfs() function.
    740766  ///\tparam GR Digraph type.
    741767  template<class GR>
    742768  struct DfsWizardDefaultTraits
    743769  {
    744     ///The digraph type the algorithm runs on.
     770    ///The type of the digraph the algorithm runs on.
    745771    typedef GR Digraph;
    746     ///\brief The type of the map that stores the last
     772
     773    ///\brief The type of the map that stores the predecessor
    747774    ///arcs of the %DFS paths.
    748775    ///
    749     ///The type of the map that stores the last
     776    ///The type of the map that stores the predecessor
    750777    ///arcs of the %DFS paths.
    751778    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    752779    ///
    753     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
    754     ///Instantiates a PredMap.
     780    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     781    ///Instantiates a \ref PredMap.
    755782
    756783    ///This function instantiates a \ref PredMap.
    757     ///\param g is the digraph, to which we would like to define the PredMap.
     784    ///\param g is the digraph, to which we would like to define the
     785    ///\ref PredMap.
    758786    ///\todo The digraph alone may be insufficient to initialize
    759787#ifdef DOXYGEN
    760     static PredMap *createPredMap(const GR &g)
     788    static PredMap *createPredMap(const Digraph &g)
    761789#else
    762     static PredMap *createPredMap(const GR &)
     790    static PredMap *createPredMap(const Digraph &)
    763791#endif
    764792    {
    … …  
    770798    ///The type of the map that indicates which nodes are processed.
    771799    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    772     ///\todo named parameter to set this type, function to read and write.
    773800    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    774     ///Instantiates a ProcessedMap.
     801    ///Instantiates a \ref ProcessedMap.
    775802
    776803    ///This function instantiates a \ref ProcessedMap.
    777804    ///\param g is the digraph, to which
    778     ///we would like to define the \ref ProcessedMap
     805    ///we would like to define the \ref ProcessedMap.
    779806#ifdef DOXYGEN
    780     static ProcessedMap *createProcessedMap(const GR &g)
     807    static ProcessedMap *createProcessedMap(const Digraph &g)
    781808#else
    782     static ProcessedMap *createProcessedMap(const GR &)
     809    static ProcessedMap *createProcessedMap(const Digraph &)
    783810#endif
    784811    {
    785812      return new ProcessedMap();
    786813    }
     814
    787815    ///The type of the map that indicates which nodes are reached.
    788816
    789817    ///The type of the map that indicates which nodes are reached.
     818    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     819    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     820    ///Instantiates a \ref ReachedMap.
     821
     822    ///This function instantiates a \ref ReachedMap.
     823    ///\param g is the digraph, to which
     824    ///we would like to define the \ref ReachedMap.
     825    static ReachedMap *createReachedMap(const Digraph &g)
     826    {
     827      return new ReachedMap(g);
     828    }
     829
     830    ///The type of the map that stores the distances of the nodes.
     831
     832    ///The type of the map that stores the distances of the nodes.
    790833    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    791     ///\todo named parameter to set this type, function to read and write.
    792     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    793     ///Instantiates a ReachedMap.
    794 
    795     ///This function instantiates a \ref ReachedMap.
    796     ///\param G is the digraph, to which
    797     ///we would like to define the \ref ReachedMap.
    798     static ReachedMap *createReachedMap(const GR &G)
    799     {
    800       return new ReachedMap(G);
    801     }
    802     ///The type of the map that stores the dists of the nodes.
    803 
    804     ///The type of the map that stores the dists of the nodes.
    805     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    806834    ///
    807835    typedef NullMap<typename Digraph::Node,int> DistMap;
    808     ///Instantiates a DistMap.
     836    ///Instantiates a \ref DistMap.
    809837
    810838    ///This function instantiates a \ref DistMap.
    … …  
    812840    ///the \ref DistMap
    813841#ifdef DOXYGEN
    814     static DistMap *createDistMap(const GR &g)
     842    static DistMap *createDistMap(const Digraph &g)
    815843#else
    816     static DistMap *createDistMap(const GR &)
     844    static DistMap *createDistMap(const Digraph &)
    817845#endif
    818846    {
    … …  
    821849  };
    822850
    823   /// Default traits used by \ref DfsWizard
     851  /// Default traits class used by \ref DfsWizard
    824852
    825853  /// To make it easier to use Dfs algorithm
    826   ///we have created a wizard class.
     854  /// we have created a wizard class.
    827855  /// This \ref DfsWizard class needs default traits,
    828   ///as well as the \ref Dfs class.
     856  /// as well as the \ref Dfs class.
    829857  /// The \ref DfsWizardBase is a class to be the default traits of the
    830858  /// \ref DfsWizard class.
    … …  
    835863    typedef DfsWizardDefaultTraits<GR> Base;
    836864  protected:
    837     /// Type of the nodes in the digraph.
     865    //The type of the nodes in the digraph.
    838866    typedef typename Base::Digraph::Node Node;
    839867
    840     /// Pointer to the underlying digraph.
     868    //Pointer to the digraph the algorithm runs on.
    841869    void *_g;
    842     ///Pointer to the map of reached nodes.
     870    //Pointer to the map of reached nodes.
    843871    void *_reached;
    844     ///Pointer to the map of processed nodes.
     872    //Pointer to the map of processed nodes.
    845873    void *_processed;
    846     ///Pointer to the map of predecessors arcs.
     874    //Pointer to the map of predecessors arcs.
    847875    void *_pred;
    848     ///Pointer to the map of distances.
     876    //Pointer to the map of distances.
    849877    void *_dist;
    850     ///Pointer to the source node.
     878    //Pointer to the source node.
    851879    Node _source;
    852880
    … …  
    857885    /// all of the attributes to default values (0, INVALID).
    858886    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    859                            _dist(0), _source(INVALID) {}
     887                      _dist(0), _source(INVALID) {}
    860888
    861889    /// Constructor.
    … …  
    864892    /// listed in the parameters list.
    865893    /// Others are initiated to 0.
    866     /// \param g is the initial value of  \ref _g
    867     /// \param s is the initial value of  \ref _source
     894    /// \param g The digraph the algorithm runs on.
     895    /// \param s The source node.
    868896    DfsWizardBase(const GR &g, Node s=INVALID) :
    869897      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    … …  
    872900  };
    873901
    874   /// A class to make the usage of the Dfs algorithm easier
    875 
    876   /// This class is created to make it easier to use the Dfs algorithm.
    877   /// It uses the functions and features of the plain \ref Dfs,
    878   /// but it is much simpler to use it.
     902  /// Auxiliary class for the function type interface of DFS algorithm.
     903
     904  /// This auxiliary class is created to implement the function type
     905  /// interface of \ref Dfs algorithm. It uses the functions and features
     906  /// of the plain \ref Dfs, but it is much simpler to use it.
     907  /// It should only be used through the \ref dfs() function, which makes
     908  /// it easier to use the algorithm.
    879909  ///
    880910  /// Simplicity means that the way to change the types defined
    … …  
    885915  /// the original class by using the ::
    886916  /// operator. In the case of \ref DfsWizard only
    887   /// a function have to be called and it will
     917  /// a function have to be called, and it will
    888918  /// return the needed class.
    889919  ///
    890   /// It does not have own \ref run method. When its \ref run method is called
    891   /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
    892   /// method of it.
     920  /// It does not have own \ref run() method. When its \ref run() method
     921  /// is called, it initiates a plain \ref Dfs object, and calls the
     922  /// \ref Dfs::run() method of it.
    893923  template<class TR>
    894924  class DfsWizard : public TR
    … …  
    896926    typedef TR Base;
    897927
    898     ///The type of the underlying digraph.
     928    ///The type of the digraph the algorithm runs on.
    899929    typedef typename TR::Digraph Digraph;
    900     //\e
     930
    901931    typedef typename Digraph::Node Node;
    902     //\e
    903932    typedef typename Digraph::NodeIt NodeIt;
    904     //\e
    905933    typedef typename Digraph::Arc Arc;
    906     //\e
    907934    typedef typename Digraph::OutArcIt OutArcIt;
    908935
    909     ///\brief The type of the map that stores
    910     ///the reached nodes
     936    ///\brief The type of the map that stores the predecessor
     937    ///arcs of the shortest paths.
     938    typedef typename TR::PredMap PredMap;
     939    ///\brief The type of the map that stores the distances of the nodes.
     940    typedef typename TR::DistMap DistMap;
     941    ///\brief The type of the map that indicates which nodes are reached.
    911942    typedef typename TR::ReachedMap ReachedMap;
    912     ///\brief The type of the map that stores
    913     ///the processed nodes
     943    ///\brief The type of the map that indicates which nodes are processed.
    914944    typedef typename TR::ProcessedMap ProcessedMap;
    915     ///\brief The type of the map that stores the last
    916     ///arcs of the %DFS paths.
    917     typedef typename TR::PredMap PredMap;
    918     ///The type of the map that stores the distances of the nodes.
    919     typedef typename TR::DistMap DistMap;
    920945
    921946  public:
     947
    922948    /// Constructor.
    923949    DfsWizard() : TR() {}
    … …  
    935961    ~DfsWizard() {}
    936962
    937     ///Runs Dfs algorithm from a given node.
    938 
    939     ///Runs Dfs algorithm from a given node.
    940     ///The node can be given by the \ref source function.
     963    ///Runs DFS algorithm from a source node.
     964
     965    ///Runs DFS algorithm from a source node.
     966    ///The node can be given with the \ref source() function.
    941967    void run()
    942968    {
    … …  
    954980    }
    955981
    956     ///Runs Dfs algorithm from the given node.
    957 
    958     ///Runs Dfs algorithm from the given node.
     982    ///Runs DFS algorithm from the given node.
     983
     984    ///Runs DFS algorithm from the given node.
    959985    ///\param s is the given source.
    960986    void run(Node s)
    … …  
    962988      Base::_source=s;
    963989      run();
     990    }
     991
     992    /// Sets the source node, from which the Dfs algorithm runs.
     993
     994    /// Sets the source node, from which the Dfs algorithm runs.
     995    /// \param s is the source node.
     996    DfsWizard<TR> &source(Node s)
     997    {
     998      Base::_source=s;
     999      return *this;
    9641000    }
    9651001
    … …  
    9701006      DefPredMapBase(const TR &b) : TR(b) {}
    9711007    };
    972 
    9731008    ///\brief \ref named-templ-param "Named parameter"
    974     ///function for setting PredMap type
    975     ///
    976     /// \ref named-templ-param "Named parameter"
    977     ///function for setting PredMap type
    978     ///
     1009    ///for setting \ref PredMap object.
     1010    ///
     1011    ///\ref named-templ-param "Named parameter"
     1012    ///for setting \ref PredMap object.
    9791013    template<class T>
    9801014    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
    … …  
    9831017      return DfsWizard<DefPredMapBase<T> >(*this);
    9841018    }
    985 
    9861019
    9871020    template<class T>
    … …  
    9911024      DefReachedMapBase(const TR &b) : TR(b) {}
    9921025    };
    993 
    9941026    ///\brief \ref named-templ-param "Named parameter"
    995     ///function for setting ReachedMap
     1027    ///for setting \ref ReachedMap object.
    9961028    ///
    9971029    /// \ref named-templ-param "Named parameter"
    998     ///function for setting ReachedMap
    999     ///
     1030    ///for setting \ref ReachedMap object.
    10001031    template<class T>
    10011032    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
    … …  
    10041035      return DfsWizard<DefReachedMapBase<T> >(*this);
    10051036    }
    1006 
    10071037
    10081038    template<class T>
    … …  
    10121042      DefProcessedMapBase(const TR &b) : TR(b) {}
    10131043    };
    1014 
    10151044    ///\brief \ref named-templ-param "Named parameter"
    1016     ///function for setting ProcessedMap
     1045    ///for setting \ref ProcessedMap object.
    10171046    ///
    10181047    /// \ref named-templ-param "Named parameter"
    1019     ///function for setting ProcessedMap
    1020     ///
     1048    ///for setting \ref ProcessedMap object.
    10211049    template<class T>
    10221050    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
    … …  
    10321060      DefDistMapBase(const TR &b) : TR(b) {}
    10331061    };
    1034 
    10351062    ///\brief \ref named-templ-param "Named parameter"
    1036     ///function for setting DistMap type
    1037     ///
    1038     /// \ref named-templ-param "Named parameter"
    1039     ///function for setting DistMap type
    1040     ///
     1063    ///for setting \ref DistMap object.
     1064    ///
     1065    ///\ref named-templ-param "Named parameter"
     1066    ///for setting \ref DistMap object.
    10411067    template<class T>
    10421068    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
    … …  
    10441070      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    10451071      return DfsWizard<DefDistMapBase<T> >(*this);
    1046     }
    1047 
    1048     /// Sets the source node, from which the Dfs algorithm runs.
    1049 
    1050     /// Sets the source node, from which the Dfs algorithm runs.
    1051     /// \param s is the source node.
    1052     DfsWizard<TR> &source(Node s)
    1053     {
    1054       Base::_source=s;
    1055       return *this;
    10561072    }
    10571073
    … …  
    10831099
    10841100#ifdef DOXYGEN
    1085   /// \brief Visitor class for dfs.
     1101  /// \brief Visitor class for DFS.
    10861102  ///
    1087   /// It gives a simple interface for a functional interface for dfs
    1088   /// traversal. The traversal on a linear data structure.
     1103  /// This class defines the interface of the DfsVisit events, and
     1104  /// it could be the base of a real visitor class.
    10891105  template <typename _Digraph>
    10901106  struct DfsVisitor {
    … …  
    10921108    typedef typename Digraph::Arc Arc;
    10931109    typedef typename Digraph::Node Node;
    1094     /// \brief Called when the arc reach a node.
    1095     ///
    1096     /// It is called when the dfs find an arc which target is not
    1097     /// reached yet.
     1110    /// \brief Called for the source node of the DFS.
     1111    ///
     1112    /// This function is called for the source node of the DFS.
     1113    void start(const Node& node) {}
     1114    /// \brief Called when the source node is leaved.
     1115    ///
     1116    /// This function is called when the source node is leaved.
     1117    void stop(const Node& node) {}
     1118    /// \brief Called when a node is reached first time.
     1119    ///
     1120    /// This function is called when a node is reached first time.
     1121    void reach(const Node& node) {}
     1122    /// \brief Called when an arc reaches a new node.
     1123    ///
     1124    /// This function is called when the DFS finds an arc whose target node
     1125    /// is not reached yet.
    10981126    void discover(const Arc& arc) {}
    1099     /// \brief Called when the node reached first time.
    1100     ///
    1101     /// It is Called when the node reached first time.
    1102     void reach(const Node& node) {}
    1103     /// \brief Called when we step back on an arc.
    1104     ///
    1105     /// It is called when the dfs should step back on the arc.
    1106     void backtrack(const Arc& arc) {}
    1107     /// \brief Called when we step back from the node.
    1108     ///
    1109     /// It is called when we step back from the node.
    1110     void leave(const Node& node) {}
    1111     /// \brief Called when the arc examined but target of the arc
     1127    /// \brief Called when an arc is examined but its target node is
    11121128    /// already discovered.
    11131129    ///
    1114     /// It called when the arc examined but the target of the arc
     1130    /// This function is called when an arc is examined but its target node is
    11151131    /// already discovered.
    11161132    void examine(const Arc& arc) {}
    1117     /// \brief Called for the source node of the dfs.
    1118     ///
    1119     /// It is called for the source node of the dfs.
    1120     void start(const Node& node) {}
    1121     /// \brief Called when we leave the source node of the dfs.
    1122     ///
    1123     /// It is called when we leave the source node of the dfs.
    1124     void stop(const Node& node) {}
    1125 
     1133    /// \brief Called when the DFS steps back from a node.
     1134    ///
     1135    /// This function is called when the DFS steps back from a node.
     1136    void leave(const Node& node) {}
     1137    /// \brief Called when the DFS steps back on an arc.
     1138    ///
     1139    /// This function is called when the DFS steps back on an arc.
     1140    void backtrack(const Arc& arc) {}
    11261141  };
    11271142#else
    … …  
    11311146    typedef typename Digraph::Arc Arc;
    11321147    typedef typename Digraph::Node Node;
    1133     void discover(const Arc&) {}
    1134     void reach(const Node&) {}
    1135     void backtrack(const Arc&) {}
    1136     void leave(const Node&) {}
    1137     void examine(const Arc&) {}
    11381148    void start(const Node&) {}
    11391149    void stop(const Node&) {}
     1150    void reach(const Node&) {}
     1151    void discover(const Arc&) {}
     1152    void examine(const Arc&) {}
     1153    void leave(const Node&) {}
     1154    void backtrack(const Arc&) {}
    11401155
    11411156    template <typename _Visitor>
    … …  
    11441159        Arc arc;
    11451160        Node node;
    1146         visitor.discover(arc);
    1147         visitor.reach(node);
    1148         visitor.backtrack(arc);
    1149         visitor.leave(node);
    1150         visitor.examine(arc);
    11511161        visitor.start(node);
    11521162        visitor.stop(arc);
     1163        visitor.reach(node);
     1164        visitor.discover(arc);
     1165        visitor.examine(arc);
     1166        visitor.leave(node);
     1167        visitor.backtrack(arc);
    11531168      }
    11541169      _Visitor& visitor;
    … …  
    11601175  ///
    11611176  /// Default traits class of DfsVisit class.
    1162   /// \tparam _Digraph Digraph type.
     1177  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11631178  template<class _Digraph>
    11641179  struct DfsVisitDefaultTraits {
    11651180
    1166     /// \brief The digraph type the algorithm runs on.
     1181    /// \brief The type of the digraph the algorithm runs on.
    11671182    typedef _Digraph Digraph;
    11681183
    … …  
    11701185    ///
    11711186    /// The type of the map that indicates which nodes are reached.
    1172     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1173     /// \todo named parameter to set this type, function to read and write.
     1187    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    11741188    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    11751189
    1176     /// \brief Instantiates a ReachedMap.
     1190    /// \brief Instantiates a \ref ReachedMap.
    11771191    ///
    11781192    /// This function instantiates a \ref ReachedMap.
    … …  
    11851199  };
    11861200
    1187   /// %DFS Visit algorithm class.
    1188 
    11891201  /// \ingroup search
     1202  ///
     1203  /// \brief %DFS algorithm class with visitor interface.
     1204  ///
    11901205  /// This class provides an efficient implementation of the %DFS algorithm
    11911206  /// with visitor interface.
    … …  
    11931208  /// The %DfsVisit class provides an alternative interface to the Dfs
    11941209  /// class. It works with callback mechanism, the DfsVisit object calls
    1195   /// on every dfs event the \c Visitor class member functions.
     1210  /// the member functions of the \c Visitor class on every DFS event.
    11961211  ///
    1197   /// \tparam _Digraph The digraph type the algorithm runs on.
     1212  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11981213  /// The default value is
    1199   /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
    1200   /// is only passed to \ref DfsDefaultTraits.
    1201   /// \tparam _Visitor The Visitor object for the algorithm. The
    1202   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
    1203   /// does not observe the Dfs events. If you want to observe the dfs
    1204   /// events you should implement your own Visitor class.
     1214  /// \ref ListDigraph. The value of _Digraph is not used directly by
     1215  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
     1216  /// \tparam _Visitor The Visitor type that is used by the algorithm.
     1217  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
     1218  /// does not observe the DFS events. If you want to observe the DFS
     1219  /// events, you should implement your own visitor class.
    12051220  /// \tparam _Traits Traits class to set various data types used by the
    12061221  /// algorithm. The default traits class is
    12071222  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
    12081223  /// See \ref DfsVisitDefaultTraits for the documentation of
    1209   /// a Dfs visit traits class.
    1210   ///
    1211   /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
     1224  /// a DFS visit traits class.
    12121225#ifdef DOXYGEN
    12131226  template <typename _Digraph, typename _Visitor, typename _Traits>
    … …  
    12231236    ///
    12241237    /// This error represents problems in the initialization
    1225     /// of the parameters of the algorithms.
     1238    /// of the parameters of the algorithm.
    12261239    class UninitializedParameter : public lemon::UninitializedParameter {
    12271240    public:
    … …  
    12321245    };
    12331246
     1247    ///The traits class.
    12341248    typedef _Traits Traits;
    12351249
     1250    ///The type of the digraph the algorithm runs on.
    12361251    typedef typename Traits::Digraph Digraph;
    12371252
     1253    ///The visitor type used by the algorithm.
    12381254    typedef _Visitor Visitor;
    12391255
    1240     ///The type of the map indicating which nodes are reached.
     1256    ///The type of the map that indicates which nodes are reached.
    12411257    typedef typename Traits::ReachedMap ReachedMap;
    12421258
    … …  
    12481264    typedef typename Digraph::OutArcIt OutArcIt;
    12491265
    1250     /// Pointer to the underlying digraph.
     1266    //Pointer to the underlying digraph.
    12511267    const Digraph *_digraph;
    1252     /// Pointer to the visitor object.
     1268    //Pointer to the visitor object.
    12531269    Visitor *_visitor;
    1254     ///Pointer to the map of reached status of the nodes.
     1270    //Pointer to the map of reached status of the nodes.
    12551271    ReachedMap *_reached;
    1256     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1272    //Indicates if _reached is locally allocated (true) or not.
    12571273    bool local_reached;
    12581274
    … …  
    12601276    int _stack_head;
    12611277
    1262     /// \brief Creates the maps if necessary.
    1263     ///
    1264     /// Creates the maps if necessary.
     1278    ///Creates the maps if necessary.
     1279    ///\todo Better memory allocation (instead of new).
    12651280    void create_maps() {
    12661281      if(!_reached) {
    … …  
    12891304    };
    12901305    /// \brief \ref named-templ-param "Named parameter" for setting
    1291     /// ReachedMap type
    1292     ///
    1293     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1306    /// ReachedMap type.
     1307    ///
     1308    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    12941309    template <class T>
    12951310    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
    … …  
    13051320    /// Constructor.
    13061321    ///
    1307     /// \param digraph the digraph the algorithm will run on.
    1308     /// \param visitor The visitor of the algorithm.
    1309     ///
     1322    /// \param digraph The digraph the algorithm runs on.
     1323    /// \param visitor The visitor object of the algorithm.
    13101324    DfsVisit(const Digraph& digraph, Visitor& visitor)
    13111325      : _digraph(&digraph), _visitor(&visitor),
    … …  
    13131327
    13141328    /// \brief Destructor.
    1315     ///
    1316     /// Destructor.
    13171329    ~DfsVisit() {
    13181330      if(local_reached) delete _reached;
    13191331    }
    13201332
    1321     /// \brief Sets the map indicating if a node is reached.
    1322     ///
    1323     /// Sets the map indicating if a node is reached.
     1333    /// \brief Sets the map that indicates which nodes are reached.
     1334    ///
     1335    /// Sets the map that indicates which nodes are reached.
    13241336    /// If you don't use this function before calling \ref run(),
    1325     /// it will allocate one. The destuctor deallocates this
     1337    /// it will allocate one. The destructor deallocates this
    13261338    /// automatically allocated map, of course.
    13271339    /// \return <tt> (*this) </tt>
    … …  
    13361348
    13371349  public:
     1350
    13381351    /// \name Execution control
    13391352    /// The simplest way to execute the algorithm is to use
    1340     /// one of the member functions called \c run(...).
     1353    /// one of the member functions called \ref lemon::DfsVisit::run()
     1354    /// "run()".
    13411355    /// \n
    1342     /// If you need more control on the execution,
    1343     /// first you must call \ref init(), then you can adda source node
    1344     /// with \ref addSource().
    1345     /// Finally \ref start() will perform the actual path
    1346     /// computation.
     1356    /// If you need more control on the execution, first you must call
     1357    /// \ref lemon::DfsVisit::init() "init()", then you can add several
     1358    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
     1359    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
     1360    /// actual path computation.
    13471361
    13481362    /// @{
     1363
    13491364    /// \brief Initializes the internal data structures.
    13501365    ///
    13511366    /// Initializes the internal data structures.
    1352     ///
    13531367    void init() {
    13541368      create_maps();
    … …  
    13601374    }
    13611375
    1362     /// \brief Adds a new source node.
    1363     ///
    1364     /// Adds a new source node to the set of nodes to be processed.
    1365     void addSource(Node s) {
     1376    ///Adds a new source node.
     1377
     1378    ///Adds a new source node to the set of nodes to be processed.
     1379    ///
     1380    ///\pre The stack must be empty. (Otherwise the algorithm gives
     1381    ///false results.)
     1382    ///
     1383    ///\warning Distances will be wrong (or at least strange) in case of
     1384    ///multiple sources.
     1385    void addSource(Node s)
     1386    {
     1387      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
    13661388      if(!(*_reached)[s]) {
    13671389          _reached->set(s,true);
    … …  
    13841406    /// \return The processed arc.
    13851407    ///
    1386     /// \pre The stack must not be empty!
     1408    /// \pre The stack must not be empty.
    13871409    Arc processNextArc() {
    13881410      Arc e = _stack[_stack_head];
    … …  
    14181440    /// \return The next arc to be processed or INVALID if the stack is
    14191441    /// empty.
    1420     Arc nextArc() {
     1442    Arc nextArc() const {
    14211443      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
    14221444    }
    14231445
    14241446    /// \brief Returns \c false if there are nodes
    1425     /// to be processed in the queue
     1447    /// to be processed.
    14261448    ///
    14271449    /// Returns \c false if there are nodes
    1428     /// to be processed in the queue
    1429     bool emptyQueue() { return _stack_head < 0; }
     1450    /// to be processed in the queue (stack).
     1451    bool emptyQueue() const { return _stack_head < 0; }
    14301452
    14311453    /// \brief Returns the number of the nodes to be processed.
    14321454    ///
    1433     /// Returns the number of the nodes to be processed in the queue.
    1434     int queueSize() { return _stack_head + 1; }
     1455    /// Returns the number of the nodes to be processed in the queue (stack).
     1456    int queueSize() const { return _stack_head + 1; }
    14351457
    14361458    /// \brief Executes the algorithm.
    … …  
    14381460    /// Executes the algorithm.
    14391461    ///
    1440     /// \pre init() must be called and at least one node should be added
    1441     /// with addSource() before using this function.
     1462    /// This method runs the %DFS algorithm from the root node
     1463    /// in order to compute the %DFS path to each node.
     1464    ///
     1465    /// The algorithm computes
     1466    /// - the %DFS tree,
     1467    /// - the distance of each node from the root in the %DFS tree.
     1468    ///
     1469    /// \pre init() must be called and a root node should be
     1470    /// added with addSource() before using this function.
     1471    ///
     1472    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
     1473    /// \code
     1474    ///   while ( !d.emptyQueue() ) {
     1475    ///     d.processNextArc();
     1476    ///   }
     1477    /// \endcode
    14421478    void start() {
    14431479      while ( !emptyQueue() ) processNextArc();
    14441480    }
    14451481
    1446     /// \brief Executes the algorithm until \c dest is reached.
    1447     ///
    1448     /// Executes the algorithm until \c dest is reached.
    1449     ///
    1450     /// \pre init() must be called and at least one node should be added
     1482    /// \brief Executes the algorithm until the given target node is reached.
     1483    ///
     1484    /// Executes the algorithm until the given target node is reached.
     1485    ///
     1486    /// This method runs the %DFS algorithm from the root node
     1487    /// in order to compute the DFS path to \c dest.
     1488    ///
     1489    /// The algorithm computes
     1490    /// - the %DFS path to \c dest,
     1491    /// - the distance of \c dest from the root in the %DFS tree.
     1492    ///
     1493    /// \pre init() must be called and a root node should be added
    14511494    /// with addSource() before using this function.
    14521495    void start(Node dest) {
    … …  
    14591502    /// Executes the algorithm until a condition is met.
    14601503    ///
    1461     /// \pre init() must be called and at least one node should be added
     1504    /// This method runs the %DFS algorithm from the root node
     1505    /// until an arc \c a with <tt>am[a]</tt> true is found.
     1506    ///
     1507    /// \param am A \c bool (or convertible) arc map. The algorithm
     1508    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
     1509    ///
     1510    /// \return The reached arc \c a with <tt>am[a]</tt> true or
     1511    /// \c INVALID if no such arc was found.
     1512    ///
     1513    /// \pre init() must be called and a root node should be added
    14621514    /// with addSource() before using this function.
    14631515    ///
    1464     /// \param em must be a bool (or convertible) arc map. The algorithm
    1465     /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
    1466     ///
    1467     ///\return The reached arc \c e with <tt>em[e]</tt> true or
    1468     ///\c INVALID if no such arc was found.
    1469     ///
    1470     /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
     1516    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
    14711517    /// not a node map.
    1472     template <typename EM>
    1473     Arc start(const EM &em) {
    1474       while ( !emptyQueue() && !em[_stack[_stack_head]] )
     1518    template <typename AM>
     1519    Arc start(const AM &am) {
     1520      while ( !emptyQueue() && !am[_stack[_stack_head]] )
    14751521        processNextArc();
    14761522      return emptyQueue() ? INVALID : _stack[_stack_head];
    14771523    }
    14781524
    1479     /// \brief Runs %DFSVisit algorithm from node \c s.
    1480     ///
    1481     /// This method runs the %DFS algorithm from a root node \c s.
    1482     /// \note d.run(s) is just a shortcut of the following code.
     1525    /// \brief Runs the algorithm from the given node.
     1526    ///
     1527    /// This method runs the %DFS algorithm from node \c s.
     1528    /// in order to compute the DFS path to each node.
     1529    ///
     1530    /// The algorithm computes
     1531    /// - the %DFS tree,
     1532    /// - the distance of each node from the root in the %DFS tree.
     1533    ///
     1534    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
    14831535    ///\code
    14841536    ///   d.init();
    … …  
    14921544    }
    14931545
    1494     /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
     1546    /// \brief Finds the %DFS path between \c s and \c t.
     1547
     1548    /// This method runs the %DFS algorithm from node \c s
     1549    /// in order to compute the DFS path to \c t.
     1550    ///
     1551    /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
     1552    /// if \c t is reachable form \c s, \c 0 otherwise.
     1553    ///
     1554    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
     1555    /// just a shortcut of the following code.
     1556    ///\code
     1557    ///   d.init();
     1558    ///   d.addSource(s);
     1559    ///   d.start(t);
     1560    ///\endcode
     1561    int run(Node s,Node t) {
     1562      init();
     1563      addSource(s);
     1564      start(t);
     1565      return reached(t)?_stack_head+1:0;
     1566    }
     1567
     1568    /// \brief Runs the algorithm to visit all nodes in the digraph.
    14951569
    14961570    /// This method runs the %DFS algorithm in order to
    1497     /// compute the %DFS path to each node. The algorithm computes
    1498     /// - The %DFS tree.
    1499     /// - The distance of each node from the root in the %DFS tree.
    1500     ///
    1501     ///\note d.run() is just a shortcut of the following code.
     1571    /// compute the %DFS path to each node.
     1572    ///
     1573    /// The algorithm computes
     1574    /// - the %DFS tree,
     1575    /// - the distance of each node from the root in the %DFS tree.
     1576    ///
     1577    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
    15021578    ///\code
    1503     ///  d.init();
    1504     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    1505     ///    if (!d.reached(it)) {
    1506     ///      d.addSource(it);
    1507     ///      d.start();
    1508     ///    }
    1509     ///  }
     1579    ///   d.init();
     1580    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
     1581    ///     if (!d.reached(n)) {
     1582    ///       d.addSource(n);
     1583    ///       d.start();
     1584    ///     }
     1585    ///   }
    15101586    ///\endcode
    15111587    void run() {
    … …  
    15181594      }
    15191595    }
     1596
    15201597    ///@}
    15211598
    … …  
    15231600    /// The result of the %DFS algorithm can be obtained using these
    15241601    /// functions.\n
    1525     /// Before the use of these functions,
    1526     /// either run() or start() must be called.
     1602    /// Either \ref lemon::DfsVisit::run() "run()" or
     1603    /// \ref lemon::DfsVisit::start() "start()" must be called before
     1604    /// using them.
    15271605    ///@{
    1528     /// \brief Checks if a node is reachable from the root.
     1606
     1607    /// \brief Checks if a node is reachable from the root(s).
    15291608    ///
    15301609    /// Returns \c true if \c v is reachable from the root(s).
    1531     /// \warning The source nodes are inditated as unreachable.
    15321610    /// \pre Either \ref run() or \ref start()
    15331611    /// must be called before using this function.
    1534     ///
    15351612    bool reached(Node v) { return (*_reached)[v]; }
     1613
    15361614    ///@}
     1615
    15371616  };
    15381617
    1539 
    15401618} //END OF NAMESPACE LEMON
    15411619
    15421620#endif
    1543 
Note: See TracChangeset for help on using the changeset viewer.