COIN-OR::LEMON - Graph Library

Changeset 244:c30731a37f91 in lemon-1.2 for lemon


Ignore:
Timestamp:
08/03/08 13:34:57 (16 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.
Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r210 r244  
    2222///\ingroup search
    2323///\file
    24 ///\brief Bfs algorithm.
     24///\brief BFS algorithm.
    2525
    2626#include <lemon/list_graph.h>
     
    3333namespace lemon {
    3434
    35 
    36 
    3735  ///Default traits class of Bfs class.
    3836
     
    4240  struct BfsDefaultTraits
    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 shortest 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 shortest 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);
    62     }
     58    static PredMap *createPredMap(const Digraph &g)
     59    {
     60      return new PredMap(g);
     61    }
     62
    6363    ///The type of the map that indicates which nodes are processed.
    6464
    6565    ///The type of the map that indicates which nodes are processed.
    6666    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    67     ///\todo named parameter to set this type, function to read and write.
     67    ///By default it is a NullMap.
    6868    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    69     ///Instantiates a ProcessedMap.
     69    ///Instantiates a \ref ProcessedMap.
    7070
    7171    ///This function instantiates a \ref ProcessedMap.
     
    7373    ///we would like to define the \ref ProcessedMap
    7474#ifdef DOXYGEN
    75     static ProcessedMap *createProcessedMap(const GR &g)
     75    static ProcessedMap *createProcessedMap(const Digraph &g)
    7676#else
    77     static ProcessedMap *createProcessedMap(const GR &)
     77    static ProcessedMap *createProcessedMap(const Digraph &)
    7878#endif
    7979    {
    8080      return new ProcessedMap();
    8181    }
     82
    8283    ///The type of the map that indicates which nodes are reached.
    8384
    8485    ///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.
    85101    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    86     ///\todo named parameter to set this type, function to read and write.
    87     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    88     ///Instantiates a 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 GR &G)
    94     {
    95       return new ReachedMap(G);
    96     }
    97     ///The type of the map that stores the dists of the nodes.
    98 
    99     ///The type of the map that stores the dists of the nodes.
    100     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    101     ///
    102102    typedef typename Digraph::template NodeMap<int> DistMap;
    103     ///Instantiates a DistMap.
     103    ///Instantiates a \ref DistMap.
    104104
    105105    ///This function instantiates a \ref DistMap.
    106     ///\param G is the digraph, to which we would like to define
    107     ///the \ref DistMap
    108     static DistMap *createDistMap(const GR &G)
    109     {
    110       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);
    111111    }
    112112  };
     
    117117  ///This class provides an efficient implementation of the %BFS algorithm.
    118118  ///
    119   ///\tparam GR The digraph type the algorithm runs on. The default value is
    120   ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
    121   ///is only passed to \ref BfsDefaultTraits.
     119  ///There is also a \ref bfs() "function type interface" for the BFS
     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 Bfs, it is only passed to \ref BfsDefaultTraits.
    122126  ///\tparam TR Traits class to set various data types used by the algorithm.
    123127  ///The default traits class is
     
    125129  ///See \ref BfsDefaultTraits for the documentation of
    126130  ///a Bfs traits class.
    127 
    128131#ifdef DOXYGEN
    129132  template <typename GR,
     
    135138  class Bfs {
    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    ///shortest 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 
    154     ///\brief The type of the map that stores the last
    155     ///arcs of the shortest paths.
    156     typedef typename TR::PredMap PredMap;
    157     ///The type of the map indicating which nodes are reached.
    158     typedef typename TR::ReachedMap ReachedMap;
    159     ///The type of the map indicating which nodes are processed.
    160     typedef typename TR::ProcessedMap ProcessedMap;
    161     ///The type of the map that stores the dists of the nodes.
    162     typedef typename TR::DistMap DistMap;
     168
    163169  private:
    164170
     
    168174    typedef typename Digraph::OutArcIt OutArcIt;
    169175
    170     /// Pointer to the underlying digraph.
     176    //Pointer to the underlying digraph.
    171177    const Digraph *G;
    172     ///Pointer to the map of predecessors arcs.
     178    //Pointer to the map of predecessor arcs.
    173179    PredMap *_pred;
    174     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     180    //Indicates if _pred is locally allocated (true) or not.
    175181    bool local_pred;
    176     ///Pointer to the map of distances.
     182    //Pointer to the map of distances.
    177183    DistMap *_dist;
    178     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     184    //Indicates if _dist is locally allocated (true) or not.
    179185    bool local_dist;
    180     ///Pointer to the map of reached status of the nodes.
     186    //Pointer to the map of reached status of the nodes.
    181187    ReachedMap *_reached;
    182     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     188    //Indicates if _reached is locally allocated (true) or not.
    183189    bool local_reached;
    184     ///Pointer to the map of processed status of the nodes.
     190    //Pointer to the map of processed status of the nodes.
    185191    ProcessedMap *_processed;
    186     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     192    //Indicates if _processed is locally allocated (true) or not.
    187193    bool local_processed;
    188194
     
    192198
    193199    ///Creates the maps if necessary.
    194 
    195200    ///\todo Better memory allocation (instead of new).
    196201    void create_maps()
     
    235240    };
    236241    ///\brief \ref named-templ-param "Named parameter" for setting
    237     ///PredMap type
    238     ///
    239     ///\ref named-templ-param "Named parameter" for setting PredMap type
    240     ///
     242    ///\ref PredMap type.
     243    ///
     244    ///\ref named-templ-param "Named parameter" for setting
     245    ///\ref PredMap type.
    241246    template <class T>
    242247    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
     
    253258    };
    254259    ///\brief \ref named-templ-param "Named parameter" for setting
    255     ///DistMap type
    256     ///
    257     ///\ref named-templ-param "Named parameter" for setting DistMap type
    258     ///
     260    ///\ref DistMap type.
     261    ///
     262    ///\ref named-templ-param "Named parameter" for setting
     263    ///\ref DistMap type.
    259264    template <class T>
    260265    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
     
    271276    };
    272277    ///\brief \ref named-templ-param "Named parameter" for setting
    273     ///ReachedMap type
    274     ///
    275     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    276     ///
     278    ///\ref ReachedMap type.
     279    ///
     280    ///\ref named-templ-param "Named parameter" for setting
     281    ///\ref ReachedMap type.
    277282    template <class T>
    278283    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
     
    289294    };
    290295    ///\brief \ref named-templ-param "Named parameter" for setting
    291     ///ProcessedMap type
    292     ///
    293     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    294     ///
     296    ///\ref ProcessedMap type.
     297    ///
     298    ///\ref named-templ-param "Named parameter" for setting
     299    ///\ref ProcessedMap type.
    295300    template <class T>
    296301    struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
     
    300305    struct DefDigraphProcessedMapTraits : public Traits {
    301306      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    302       static ProcessedMap *createProcessedMap(const Digraph &G)
     307      static ProcessedMap *createProcessedMap(const Digraph &g)
    303308      {
    304         return new ProcessedMap(G);
    305       }
    306     };
    307     ///\brief \ref named-templ-param "Named parameter"
    308     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    309     ///
    310     ///\ref named-templ-param "Named parameter"
    311     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     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>.
    312317    ///If you don't set it explicitly, it will be automatically allocated.
    313318    template <class T>
     
    323328    ///Constructor.
    324329
    325     ///\param _G the digraph the algorithm will run on.
    326     ///
    327     Bfs(const Digraph& _G) :
    328       G(&_G),
     330    ///Constructor.
     331    ///\param g The digraph the algorithm runs on.
     332    Bfs(const Digraph &g) :
     333      G(&g),
    329334      _pred(NULL), local_pred(false),
    330335      _dist(NULL), local_dist(false),
     
    342347    }
    343348
    344     ///Sets the map storing the predecessor arcs.
    345 
    346     ///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.
    347352    ///If you don't use this function before calling \ref run(),
    348353    ///it will allocate one. The destructor deallocates this
     
    359364    }
    360365
    361     ///Sets the map indicating the reached nodes.
    362 
    363     ///Sets the map indicating the reached nodes.
     366    ///Sets the map that indicates which nodes are reached.
     367
     368    ///Sets the map that indicates which nodes are reached.
    364369    ///If you don't use this function before calling \ref run(),
    365370    ///it will allocate one. The destructor deallocates this
     
    376381    }
    377382
    378     ///Sets the map indicating the processed nodes.
    379 
    380     ///Sets the map indicating the processed nodes.
     383    ///Sets the map that indicates which nodes are processed.
     384
     385    ///Sets the map that indicates which nodes are processed.
    381386    ///If you don't use this function before calling \ref run(),
    382387    ///it will allocate one. The destructor deallocates this
     
    393398    }
    394399
    395     ///Sets the map storing the distances calculated by the algorithm.
    396 
    397     ///Sets the map storing the distances calculated by the algorithm.
     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.
    398404    ///If you don't use this function before calling \ref run(),
    399405    ///it will allocate one. The destructor deallocates this
     
    411417
    412418  public:
     419
    413420    ///\name Execution control
    414421    ///The simplest way to execute the algorithm is to use
    415     ///one of the member functions called \c run(...).
     422    ///one of the member functions called \ref lemon::Bfs::run() "run()".
    416423    ///\n
    417     ///If you need more control on the execution,
    418     ///first you must call \ref init(), then you can add several source nodes
    419     ///with \ref addSource().
    420     ///Finally \ref start() will perform the actual path
    421     ///computation.
     424    ///If you need more control on the execution, first you must call
     425    ///\ref lemon::Bfs::init() "init()", then you can add several source
     426    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
     427    ///Finally \ref lemon::Bfs::start() "start()" will perform the
     428    ///actual path computation.
    422429
    423430    ///@{
    424431
    425     ///\brief Initializes the internal data structures.
    426     ///
     432    ///Initializes the internal data structures.
     433
    427434    ///Initializes the internal data structures.
    428435    ///
     
    462469    ///\return The processed node.
    463470    ///
    464     ///\warning The queue must not be empty!
     471    ///\pre The queue must not be empty.
    465472    Node processNextNode()
    466473    {
     
    484491    ///Processes the next node.
    485492
    486     ///Processes the next node. And checks that the given target node
     493    ///Processes the next node and checks if the given target node
    487494    ///is reached. If the target node is reachable from the processed
    488     ///node then the reached parameter will be set true. The reached
    489     ///parameter should be initially false.
     495    ///node, then the \c reach parameter will be set to \c true.
    490496    ///
    491497    ///\param target The target node.
    492     ///\retval reach Indicates that the target node is reached.
     498    ///\retval reach Indicates if the target node is reached.
     499    ///It should be initially \c false.
     500    ///
    493501    ///\return The processed node.
    494502    ///
    495     ///\warning The queue must not be empty!
     503    ///\pre The queue must not be empty.
    496504    Node processNextNode(Node target, bool& reach)
    497505    {
     
    516524    ///Processes the next node.
    517525
    518     ///Processes the next node. And checks that at least one of
    519     ///reached node has true value in the \c nm node map. If one node
    520     ///with true value is reachable from the processed node then the
    521     ///rnode parameter will be set to the first of such nodes.
    522     ///
    523     ///\param nm The node map of possible targets.
     526    ///Processes the next node and checks if at least one of reached
     527    ///nodes has \c true value in the \c nm node map. If one node
     528    ///with \c true value is reachable from the processed node, then the
     529    ///\c rnode parameter will be set to the first of such nodes.
     530    ///
     531    ///\param nm A \c bool (or convertible) node map that indicates the
     532    ///possible targets.
    524533    ///\retval rnode The reached target node.
     534    ///It should be initially \c INVALID.
     535    ///
    525536    ///\return The processed node.
    526537    ///
    527     ///\warning The queue must not be empty!
     538    ///\pre The queue must not be empty.
    528539    template<class NM>
    529540    Node processNextNode(const NM& nm, Node& rnode)
     
    547558    }
    548559
    549     ///Next node to be processed.
    550 
    551     ///Next node to be processed.
    552     ///
    553     ///\return The next node to be processed or INVALID if the queue is
    554     /// empty.
    555     Node nextNode()
     560    ///The next node to be processed.
     561
     562    ///Returns the next node to be processed or \c INVALID if the queue
     563    ///is empty.
     564    Node nextNode() const
    556565    {
    557566      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
     
    559568
    560569    ///\brief Returns \c false if there are nodes
    561     ///to be processed in the queue
     570    ///to be processed.
    562571    ///
    563572    ///Returns \c false if there are nodes
    564     ///to be processed in the queue
    565     bool emptyQueue() { return _queue_tail==_queue_head; }
     573    ///to be processed in the queue.
     574    bool emptyQueue() const { return _queue_tail==_queue_head; }
     575
    566576    ///Returns the number of the nodes to be processed.
    567577
    568578    ///Returns the number of the nodes to be processed in the queue.
    569     int queueSize() { return _queue_head-_queue_tail; }
     579    int queueSize() const { return _queue_head-_queue_tail; }
    570580
    571581    ///Executes the algorithm.
     
    573583    ///Executes the algorithm.
    574584    ///
    575     ///\pre init() must be called and at least one node should be added
    576     ///with addSource() before using this function.
    577     ///
    578585    ///This method runs the %BFS algorithm from the root node(s)
    579     ///in order to
    580     ///compute the
    581     ///shortest path to each node. The algorithm computes
    582     ///- The shortest path tree.
    583     ///- The distance of each node from the root(s).
     586    ///in order to compute the shortest path to each node.
     587    ///
     588    ///The algorithm computes
     589    ///- the shortest path tree (forest),
     590    ///- the distance of each node from the root(s).
     591    ///
     592    ///\pre init() must be called and at least one root node should be
     593    ///added with addSource() before using this function.
     594    ///
     595    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
     596    ///\code
     597    ///  while ( !b.emptyQueue() ) {
     598    ///    b.processNextNode();
     599    ///  }
     600    ///\endcode
    584601    void start()
    585602    {
     
    587604    }
    588605
    589     ///Executes the algorithm until \c dest is reached.
    590 
    591     ///Executes the algorithm until \c dest is reached.
    592     ///
    593     ///\pre init() must be called and at least one node should be added
    594     ///with addSource() before using this function.
     606    ///Executes the algorithm until the given target node is reached.
     607
     608    ///Executes the algorithm until the given target node is reached.
    595609    ///
    596610    ///This method runs the %BFS algorithm from the root node(s)
    597611    ///in order to compute the shortest path to \c dest.
     612    ///
    598613    ///The algorithm computes
    599     ///- The shortest path to \c  dest.
    600     ///- The distance of \c dest from the root(s).
     614    ///- the shortest path to \c dest,
     615    ///- the distance of \c dest from the root(s).
     616    ///
     617    ///\pre init() must be called and at least one root node should be
     618    ///added with addSource() before using this function.
     619    ///
     620    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
     621    ///\code
     622    ///  bool reach = false;
     623    ///  while ( !b.emptyQueue() && !reach ) {
     624    ///    b.processNextNode(t, reach);
     625    ///  }
     626    ///\endcode
    601627    void start(Node dest)
    602628    {
     
    609635    ///Executes the algorithm until a condition is met.
    610636    ///
    611     ///\pre init() must be called and at least one node should be added
    612     ///with addSource() before using this function.
    613     ///
    614     ///\param nm must be a bool (or convertible) node map. The
    615     ///algorithm will stop when it reaches a node \c v with
    616     /// <tt>nm[v]</tt> true.
     637    ///This method runs the %BFS algorithm from the root node(s) in
     638    ///order to compute the shortest path to a node \c v with
     639    /// <tt>nm[v]</tt> true, if such a node can be found.
     640    ///
     641    ///\param nm A \c bool (or convertible) node map. The algorithm
     642    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
    617643    ///
    618644    ///\return The reached node \c v with <tt>nm[v]</tt> true or
    619645    ///\c INVALID if no such node was found.
    620     template<class NM>
    621     Node start(const NM &nm)
     646    ///
     647    ///\pre init() must be called and at least one root node should be
     648    ///added with addSource() before using this function.
     649    ///
     650    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
     651    ///\code
     652    ///  Node rnode = INVALID;
     653    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
     654    ///    b.processNextNode(nm, rnode);
     655    ///  }
     656    ///  return rnode;
     657    ///\endcode
     658    template<class NodeBoolMap>
     659    Node start(const NodeBoolMap &nm)
    622660    {
    623661      Node rnode = INVALID;
     
    628666    }
    629667
    630     ///Runs %BFS algorithm from node \c s.
    631 
    632     ///This method runs the %BFS algorithm from a root node \c s
    633     ///in order to
    634     ///compute the
    635     ///shortest path to each node. The algorithm computes
    636     ///- The shortest path tree.
    637     ///- The distance of each node from the root.
    638     ///
    639     ///\note b.run(s) is just a shortcut of the following code.
     668    ///Runs the algorithm from the given node.
     669
     670    ///This method runs the %BFS algorithm from node \c s
     671    ///in order to compute the shortest path to each node.
     672    ///
     673    ///The algorithm computes
     674    ///- the shortest path tree,
     675    ///- the distance of each node from the root.
     676    ///
     677    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    640678    ///\code
    641679    ///  b.init();
     
    651689    ///Finds the shortest path between \c s and \c t.
    652690
    653     ///Finds the shortest path between \c s and \c t.
    654     ///
    655     ///\return The length of the shortest s---t path if there exists one,
    656     ///0 otherwise.
    657     ///\note Apart from the return value, b.run(s) is
    658     ///just a shortcut of the following code.
     691    ///This method runs the %BFS algorithm from node \c s
     692    ///in order to compute the shortest path to \c t.
     693    ///
     694    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
     695    ///if \c t is reachable form \c s, \c 0 otherwise.
     696    ///
     697    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     698    ///shortcut of the following code.
    659699    ///\code
    660700    ///  b.init();
     
    669709    }
    670710
     711    ///Runs the algorithm to visit all nodes in the digraph.
     712
     713    ///This method runs the %BFS algorithm in order to
     714    ///compute the shortest path to each node.
     715    ///
     716    ///The algorithm computes
     717    ///- the shortest path tree (forest),
     718    ///- the distance of each node from the root(s).
     719    ///
     720    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     721    ///\code
     722    ///  b.init();
     723    ///  for (NodeIt n(gr); n != INVALID; ++n) {
     724    ///    if (!b.reached(n)) {
     725    ///      b.addSource(n);
     726    ///      b.start();
     727    ///    }
     728    ///  }
     729    ///\endcode
     730    void run() {
     731      init();
     732      for (NodeIt n(*G); n != INVALID; ++n) {
     733        if (!reached(n)) {
     734          addSource(n);
     735          start();
     736        }
     737      }
     738    }
     739
    671740    ///@}
    672741
     
    674743    ///The result of the %BFS algorithm can be obtained using these
    675744    ///functions.\n
    676     ///Before the use of these functions,
    677     ///either run() or start() must be calleb.
     745    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     746    ///"start()" must be called before using them.
    678747
    679748    ///@{
    680749
    681     typedef PredMapPath<Digraph, PredMap> Path;
    682 
    683     ///Gives back the shortest path.
    684 
    685     ///Gives back the shortest path.
    686     ///\pre The \c t should be reachable from the source.
    687     Path path(Node t)
    688     {
    689       return Path(*G, *_pred, t);
    690     }
     750    ///The shortest path to a node.
     751
     752    ///Returns the shortest path to a node.
     753    ///
     754    ///\warning \c t should be reachable from the root(s).
     755    ///
     756    ///\pre Either \ref run() or \ref start() must be called before
     757    ///using this function.
     758    Path path(Node t) const { return Path(*G, *_pred, t); }
    691759
    692760    ///The distance of a node from the root(s).
    693761
    694762    ///Returns the distance of a node from the root(s).
    695     ///\pre \ref run() must be called before using this function.
    696     ///\warning If node \c v in unreachable from the root(s) the return value
    697     ///of this function is undefined.
     763    ///
     764    ///\warning If node \c v is not reachable from the root(s), then
     765    ///the return value of this function is undefined.
     766    ///
     767    ///\pre Either \ref run() or \ref start() must be called before
     768    ///using this function.
    698769    int dist(Node v) const { return (*_dist)[v]; }
    699770
    700     ///Returns the 'previous arc' of the shortest path tree.
    701 
    702     ///For a node \c v it returns the 'previous arc'
    703     ///of the shortest path tree,
    704     ///i.e. it returns the last arc of a shortest path from the root(s) to \c
    705     ///v. It is \ref INVALID
    706     ///if \c v is unreachable from the root(s) or \c v is a root. The
    707     ///shortest path tree used here is equal to the shortest path tree used in
    708     ///\ref predNode().
    709     ///\pre Either \ref run() or \ref start() must be called before using
    710     ///this function.
     771    ///Returns the 'previous arc' of the shortest path tree for a node.
     772
     773    ///This function returns the 'previous arc' of the shortest path
     774    ///tree for the node \c v, i.e. it returns the last arc of a
     775    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     776    ///is not reachable from the root(s) or if \c v is a root.
     777    ///
     778    ///The shortest path tree used here is equal to the shortest path
     779    ///tree used in \ref predNode().
     780    ///
     781    ///\pre Either \ref run() or \ref start() must be called before
     782    ///using this function.
    711783    Arc predArc(Node v) const { return (*_pred)[v];}
    712784
    713     ///Returns the 'previous node' of the shortest path tree.
    714 
    715     ///For a node \c v it returns the 'previous node'
    716     ///of the shortest path tree,
    717     ///i.e. it returns the last but one node from a shortest path from the
    718     ///root(a) to \c /v.
    719     ///It is INVALID if \c v is unreachable from the root(s) or
    720     ///if \c v itself a root.
     785    ///Returns the 'previous node' of the shortest path tree for a node.
     786
     787    ///This function returns the 'previous node' of the shortest path
     788    ///tree for the node \c v, i.e. it returns the last but one node
     789    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     790    ///if \c v is not reachable from the root(s) or if \c v is a root.
     791    ///
    721792    ///The shortest path tree used here is equal to the shortest path
    722793    ///tree used in \ref predArc().
     794    ///
    723795    ///\pre Either \ref run() or \ref start() must be called before
    724796    ///using this function.
     
    726798                                  G->source((*_pred)[v]); }
    727799
    728     ///Returns a reference to the NodeMap of distances.
    729 
    730     ///Returns a reference to the NodeMap of distances.
    731     ///\pre Either \ref run() or \ref init() must
    732     ///be called before using this function.
     800    ///\brief Returns a const reference to the node map that stores the
     801    /// distances of the nodes.
     802    ///
     803    ///Returns a const reference to the node map that stores the distances
     804    ///of the nodes calculated by the algorithm.
     805    ///
     806    ///\pre Either \ref run() or \ref init()
     807    ///must be called before using this function.
    733808    const DistMap &distMap() const { return *_dist;}
    734809
    735     ///Returns a reference to the shortest path tree map.
    736 
    737     ///Returns a reference to the NodeMap of the arcs of the
    738     ///shortest path tree.
     810    ///\brief Returns a const reference to the node map that stores the
     811    ///predecessor arcs.
     812    ///
     813    ///Returns a const reference to the node map that stores the predecessor
     814    ///arcs, which form the shortest path tree.
     815    ///
    739816    ///\pre Either \ref run() or \ref init()
    740817    ///must be called before using this function.
    741818    const PredMap &predMap() const { return *_pred;}
    742819
    743     ///Checks if a node is reachable from the root.
    744 
    745     ///Returns \c true if \c v is reachable from the root.
    746     ///\warning The source nodes are indicated as unreached.
     820    ///Checks if a node is reachable from the root(s).
     821
     822    ///Returns \c true if \c v is reachable from the root(s).
    747823    ///\pre Either \ref run() or \ref start()
    748824    ///must be called before using this function.
    749     ///
    750     bool reached(Node v) { return (*_reached)[v]; }
     825    bool reached(Node v) const { return (*_reached)[v]; }
    751826
    752827    ///@}
    753828  };
    754829
    755   ///Default traits class of Bfs function.
    756 
    757   ///Default traits class of Bfs function.
     830  ///Default traits class of bfs() function.
     831
     832  ///Default traits class of bfs() function.
    758833  ///\tparam GR Digraph type.
    759834  template<class GR>
    760835  struct BfsWizardDefaultTraits
    761836  {
    762     ///The digraph type the algorithm runs on.
     837    ///The type of the digraph the algorithm runs on.
    763838    typedef GR Digraph;
    764     ///\brief The type of the map that stores the last
     839
     840    ///\brief The type of the map that stores the predecessor
    765841    ///arcs of the shortest paths.
    766842    ///
    767     ///The type of the map that stores the last
     843    ///The type of the map that stores the predecessor
    768844    ///arcs of the shortest paths.
    769845    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    770     ///
    771     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
    772     ///Instantiates a PredMap.
     846    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     847    ///Instantiates a \ref PredMap.
    773848
    774849    ///This function instantiates a \ref PredMap.
    775     ///\param g is the digraph, to which we would like to define the PredMap.
     850    ///\param g is the digraph, to which we would like to define the
     851    ///\ref PredMap.
    776852    ///\todo The digraph alone may be insufficient to initialize
    777853#ifdef DOXYGEN
    778     static PredMap *createPredMap(const GR &g)
     854    static PredMap *createPredMap(const Digraph &g)
    779855#else
    780     static PredMap *createPredMap(const GR &)
     856    static PredMap *createPredMap(const Digraph &)
    781857#endif
    782858    {
     
    788864    ///The type of the map that indicates which nodes are processed.
    789865    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    790     ///\todo named parameter to set this type, function to read and write.
    791866    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    792     ///Instantiates a ProcessedMap.
     867    ///Instantiates a \ref ProcessedMap.
    793868
    794869    ///This function instantiates a \ref ProcessedMap.
    795870    ///\param g is the digraph, to which
    796     ///we would like to define the \ref ProcessedMap
     871    ///we would like to define the \ref ProcessedMap.
    797872#ifdef DOXYGEN
    798     static ProcessedMap *createProcessedMap(const GR &g)
     873    static ProcessedMap *createProcessedMap(const Digraph &g)
    799874#else
    800     static ProcessedMap *createProcessedMap(const GR &)
     875    static ProcessedMap *createProcessedMap(const Digraph &)
    801876#endif
    802877    {
    803878      return new ProcessedMap();
    804879    }
     880
    805881    ///The type of the map that indicates which nodes are reached.
    806882
    807883    ///The type of the map that indicates which nodes are reached.
     884    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     885    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     886    ///Instantiates a \ref ReachedMap.
     887
     888    ///This function instantiates a \ref ReachedMap.
     889    ///\param g is the digraph, to which
     890    ///we would like to define the \ref ReachedMap.
     891    static ReachedMap *createReachedMap(const Digraph &g)
     892    {
     893      return new ReachedMap(g);
     894    }
     895
     896    ///The type of the map that stores the distances of the nodes.
     897
     898    ///The type of the map that stores the distances of the nodes.
    808899    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    809     ///\todo named parameter to set this type, function to read and write.
    810     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    811     ///Instantiates a ReachedMap.
    812 
    813     ///This function instantiates a \ref ReachedMap.
    814     ///\param G is the digraph, to which
    815     ///we would like to define the \ref ReachedMap.
    816     static ReachedMap *createReachedMap(const GR &G)
    817     {
    818       return new ReachedMap(G);
    819     }
    820     ///The type of the map that stores the dists of the nodes.
    821 
    822     ///The type of the map that stores the dists of the nodes.
    823     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    824900    ///
    825901    typedef NullMap<typename Digraph::Node,int> DistMap;
    826     ///Instantiates a DistMap.
     902    ///Instantiates a \ref DistMap.
    827903
    828904    ///This function instantiates a \ref DistMap.
     
    830906    ///the \ref DistMap
    831907#ifdef DOXYGEN
    832     static DistMap *createDistMap(const GR &g)
     908    static DistMap *createDistMap(const Digraph &g)
    833909#else
    834     static DistMap *createDistMap(const GR &)
     910    static DistMap *createDistMap(const Digraph &)
    835911#endif
    836912    {
     
    839915  };
    840916
    841   /// Default traits used by \ref BfsWizard
     917  /// Default traits class used by \ref BfsWizard
    842918
    843919  /// To make it easier to use Bfs algorithm
    844   ///we have created a wizard class.
     920  /// we have created a wizard class.
    845921  /// This \ref BfsWizard class needs default traits,
    846   ///as well as the \ref Bfs class.
     922  /// as well as the \ref Bfs class.
    847923  /// The \ref BfsWizardBase is a class to be the default traits of the
    848924  /// \ref BfsWizard class.
     
    853929    typedef BfsWizardDefaultTraits<GR> Base;
    854930  protected:
    855     /// Type of the nodes in the digraph.
     931    //The type of the nodes in the digraph.
    856932    typedef typename Base::Digraph::Node Node;
    857933
    858     /// Pointer to the underlying digraph.
     934    //Pointer to the digraph the algorithm runs on.
    859935    void *_g;
    860     ///Pointer to the map of reached nodes.
     936    //Pointer to the map of reached nodes.
    861937    void *_reached;
    862     ///Pointer to the map of processed nodes.
     938    //Pointer to the map of processed nodes.
    863939    void *_processed;
    864     ///Pointer to the map of predecessors arcs.
     940    //Pointer to the map of predecessors arcs.
    865941    void *_pred;
    866     ///Pointer to the map of distances.
     942    //Pointer to the map of distances.
    867943    void *_dist;
    868     ///Pointer to the source node.
     944    //Pointer to the source node.
    869945    Node _source;
    870946
     
    875951    /// all of the attributes to default values (0, INVALID).
    876952    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    877                            _dist(0), _source(INVALID) {}
     953                      _dist(0), _source(INVALID) {}
    878954
    879955    /// Constructor.
     
    882958    /// listed in the parameters list.
    883959    /// Others are initiated to 0.
    884     /// \param g is the initial value of  \ref _g
    885     /// \param s is the initial value of  \ref _source
     960    /// \param g The digraph the algorithm runs on.
     961    /// \param s The source node.
    886962    BfsWizardBase(const GR &g, Node s=INVALID) :
    887963      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
     
    890966  };
    891967
    892   /// A class to make the usage of Bfs algorithm easier
    893 
    894   /// This class is created to make it easier to use Bfs algorithm.
    895   /// It uses the functions and features of the plain \ref Bfs,
    896   /// but it is much simpler to use it.
     968  /// Auxiliary class for the function type interface of BFS algorithm.
     969
     970  /// This auxiliary class is created to implement the function type
     971  /// interface of \ref Bfs algorithm. It uses the functions and features
     972  /// of the plain \ref Bfs, but it is much simpler to use it.
     973  /// It should only be used through the \ref bfs() function, which makes
     974  /// it easier to use the algorithm.
    897975  ///
    898976  /// Simplicity means that the way to change the types defined
     
    903981  /// the original class by using the ::
    904982  /// operator. In the case of \ref BfsWizard only
    905   /// a function have to be called and it will
     983  /// a function have to be called, and it will
    906984  /// return the needed class.
    907985  ///
    908   /// It does not have own \ref run method. When its \ref run method is called
    909   /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
    910   /// method of it.
     986  /// It does not have own \ref run() method. When its \ref run() method
     987  /// is called, it initiates a plain \ref Bfs object, and calls the
     988  /// \ref Bfs::run() method of it.
    911989  template<class TR>
    912990  class BfsWizard : public TR
     
    914992    typedef TR Base;
    915993
    916     ///The type of the underlying digraph.
     994    ///The type of the digraph the algorithm runs on.
    917995    typedef typename TR::Digraph Digraph;
    918     //\e
     996
    919997    typedef typename Digraph::Node Node;
    920     //\e
    921998    typedef typename Digraph::NodeIt NodeIt;
    922     //\e
    923999    typedef typename Digraph::Arc Arc;
    924     //\e
    9251000    typedef typename Digraph::OutArcIt OutArcIt;
    9261001
    927     ///\brief The type of the map that stores
    928     ///the reached nodes
    929     typedef typename TR::ReachedMap ReachedMap;
    930     ///\brief The type of the map that stores
    931     ///the processed nodes
    932     typedef typename TR::ProcessedMap ProcessedMap;
    933     ///\brief The type of the map that stores the last
     1002    ///\brief The type of the map that stores the predecessor
    9341003    ///arcs of the shortest paths.
    9351004    typedef typename TR::PredMap PredMap;
    936     ///The type of the map that stores the dists of the nodes.
     1005    ///\brief The type of the map that stores the distances of the nodes.
    9371006    typedef typename TR::DistMap DistMap;
     1007    ///\brief The type of the map that indicates which nodes are reached.
     1008    typedef typename TR::ReachedMap ReachedMap;
     1009    ///\brief The type of the map that indicates which nodes are processed.
     1010    typedef typename TR::ProcessedMap ProcessedMap;
    9381011
    9391012  public:
     1013
    9401014    /// Constructor.
    9411015    BfsWizard() : TR() {}
     
    9531027    ~BfsWizard() {}
    9541028
    955     ///Runs Bfs algorithm from a given node.
    956 
    957     ///Runs Bfs algorithm from a given node.
    958     ///The node can be given by the \ref source function.
     1029    ///Runs BFS algorithm from a source node.
     1030
     1031    ///Runs BFS algorithm from a source node.
     1032    ///The node can be given with the \ref source() function.
    9591033    void run()
    9601034    {
     
    9721046    }
    9731047
    974     ///Runs Bfs algorithm from the given node.
    975 
    976     ///Runs Bfs algorithm from the given node.
     1048    ///Runs BFS algorithm from the given node.
     1049
     1050    ///Runs BFS algorithm from the given node.
    9771051    ///\param s is the given source.
    9781052    void run(Node s)
     
    9801054      Base::_source=s;
    9811055      run();
     1056    }
     1057
     1058    /// Sets the source node, from which the Bfs algorithm runs.
     1059
     1060    /// Sets the source node, from which the Bfs algorithm runs.
     1061    /// \param s is the source node.
     1062    BfsWizard<TR> &source(Node s)
     1063    {
     1064      Base::_source=s;
     1065      return *this;
    9821066    }
    9831067
     
    9881072      DefPredMapBase(const TR &b) : TR(b) {}
    9891073    };
    990 
    9911074    ///\brief \ref named-templ-param "Named parameter"
    992     ///function for setting PredMap
     1075    ///for setting \ref PredMap object.
    9931076    ///
    9941077    /// \ref named-templ-param "Named parameter"
    995     ///function for setting PredMap
    996     ///
     1078    ///for setting \ref PredMap object.
    9971079    template<class T>
    9981080    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     
    10011083      return BfsWizard<DefPredMapBase<T> >(*this);
    10021084    }
    1003 
    10041085
    10051086    template<class T>
     
    10091090      DefReachedMapBase(const TR &b) : TR(b) {}
    10101091    };
    1011 
    10121092    ///\brief \ref named-templ-param "Named parameter"
    1013     ///function for setting ReachedMap
     1093    ///for setting \ref ReachedMap object.
    10141094    ///
    10151095    /// \ref named-templ-param "Named parameter"
    1016     ///function for setting ReachedMap
    1017     ///
     1096    ///for setting \ref ReachedMap object.
    10181097    template<class T>
    10191098    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     
    10221101      return BfsWizard<DefReachedMapBase<T> >(*this);
    10231102    }
    1024 
    10251103
    10261104    template<class T>
     
    10301108      DefProcessedMapBase(const TR &b) : TR(b) {}
    10311109    };
    1032 
    10331110    ///\brief \ref named-templ-param "Named parameter"
    1034     ///function for setting ProcessedMap
     1111    ///for setting \ref ProcessedMap object.
    10351112    ///
    10361113    /// \ref named-templ-param "Named parameter"
    1037     ///function for setting ProcessedMap
    1038     ///
     1114    ///for setting \ref ProcessedMap object.
    10391115    template<class T>
    10401116    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     
    10431119      return BfsWizard<DefProcessedMapBase<T> >(*this);
    10441120    }
    1045 
    10461121
    10471122    template<class T>
     
    10511126      DefDistMapBase(const TR &b) : TR(b) {}
    10521127    };
    1053 
    10541128    ///\brief \ref named-templ-param "Named parameter"
    1055     ///function for setting DistMap type
     1129    ///for setting \ref DistMap object.
    10561130    ///
    10571131    /// \ref named-templ-param "Named parameter"
    1058     ///function for setting DistMap type
    1059     ///
     1132    ///for setting \ref DistMap object.
    10601133    template<class T>
    10611134    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
     
    10631136      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    10641137      return BfsWizard<DefDistMapBase<T> >(*this);
    1065     }
    1066 
    1067     /// Sets the source node, from which the Bfs algorithm runs.
    1068 
    1069     /// Sets the source node, from which the Bfs algorithm runs.
    1070     /// \param s is the source node.
    1071     BfsWizard<TR> &source(Node s)
    1072     {
    1073       Base::_source=s;
    1074       return *this;
    10751138    }
    10761139
     
    11021165
    11031166#ifdef DOXYGEN
    1104   /// \brief Visitor class for bfs.
     1167  /// \brief Visitor class for BFS.
    11051168  ///
    11061169  /// This class defines the interface of the BfsVisit events, and
    1107   /// it could be the base of a real Visitor class.
     1170  /// it could be the base of a real visitor class.
    11081171  template <typename _Digraph>
    11091172  struct BfsVisitor {
     
    11111174    typedef typename Digraph::Arc Arc;
    11121175    typedef typename Digraph::Node Node;
    1113     /// \brief Called when the arc reach a node.
    1114     ///
    1115     /// It is called when the bfs find an arc which target is not
    1116     /// reached yet.
     1176    /// \brief Called for the source node(s) of the BFS.
     1177    ///
     1178    /// This function is called for the source node(s) of the BFS.
     1179    void start(const Node& node) {}
     1180    /// \brief Called when a node is reached first time.
     1181    ///
     1182    /// This function is called when a node is reached first time.
     1183    void reach(const Node& node) {}
     1184    /// \brief Called when a node is processed.
     1185    ///
     1186    /// This function is called when a node is processed.
     1187    void process(const Node& node) {}
     1188    /// \brief Called when an arc reaches a new node.
     1189    ///
     1190    /// This function is called when the BFS finds an arc whose target node
     1191    /// is not reached yet.
    11171192    void discover(const Arc& arc) {}
    1118     /// \brief Called when the node reached first time.
    1119     ///
    1120     /// It is Called when the node reached first time.
    1121     void reach(const Node& node) {}
    1122     /// \brief Called when the arc examined but target of the arc
     1193    /// \brief Called when an arc is examined but its target node is
    11231194    /// already discovered.
    11241195    ///
    1125     /// It called when the arc examined but the target of the arc
     1196    /// This function is called when an arc is examined but its target node is
    11261197    /// already discovered.
    11271198    void examine(const Arc& arc) {}
    1128     /// \brief Called for the source node of the bfs.
    1129     ///
    1130     /// It is called for the source node of the bfs.
    1131     void start(const Node& node) {}
    1132     /// \brief Called when the node processed.
    1133     ///
    1134     /// It is Called when the node processed.
    1135     void process(const Node& node) {}
    11361199  };
    11371200#else
     
    11411204    typedef typename Digraph::Arc Arc;
    11421205    typedef typename Digraph::Node Node;
     1206    void start(const Node&) {}
     1207    void reach(const Node&) {}
     1208    void process(const Node&) {}
    11431209    void discover(const Arc&) {}
    1144     void reach(const Node&) {}
    11451210    void examine(const Arc&) {}
    1146     void start(const Node&) {}
    1147     void process(const Node&) {}
    11481211
    11491212    template <typename _Visitor>
     
    11521215        Arc arc;
    11531216        Node node;
     1217        visitor.start(node);
     1218        visitor.reach(node);
     1219        visitor.process(node);
    11541220        visitor.discover(arc);
    1155         visitor.reach(node);
    11561221        visitor.examine(arc);
    1157         visitor.start(node);
    1158         visitor.process(node);
    11591222      }
    11601223      _Visitor& visitor;
     
    11661229  ///
    11671230  /// Default traits class of BfsVisit class.
    1168   /// \tparam _Digraph Digraph type.
     1231  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11691232  template<class _Digraph>
    11701233  struct BfsVisitDefaultTraits {
    11711234
    1172     /// \brief The digraph type the algorithm runs on.
     1235    /// \brief The type of the digraph the algorithm runs on.
    11731236    typedef _Digraph Digraph;
    11741237
     
    11761239    ///
    11771240    /// The type of the map that indicates which nodes are reached.
    1178     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1179     /// \todo named parameter to set this type, function to read and write.
     1241    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    11801242    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    11811243
    1182     /// \brief Instantiates a ReachedMap.
     1244    /// \brief Instantiates a \ref ReachedMap.
    11831245    ///
    11841246    /// This function instantiates a \ref ReachedMap.
     
    11931255  /// \ingroup search
    11941256  ///
    1195   /// \brief %BFS Visit algorithm class.
     1257  /// \brief %BFS algorithm class with visitor interface.
    11961258  ///
    11971259  /// This class provides an efficient implementation of the %BFS algorithm
     
    12001262  /// The %BfsVisit class provides an alternative interface to the Bfs
    12011263  /// class. It works with callback mechanism, the BfsVisit object calls
    1202   /// on every bfs event the \c Visitor class member functions.
     1264  /// the member functions of the \c Visitor class on every BFS event.
    12031265  ///
    1204   /// \tparam _Digraph The digraph type the algorithm runs on.
     1266  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    12051267  /// The default value is
    1206   /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
    1207   /// is only passed to \ref BfsDefaultTraits.
    1208   /// \tparam _Visitor The Visitor object for the algorithm. The
    1209   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
    1210   /// does not observe the Bfs events. If you want to observe the bfs
    1211   /// events you should implement your own Visitor class.
     1268  /// \ref ListDigraph. The value of _Digraph is not used directly by
     1269  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
     1270  /// \tparam _Visitor The Visitor type that is used by the algorithm.
     1271  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1272  /// does not observe the BFS events. If you want to observe the BFS
     1273  /// events, you should implement your own visitor class.
    12121274  /// \tparam _Traits Traits class to set various data types used by the
    12131275  /// algorithm. The default traits class is
    12141276  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    12151277  /// See \ref BfsVisitDefaultTraits for the documentation of
    1216   /// a Bfs visit traits class.
     1278  /// a BFS visit traits class.
    12171279#ifdef DOXYGEN
    12181280  template <typename _Digraph, typename _Visitor, typename _Traits>
     
    12281290    ///
    12291291    /// This error represents problems in the initialization
    1230     /// of the parameters of the algorithms.
     1292    /// of the parameters of the algorithm.
    12311293    class UninitializedParameter : public lemon::UninitializedParameter {
    12321294    public:
     
    12371299    };
    12381300
     1301    ///The traits class.
    12391302    typedef _Traits Traits;
    12401303
     1304    ///The type of the digraph the algorithm runs on.
    12411305    typedef typename Traits::Digraph Digraph;
    12421306
     1307    ///The visitor type used by the algorithm.
    12431308    typedef _Visitor Visitor;
    12441309
    1245     ///The type of the map indicating which nodes are reached.
     1310    ///The type of the map that indicates which nodes are reached.
    12461311    typedef typename Traits::ReachedMap ReachedMap;
    12471312
     
    12531318    typedef typename Digraph::OutArcIt OutArcIt;
    12541319
    1255     /// Pointer to the underlying digraph.
     1320    //Pointer to the underlying digraph.
    12561321    const Digraph *_digraph;
    1257     /// Pointer to the visitor object.
     1322    //Pointer to the visitor object.
    12581323    Visitor *_visitor;
    1259     ///Pointer to the map of reached status of the nodes.
     1324    //Pointer to the map of reached status of the nodes.
    12601325    ReachedMap *_reached;
    1261     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1326    //Indicates if _reached is locally allocated (true) or not.
    12621327    bool local_reached;
    12631328
     
    12651330    int _list_front, _list_back;
    12661331
    1267     /// \brief Creates the maps if necessary.
    1268     ///
    1269     /// Creates the maps if necessary.
     1332    ///Creates the maps if necessary.
     1333    ///\todo Better memory allocation (instead of new).
    12701334    void create_maps() {
    12711335      if(!_reached) {
     
    12941358    };
    12951359    /// \brief \ref named-templ-param "Named parameter" for setting
    1296     /// ReachedMap type
    1297     ///
    1298     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1360    /// ReachedMap type.
     1361    ///
     1362    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    12991363    template <class T>
    13001364    struct DefReachedMap : public BfsVisit< Digraph, Visitor,
     
    13101374    /// Constructor.
    13111375    ///
    1312     /// \param digraph the digraph the algorithm will run on.
    1313     /// \param visitor The visitor of the algorithm.
    1314     ///
     1376    /// \param digraph The digraph the algorithm runs on.
     1377    /// \param visitor The visitor object of the algorithm.
    13151378    BfsVisit(const Digraph& digraph, Visitor& visitor)
    13161379      : _digraph(&digraph), _visitor(&visitor),
     
    13181381
    13191382    /// \brief Destructor.
    1320     ///
    1321     /// Destructor.
    13221383    ~BfsVisit() {
    13231384      if(local_reached) delete _reached;
    13241385    }
    13251386
    1326     /// \brief Sets the map indicating if a node is reached.
    1327     ///
    1328     /// Sets the map indicating if a node is reached.
     1387    /// \brief Sets the map that indicates which nodes are reached.
     1388    ///
     1389    /// Sets the map that indicates which nodes are reached.
    13291390    /// If you don't use this function before calling \ref run(),
    1330     /// it will allocate one. The destuctor deallocates this
     1391    /// it will allocate one. The destructor deallocates this
    13311392    /// automatically allocated map, of course.
    13321393    /// \return <tt> (*this) </tt>
     
    13411402
    13421403  public:
     1404
    13431405    /// \name Execution control
    13441406    /// The simplest way to execute the algorithm is to use
    1345     /// one of the member functions called \c run(...).
     1407    /// one of the member functions called \ref lemon::BfsVisit::run()
     1408    /// "run()".
    13461409    /// \n
    1347     /// If you need more control on the execution,
    1348     /// first you must call \ref init(), then you can adda source node
    1349     /// with \ref addSource().
    1350     /// Finally \ref start() will perform the actual path
    1351     /// computation.
     1410    /// If you need more control on the execution, first you must call
     1411    /// \ref lemon::BfsVisit::init() "init()", then you can add several
     1412    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
     1413    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
     1414    /// actual path computation.
    13521415
    13531416    /// @{
     1417
    13541418    /// \brief Initializes the internal data structures.
    13551419    ///
    13561420    /// Initializes the internal data structures.
    1357     ///
    13581421    void init() {
    13591422      create_maps();
     
    13831446    /// \return The processed node.
    13841447    ///
    1385     /// \pre The queue must not be empty!
     1448    /// \pre The queue must not be empty.
    13861449    Node processNextNode() {
    13871450      Node n = _list[++_list_front];
     
    14041467    /// \brief Processes the next node.
    14051468    ///
    1406     /// Processes the next node. And checks that the given target node
     1469    /// Processes the next node and checks if the given target node
    14071470    /// is reached. If the target node is reachable from the processed
    1408     /// node then the reached parameter will be set true. The reached
    1409     /// parameter should be initially false.
     1471    /// node, then the \c reach parameter will be set to \c true.
    14101472    ///
    14111473    /// \param target The target node.
    1412     /// \retval reach Indicates that the target node is reached.
     1474    /// \retval reach Indicates if the target node is reached.
     1475    /// It should be initially \c false.
     1476    ///
    14131477    /// \return The processed node.
    14141478    ///
    1415     /// \warning The queue must not be empty!
     1479    /// \pre The queue must not be empty.
    14161480    Node processNextNode(Node target, bool& reach) {
    14171481      Node n = _list[++_list_front];
     
    14351499    /// \brief Processes the next node.
    14361500    ///
    1437     /// Processes the next node. And checks that at least one of
    1438     /// reached node has true value in the \c nm node map. If one node
    1439     /// with true value is reachable from the processed node then the
    1440     /// rnode parameter will be set to the first of such nodes.
    1441     ///
    1442     /// \param nm The node map of possible targets.
     1501    /// Processes the next node and checks if at least one of reached
     1502    /// nodes has \c true value in the \c nm node map. If one node
     1503    /// with \c true value is reachable from the processed node, then the
     1504    /// \c rnode parameter will be set to the first of such nodes.
     1505    ///
     1506    /// \param nm A \c bool (or convertible) node map that indicates the
     1507    /// possible targets.
    14431508    /// \retval rnode The reached target node.
     1509    /// It should be initially \c INVALID.
     1510    ///
    14441511    /// \return The processed node.
    14451512    ///
    1446     /// \warning The queue must not be empty!
     1513    /// \pre The queue must not be empty.
    14471514    template <typename NM>
    14481515    Node processNextNode(const NM& nm, Node& rnode) {
     
    14651532    }
    14661533
    1467     /// \brief Next node to be processed.
    1468     ///
    1469     /// Next node to be processed.
    1470     ///
    1471     /// \return The next node to be processed or INVALID if the stack is
    1472     /// empty.
    1473     Node nextNode() {
     1534    /// \brief The next node to be processed.
     1535    ///
     1536    /// Returns the next node to be processed or \c INVALID if the queue
     1537    /// is empty.
     1538    Node nextNode() const {
    14741539      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
    14751540    }
    14761541
    14771542    /// \brief Returns \c false if there are nodes
    1478     /// to be processed in the queue
     1543    /// to be processed.
    14791544    ///
    14801545    /// Returns \c false if there are nodes
    1481     /// to be processed in the queue
    1482     bool emptyQueue() { return _list_front == _list_back; }
     1546    /// to be processed in the queue.
     1547    bool emptyQueue() const { return _list_front == _list_back; }
    14831548
    14841549    /// \brief Returns the number of the nodes to be processed.
    14851550    ///
    14861551    /// Returns the number of the nodes to be processed in the queue.
    1487     int queueSize() { return _list_back - _list_front; }
     1552    int queueSize() const { return _list_back - _list_front; }
    14881553
    14891554    /// \brief Executes the algorithm.
     
    14911556    /// Executes the algorithm.
    14921557    ///
    1493     /// \pre init() must be called and at least one node should be added
     1558    /// This method runs the %BFS algorithm from the root node(s)
     1559    /// in order to compute the shortest path to each node.
     1560    ///
     1561    /// The algorithm computes
     1562    /// - the shortest path tree (forest),
     1563    /// - the distance of each node from the root(s).
     1564    ///
     1565    /// \pre init() must be called and at least one root node should be added
    14941566    /// with addSource() before using this function.
     1567    ///
     1568    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
     1569    /// \code
     1570    ///   while ( !b.emptyQueue() ) {
     1571    ///     b.processNextNode();
     1572    ///   }
     1573    /// \endcode
    14951574    void start() {
    14961575      while ( !emptyQueue() ) processNextNode();
    14971576    }
    14981577
    1499     /// \brief Executes the algorithm until \c dest is reached.
    1500     ///
    1501     /// Executes the algorithm until \c dest is reached.
    1502     ///
    1503     /// \pre init() must be called and at least one node should be added
    1504     /// with addSource() before using this function.
     1578    /// \brief Executes the algorithm until the given target node is reached.
     1579    ///
     1580    /// Executes the algorithm until the given target node is reached.
     1581    ///
     1582    /// This method runs the %BFS algorithm from the root node(s)
     1583    /// in order to compute the shortest path to \c dest.
     1584    ///
     1585    /// The algorithm computes
     1586    /// - the shortest path to \c dest,
     1587    /// - the distance of \c dest from the root(s).
     1588    ///
     1589    /// \pre init() must be called and at least one root node should be
     1590    /// added with addSource() before using this function.
     1591    ///
     1592    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
     1593    /// \code
     1594    ///   bool reach = false;
     1595    ///   while ( !b.emptyQueue() && !reach ) {
     1596    ///     b.processNextNode(t, reach);
     1597    ///   }
     1598    /// \endcode
    15051599    void start(Node dest) {
    15061600      bool reach = false;
     
    15121606    /// Executes the algorithm until a condition is met.
    15131607    ///
    1514     /// \pre init() must be called and at least one node should be added
    1515     /// with addSource() before using this function.
    1516     ///
    1517     ///\param nm must be a bool (or convertible) node map. The
    1518     ///algorithm will stop when it reaches a node \c v with
     1608    /// This method runs the %BFS algorithm from the root node(s) in
     1609    /// order to compute the shortest path to a node \c v with
     1610    /// <tt>nm[v]</tt> true, if such a node can be found.
     1611    ///
     1612    /// \param nm must be a bool (or convertible) node map. The
     1613    /// algorithm will stop when it reaches a node \c v with
    15191614    /// <tt>nm[v]</tt> true.
    15201615    ///
    1521     ///\return The reached node \c v with <tt>nm[v]</tt> true or
    1522     ///\c INVALID if no such node was found.
     1616    /// \return The reached node \c v with <tt>nm[v]</tt> true or
     1617    /// \c INVALID if no such node was found.
     1618    ///
     1619    /// \pre init() must be called and at least one root node should be
     1620    /// added with addSource() before using this function.
     1621    ///
     1622    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
     1623    /// \code
     1624    ///   Node rnode = INVALID;
     1625    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
     1626    ///     b.processNextNode(nm, rnode);
     1627    ///   }
     1628    ///   return rnode;
     1629    /// \endcode
    15231630    template <typename NM>
    15241631    Node start(const NM &nm) {
     
    15301637    }
    15311638
    1532     /// \brief Runs %BFSVisit algorithm from node \c s.
    1533     ///
    1534     /// This method runs the %BFS algorithm from a root node \c s.
    1535     /// \note b.run(s) is just a shortcut of the following code.
     1639    /// \brief Runs the algorithm from the given node.
     1640    ///
     1641    /// This method runs the %BFS algorithm from node \c s
     1642    /// in order to compute the shortest path to each node.
     1643    ///
     1644    /// The algorithm computes
     1645    /// - the shortest path tree,
     1646    /// - the distance of each node from the root.
     1647    ///
     1648    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    15361649    ///\code
    15371650    ///   b.init();
     
    15451658    }
    15461659
    1547     /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
     1660    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15481661    ///
    15491662    /// This method runs the %BFS algorithm in order to
    1550     /// compute the %BFS path to each node. The algorithm computes
    1551     /// - The %BFS tree.
    1552     /// - The distance of each node from the root in the %BFS tree.
    1553     ///
    1554     ///\note b.run() is just a shortcut of the following code.
     1663    /// compute the shortest path to each node.
     1664    ///
     1665    /// The algorithm computes
     1666    /// - the shortest path tree (forest),
     1667    /// - the distance of each node from the root(s).
     1668    ///
     1669    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    15551670    ///\code
    15561671    ///  b.init();
    1557     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    1558     ///    if (!b.reached(it)) {
    1559     ///      b.addSource(it);
     1672    ///  for (NodeIt n(gr); n != INVALID; ++n) {
     1673    ///    if (!b.reached(n)) {
     1674    ///      b.addSource(n);
    15601675    ///      b.start();
    15611676    ///    }
     
    15711686      }
    15721687    }
     1688
    15731689    ///@}
    15741690
     
    15761692    /// The result of the %BFS algorithm can be obtained using these
    15771693    /// functions.\n
    1578     /// Before the use of these functions,
    1579     /// either run() or start() must be called.
     1694    /// Either \ref lemon::BfsVisit::run() "run()" or
     1695    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1696    /// using them.
    15801697    ///@{
    15811698
    1582     /// \brief Checks if a node is reachable from the root.
     1699    /// \brief Checks if a node is reachable from the root(s).
    15831700    ///
    15841701    /// Returns \c true if \c v is reachable from the root(s).
    1585     /// \warning The source nodes are inditated as unreachable.
    15861702    /// \pre Either \ref run() or \ref start()
    15871703    /// must be called before using this function.
    1588     ///
    15891704    bool reached(Node v) { return (*_reached)[v]; }
     1705
    15901706    ///@}
     1707
    15911708  };
    15921709
     
    15941711
    15951712#endif
    1596 
  • 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 
  • lemon/dijkstra.h

    r210 r244  
    3434namespace lemon {
    3535
    36   /// \brief Default OperationTraits for the Dijkstra algorithm class.
     36  /// \brief Default operation traits for the Dijkstra algorithm class.
    3737  ///
    38   /// It defines all computational operations and constants which are
    39   /// used in the Dijkstra algorithm.
     38  /// This operation traits class defines all computational operations and
     39  /// constants which are used in the Dijkstra algorithm.
    4040  template <typename Value>
    4141  struct DijkstraDefaultOperationTraits {
     
    4848      return left + right;
    4949    }
    50     /// \brief Gives back true only if the first value less than the second.
     50    /// \brief Gives back true only if the first value is less than the second.
    5151    static bool less(const Value& left, const Value& right) {
    5252      return left < right;
     
    5454  };
    5555
    56   /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
     56  /// \brief Widest path operation traits for the Dijkstra algorithm class.
    5757  ///
    58   /// It defines all computational operations and constants which are
    59   /// used in the Dijkstra algorithm for widest path computation.
     58  /// This operation traits class defines all computational operations and
     59  /// constants which are used in the Dijkstra algorithm for widest path
     60  /// computation.
     61  ///
     62  /// \see DijkstraDefaultOperationTraits
    6063  template <typename Value>
    6164  struct DijkstraWidestPathOperationTraits {
     
    6871      return std::min(left, right);
    6972    }
    70     /// \brief Gives back true only if the first value less than the second.
     73    /// \brief Gives back true only if the first value is less than the second.
    7174    static bool less(const Value& left, const Value& right) {
    7275      return left < right;
     
    7780
    7881  ///Default traits class of Dijkstra class.
    79   ///\tparam GR Digraph type.
    80   ///\tparam LM Type of length map.
     82  ///\tparam GR The type of the digraph.
     83  ///\tparam LM The type of the length map.
    8184  template<class GR, class LM>
    8285  struct DijkstraDefaultTraits
    8386  {
    84     ///The digraph type the algorithm runs on.
     87    ///The type of the digraph the algorithm runs on.
    8588    typedef GR Digraph;
     89
    8690    ///The type of the map that stores the arc lengths.
    8791
     
    8993    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    9094    typedef LM LengthMap;
    91     //The type of the length of the arcs.
     95    ///The type of the length of the arcs.
    9296    typedef typename LM::Value Value;
     97
    9398    /// Operation traits for Dijkstra algorithm.
    9499
    95     /// It defines the used operation by the algorithm.
     100    /// This class defines the operations that are used in the algorithm.
    96101    /// \see DijkstraDefaultOperationTraits
    97102    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    98     /// The cross reference type used by heap.
    99 
    100 
    101     /// The cross reference type used by heap.
     103
     104    /// The cross reference type used by the heap.
     105
     106    /// The cross reference type used by the heap.
    102107    /// Usually it is \c Digraph::NodeMap<int>.
    103108    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    104     ///Instantiates a HeapCrossRef.
    105 
    106     ///This function instantiates a \c HeapCrossRef.
    107     /// \param G is the digraph, to which we would like to define the
    108     /// HeapCrossRef.
    109     static HeapCrossRef *createHeapCrossRef(const GR &G)
    110     {
    111       return new HeapCrossRef(G);
    112     }
    113 
    114     ///The heap type used by Dijkstra algorithm.
    115 
    116     ///The heap type used by Dijkstra algorithm.
     109    ///Instantiates a \ref HeapCrossRef.
     110
     111    ///This function instantiates a \ref HeapCrossRef.
     112    /// \param g is the digraph, to which we would like to define the
     113    /// \ref HeapCrossRef.
     114    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
     115    {
     116      return new HeapCrossRef(g);
     117    }
     118
     119    ///The heap type used by the Dijkstra algorithm.
     120
     121    ///The heap type used by the Dijkstra algorithm.
    117122    ///
    118123    ///\sa BinHeap
    119124    ///\sa Dijkstra
    120125    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    121 
    122     static Heap *createHeap(HeapCrossRef& R)
    123     {
    124       return new Heap(R);
    125     }
    126 
    127     ///\brief The type of the map that stores the last
     126    ///Instantiates a \ref Heap.
     127
     128    ///This function instantiates a \ref Heap.
     129    static Heap *createHeap(HeapCrossRef& r)
     130    {
     131      return new Heap(r);
     132    }
     133
     134    ///\brief The type of the map that stores the predecessor
    128135    ///arcs of the shortest paths.
    129136    ///
    130     ///The type of the map that stores the last
     137    ///The type of the map that stores the predecessor
    131138    ///arcs of the shortest paths.
    132139    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    133     ///
    134     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    135     ///Instantiates a PredMap.
    136 
    137     ///This function instantiates a \c PredMap.
    138     ///\param G is the digraph, to which we would like to define the PredMap.
     140    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     141    ///Instantiates a \ref PredMap.
     142
     143    ///This function instantiates a \ref PredMap.
     144    ///\param g is the digraph, to which we would like to define the
     145    ///\ref PredMap.
    139146    ///\todo The digraph alone may be insufficient for the initialization
    140     static PredMap *createPredMap(const GR &G)
    141     {
    142       return new PredMap(G);
    143     }
    144 
    145     ///The type of the map that stores whether a nodes is processed.
    146 
    147     ///The type of the map that stores whether a nodes is processed.
     147    static PredMap *createPredMap(const Digraph &g)
     148    {
     149      return new PredMap(g);
     150    }
     151
     152    ///The type of the map that indicates which nodes are processed.
     153
     154    ///The type of the map that indicates which nodes are processed.
    148155    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    149156    ///By default it is a NullMap.
    150157    ///\todo If it is set to a real map,
    151158    ///Dijkstra::processed() should read this.
    152     ///\todo named parameter to set this type, function to read and write.
    153159    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    154     ///Instantiates a ProcessedMap.
    155 
    156     ///This function instantiates a \c ProcessedMap.
     160    ///Instantiates a \ref ProcessedMap.
     161
     162    ///This function instantiates a \ref ProcessedMap.
    157163    ///\param g is the digraph, to which
    158     ///we would like to define the \c ProcessedMap
     164    ///we would like to define the \ref ProcessedMap
    159165#ifdef DOXYGEN
    160     static ProcessedMap *createProcessedMap(const GR &g)
     166    static ProcessedMap *createProcessedMap(const Digraph &g)
    161167#else
    162     static ProcessedMap *createProcessedMap(const GR &)
     168    static ProcessedMap *createProcessedMap(const Digraph &)
    163169#endif
    164170    {
    165171      return new ProcessedMap();
    166172    }
    167     ///The type of the map that stores the dists of the nodes.
    168 
    169     ///The type of the map that stores the dists of the nodes.
     173
     174    ///The type of the map that stores the distances of the nodes.
     175
     176    ///The type of the map that stores the distances of the nodes.
    170177    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    171     ///
    172178    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    173     ///Instantiates a DistMap.
     179    ///Instantiates a \ref DistMap.
    174180
    175181    ///This function instantiates a \ref DistMap.
    176     ///\param G is the digraph, to which we would like to define
     182    ///\param g is the digraph, to which we would like to define
    177183    ///the \ref DistMap
    178     static DistMap *createDistMap(const GR &G)
    179     {
    180       return new DistMap(G);
     184    static DistMap *createDistMap(const Digraph &g)
     185    {
     186      return new DistMap(g);
    181187    }
    182188  };
     
    185191
    186192  /// \ingroup shortest_path
    187   ///This class provides an efficient implementation of %Dijkstra algorithm.
     193  ///This class provides an efficient implementation of the %Dijkstra algorithm.
     194  ///
    188195  ///The arc lengths are passed to the algorithm using a
    189196  ///\ref concepts::ReadMap "ReadMap",
    190197  ///so it is easy to change it to any kind of length.
    191   ///
    192198  ///The type of the length is determined by the
    193199  ///\ref concepts::ReadMap::Value "Value" of the length map.
    194   ///
    195200  ///It is also possible to change the underlying priority heap.
    196201  ///
    197   ///\tparam GR The digraph type the algorithm runs on. The default value
    198   ///is \ref ListDigraph. The value of GR is not used directly by
    199   ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
    200   ///\tparam LM This read-only ArcMap determines the lengths of the
     202  ///There is also a \ref dijkstra() "function type interface" for the
     203  ///%Dijkstra algorithm, which is convenient in the simplier cases and
     204  ///it can be used easier.
     205  ///
     206  ///\tparam GR The type of the digraph the algorithm runs on.
     207  ///The default value is \ref ListDigraph.
     208  ///The value of GR is not used directly by \ref Dijkstra, it is only
     209  ///passed to \ref DijkstraDefaultTraits.
     210  ///\tparam LM A readable arc map that determines the lengths of the
    201211  ///arcs. It is read once for each arc, so the map may involve in
    202   ///relatively time consuming process to compute the arc length if
     212  ///relatively time consuming process to compute the arc lengths if
    203213  ///it is necessary. The default map type is \ref
    204   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
    205   ///of LM is not used directly by Dijkstra, it is only passed to \ref
    206   ///DijkstraDefaultTraits.
    207   ///\tparam TR Traits class to set
    208   ///various data types used by the algorithm.  The default traits
    209   ///class is \ref DijkstraDefaultTraits
    210   ///"DijkstraDefaultTraits<GR,LM>".  See \ref
    211   ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
    212   ///class.
    213 
     214  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     215  ///The value of LM is not used directly by \ref Dijkstra, it is only
     216  ///passed to \ref DijkstraDefaultTraits.
     217  ///\tparam TR Traits class to set various data types used by the algorithm.
     218  ///The default traits class is \ref DijkstraDefaultTraits
     219  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
     220  ///for the documentation of a Dijkstra traits class.
    214221#ifdef DOXYGEN
    215222  template <typename GR, typename LM, typename TR>
     
    221228  class Dijkstra {
    222229  public:
    223     /**
    224      * \brief \ref Exception for uninitialized parameters.
    225      *
    226      * This error represents problems in the initialization
    227      * of the parameters of the algorithms.
    228      */
     230    ///\ref Exception for uninitialized parameters.
     231
     232    ///This error represents problems in the initialization of the
     233    ///parameters of the algorithm.
    229234    class UninitializedParameter : public lemon::UninitializedParameter {
    230235    public:
     
    234239    };
    235240
    236     typedef TR Traits;
    237     ///The type of the underlying digraph.
     241    ///The type of the digraph the algorithm runs on.
    238242    typedef typename TR::Digraph Digraph;
    239     ///\e
    240     typedef typename Digraph::Node Node;
    241     ///\e
    242     typedef typename Digraph::NodeIt NodeIt;
    243     ///\e
    244     typedef typename Digraph::Arc Arc;
    245     ///\e
    246     typedef typename Digraph::OutArcIt OutArcIt;
    247243
    248244    ///The type of the length of the arcs.
     
    250246    ///The type of the map that stores the arc lengths.
    251247    typedef typename TR::LengthMap LengthMap;
    252     ///\brief The type of the map that stores the last
    253     ///arcs of the shortest paths.
     248    ///\brief The type of the map that stores the predecessor arcs of the
     249    ///shortest paths.
    254250    typedef typename TR::PredMap PredMap;
    255     ///The type of the map indicating if a node is processed.
     251    ///The type of the map that stores the distances of the nodes.
     252    typedef typename TR::DistMap DistMap;
     253    ///The type of the map that indicates which nodes are processed.
    256254    typedef typename TR::ProcessedMap ProcessedMap;
    257     ///The type of the map that stores the dists of the nodes.
    258     typedef typename TR::DistMap DistMap;
     255    ///The type of the paths.
     256    typedef PredMapPath<Digraph, PredMap> Path;
    259257    ///The cross reference type used for the current heap.
    260258    typedef typename TR::HeapCrossRef HeapCrossRef;
    261     ///The heap type used by the dijkstra algorithm.
     259    ///The heap type used by the algorithm.
    262260    typedef typename TR::Heap Heap;
    263     ///The operation traits.
     261    ///The operation traits class.
    264262    typedef typename TR::OperationTraits OperationTraits;
     263
     264    ///The traits class.
     265    typedef TR Traits;
     266
    265267  private:
    266     /// Pointer to the underlying digraph.
     268
     269    typedef typename Digraph::Node Node;
     270    typedef typename Digraph::NodeIt NodeIt;
     271    typedef typename Digraph::Arc Arc;
     272    typedef typename Digraph::OutArcIt OutArcIt;
     273
     274    //Pointer to the underlying digraph.
    267275    const Digraph *G;
    268     /// Pointer to the length map
     276    //Pointer to the length map.
    269277    const LengthMap *length;
    270     ///Pointer to the map of predecessors arcs.
     278    //Pointer to the map of predecessors arcs.
    271279    PredMap *_pred;
    272     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     280    //Indicates if _pred is locally allocated (true) or not.
    273281    bool local_pred;
    274     ///Pointer to the map of distances.
     282    //Pointer to the map of distances.
    275283    DistMap *_dist;
    276     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     284    //Indicates if _dist is locally allocated (true) or not.
    277285    bool local_dist;
    278     ///Pointer to the map of processed status of the nodes.
     286    //Pointer to the map of processed status of the nodes.
    279287    ProcessedMap *_processed;
    280     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     288    //Indicates if _processed is locally allocated (true) or not.
    281289    bool local_processed;
    282     ///Pointer to the heap cross references.
     290    //Pointer to the heap cross references.
    283291    HeapCrossRef *_heap_cross_ref;
    284     ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
     292    //Indicates if _heap_cross_ref is locally allocated (true) or not.
    285293    bool local_heap_cross_ref;
    286     ///Pointer to the heap.
     294    //Pointer to the heap.
    287295    Heap *_heap;
    288     ///Indicates if \ref _heap is locally allocated (\c true) or not.
     296    //Indicates if _heap is locally allocated (true) or not.
    289297    bool local_heap;
    290298
    291299    ///Creates the maps if necessary.
    292 
    293300    ///\todo Better memory allocation (instead of new).
    294301    void create_maps()
     
    316323    }
    317324
    318   public :
     325  public:
    319326
    320327    typedef Dijkstra Create;
     
    332339      }
    333340    };
    334     ///\ref named-templ-param "Named parameter" for setting PredMap type
    335 
    336     ///\ref named-templ-param "Named parameter" for setting PredMap type
    337     ///
     341    ///\brief \ref named-templ-param "Named parameter" for setting
     342    ///\ref PredMap type.
     343    ///
     344    ///\ref named-templ-param "Named parameter" for setting
     345    ///\ref PredMap type.
    338346    template <class T>
    339347    struct DefPredMap
     
    350358      }
    351359    };
    352     ///\ref named-templ-param "Named parameter" for setting DistMap type
    353 
    354     ///\ref named-templ-param "Named parameter" for setting DistMap type
    355     ///
     360    ///\brief \ref named-templ-param "Named parameter" for setting
     361    ///\ref DistMap type.
     362    ///
     363    ///\ref named-templ-param "Named parameter" for setting
     364    ///\ref DistMap type.
    356365    template <class T>
    357366    struct DefDistMap
     
    363372    struct DefProcessedMapTraits : public Traits {
    364373      typedef T ProcessedMap;
    365       static ProcessedMap *createProcessedMap(const Digraph &G)
     374      static ProcessedMap *createProcessedMap(const Digraph &)
    366375      {
    367376        throw UninitializedParameter();
    368377      }
    369378    };
    370     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    371 
    372     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    373     ///
     379    ///\brief \ref named-templ-param "Named parameter" for setting
     380    ///\ref ProcessedMap type.
     381    ///
     382    ///\ref named-templ-param "Named parameter" for setting
     383    ///\ref ProcessedMap type.
    374384    template <class T>
    375385    struct DefProcessedMap
     
    380390    struct DefDigraphProcessedMapTraits : public Traits {
    381391      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    382       static ProcessedMap *createProcessedMap(const Digraph &G)
     392      static ProcessedMap *createProcessedMap(const Digraph &g)
    383393      {
    384         return new ProcessedMap(G);
    385       }
    386     };
    387     ///\brief \ref named-templ-param "Named parameter"
    388     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    389     ///
    390     ///\ref named-templ-param "Named parameter"
    391     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    392     ///If you don't set it explicitely, it will be automatically allocated.
     394        return new ProcessedMap(g);
     395      }
     396    };
     397    ///\brief \ref named-templ-param "Named parameter" for setting
     398    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     399    ///
     400    ///\ref named-templ-param "Named parameter" for setting
     401    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     402    ///If you don't set it explicitly, it will be automatically allocated.
    393403    template <class T>
    394404    struct DefProcessedMapToBeDefaultMap
     
    414424    ///
    415425    ///\ref named-templ-param "Named parameter" for setting heap and cross
    416     ///reference type
    417     ///
     426    ///reference type.
    418427    template <class H, class CR = typename Digraph::template NodeMap<int> >
    419428    struct DefHeap
     
    454463
    455464    /// \brief \ref named-templ-param "Named parameter" for setting
    456     /// OperationTraits type
    457     ///
    458     /// \ref named-templ-param "Named parameter" for setting OperationTraits
    459     /// type
     465    ///\ref OperationTraits type
     466    ///
     467    ///\ref named-templ-param "Named parameter" for setting
     468    ///\ref OperationTraits type.
    460469    template <class T>
    461470    struct DefOperationTraits
     
    467476    ///@}
    468477
    469 
    470478  protected:
    471479
     
    476484    ///Constructor.
    477485
    478     ///\param _G the digraph the algorithm will run on.
    479     ///\param _length the length map used by the algorithm.
    480     Dijkstra(const Digraph& _G, const LengthMap& _length) :
    481       G(&_G), length(&_length),
     486    ///Constructor.
     487    ///\param _g The digraph the algorithm runs on.
     488    ///\param _length The length map used by the algorithm.
     489    Dijkstra(const Digraph& _g, const LengthMap& _length) :
     490      G(&_g), length(&_length),
    482491      _pred(NULL), local_pred(false),
    483492      _dist(NULL), local_dist(false),
     
    507516    }
    508517
    509     ///Sets the map storing the predecessor arcs.
    510 
    511     ///Sets the map storing the predecessor arcs.
     518    ///Sets the map that stores the predecessor arcs.
     519
     520    ///Sets the map that stores the predecessor arcs.
    512521    ///If you don't use this function before calling \ref run(),
    513     ///it will allocate one. The destuctor deallocates this
     522    ///it will allocate one. The destructor deallocates this
    514523    ///automatically allocated map, of course.
    515524    ///\return <tt> (*this) </tt>
     
    524533    }
    525534
    526     ///Sets the map storing the distances calculated by the algorithm.
    527 
    528     ///Sets the map storing the distances calculated by the algorithm.
     535    ///Sets the map that indicates which nodes are processed.
     536
     537    ///Sets the map that indicates which nodes are processed.
    529538    ///If you don't use this function before calling \ref run(),
    530     ///it will allocate one. The destuctor deallocates this
     539    ///it will allocate one. The destructor deallocates this
     540    ///automatically allocated map, of course.
     541    ///\return <tt> (*this) </tt>
     542    Dijkstra &processedMap(ProcessedMap &m)
     543    {
     544      if(local_processed) {
     545        delete _processed;
     546        local_processed=false;
     547      }
     548      _processed = &m;
     549      return *this;
     550    }
     551
     552    ///Sets the map that stores the distances of the nodes.
     553
     554    ///Sets the map that stores the distances of the nodes calculated by the
     555    ///algorithm.
     556    ///If you don't use this function before calling \ref run(),
     557    ///it will allocate one. The destructor deallocates this
    531558    ///automatically allocated map, of course.
    532559    ///\return <tt> (*this) </tt>
     
    545572    ///Sets the heap and the cross reference used by algorithm.
    546573    ///If you don't use this function before calling \ref run(),
    547     ///it will allocate one. The destuctor deallocates this
     574    ///it will allocate one. The destructor deallocates this
    548575    ///automatically allocated heap and cross reference, of course.
    549576    ///\return <tt> (*this) </tt>
     
    564591
    565592  private:
     593
    566594    void finalizeNodeData(Node v,Value dst)
    567595    {
     
    572600  public:
    573601
    574     typedef PredMapPath<Digraph, PredMap> Path;
    575 
    576602    ///\name Execution control
    577     ///The simplest way to execute the algorithm is to use
    578     ///one of the member functions called \c run(...).
     603    ///The simplest way to execute the algorithm is to use one of the
     604    ///member functions called \ref lemon::Dijkstra::run() "run()".
    579605    ///\n
    580     ///If you need more control on the execution,
    581     ///first you must call \ref init(), then you can add several source nodes
    582     ///with \ref addSource().
    583     ///Finally \ref start() will perform the actual path
    584     ///computation.
     606    ///If you need more control on the execution, first you must call
     607    ///\ref lemon::Dijkstra::init() "init()", then you can add several
     608    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
     609    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
     610    ///actual path computation.
    585611
    586612    ///@{
     
    604630
    605631    ///Adds a new source node to the priority heap.
    606     ///
    607632    ///The optional second parameter is the initial distance of the node.
    608633    ///
    609     ///It checks if the node has already been added to the heap and
     634    ///The function checks if the node has already been added to the heap and
    610635    ///it is pushed to the heap only if either it was not in the heap
    611636    ///or the shortest path found till then is shorter than \c dst.
     
    626651    ///\return The processed node.
    627652    ///
    628     ///\warning The priority heap must not be empty!
     653    ///\warning The priority heap must not be empty.
    629654    Node processNextNode()
    630655    {
     
    657682    }
    658683
    659     ///Next node to be processed.
    660 
    661     ///Next node to be processed.
    662     ///
    663     ///\return The next node to be processed or INVALID if the priority heap
    664     /// is empty.
    665     Node nextNode()
     684    ///The next node to be processed.
     685
     686    ///Returns the next node to be processed or \c INVALID if the
     687    ///priority heap is empty.
     688    Node nextNode() const
    666689    {
    667690      return !_heap->empty()?_heap->top():INVALID;
     
    669692
    670693    ///\brief Returns \c false if there are nodes
    671     ///to be processed in the priority heap
     694    ///to be processed.
    672695    ///
    673696    ///Returns \c false if there are nodes
    674     ///to be processed in the priority heap
    675     bool emptyQueue() { return _heap->empty(); }
     697    ///to be processed in the priority heap.
     698    bool emptyQueue() const { return _heap->empty(); }
     699
    676700    ///Returns the number of the nodes to be processed in the priority heap
    677701
    678     ///Returns the number of the nodes to be processed in the priority heap
    679     ///
    680     int queueSize() { return _heap->size(); }
     702    ///Returns the number of the nodes to be processed in the priority heap.
     703    ///
     704    int queueSize() const { return _heap->size(); }
    681705
    682706    ///Executes the algorithm.
     
    684708    ///Executes the algorithm.
    685709    ///
    686     ///\pre init() must be called and at least one node should be added
    687     ///with addSource() before using this function.
    688     ///
    689710    ///This method runs the %Dijkstra algorithm from the root node(s)
    690     ///in order to
    691     ///compute the
    692     ///shortest path to each node. The algorithm computes
    693     ///- The shortest path tree.
    694     ///- The distance of each node from the root(s).
    695     ///
     711    ///in order to compute the shortest path to each node.
     712    ///
     713    ///The algorithm computes
     714    ///- the shortest path tree (forest),
     715    ///- the distance of each node from the root(s).
     716    ///
     717    ///\pre init() must be called and at least one root node should be
     718    ///added with addSource() before using this function.
     719    ///
     720    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
     721    ///\code
     722    ///  while ( !d.emptyQueue() ) {
     723    ///    d.processNextNode();
     724    ///  }
     725    ///\endcode
    696726    void start()
    697727    {
    698       while ( !_heap->empty() ) processNextNode();
    699     }
    700 
    701     ///Executes the algorithm until \c dest is reached.
    702 
    703     ///Executes the algorithm until \c dest is reached.
    704     ///
    705     ///\pre init() must be called and at least one node should be added
    706     ///with addSource() before using this function.
     728      while ( !emptyQueue() ) processNextNode();
     729    }
     730
     731    ///Executes the algorithm until the given target node is reached.
     732
     733    ///Executes the algorithm until the given target node is reached.
    707734    ///
    708735    ///This method runs the %Dijkstra algorithm from the root node(s)
    709     ///in order to
    710     ///compute the
    711     ///shortest path to \c dest. The algorithm computes
    712     ///- The shortest path to \c  dest.
    713     ///- The distance of \c dest from the root(s).
    714     ///
     736    ///in order to compute the shortest path to \c dest.
     737    ///
     738    ///The algorithm computes
     739    ///- the shortest path to \c dest,
     740    ///- the distance of \c dest from the root(s).
     741    ///
     742    ///\pre init() must be called and at least one root node should be
     743    ///added with addSource() before using this function.
    715744    void start(Node dest)
    716745    {
     
    723752    ///Executes the algorithm until a condition is met.
    724753    ///
    725     ///\pre init() must be called and at least one node should be added
    726     ///with addSource() before using this function.
    727     ///
    728     ///\param nm must be a bool (or convertible) node map. The algorithm
     754    ///This method runs the %Dijkstra algorithm from the root node(s) in
     755    ///order to compute the shortest path to a node \c v with
     756    /// <tt>nm[v]</tt> true, if such a node can be found.
     757    ///
     758    ///\param nm A \c bool (or convertible) node map. The algorithm
    729759    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
    730760    ///
    731761    ///\return The reached node \c v with <tt>nm[v]</tt> true or
    732762    ///\c INVALID if no such node was found.
     763    ///
     764    ///\pre init() must be called and at least one root node should be
     765    ///added with addSource() before using this function.
    733766    template<class NodeBoolMap>
    734767    Node start(const NodeBoolMap &nm)
     
    740773    }
    741774
    742     ///Runs %Dijkstra algorithm from node \c s.
    743 
    744     ///This method runs the %Dijkstra algorithm from a root node \c s
    745     ///in order to
    746     ///compute the
    747     ///shortest path to each node. The algorithm computes
    748     ///- The shortest path tree.
    749     ///- The distance of each node from the root.
    750     ///
    751     ///\note d.run(s) is just a shortcut of the following code.
     775    ///Runs the algorithm from the given node.
     776
     777    ///This method runs the %Dijkstra algorithm from node \c s
     778    ///in order to compute the shortest path to each node.
     779    ///
     780    ///The algorithm computes
     781    ///- the shortest path tree,
     782    ///- the distance of each node from the root.
     783    ///
     784    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
    752785    ///\code
    753786    ///  d.init();
     
    763796    ///Finds the shortest path between \c s and \c t.
    764797
    765     ///Finds the shortest path between \c s and \c t.
    766     ///
    767     ///\return The length of the shortest s---t path if there exists one,
    768     ///0 otherwise.
    769     ///\note Apart from the return value, d.run(s) is
    770     ///just a shortcut of the following code.
     798    ///This method runs the %Dijkstra algorithm from node \c s
     799    ///in order to compute the shortest path to \c t.
     800    ///
     801    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
     802    ///if \c t is reachable form \c s, \c 0 otherwise.
     803    ///
     804    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
     805    ///shortcut of the following code.
    771806    ///\code
    772807    ///  d.init();
     
    786821    ///The result of the %Dijkstra algorithm can be obtained using these
    787822    ///functions.\n
    788     ///Before the use of these functions,
    789     ///either run() or start() must be called.
     823    ///Either \ref lemon::Dijkstra::run() "run()" or
     824    ///\ref lemon::Dijkstra::start() "start()" must be called before
     825    ///using them.
    790826
    791827    ///@{
    792828
    793     ///Gives back the shortest path.
    794 
    795     ///Gives back the shortest path.
    796     ///\pre The \c t should be reachable from the source.
    797     Path path(Node t)
    798     {
    799       return Path(*G, *_pred, t);
    800     }
    801 
    802     ///The distance of a node from the root.
    803 
    804     ///Returns the distance of a node from the root.
    805     ///\pre \ref run() must be called before using this function.
    806     ///\warning If node \c v in unreachable from the root the return value
    807     ///of this funcion is undefined.
     829    ///The shortest path to a node.
     830
     831    ///Returns the shortest path to a node.
     832    ///
     833    ///\warning \c t should be reachable from the root(s).
     834    ///
     835    ///\pre Either \ref run() or \ref start() must be called before
     836    ///using this function.
     837    Path path(Node t) const { return Path(*G, *_pred, t); }
     838
     839    ///The distance of a node from the root(s).
     840
     841    ///Returns the distance of a node from the root(s).
     842    ///
     843    ///\warning If node \c v is not reachable from the root(s), then
     844    ///the return value of this function is undefined.
     845    ///
     846    ///\pre Either \ref run() or \ref start() must be called before
     847    ///using this function.
    808848    Value dist(Node v) const { return (*_dist)[v]; }
    809849
    810     ///The current distance of a node from the root.
    811 
    812     ///Returns the current distance of a node from the root.
    813     ///It may be decreased in the following processes.
    814     ///\pre \c node should be reached but not processed
    815     Value currentDist(Node v) const { return (*_heap)[v]; }
    816 
    817     ///Returns the 'previous arc' of the shortest path tree.
    818 
    819     ///For a node \c v it returns the 'previous arc' of the shortest path tree,
    820     ///i.e. it returns the last arc of a shortest path from the root to \c
    821     ///v. It is \ref INVALID
    822     ///if \c v is unreachable from the root or if \c v=s. The
    823     ///shortest path tree used here is equal to the shortest path tree used in
    824     ///\ref predNode().  \pre \ref run() must be called before using
    825     ///this function.
     850    ///Returns the 'previous arc' of the shortest path tree for a node.
     851
     852    ///This function returns the 'previous arc' of the shortest path
     853    ///tree for the node \c v, i.e. it returns the last arc of a
     854    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     855    ///is not reachable from the root(s) or if \c v is a root.
     856    ///
     857    ///The shortest path tree used here is equal to the shortest path
     858    ///tree used in \ref predNode().
     859    ///
     860    ///\pre Either \ref run() or \ref start() must be called before
     861    ///using this function.
    826862    Arc predArc(Node v) const { return (*_pred)[v]; }
    827863
    828     ///Returns the 'previous node' of the shortest path tree.
    829 
    830     ///For a node \c v it returns the 'previous node' of the shortest path tree,
    831     ///i.e. it returns the last but one node from a shortest path from the
    832     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    833     ///\c v=s. The shortest path tree used here is equal to the shortest path
    834     ///tree used in \ref predArc().  \pre \ref run() must be called before
     864    ///Returns the 'previous node' of the shortest path tree for a node.
     865
     866    ///This function returns the 'previous node' of the shortest path
     867    ///tree for the node \c v, i.e. it returns the last but one node
     868    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     869    ///if \c v is not reachable from the root(s) or if \c v is a root.
     870    ///
     871    ///The shortest path tree used here is equal to the shortest path
     872    ///tree used in \ref predArc().
     873    ///
     874    ///\pre Either \ref run() or \ref start() must be called before
    835875    ///using this function.
    836876    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    837877                                  G->source((*_pred)[v]); }
    838878
    839     ///Returns a reference to the NodeMap of distances.
    840 
    841     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
    842     ///be called before using this function.
     879    ///\brief Returns a const reference to the node map that stores the
     880    ///distances of the nodes.
     881    ///
     882    ///Returns a const reference to the node map that stores the distances
     883    ///of the nodes calculated by the algorithm.
     884    ///
     885    ///\pre Either \ref run() or \ref init()
     886    ///must be called before using this function.
    843887    const DistMap &distMap() const { return *_dist;}
    844888
    845     ///Returns a reference to the shortest path tree map.
    846 
    847     ///Returns a reference to the NodeMap of the arcs of the
    848     ///shortest path tree.
    849     ///\pre \ref run() must be called before using this function.
     889    ///\brief Returns a const reference to the node map that stores the
     890    ///predecessor arcs.
     891    ///
     892    ///Returns a const reference to the node map that stores the predecessor
     893    ///arcs, which form the shortest path tree.
     894    ///
     895    ///\pre Either \ref run() or \ref init()
     896    ///must be called before using this function.
    850897    const PredMap &predMap() const { return *_pred;}
    851898
    852     ///Checks if a node is reachable from the root.
    853 
    854     ///Returns \c true if \c v is reachable from the root.
    855     ///\warning The source nodes are inditated as unreached.
    856     ///\pre \ref run() must be called before using this function.
    857     ///
    858     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
     899    ///Checks if a node is reachable from the root(s).
     900
     901    ///Returns \c true if \c v is reachable from the root(s).
     902    ///\pre Either \ref run() or \ref start()
     903    ///must be called before using this function.
     904    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     905                                        Heap::PRE_HEAP; }
    859906
    860907    ///Checks if a node is processed.
     
    862909    ///Returns \c true if \c v is processed, i.e. the shortest
    863910    ///path to \c v has already found.
    864     ///\pre \ref run() must be called before using this function.
    865     ///
    866     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
     911    ///\pre Either \ref run() or \ref start()
     912    ///must be called before using this function.
     913    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     914                                          Heap::POST_HEAP; }
     915
     916    ///The current distance of a node from the root(s).
     917
     918    ///Returns the current distance of a node from the root(s).
     919    ///It may be decreased in the following processes.
     920    ///\pre \c v should be reached but not processed.
     921    Value currentDist(Node v) const { return (*_heap)[v]; }
    867922
    868923    ///@}
     
    870925
    871926
    872 
    873 
    874 
    875   ///Default traits class of Dijkstra function.
    876 
    877   ///Default traits class of Dijkstra function.
    878   ///\tparam GR Digraph type.
    879   ///\tparam LM Type of length map.
     927  ///Default traits class of dijkstra() function.
     928
     929  ///Default traits class of dijkstra() function.
     930  ///\tparam GR The type of the digraph.
     931  ///\tparam LM The type of the length map.
    880932  template<class GR, class LM>
    881933  struct DijkstraWizardDefaultTraits
    882934  {
    883     ///The digraph type the algorithm runs on.
     935    ///The type of the digraph the algorithm runs on.
    884936    typedef GR Digraph;
    885937    ///The type of the map that stores the arc lengths.
     
    888940    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    889941    typedef LM LengthMap;
    890     //The type of the length of the arcs.
     942    ///The type of the length of the arcs.
    891943    typedef typename LM::Value Value;
     944
    892945    /// Operation traits for Dijkstra algorithm.
    893946
    894     /// It defines the used operation by the algorithm.
     947    /// This class defines the operations that are used in the algorithm.
    895948    /// \see DijkstraDefaultOperationTraits
    896949    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    897     ///The heap type used by Dijkstra algorithm.
    898 
    899     /// The cross reference type used by heap.
    900 
    901     /// The cross reference type used by heap.
     950
     951    /// The cross reference type used by the heap.
     952
     953    /// The cross reference type used by the heap.
    902954    /// Usually it is \c Digraph::NodeMap<int>.
    903955    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    904     ///Instantiates a HeapCrossRef.
     956    ///Instantiates a \ref HeapCrossRef.
    905957
    906958    ///This function instantiates a \ref HeapCrossRef.
    907     /// \param G is the digraph, to which we would like to define the
     959    /// \param g is the digraph, to which we would like to define the
    908960    /// HeapCrossRef.
    909961    /// \todo The digraph alone may be insufficient for the initialization
    910     static HeapCrossRef *createHeapCrossRef(const GR &G)
    911     {
    912       return new HeapCrossRef(G);
    913     }
    914 
    915     ///The heap type used by Dijkstra algorithm.
    916 
    917     ///The heap type used by Dijkstra algorithm.
     962    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
     963    {
     964      return new HeapCrossRef(g);
     965    }
     966
     967    ///The heap type used by the Dijkstra algorithm.
     968
     969    ///The heap type used by the Dijkstra algorithm.
    918970    ///
    919971    ///\sa BinHeap
    920972    ///\sa Dijkstra
    921     typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
     973    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
    922974                    std::less<Value> > Heap;
    923975
    924     static Heap *createHeap(HeapCrossRef& R)
    925     {
    926       return new Heap(R);
    927     }
    928 
    929     ///\brief The type of the map that stores the last
     976    ///Instantiates a \ref Heap.
     977
     978    ///This function instantiates a \ref Heap.
     979    /// \param r is the HeapCrossRef which is used.
     980    static Heap *createHeap(HeapCrossRef& r)
     981    {
     982      return new Heap(r);
     983    }
     984
     985    ///\brief The type of the map that stores the predecessor
    930986    ///arcs of the shortest paths.
    931987    ///
    932     ///The type of the map that stores the last
     988    ///The type of the map that stores the predecessor
    933989    ///arcs of the shortest paths.
    934990    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    935     ///
    936     typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
    937     ///Instantiates a PredMap.
     991    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
     992    ///Instantiates a \ref PredMap.
    938993
    939994    ///This function instantiates a \ref PredMap.
    940     ///\param g is the digraph, to which we would like to define the PredMap.
    941     ///\todo The digraph alone may be insufficient for the initialization
     995    ///\param g is the digraph, to which we would like to define the
     996    ///\ref PredMap.
     997    ///\todo The digraph alone may be insufficient to initialize
    942998#ifdef DOXYGEN
    943     static PredMap *createPredMap(const GR &g)
     999    static PredMap *createPredMap(const Digraph &g)
    9441000#else
    945     static PredMap *createPredMap(const GR &)
     1001    static PredMap *createPredMap(const Digraph &)
    9461002#endif
    9471003    {
    9481004      return new PredMap();
    9491005    }
    950     ///The type of the map that stores whether a nodes is processed.
    951 
    952     ///The type of the map that stores whether a nodes is processed.
     1006
     1007    ///The type of the map that indicates which nodes are processed.
     1008
     1009    ///The type of the map that indicates which nodes are processed.
    9531010    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    9541011    ///By default it is a NullMap.
     
    9571014    ///\todo named parameter to set this type, function to read and write.
    9581015    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    959     ///Instantiates a ProcessedMap.
     1016    ///Instantiates a \ref ProcessedMap.
    9601017
    9611018    ///This function instantiates a \ref ProcessedMap.
    9621019    ///\param g is the digraph, to which
    963     ///we would like to define the \ref ProcessedMap
     1020    ///we would like to define the \ref ProcessedMap.
    9641021#ifdef DOXYGEN
    965     static ProcessedMap *createProcessedMap(const GR &g)
     1022    static ProcessedMap *createProcessedMap(const Digraph &g)
    9661023#else
    967     static ProcessedMap *createProcessedMap(const GR &)
     1024    static ProcessedMap *createProcessedMap(const Digraph &)
    9681025#endif
    9691026    {
    9701027      return new ProcessedMap();
    9711028    }
    972     ///The type of the map that stores the dists of the nodes.
    973 
    974     ///The type of the map that stores the dists of the nodes.
     1029
     1030    ///The type of the map that stores the distances of the nodes.
     1031
     1032    ///The type of the map that stores the distances of the nodes.
    9751033    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    976     ///
    977     typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
    978     ///Instantiates a DistMap.
     1034    typedef NullMap<typename Digraph::Node,Value> DistMap;
     1035    ///Instantiates a \ref DistMap.
    9791036
    9801037    ///This function instantiates a \ref DistMap.
     
    9821039    ///the \ref DistMap
    9831040#ifdef DOXYGEN
    984     static DistMap *createDistMap(const GR &g)
     1041    static DistMap *createDistMap(const Digraph &g)
    9851042#else
    986     static DistMap *createDistMap(const GR &)
     1043    static DistMap *createDistMap(const Digraph &)
    9871044#endif
    9881045    {
     
    9911048  };
    9921049
    993   /// Default traits used by \ref DijkstraWizard
     1050  /// Default traits class used by \ref DijkstraWizard
    9941051
    9951052  /// To make it easier to use Dijkstra algorithm
    996   ///we have created a wizard class.
     1053  /// we have created a wizard class.
    9971054  /// This \ref DijkstraWizard class needs default traits,
    998   ///as well as the \ref Dijkstra class.
     1055  /// as well as the \ref Dijkstra class.
    9991056  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10001057  /// \ref DijkstraWizard class.
     
    10031060  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
    10041061  {
    1005 
    10061062    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
    10071063  protected:
    1008     /// Type of the nodes in the digraph.
     1064    //The type of the nodes in the digraph.
    10091065    typedef typename Base::Digraph::Node Node;
    10101066
    1011     /// Pointer to the underlying digraph.
     1067    //Pointer to the digraph the algorithm runs on.
    10121068    void *_g;
    1013     /// Pointer to the length map
     1069    //Pointer to the length map
    10141070    void *_length;
    1015     ///Pointer to the map of predecessors arcs.
     1071    //Pointer to the map of predecessors arcs.
    10161072    void *_pred;
    1017     ///Pointer to the map of distances.
     1073    //Pointer to the map of distances.
    10181074    void *_dist;
    1019     ///Pointer to the source node.
     1075    //Pointer to the source node.
    10201076    Node _source;
    10211077
    1022     public:
     1078  public:
    10231079    /// Constructor.
    10241080
     
    10331089    /// listed in the parameters list.
    10341090    /// Others are initiated to 0.
    1035     /// \param g is the initial value of  \ref _g
    1036     /// \param l is the initial value of  \ref _length
    1037     /// \param s is the initial value of  \ref _source
     1091    /// \param g The digraph the algorithm runs on.
     1092    /// \param l The length map.
     1093    /// \param s The source node.
    10381094    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
    10391095      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
     
    10431099  };
    10441100
    1045   /// A class to make the usage of Dijkstra algorithm easier
    1046 
    1047   /// This class is created to make it easier to use Dijkstra algorithm.
    1048   /// It uses the functions and features of the plain \ref Dijkstra,
    1049   /// but it is much simpler to use it.
     1101  /// Auxiliary class for the function type interface of Dijkstra algorithm.
     1102
     1103  /// This auxiliary class is created to implement the function type
     1104  /// interface of \ref Dijkstra algorithm. It uses the functions and features
     1105  /// of the plain \ref Dijkstra, but it is much simpler to use it.
     1106  /// It should only be used through the \ref dijkstra() function, which makes
     1107  /// it easier to use the algorithm.
    10501108  ///
    10511109  /// Simplicity means that the way to change the types defined
     
    10561114  /// the original class by using the ::
    10571115  /// operator. In the case of \ref DijkstraWizard only
    1058   /// a function have to be called and it will
     1116  /// a function have to be called, and it will
    10591117  /// return the needed class.
    10601118  ///
    1061   /// It does not have own \ref run method. When its \ref run method is called
    1062   /// it initiates a plain \ref Dijkstra class, and calls the \ref
    1063   /// Dijkstra::run method of it.
     1119  /// It does not have own \ref run() method. When its \ref run() method
     1120  /// is called, it initiates a plain \ref Dijkstra object, and calls the
     1121  /// \ref Dijkstra::run() method of it.
    10641122  template<class TR>
    10651123  class DijkstraWizard : public TR
     
    10671125    typedef TR Base;
    10681126
    1069     ///The type of the underlying digraph.
     1127    ///The type of the digraph the algorithm runs on.
    10701128    typedef typename TR::Digraph Digraph;
    1071     //\e
     1129
    10721130    typedef typename Digraph::Node Node;
    1073     //\e
    10741131    typedef typename Digraph::NodeIt NodeIt;
    1075     //\e
    10761132    typedef typename Digraph::Arc Arc;
    1077     //\e
    10781133    typedef typename Digraph::OutArcIt OutArcIt;
    10791134
     
    10821137    ///The type of the length of the arcs.
    10831138    typedef typename LengthMap::Value Value;
    1084     ///\brief The type of the map that stores the last
     1139    ///\brief The type of the map that stores the predecessor
    10851140    ///arcs of the shortest paths.
    10861141    typedef typename TR::PredMap PredMap;
    1087     ///The type of the map that stores the dists of the nodes.
     1142    ///The type of the map that stores the distances of the nodes.
    10881143    typedef typename TR::DistMap DistMap;
     1144    ///The type of the map that indicates which nodes are processed.
     1145    typedef typename TR::ProcessedMap ProcessedMap;
    10891146    ///The heap type used by the dijkstra algorithm.
    10901147    typedef typename TR::Heap Heap;
     1148
    10911149  public:
     1150
    10921151    /// Constructor.
    10931152    DijkstraWizard() : TR() {}
     
    11051164    ~DijkstraWizard() {}
    11061165
    1107     ///Runs Dijkstra algorithm from a given node.
    1108 
    1109     ///Runs Dijkstra algorithm from a given node.
    1110     ///The node can be given by the \ref source function.
     1166    ///Runs Dijkstra algorithm from a source node.
     1167
     1168    ///Runs Dijkstra algorithm from a source node.
     1169    ///The node can be given with the \ref source() function.
    11111170    void run()
    11121171    {
     
    11301189    }
    11311190
     1191    /// Sets the source node, from which the Dijkstra algorithm runs.
     1192
     1193    /// Sets the source node, from which the Dijkstra algorithm runs.
     1194    /// \param s is the source node.
     1195    DijkstraWizard<TR> &source(Node s)
     1196    {
     1197      Base::_source=s;
     1198      return *this;
     1199    }
     1200
    11321201    template<class T>
    11331202    struct DefPredMapBase : public Base {
     
    11361205      DefPredMapBase(const TR &b) : TR(b) {}
    11371206    };
    1138 
    11391207    ///\brief \ref named-templ-param "Named parameter"
    1140     ///function for setting PredMap type
    1141     ///
    1142     /// \ref named-templ-param "Named parameter"
    1143     ///function for setting PredMap type
    1144     ///
     1208    ///for setting \ref PredMap object.
     1209    ///
     1210    ///\ref named-templ-param "Named parameter"
     1211    ///for setting \ref PredMap object.
    11451212    template<class T>
    11461213    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
     
    11481215      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    11491216      return DijkstraWizard<DefPredMapBase<T> >(*this);
     1217    }
     1218
     1219    template<class T>
     1220    struct DefProcessedMapBase : public Base {
     1221      typedef T ProcessedMap;
     1222      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
     1223      DefProcessedMapBase(const TR &b) : TR(b) {}
     1224    };
     1225    ///\brief \ref named-templ-param "Named parameter"
     1226    ///for setting \ref ProcessedMap object.
     1227    ///
     1228    /// \ref named-templ-param "Named parameter"
     1229    ///for setting \ref ProcessedMap object.
     1230    template<class T>
     1231    DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1232    {
     1233      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
     1234      return DijkstraWizard<DefProcessedMapBase<T> >(*this);
    11501235    }
    11511236
     
    11561241      DefDistMapBase(const TR &b) : TR(b) {}
    11571242    };
    1158 
    11591243    ///\brief \ref named-templ-param "Named parameter"
    1160     ///function for setting DistMap type
    1161     ///
    1162     /// \ref named-templ-param "Named parameter"
    1163     ///function for setting DistMap type
    1164     ///
     1244    ///for setting \ref DistMap object.
     1245    ///
     1246    ///\ref named-templ-param "Named parameter"
     1247    ///for setting \ref DistMap object.
    11651248    template<class T>
    11661249    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
     
    11681251      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    11691252      return DijkstraWizard<DefDistMapBase<T> >(*this);
    1170     }
    1171 
    1172     /// Sets the source node, from which the Dijkstra algorithm runs.
    1173 
    1174     /// Sets the source node, from which the Dijkstra algorithm runs.
    1175     /// \param s is the source node.
    1176     DijkstraWizard<TR> &source(Node s)
    1177     {
    1178       Base::_source=s;
    1179       return *this;
    11801253    }
    11811254
Note: See TracChangeset for help on using the changeset viewer.