COIN-OR::LEMON - Graph Library

Changeset 247:f1158744a112 in lemon-1.2


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

Merge

Location:
lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

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

    r220 r247  
    2222///\ingroup search
    2323///\file
    24 ///\brief Bfs algorithm.
     24///\brief BFS algorithm.
    2525
    2626#include <lemon/list_graph.h>
     
    3232namespace lemon {
    3333
    34 
    35 
    3634  ///Default traits class of Bfs class.
    3735
     
    4139  struct BfsDefaultTraits
    4240  {
    43     ///The digraph type the algorithm runs on.
     41    ///The type of the digraph the algorithm runs on.
    4442    typedef GR Digraph;
    45     ///\brief The type of the map that stores the last
     43
     44    ///\brief The type of the map that stores the predecessor
    4645    ///arcs of the shortest paths.
    4746    ///
    48     ///The type of the map that stores the last
     47    ///The type of the map that stores the predecessor
    4948    ///arcs of the shortest paths.
    5049    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    51     ///
    52     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    53     ///Instantiates a PredMap.
     50    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     51    ///Instantiates a \ref PredMap.
    5452
    5553    ///This function instantiates a \ref PredMap.
    56     ///\param G is the digraph, to which we would like to define the PredMap.
     54    ///\param g is the digraph, to which we would like to define the
     55    ///\ref PredMap.
    5756    ///\todo The digraph alone may be insufficient to initialize
    58     static PredMap *createPredMap(const GR &G)
    59     {
    60       return new PredMap(G);
    61     }
     57    static PredMap *createPredMap(const Digraph &g)
     58    {
     59      return new PredMap(g);
     60    }
     61
    6262    ///The type of the map that indicates which nodes are processed.
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    66     ///\todo named parameter to set this type, function to read and write.
     66    ///By default it is a NullMap.
    6767    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a ProcessedMap.
     68    ///Instantiates a \ref ProcessedMap.
    6969
    7070    ///This function instantiates a \ref ProcessedMap.
     
    7272    ///we would like to define the \ref ProcessedMap
    7373#ifdef DOXYGEN
    74     static ProcessedMap *createProcessedMap(const GR &g)
     74    static ProcessedMap *createProcessedMap(const Digraph &g)
    7575#else
    76     static ProcessedMap *createProcessedMap(const GR &)
     76    static ProcessedMap *createProcessedMap(const Digraph &)
    7777#endif
    7878    {
    7979      return new ProcessedMap();
    8080    }
     81
    8182    ///The type of the map that indicates which nodes are reached.
    8283
    8384    ///The type of the map that indicates which nodes are reached.
     85    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     86    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     87    ///Instantiates a \ref ReachedMap.
     88
     89    ///This function instantiates a \ref ReachedMap.
     90    ///\param g is the digraph, to which
     91    ///we would like to define the \ref ReachedMap.
     92    static ReachedMap *createReachedMap(const Digraph &g)
     93    {
     94      return new ReachedMap(g);
     95    }
     96
     97    ///The type of the map that stores the distances of the nodes.
     98
     99    ///The type of the map that stores the distances of the nodes.
    84100    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    85     ///\todo named parameter to set this type, function to read and write.
    86     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    87     ///Instantiates a ReachedMap.
    88 
    89     ///This function instantiates a \ref ReachedMap.
    90     ///\param G is the digraph, to which
    91     ///we would like to define the \ref ReachedMap.
    92     static ReachedMap *createReachedMap(const GR &G)
    93     {
    94       return new ReachedMap(G);
    95     }
    96     ///The type of the map that stores the dists of the nodes.
    97 
    98     ///The type of the map that stores the dists of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100     ///
    101101    typedef typename Digraph::template NodeMap<int> DistMap;
    102     ///Instantiates a DistMap.
     102    ///Instantiates a \ref DistMap.
    103103
    104104    ///This function instantiates a \ref DistMap.
    105     ///\param G is the digraph, to which we would like to define
    106     ///the \ref DistMap
    107     static DistMap *createDistMap(const GR &G)
    108     {
    109       return new DistMap(G);
     105    ///\param g is the digraph, to which we would like to define the
     106    ///\ref DistMap.
     107    static DistMap *createDistMap(const Digraph &g)
     108    {
     109      return new DistMap(g);
    110110    }
    111111  };
     
    116116  ///This class provides an efficient implementation of the %BFS algorithm.
    117117  ///
    118   ///\tparam GR The digraph type the algorithm runs on. The default value is
    119   ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
    120   ///is only passed to \ref BfsDefaultTraits.
     118  ///There is also a \ref bfs() "function type interface" for the BFS
     119  ///algorithm, which is convenient in the simplier cases and it can be
     120  ///used easier.
     121  ///
     122  ///\tparam GR The type of the digraph the algorithm runs on.
     123  ///The default value is \ref ListDigraph. The value of GR is not used
     124  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    121125  ///\tparam TR Traits class to set various data types used by the algorithm.
    122126  ///The default traits class is
     
    124128  ///See \ref BfsDefaultTraits for the documentation of
    125129  ///a Bfs traits class.
    126 
    127130#ifdef DOXYGEN
    128131  template <typename GR,
     
    134137  class Bfs {
    135138  public:
    136     /**
    137      * \brief \ref Exception for uninitialized parameters.
    138      *
    139      * This error represents problems in the initialization
    140      * of the parameters of the algorithms.
    141      */
     139    ///\ref Exception for uninitialized parameters.
     140
     141    ///This error represents problems in the initialization of the
     142    ///parameters of the algorithm.
    142143    class UninitializedParameter : public lemon::UninitializedParameter {
    143144    public:
     
    147148    };
    148149
     150    ///The type of the digraph the algorithm runs on.
     151    typedef typename TR::Digraph Digraph;
     152
     153    ///\brief The type of the map that stores the predecessor arcs of the
     154    ///shortest paths.
     155    typedef typename TR::PredMap PredMap;
     156    ///The type of the map that stores the distances of the nodes.
     157    typedef typename TR::DistMap DistMap;
     158    ///The type of the map that indicates which nodes are reached.
     159    typedef typename TR::ReachedMap ReachedMap;
     160    ///The type of the map that indicates which nodes are processed.
     161    typedef typename TR::ProcessedMap ProcessedMap;
     162    ///The type of the paths.
     163    typedef PredMapPath<Digraph, PredMap> Path;
     164
     165    ///The traits class.
    149166    typedef TR Traits;
    150     ///The type of the underlying digraph.
    151     typedef typename TR::Digraph Digraph;
    152 
    153     ///\brief The type of the map that stores the last
    154     ///arcs of the shortest paths.
    155     typedef typename TR::PredMap PredMap;
    156     ///The type of the map indicating which nodes are reached.
    157     typedef typename TR::ReachedMap ReachedMap;
    158     ///The type of the map indicating which nodes are processed.
    159     typedef typename TR::ProcessedMap ProcessedMap;
    160     ///The type of the map that stores the dists of the nodes.
    161     typedef typename TR::DistMap DistMap;
     167
    162168  private:
    163169
     
    167173    typedef typename Digraph::OutArcIt OutArcIt;
    168174
    169     /// Pointer to the underlying digraph.
     175    //Pointer to the underlying digraph.
    170176    const Digraph *G;
    171     ///Pointer to the map of predecessors arcs.
     177    //Pointer to the map of predecessor arcs.
    172178    PredMap *_pred;
    173     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     179    //Indicates if _pred is locally allocated (true) or not.
    174180    bool local_pred;
    175     ///Pointer to the map of distances.
     181    //Pointer to the map of distances.
    176182    DistMap *_dist;
    177     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     183    //Indicates if _dist is locally allocated (true) or not.
    178184    bool local_dist;
    179     ///Pointer to the map of reached status of the nodes.
     185    //Pointer to the map of reached status of the nodes.
    180186    ReachedMap *_reached;
    181     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     187    //Indicates if _reached is locally allocated (true) or not.
    182188    bool local_reached;
    183     ///Pointer to the map of processed status of the nodes.
     189    //Pointer to the map of processed status of the nodes.
    184190    ProcessedMap *_processed;
    185     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     191    //Indicates if _processed is locally allocated (true) or not.
    186192    bool local_processed;
    187193
     
    191197
    192198    ///Creates the maps if necessary.
    193 
    194199    ///\todo Better memory allocation (instead of new).
    195200    void create_maps()
     
    234239    };
    235240    ///\brief \ref named-templ-param "Named parameter" for setting
    236     ///PredMap type
    237     ///
    238     ///\ref named-templ-param "Named parameter" for setting PredMap type
    239     ///
     241    ///\ref PredMap type.
     242    ///
     243    ///\ref named-templ-param "Named parameter" for setting
     244    ///\ref PredMap type.
    240245    template <class T>
    241246    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
     
    252257    };
    253258    ///\brief \ref named-templ-param "Named parameter" for setting
    254     ///DistMap type
    255     ///
    256     ///\ref named-templ-param "Named parameter" for setting DistMap type
    257     ///
     259    ///\ref DistMap type.
     260    ///
     261    ///\ref named-templ-param "Named parameter" for setting
     262    ///\ref DistMap type.
    258263    template <class T>
    259264    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
     
    270275    };
    271276    ///\brief \ref named-templ-param "Named parameter" for setting
    272     ///ReachedMap type
    273     ///
    274     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    275     ///
     277    ///\ref ReachedMap type.
     278    ///
     279    ///\ref named-templ-param "Named parameter" for setting
     280    ///\ref ReachedMap type.
    276281    template <class T>
    277282    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
     
    288293    };
    289294    ///\brief \ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type
    291     ///
    292     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    293     ///
     295    ///\ref ProcessedMap type.
     296    ///
     297    ///\ref named-templ-param "Named parameter" for setting
     298    ///\ref ProcessedMap type.
    294299    template <class T>
    295300    struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
     
    299304    struct DefDigraphProcessedMapTraits : public Traits {
    300305      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    301       static ProcessedMap *createProcessedMap(const Digraph &G)
     306      static ProcessedMap *createProcessedMap(const Digraph &g)
    302307      {
    303         return new ProcessedMap(G);
    304       }
    305     };
    306     ///\brief \ref named-templ-param "Named parameter"
    307     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    308     ///
    309     ///\ref named-templ-param "Named parameter"
    310     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     308        return new ProcessedMap(g);
     309      }
     310    };
     311    ///\brief \ref named-templ-param "Named parameter" for setting
     312    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     313    ///
     314    ///\ref named-templ-param "Named parameter" for setting
     315    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    311316    ///If you don't set it explicitly, it will be automatically allocated.
    312317    template <class T>
     
    322327    ///Constructor.
    323328
    324     ///\param _G the digraph the algorithm will run on.
    325     ///
    326     Bfs(const Digraph& _G) :
    327       G(&_G),
     329    ///Constructor.
     330    ///\param g The digraph the algorithm runs on.
     331    Bfs(const Digraph &g) :
     332      G(&g),
    328333      _pred(NULL), local_pred(false),
    329334      _dist(NULL), local_dist(false),
     
    341346    }
    342347
    343     ///Sets the map storing the predecessor arcs.
    344 
    345     ///Sets the map storing the predecessor arcs.
     348    ///Sets the map that stores the predecessor arcs.
     349
     350    ///Sets the map that stores the predecessor arcs.
    346351    ///If you don't use this function before calling \ref run(),
    347352    ///it will allocate one. The destructor deallocates this
     
    358363    }
    359364
    360     ///Sets the map indicating the reached nodes.
    361 
    362     ///Sets the map indicating the reached nodes.
     365    ///Sets the map that indicates which nodes are reached.
     366
     367    ///Sets the map that indicates which nodes are reached.
    363368    ///If you don't use this function before calling \ref run(),
    364369    ///it will allocate one. The destructor deallocates this
     
    375380    }
    376381
    377     ///Sets the map indicating the processed nodes.
    378 
    379     ///Sets the map indicating the processed nodes.
     382    ///Sets the map that indicates which nodes are processed.
     383
     384    ///Sets the map that indicates which nodes are processed.
    380385    ///If you don't use this function before calling \ref run(),
    381386    ///it will allocate one. The destructor deallocates this
     
    392397    }
    393398
    394     ///Sets the map storing the distances calculated by the algorithm.
    395 
    396     ///Sets the map storing the distances calculated by the algorithm.
     399    ///Sets the map that stores the distances of the nodes.
     400
     401    ///Sets the map that stores the distances of the nodes calculated by
     402    ///the algorithm.
    397403    ///If you don't use this function before calling \ref run(),
    398404    ///it will allocate one. The destructor deallocates this
     
    410416
    411417  public:
     418
    412419    ///\name Execution control
    413420    ///The simplest way to execute the algorithm is to use
    414     ///one of the member functions called \c run(...).
     421    ///one of the member functions called \ref lemon::Bfs::run() "run()".
    415422    ///\n
    416     ///If you need more control on the execution,
    417     ///first you must call \ref init(), then you can add several source nodes
    418     ///with \ref addSource().
    419     ///Finally \ref start() will perform the actual path
    420     ///computation.
     423    ///If you need more control on the execution, first you must call
     424    ///\ref lemon::Bfs::init() "init()", then you can add several source
     425    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
     426    ///Finally \ref lemon::Bfs::start() "start()" will perform the
     427    ///actual path computation.
    421428
    422429    ///@{
    423430
    424     ///\brief Initializes the internal data structures.
    425     ///
     431    ///Initializes the internal data structures.
     432
    426433    ///Initializes the internal data structures.
    427434    ///
     
    461468    ///\return The processed node.
    462469    ///
    463     ///\warning The queue must not be empty!
     470    ///\pre The queue must not be empty.
    464471    Node processNextNode()
    465472    {
     
    483490    ///Processes the next node.
    484491
    485     ///Processes the next node. And checks that the given target node
     492    ///Processes the next node and checks if the given target node
    486493    ///is reached. If the target node is reachable from the processed
    487     ///node then the reached parameter will be set true. The reached
    488     ///parameter should be initially false.
     494    ///node, then the \c reach parameter will be set to \c true.
    489495    ///
    490496    ///\param target The target node.
    491     ///\retval reach Indicates that the target node is reached.
     497    ///\retval reach Indicates if the target node is reached.
     498    ///It should be initially \c false.
     499    ///
    492500    ///\return The processed node.
    493501    ///
    494     ///\warning The queue must not be empty!
     502    ///\pre The queue must not be empty.
    495503    Node processNextNode(Node target, bool& reach)
    496504    {
     
    515523    ///Processes the next node.
    516524
    517     ///Processes the next node. And checks that at least one of
    518     ///reached node has true value in the \c nm node map. If one node
    519     ///with true value is reachable from the processed node then the
    520     ///rnode parameter will be set to the first of such nodes.
    521     ///
    522     ///\param nm The node map of possible targets.
     525    ///Processes the next node and checks if at least one of reached
     526    ///nodes has \c true value in the \c nm node map. If one node
     527    ///with \c true value is reachable from the processed node, then the
     528    ///\c rnode parameter will be set to the first of such nodes.
     529    ///
     530    ///\param nm A \c bool (or convertible) node map that indicates the
     531    ///possible targets.
    523532    ///\retval rnode The reached target node.
     533    ///It should be initially \c INVALID.
     534    ///
    524535    ///\return The processed node.
    525536    ///
    526     ///\warning The queue must not be empty!
     537    ///\pre The queue must not be empty.
    527538    template<class NM>
    528539    Node processNextNode(const NM& nm, Node& rnode)
     
    546557    }
    547558
    548     ///Next node to be processed.
    549 
    550     ///Next node to be processed.
    551     ///
    552     ///\return The next node to be processed or INVALID if the queue is
    553     /// empty.
    554     Node nextNode()
     559    ///The next node to be processed.
     560
     561    ///Returns the next node to be processed or \c INVALID if the queue
     562    ///is empty.
     563    Node nextNode() const
    555564    {
    556565      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
     
    558567
    559568    ///\brief Returns \c false if there are nodes
    560     ///to be processed in the queue
     569    ///to be processed.
    561570    ///
    562571    ///Returns \c false if there are nodes
    563     ///to be processed in the queue
    564     bool emptyQueue() { return _queue_tail==_queue_head; }
     572    ///to be processed in the queue.
     573    bool emptyQueue() const { return _queue_tail==_queue_head; }
     574
    565575    ///Returns the number of the nodes to be processed.
    566576
    567577    ///Returns the number of the nodes to be processed in the queue.
    568     int queueSize() { return _queue_head-_queue_tail; }
     578    int queueSize() const { return _queue_head-_queue_tail; }
    569579
    570580    ///Executes the algorithm.
     
    572582    ///Executes the algorithm.
    573583    ///
    574     ///\pre init() must be called and at least one node should be added
    575     ///with addSource() before using this function.
    576     ///
    577584    ///This method runs the %BFS algorithm from the root node(s)
    578     ///in order to
    579     ///compute the
    580     ///shortest path to each node. The algorithm computes
    581     ///- The shortest path tree.
    582     ///- The distance of each node from the root(s).
     585    ///in order to compute the shortest path to each node.
     586    ///
     587    ///The algorithm computes
     588    ///- the shortest path tree (forest),
     589    ///- the distance of each node from the root(s).
     590    ///
     591    ///\pre init() must be called and at least one root node should be
     592    ///added with addSource() before using this function.
     593    ///
     594    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
     595    ///\code
     596    ///  while ( !b.emptyQueue() ) {
     597    ///    b.processNextNode();
     598    ///  }
     599    ///\endcode
    583600    void start()
    584601    {
     
    586603    }
    587604
    588     ///Executes the algorithm until \c dest is reached.
    589 
    590     ///Executes the algorithm until \c dest is reached.
    591     ///
    592     ///\pre init() must be called and at least one node should be added
    593     ///with addSource() before using this function.
     605    ///Executes the algorithm until the given target node is reached.
     606
     607    ///Executes the algorithm until the given target node is reached.
    594608    ///
    595609    ///This method runs the %BFS algorithm from the root node(s)
    596610    ///in order to compute the shortest path to \c dest.
     611    ///
    597612    ///The algorithm computes
    598     ///- The shortest path to \c  dest.
    599     ///- The distance of \c dest from the root(s).
     613    ///- the shortest path to \c dest,
     614    ///- the distance of \c dest from the root(s).
     615    ///
     616    ///\pre init() must be called and at least one root node should be
     617    ///added with addSource() before using this function.
     618    ///
     619    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
     620    ///\code
     621    ///  bool reach = false;
     622    ///  while ( !b.emptyQueue() && !reach ) {
     623    ///    b.processNextNode(t, reach);
     624    ///  }
     625    ///\endcode
    600626    void start(Node dest)
    601627    {
     
    608634    ///Executes the algorithm until a condition is met.
    609635    ///
    610     ///\pre init() must be called and at least one node should be added
    611     ///with addSource() before using this function.
    612     ///
    613     ///\param nm must be a bool (or convertible) node map. The
    614     ///algorithm will stop when it reaches a node \c v with
    615     /// <tt>nm[v]</tt> true.
     636    ///This method runs the %BFS algorithm from the root node(s) in
     637    ///order to compute the shortest path to a node \c v with
     638    /// <tt>nm[v]</tt> true, if such a node can be found.
     639    ///
     640    ///\param nm A \c bool (or convertible) node map. The algorithm
     641    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
    616642    ///
    617643    ///\return The reached node \c v with <tt>nm[v]</tt> true or
    618644    ///\c INVALID if no such node was found.
    619     template<class NM>
    620     Node start(const NM &nm)
     645    ///
     646    ///\pre init() must be called and at least one root node should be
     647    ///added with addSource() before using this function.
     648    ///
     649    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
     650    ///\code
     651    ///  Node rnode = INVALID;
     652    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
     653    ///    b.processNextNode(nm, rnode);
     654    ///  }
     655    ///  return rnode;
     656    ///\endcode
     657    template<class NodeBoolMap>
     658    Node start(const NodeBoolMap &nm)
    621659    {
    622660      Node rnode = INVALID;
     
    627665    }
    628666
    629     ///Runs %BFS algorithm from node \c s.
    630 
    631     ///This method runs the %BFS algorithm from a root node \c s
    632     ///in order to
    633     ///compute the
    634     ///shortest path to each node. The algorithm computes
    635     ///- The shortest path tree.
    636     ///- The distance of each node from the root.
    637     ///
    638     ///\note b.run(s) is just a shortcut of the following code.
     667    ///Runs the algorithm from the given node.
     668
     669    ///This method runs the %BFS algorithm from node \c s
     670    ///in order to compute the shortest path to each node.
     671    ///
     672    ///The algorithm computes
     673    ///- the shortest path tree,
     674    ///- the distance of each node from the root.
     675    ///
     676    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    639677    ///\code
    640678    ///  b.init();
     
    650688    ///Finds the shortest path between \c s and \c t.
    651689
    652     ///Finds the shortest path between \c s and \c t.
    653     ///
    654     ///\return The length of the shortest s---t path if there exists one,
    655     ///0 otherwise.
    656     ///\note Apart from the return value, b.run(s) is
    657     ///just a shortcut of the following code.
     690    ///This method runs the %BFS algorithm from node \c s
     691    ///in order to compute the shortest path to \c t.
     692    ///
     693    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
     694    ///if \c t is reachable form \c s, \c 0 otherwise.
     695    ///
     696    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     697    ///shortcut of the following code.
    658698    ///\code
    659699    ///  b.init();
     
    668708    }
    669709
     710    ///Runs the algorithm to visit all nodes in the digraph.
     711
     712    ///This method runs the %BFS algorithm in order to
     713    ///compute the shortest path to each node.
     714    ///
     715    ///The algorithm computes
     716    ///- the shortest path tree (forest),
     717    ///- the distance of each node from the root(s).
     718    ///
     719    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     720    ///\code
     721    ///  b.init();
     722    ///  for (NodeIt n(gr); n != INVALID; ++n) {
     723    ///    if (!b.reached(n)) {
     724    ///      b.addSource(n);
     725    ///      b.start();
     726    ///    }
     727    ///  }
     728    ///\endcode
     729    void run() {
     730      init();
     731      for (NodeIt n(*G); n != INVALID; ++n) {
     732        if (!reached(n)) {
     733          addSource(n);
     734          start();
     735        }
     736      }
     737    }
     738
    670739    ///@}
    671740
     
    673742    ///The result of the %BFS algorithm can be obtained using these
    674743    ///functions.\n
    675     ///Before the use of these functions,
    676     ///either run() or start() must be calleb.
     744    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     745    ///"start()" must be called before using them.
    677746
    678747    ///@{
    679748
    680     typedef PredMapPath<Digraph, PredMap> Path;
    681 
    682     ///Gives back the shortest path.
    683 
    684     ///Gives back the shortest path.
    685     ///\pre The \c t should be reachable from the source.
    686     Path path(Node t)
    687     {
    688       return Path(*G, *_pred, t);
    689     }
     749    ///The shortest path to a node.
     750
     751    ///Returns the shortest path to a node.
     752    ///
     753    ///\warning \c t should be reachable from the root(s).
     754    ///
     755    ///\pre Either \ref run() or \ref start() must be called before
     756    ///using this function.
     757    Path path(Node t) const { return Path(*G, *_pred, t); }
    690758
    691759    ///The distance of a node from the root(s).
    692760
    693761    ///Returns the distance of a node from the root(s).
    694     ///\pre \ref run() must be called before using this function.
    695     ///\warning If node \c v in unreachable from the root(s) the return value
    696     ///of this function is undefined.
     762    ///
     763    ///\warning If node \c v is not reachable from the root(s), then
     764    ///the return value of this function is undefined.
     765    ///
     766    ///\pre Either \ref run() or \ref start() must be called before
     767    ///using this function.
    697768    int dist(Node v) const { return (*_dist)[v]; }
    698769
    699     ///Returns the 'previous arc' of the shortest path tree.
    700 
    701     ///For a node \c v it returns the 'previous arc'
    702     ///of the shortest path tree,
    703     ///i.e. it returns the last arc of a shortest path from the root(s) to \c
    704     ///v. It is \ref INVALID
    705     ///if \c v is unreachable from the root(s) or \c v is a root. The
    706     ///shortest path tree used here is equal to the shortest path tree used in
    707     ///\ref predNode().
    708     ///\pre Either \ref run() or \ref start() must be called before using
    709     ///this function.
     770    ///Returns the 'previous arc' of the shortest path tree for a node.
     771
     772    ///This function returns the 'previous arc' of the shortest path
     773    ///tree for the node \c v, i.e. it returns the last arc of a
     774    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     775    ///is not reachable from the root(s) or if \c v is a root.
     776    ///
     777    ///The shortest path tree used here is equal to the shortest path
     778    ///tree used in \ref predNode().
     779    ///
     780    ///\pre Either \ref run() or \ref start() must be called before
     781    ///using this function.
    710782    Arc predArc(Node v) const { return (*_pred)[v];}
    711783
    712     ///Returns the 'previous node' of the shortest path tree.
    713 
    714     ///For a node \c v it returns the 'previous node'
    715     ///of the shortest path tree,
    716     ///i.e. it returns the last but one node from a shortest path from the
    717     ///root(a) to \c /v.
    718     ///It is INVALID if \c v is unreachable from the root(s) or
    719     ///if \c v itself a root.
     784    ///Returns the 'previous node' of the shortest path tree for a node.
     785
     786    ///This function returns the 'previous node' of the shortest path
     787    ///tree for the node \c v, i.e. it returns the last but one node
     788    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     789    ///if \c v is not reachable from the root(s) or if \c v is a root.
     790    ///
    720791    ///The shortest path tree used here is equal to the shortest path
    721792    ///tree used in \ref predArc().
     793    ///
    722794    ///\pre Either \ref run() or \ref start() must be called before
    723795    ///using this function.
     
    725797                                  G->source((*_pred)[v]); }
    726798
    727     ///Returns a reference to the NodeMap of distances.
    728 
    729     ///Returns a reference to the NodeMap of distances.
    730     ///\pre Either \ref run() or \ref init() must
    731     ///be called before using this function.
     799    ///\brief Returns a const reference to the node map that stores the
     800    /// distances of the nodes.
     801    ///
     802    ///Returns a const reference to the node map that stores the distances
     803    ///of the nodes calculated by the algorithm.
     804    ///
     805    ///\pre Either \ref run() or \ref init()
     806    ///must be called before using this function.
    732807    const DistMap &distMap() const { return *_dist;}
    733808
    734     ///Returns a reference to the shortest path tree map.
    735 
    736     ///Returns a reference to the NodeMap of the arcs of the
    737     ///shortest path tree.
     809    ///\brief Returns a const reference to the node map that stores the
     810    ///predecessor arcs.
     811    ///
     812    ///Returns a const reference to the node map that stores the predecessor
     813    ///arcs, which form the shortest path tree.
     814    ///
    738815    ///\pre Either \ref run() or \ref init()
    739816    ///must be called before using this function.
    740817    const PredMap &predMap() const { return *_pred;}
    741818
    742     ///Checks if a node is reachable from the root.
    743 
    744     ///Returns \c true if \c v is reachable from the root.
    745     ///\warning The source nodes are indicated as unreached.
     819    ///Checks if a node is reachable from the root(s).
     820
     821    ///Returns \c true if \c v is reachable from the root(s).
    746822    ///\pre Either \ref run() or \ref start()
    747823    ///must be called before using this function.
    748     ///
    749     bool reached(Node v) { return (*_reached)[v]; }
     824    bool reached(Node v) const { return (*_reached)[v]; }
    750825
    751826    ///@}
    752827  };
    753828
    754   ///Default traits class of Bfs function.
    755 
    756   ///Default traits class of Bfs function.
     829  ///Default traits class of bfs() function.
     830
     831  ///Default traits class of bfs() function.
    757832  ///\tparam GR Digraph type.
    758833  template<class GR>
    759834  struct BfsWizardDefaultTraits
    760835  {
    761     ///The digraph type the algorithm runs on.
     836    ///The type of the digraph the algorithm runs on.
    762837    typedef GR Digraph;
    763     ///\brief The type of the map that stores the last
     838
     839    ///\brief The type of the map that stores the predecessor
    764840    ///arcs of the shortest paths.
    765841    ///
    766     ///The type of the map that stores the last
     842    ///The type of the map that stores the predecessor
    767843    ///arcs of the shortest paths.
    768844    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    769     ///
    770     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
    771     ///Instantiates a PredMap.
     845    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     846    ///Instantiates a \ref PredMap.
    772847
    773848    ///This function instantiates a \ref PredMap.
    774     ///\param g is the digraph, to which we would like to define the PredMap.
     849    ///\param g is the digraph, to which we would like to define the
     850    ///\ref PredMap.
    775851    ///\todo The digraph alone may be insufficient to initialize
    776852#ifdef DOXYGEN
    777     static PredMap *createPredMap(const GR &g)
     853    static PredMap *createPredMap(const Digraph &g)
    778854#else
    779     static PredMap *createPredMap(const GR &)
     855    static PredMap *createPredMap(const Digraph &)
    780856#endif
    781857    {
     
    787863    ///The type of the map that indicates which nodes are processed.
    788864    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    789     ///\todo named parameter to set this type, function to read and write.
    790865    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    791     ///Instantiates a ProcessedMap.
     866    ///Instantiates a \ref ProcessedMap.
    792867
    793868    ///This function instantiates a \ref ProcessedMap.
    794869    ///\param g is the digraph, to which
    795     ///we would like to define the \ref ProcessedMap
     870    ///we would like to define the \ref ProcessedMap.
    796871#ifdef DOXYGEN
    797     static ProcessedMap *createProcessedMap(const GR &g)
     872    static ProcessedMap *createProcessedMap(const Digraph &g)
    798873#else
    799     static ProcessedMap *createProcessedMap(const GR &)
     874    static ProcessedMap *createProcessedMap(const Digraph &)
    800875#endif
    801876    {
    802877      return new ProcessedMap();
    803878    }
     879
    804880    ///The type of the map that indicates which nodes are reached.
    805881
    806882    ///The type of the map that indicates which nodes are reached.
     883    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     884    typedef typename Digraph::template NodeMap<bool> ReachedMap;
     885    ///Instantiates a \ref ReachedMap.
     886
     887    ///This function instantiates a \ref ReachedMap.
     888    ///\param g is the digraph, to which
     889    ///we would like to define the \ref ReachedMap.
     890    static ReachedMap *createReachedMap(const Digraph &g)
     891    {
     892      return new ReachedMap(g);
     893    }
     894
     895    ///The type of the map that stores the distances of the nodes.
     896
     897    ///The type of the map that stores the distances of the nodes.
    807898    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    808     ///\todo named parameter to set this type, function to read and write.
    809     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    810     ///Instantiates a ReachedMap.
    811 
    812     ///This function instantiates a \ref ReachedMap.
    813     ///\param G is the digraph, to which
    814     ///we would like to define the \ref ReachedMap.
    815     static ReachedMap *createReachedMap(const GR &G)
    816     {
    817       return new ReachedMap(G);
    818     }
    819     ///The type of the map that stores the dists of the nodes.
    820 
    821     ///The type of the map that stores the dists of the nodes.
    822     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    823899    ///
    824900    typedef NullMap<typename Digraph::Node,int> DistMap;
    825     ///Instantiates a DistMap.
     901    ///Instantiates a \ref DistMap.
    826902
    827903    ///This function instantiates a \ref DistMap.
     
    829905    ///the \ref DistMap
    830906#ifdef DOXYGEN
    831     static DistMap *createDistMap(const GR &g)
     907    static DistMap *createDistMap(const Digraph &g)
    832908#else
    833     static DistMap *createDistMap(const GR &)
     909    static DistMap *createDistMap(const Digraph &)
    834910#endif
    835911    {
     
    838914  };
    839915
    840   /// Default traits used by \ref BfsWizard
     916  /// Default traits class used by \ref BfsWizard
    841917
    842918  /// To make it easier to use Bfs algorithm
    843   ///we have created a wizard class.
     919  /// we have created a wizard class.
    844920  /// This \ref BfsWizard class needs default traits,
    845   ///as well as the \ref Bfs class.
     921  /// as well as the \ref Bfs class.
    846922  /// The \ref BfsWizardBase is a class to be the default traits of the
    847923  /// \ref BfsWizard class.
     
    852928    typedef BfsWizardDefaultTraits<GR> Base;
    853929  protected:
    854     /// Type of the nodes in the digraph.
     930    //The type of the nodes in the digraph.
    855931    typedef typename Base::Digraph::Node Node;
    856932
    857     /// Pointer to the underlying digraph.
     933    //Pointer to the digraph the algorithm runs on.
    858934    void *_g;
    859     ///Pointer to the map of reached nodes.
     935    //Pointer to the map of reached nodes.
    860936    void *_reached;
    861     ///Pointer to the map of processed nodes.
     937    //Pointer to the map of processed nodes.
    862938    void *_processed;
    863     ///Pointer to the map of predecessors arcs.
     939    //Pointer to the map of predecessors arcs.
    864940    void *_pred;
    865     ///Pointer to the map of distances.
     941    //Pointer to the map of distances.
    866942    void *_dist;
    867     ///Pointer to the source node.
     943    //Pointer to the source node.
    868944    Node _source;
    869945
     
    874950    /// all of the attributes to default values (0, INVALID).
    875951    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    876                            _dist(0), _source(INVALID) {}
     952                      _dist(0), _source(INVALID) {}
    877953
    878954    /// Constructor.
     
    881957    /// listed in the parameters list.
    882958    /// Others are initiated to 0.
    883     /// \param g is the initial value of  \ref _g
    884     /// \param s is the initial value of  \ref _source
     959    /// \param g The digraph the algorithm runs on.
     960    /// \param s The source node.
    885961    BfsWizardBase(const GR &g, Node s=INVALID) :
    886962      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
     
    889965  };
    890966
    891   /// A class to make the usage of Bfs algorithm easier
    892 
    893   /// This class is created to make it easier to use Bfs algorithm.
    894   /// It uses the functions and features of the plain \ref Bfs,
    895   /// but it is much simpler to use it.
     967  /// Auxiliary class for the function type interface of BFS algorithm.
     968
     969  /// This auxiliary class is created to implement the function type
     970  /// interface of \ref Bfs algorithm. It uses the functions and features
     971  /// of the plain \ref Bfs, but it is much simpler to use it.
     972  /// It should only be used through the \ref bfs() function, which makes
     973  /// it easier to use the algorithm.
    896974  ///
    897975  /// Simplicity means that the way to change the types defined
     
    902980  /// the original class by using the ::
    903981  /// operator. In the case of \ref BfsWizard only
    904   /// a function have to be called and it will
     982  /// a function have to be called, and it will
    905983  /// return the needed class.
    906984  ///
    907   /// It does not have own \ref run method. When its \ref run method is called
    908   /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
    909   /// method of it.
     985  /// It does not have own \ref run() method. When its \ref run() method
     986  /// is called, it initiates a plain \ref Bfs object, and calls the
     987  /// \ref Bfs::run() method of it.
    910988  template<class TR>
    911989  class BfsWizard : public TR
     
    913991    typedef TR Base;
    914992
    915     ///The type of the underlying digraph.
     993    ///The type of the digraph the algorithm runs on.
    916994    typedef typename TR::Digraph Digraph;
    917     //\e
     995
    918996    typedef typename Digraph::Node Node;
    919     //\e
    920997    typedef typename Digraph::NodeIt NodeIt;
    921     //\e
    922998    typedef typename Digraph::Arc Arc;
    923     //\e
    924999    typedef typename Digraph::OutArcIt OutArcIt;
    9251000
    926     ///\brief The type of the map that stores
    927     ///the reached nodes
    928     typedef typename TR::ReachedMap ReachedMap;
    929     ///\brief The type of the map that stores
    930     ///the processed nodes
    931     typedef typename TR::ProcessedMap ProcessedMap;
    932     ///\brief The type of the map that stores the last
     1001    ///\brief The type of the map that stores the predecessor
    9331002    ///arcs of the shortest paths.
    9341003    typedef typename TR::PredMap PredMap;
    935     ///The type of the map that stores the dists of the nodes.
     1004    ///\brief The type of the map that stores the distances of the nodes.
    9361005    typedef typename TR::DistMap DistMap;
     1006    ///\brief The type of the map that indicates which nodes are reached.
     1007    typedef typename TR::ReachedMap ReachedMap;
     1008    ///\brief The type of the map that indicates which nodes are processed.
     1009    typedef typename TR::ProcessedMap ProcessedMap;
    9371010
    9381011  public:
     1012
    9391013    /// Constructor.
    9401014    BfsWizard() : TR() {}
     
    9521026    ~BfsWizard() {}
    9531027
    954     ///Runs Bfs algorithm from a given node.
    955 
    956     ///Runs Bfs algorithm from a given node.
    957     ///The node can be given by the \ref source function.
     1028    ///Runs BFS algorithm from a source node.
     1029
     1030    ///Runs BFS algorithm from a source node.
     1031    ///The node can be given with the \ref source() function.
    9581032    void run()
    9591033    {
     
    9711045    }
    9721046
    973     ///Runs Bfs algorithm from the given node.
    974 
    975     ///Runs Bfs algorithm from the given node.
     1047    ///Runs BFS algorithm from the given node.
     1048
     1049    ///Runs BFS algorithm from the given node.
    9761050    ///\param s is the given source.
    9771051    void run(Node s)
     
    9791053      Base::_source=s;
    9801054      run();
     1055    }
     1056
     1057    /// Sets the source node, from which the Bfs algorithm runs.
     1058
     1059    /// Sets the source node, from which the Bfs algorithm runs.
     1060    /// \param s is the source node.
     1061    BfsWizard<TR> &source(Node s)
     1062    {
     1063      Base::_source=s;
     1064      return *this;
    9811065    }
    9821066
     
    9871071      DefPredMapBase(const TR &b) : TR(b) {}
    9881072    };
    989 
    9901073    ///\brief \ref named-templ-param "Named parameter"
    991     ///function for setting PredMap
     1074    ///for setting \ref PredMap object.
    9921075    ///
    9931076    /// \ref named-templ-param "Named parameter"
    994     ///function for setting PredMap
    995     ///
     1077    ///for setting \ref PredMap object.
    9961078    template<class T>
    9971079    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     
    10001082      return BfsWizard<DefPredMapBase<T> >(*this);
    10011083    }
    1002 
    10031084
    10041085    template<class T>
     
    10081089      DefReachedMapBase(const TR &b) : TR(b) {}
    10091090    };
    1010 
    10111091    ///\brief \ref named-templ-param "Named parameter"
    1012     ///function for setting ReachedMap
     1092    ///for setting \ref ReachedMap object.
    10131093    ///
    10141094    /// \ref named-templ-param "Named parameter"
    1015     ///function for setting ReachedMap
    1016     ///
     1095    ///for setting \ref ReachedMap object.
    10171096    template<class T>
    10181097    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     
    10211100      return BfsWizard<DefReachedMapBase<T> >(*this);
    10221101    }
    1023 
    10241102
    10251103    template<class T>
     
    10291107      DefProcessedMapBase(const TR &b) : TR(b) {}
    10301108    };
    1031 
    10321109    ///\brief \ref named-templ-param "Named parameter"
    1033     ///function for setting ProcessedMap
     1110    ///for setting \ref ProcessedMap object.
    10341111    ///
    10351112    /// \ref named-templ-param "Named parameter"
    1036     ///function for setting ProcessedMap
    1037     ///
     1113    ///for setting \ref ProcessedMap object.
    10381114    template<class T>
    10391115    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     
    10421118      return BfsWizard<DefProcessedMapBase<T> >(*this);
    10431119    }
    1044 
    10451120
    10461121    template<class T>
     
    10501125      DefDistMapBase(const TR &b) : TR(b) {}
    10511126    };
    1052 
    10531127    ///\brief \ref named-templ-param "Named parameter"
    1054     ///function for setting DistMap type
     1128    ///for setting \ref DistMap object.
    10551129    ///
    10561130    /// \ref named-templ-param "Named parameter"
    1057     ///function for setting DistMap type
    1058     ///
     1131    ///for setting \ref DistMap object.
    10591132    template<class T>
    10601133    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
     
    10621135      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    10631136      return BfsWizard<DefDistMapBase<T> >(*this);
    1064     }
    1065 
    1066     /// Sets the source node, from which the Bfs algorithm runs.
    1067 
    1068     /// Sets the source node, from which the Bfs algorithm runs.
    1069     /// \param s is the source node.
    1070     BfsWizard<TR> &source(Node s)
    1071     {
    1072       Base::_source=s;
    1073       return *this;
    10741137    }
    10751138
     
    11011164
    11021165#ifdef DOXYGEN
    1103   /// \brief Visitor class for bfs.
     1166  /// \brief Visitor class for BFS.
    11041167  ///
    11051168  /// This class defines the interface of the BfsVisit events, and
    1106   /// it could be the base of a real Visitor class.
     1169  /// it could be the base of a real visitor class.
    11071170  template <typename _Digraph>
    11081171  struct BfsVisitor {
     
    11101173    typedef typename Digraph::Arc Arc;
    11111174    typedef typename Digraph::Node Node;
    1112     /// \brief Called when the arc reach a node.
    1113     ///
    1114     /// It is called when the bfs find an arc which target is not
    1115     /// reached yet.
     1175    /// \brief Called for the source node(s) of the BFS.
     1176    ///
     1177    /// This function is called for the source node(s) of the BFS.
     1178    void start(const Node& node) {}
     1179    /// \brief Called when a node is reached first time.
     1180    ///
     1181    /// This function is called when a node is reached first time.
     1182    void reach(const Node& node) {}
     1183    /// \brief Called when a node is processed.
     1184    ///
     1185    /// This function is called when a node is processed.
     1186    void process(const Node& node) {}
     1187    /// \brief Called when an arc reaches a new node.
     1188    ///
     1189    /// This function is called when the BFS finds an arc whose target node
     1190    /// is not reached yet.
    11161191    void discover(const Arc& arc) {}
    1117     /// \brief Called when the node reached first time.
    1118     ///
    1119     /// It is Called when the node reached first time.
    1120     void reach(const Node& node) {}
    1121     /// \brief Called when the arc examined but target of the arc
     1192    /// \brief Called when an arc is examined but its target node is
    11221193    /// already discovered.
    11231194    ///
    1124     /// It called when the arc examined but the target of the arc
     1195    /// This function is called when an arc is examined but its target node is
    11251196    /// already discovered.
    11261197    void examine(const Arc& arc) {}
    1127     /// \brief Called for the source node of the bfs.
    1128     ///
    1129     /// It is called for the source node of the bfs.
    1130     void start(const Node& node) {}
    1131     /// \brief Called when the node processed.
    1132     ///
    1133     /// It is Called when the node processed.
    1134     void process(const Node& node) {}
    11351198  };
    11361199#else
     
    11401203    typedef typename Digraph::Arc Arc;
    11411204    typedef typename Digraph::Node Node;
     1205    void start(const Node&) {}
     1206    void reach(const Node&) {}
     1207    void process(const Node&) {}
    11421208    void discover(const Arc&) {}
    1143     void reach(const Node&) {}
    11441209    void examine(const Arc&) {}
    1145     void start(const Node&) {}
    1146     void process(const Node&) {}
    11471210
    11481211    template <typename _Visitor>
     
    11511214        Arc arc;
    11521215        Node node;
     1216        visitor.start(node);
     1217        visitor.reach(node);
     1218        visitor.process(node);
    11531219        visitor.discover(arc);
    1154         visitor.reach(node);
    11551220        visitor.examine(arc);
    1156         visitor.start(node);
    1157         visitor.process(node);
    11581221      }
    11591222      _Visitor& visitor;
     
    11651228  ///
    11661229  /// Default traits class of BfsVisit class.
    1167   /// \tparam _Digraph Digraph type.
     1230  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11681231  template<class _Digraph>
    11691232  struct BfsVisitDefaultTraits {
    11701233
    1171     /// \brief The digraph type the algorithm runs on.
     1234    /// \brief The type of the digraph the algorithm runs on.
    11721235    typedef _Digraph Digraph;
    11731236
     
    11751238    ///
    11761239    /// The type of the map that indicates which nodes are reached.
    1177     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1178     /// \todo named parameter to set this type, function to read and write.
     1240    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    11791241    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    11801242
    1181     /// \brief Instantiates a ReachedMap.
     1243    /// \brief Instantiates a \ref ReachedMap.
    11821244    ///
    11831245    /// This function instantiates a \ref ReachedMap.
     
    11921254  /// \ingroup search
    11931255  ///
    1194   /// \brief %BFS Visit algorithm class.
     1256  /// \brief %BFS algorithm class with visitor interface.
    11951257  ///
    11961258  /// This class provides an efficient implementation of the %BFS algorithm
     
    11991261  /// The %BfsVisit class provides an alternative interface to the Bfs
    12001262  /// class. It works with callback mechanism, the BfsVisit object calls
    1201   /// on every bfs event the \c Visitor class member functions.
     1263  /// the member functions of the \c Visitor class on every BFS event.
    12021264  ///
    1203   /// \tparam _Digraph The digraph type the algorithm runs on.
     1265  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    12041266  /// The default value is
    1205   /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
    1206   /// is only passed to \ref BfsDefaultTraits.
    1207   /// \tparam _Visitor The Visitor object for the algorithm. The
    1208   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
    1209   /// does not observe the Bfs events. If you want to observe the bfs
    1210   /// events you should implement your own Visitor class.
     1267  /// \ref ListDigraph. The value of _Digraph is not used directly by
     1268  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
     1269  /// \tparam _Visitor The Visitor type that is used by the algorithm.
     1270  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1271  /// does not observe the BFS events. If you want to observe the BFS
     1272  /// events, you should implement your own visitor class.
    12111273  /// \tparam _Traits Traits class to set various data types used by the
    12121274  /// algorithm. The default traits class is
    12131275  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    12141276  /// See \ref BfsVisitDefaultTraits for the documentation of
    1215   /// a Bfs visit traits class.
     1277  /// a BFS visit traits class.
    12161278#ifdef DOXYGEN
    12171279  template <typename _Digraph, typename _Visitor, typename _Traits>
     
    12271289    ///
    12281290    /// This error represents problems in the initialization
    1229     /// of the parameters of the algorithms.
     1291    /// of the parameters of the algorithm.
    12301292    class UninitializedParameter : public lemon::UninitializedParameter {
    12311293    public:
     
    12361298    };
    12371299
     1300    ///The traits class.
    12381301    typedef _Traits Traits;
    12391302
     1303    ///The type of the digraph the algorithm runs on.
    12401304    typedef typename Traits::Digraph Digraph;
    12411305
     1306    ///The visitor type used by the algorithm.
    12421307    typedef _Visitor Visitor;
    12431308
    1244     ///The type of the map indicating which nodes are reached.
     1309    ///The type of the map that indicates which nodes are reached.
    12451310    typedef typename Traits::ReachedMap ReachedMap;
    12461311
     
    12521317    typedef typename Digraph::OutArcIt OutArcIt;
    12531318
    1254     /// Pointer to the underlying digraph.
     1319    //Pointer to the underlying digraph.
    12551320    const Digraph *_digraph;
    1256     /// Pointer to the visitor object.
     1321    //Pointer to the visitor object.
    12571322    Visitor *_visitor;
    1258     ///Pointer to the map of reached status of the nodes.
     1323    //Pointer to the map of reached status of the nodes.
    12591324    ReachedMap *_reached;
    1260     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1325    //Indicates if _reached is locally allocated (true) or not.
    12611326    bool local_reached;
    12621327
     
    12641329    int _list_front, _list_back;
    12651330
    1266     /// \brief Creates the maps if necessary.
    1267     ///
    1268     /// Creates the maps if necessary.
     1331    ///Creates the maps if necessary.
     1332    ///\todo Better memory allocation (instead of new).
    12691333    void create_maps() {
    12701334      if(!_reached) {
     
    12931357    };
    12941358    /// \brief \ref named-templ-param "Named parameter" for setting
    1295     /// ReachedMap type
    1296     ///
    1297     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1359    /// ReachedMap type.
     1360    ///
     1361    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    12981362    template <class T>
    12991363    struct DefReachedMap : public BfsVisit< Digraph, Visitor,
     
    13091373    /// Constructor.
    13101374    ///
    1311     /// \param digraph the digraph the algorithm will run on.
    1312     /// \param visitor The visitor of the algorithm.
    1313     ///
     1375    /// \param digraph The digraph the algorithm runs on.
     1376    /// \param visitor The visitor object of the algorithm.
    13141377    BfsVisit(const Digraph& digraph, Visitor& visitor)
    13151378      : _digraph(&digraph), _visitor(&visitor),
     
    13171380
    13181381    /// \brief Destructor.
    1319     ///
    1320     /// Destructor.
    13211382    ~BfsVisit() {
    13221383      if(local_reached) delete _reached;
    13231384    }
    13241385
    1325     /// \brief Sets the map indicating if a node is reached.
    1326     ///
    1327     /// Sets the map indicating if a node is reached.
     1386    /// \brief Sets the map that indicates which nodes are reached.
     1387    ///
     1388    /// Sets the map that indicates which nodes are reached.
    13281389    /// If you don't use this function before calling \ref run(),
    1329     /// it will allocate one. The destuctor deallocates this
     1390    /// it will allocate one. The destructor deallocates this
    13301391    /// automatically allocated map, of course.
    13311392    /// \return <tt> (*this) </tt>
     
    13401401
    13411402  public:
     1403
    13421404    /// \name Execution control
    13431405    /// The simplest way to execute the algorithm is to use
    1344     /// one of the member functions called \c run(...).
     1406    /// one of the member functions called \ref lemon::BfsVisit::run()
     1407    /// "run()".
    13451408    /// \n
    1346     /// If you need more control on the execution,
    1347     /// first you must call \ref init(), then you can adda source node
    1348     /// with \ref addSource().
    1349     /// Finally \ref start() will perform the actual path
    1350     /// computation.
     1409    /// If you need more control on the execution, first you must call
     1410    /// \ref lemon::BfsVisit::init() "init()", then you can add several
     1411    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
     1412    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
     1413    /// actual path computation.
    13511414
    13521415    /// @{
     1416
    13531417    /// \brief Initializes the internal data structures.
    13541418    ///
    13551419    /// Initializes the internal data structures.
    1356     ///
    13571420    void init() {
    13581421      create_maps();
     
    13821445    /// \return The processed node.
    13831446    ///
    1384     /// \pre The queue must not be empty!
     1447    /// \pre The queue must not be empty.
    13851448    Node processNextNode() {
    13861449      Node n = _list[++_list_front];
     
    14031466    /// \brief Processes the next node.
    14041467    ///
    1405     /// Processes the next node. And checks that the given target node
     1468    /// Processes the next node and checks if the given target node
    14061469    /// is reached. If the target node is reachable from the processed
    1407     /// node then the reached parameter will be set true. The reached
    1408     /// parameter should be initially false.
     1470    /// node, then the \c reach parameter will be set to \c true.
    14091471    ///
    14101472    /// \param target The target node.
    1411     /// \retval reach Indicates that the target node is reached.
     1473    /// \retval reach Indicates if the target node is reached.
     1474    /// It should be initially \c false.
     1475    ///
    14121476    /// \return The processed node.
    14131477    ///
    1414     /// \warning The queue must not be empty!
     1478    /// \pre The queue must not be empty.
    14151479    Node processNextNode(Node target, bool& reach) {
    14161480      Node n = _list[++_list_front];
     
    14341498    /// \brief Processes the next node.
    14351499    ///
    1436     /// Processes the next node. And checks that at least one of
    1437     /// reached node has true value in the \c nm node map. If one node
    1438     /// with true value is reachable from the processed node then the
    1439     /// rnode parameter will be set to the first of such nodes.
    1440     ///
    1441     /// \param nm The node map of possible targets.
     1500    /// Processes the next node and checks if at least one of reached
     1501    /// nodes has \c true value in the \c nm node map. If one node
     1502    /// with \c true value is reachable from the processed node, then the
     1503    /// \c rnode parameter will be set to the first of such nodes.
     1504    ///
     1505    /// \param nm A \c bool (or convertible) node map that indicates the
     1506    /// possible targets.
    14421507    /// \retval rnode The reached target node.
     1508    /// It should be initially \c INVALID.
     1509    ///
    14431510    /// \return The processed node.
    14441511    ///
    1445     /// \warning The queue must not be empty!
     1512    /// \pre The queue must not be empty.
    14461513    template <typename NM>
    14471514    Node processNextNode(const NM& nm, Node& rnode) {
     
    14641531    }
    14651532
    1466     /// \brief Next node to be processed.
    1467     ///
    1468     /// Next node to be processed.
    1469     ///
    1470     /// \return The next node to be processed or INVALID if the stack is
    1471     /// empty.
    1472     Node nextNode() {
     1533    /// \brief The next node to be processed.
     1534    ///
     1535    /// Returns the next node to be processed or \c INVALID if the queue
     1536    /// is empty.
     1537    Node nextNode() const {
    14731538      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
    14741539    }
    14751540
    14761541    /// \brief Returns \c false if there are nodes
    1477     /// to be processed in the queue
     1542    /// to be processed.
    14781543    ///
    14791544    /// Returns \c false if there are nodes
    1480     /// to be processed in the queue
    1481     bool emptyQueue() { return _list_front == _list_back; }
     1545    /// to be processed in the queue.
     1546    bool emptyQueue() const { return _list_front == _list_back; }
    14821547
    14831548    /// \brief Returns the number of the nodes to be processed.
    14841549    ///
    14851550    /// Returns the number of the nodes to be processed in the queue.
    1486     int queueSize() { return _list_back - _list_front; }
     1551    int queueSize() const { return _list_back - _list_front; }
    14871552
    14881553    /// \brief Executes the algorithm.
     
    14901555    /// Executes the algorithm.
    14911556    ///
    1492     /// \pre init() must be called and at least one node should be added
     1557    /// This method runs the %BFS algorithm from the root node(s)
     1558    /// in order to compute the shortest path to each node.
     1559    ///
     1560    /// The algorithm computes
     1561    /// - the shortest path tree (forest),
     1562    /// - the distance of each node from the root(s).
     1563    ///
     1564    /// \pre init() must be called and at least one root node should be added
    14931565    /// with addSource() before using this function.
     1566    ///
     1567    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
     1568    /// \code
     1569    ///   while ( !b.emptyQueue() ) {
     1570    ///     b.processNextNode();
     1571    ///   }
     1572    /// \endcode
    14941573    void start() {
    14951574      while ( !emptyQueue() ) processNextNode();
    14961575    }
    14971576
    1498     /// \brief Executes the algorithm until \c dest is reached.
    1499     ///
    1500     /// Executes the algorithm until \c dest is reached.
    1501     ///
    1502     /// \pre init() must be called and at least one node should be added
    1503     /// with addSource() before using this function.
     1577    /// \brief Executes the algorithm until the given target node is reached.
     1578    ///
     1579    /// Executes the algorithm until the given target node is reached.
     1580    ///
     1581    /// This method runs the %BFS algorithm from the root node(s)
     1582    /// in order to compute the shortest path to \c dest.
     1583    ///
     1584    /// The algorithm computes
     1585    /// - the shortest path to \c dest,
     1586    /// - the distance of \c dest from the root(s).
     1587    ///
     1588    /// \pre init() must be called and at least one root node should be
     1589    /// added with addSource() before using this function.
     1590    ///
     1591    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
     1592    /// \code
     1593    ///   bool reach = false;
     1594    ///   while ( !b.emptyQueue() && !reach ) {
     1595    ///     b.processNextNode(t, reach);
     1596    ///   }
     1597    /// \endcode
    15041598    void start(Node dest) {
    15051599      bool reach = false;
     
    15111605    /// Executes the algorithm until a condition is met.
    15121606    ///
    1513     /// \pre init() must be called and at least one node should be added
    1514     /// with addSource() before using this function.
    1515     ///
    1516     ///\param nm must be a bool (or convertible) node map. The
    1517     ///algorithm will stop when it reaches a node \c v with
     1607    /// This method runs the %BFS algorithm from the root node(s) in
     1608    /// order to compute the shortest path to a node \c v with
     1609    /// <tt>nm[v]</tt> true, if such a node can be found.
     1610    ///
     1611    /// \param nm must be a bool (or convertible) node map. The
     1612    /// algorithm will stop when it reaches a node \c v with
    15181613    /// <tt>nm[v]</tt> true.
    15191614    ///
    1520     ///\return The reached node \c v with <tt>nm[v]</tt> true or
    1521     ///\c INVALID if no such node was found.
     1615    /// \return The reached node \c v with <tt>nm[v]</tt> true or
     1616    /// \c INVALID if no such node was found.
     1617    ///
     1618    /// \pre init() must be called and at least one root node should be
     1619    /// added with addSource() before using this function.
     1620    ///
     1621    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
     1622    /// \code
     1623    ///   Node rnode = INVALID;
     1624    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
     1625    ///     b.processNextNode(nm, rnode);
     1626    ///   }
     1627    ///   return rnode;
     1628    /// \endcode
    15221629    template <typename NM>
    15231630    Node start(const NM &nm) {
     
    15291636    }
    15301637
    1531     /// \brief Runs %BFSVisit algorithm from node \c s.
    1532     ///
    1533     /// This method runs the %BFS algorithm from a root node \c s.
    1534     /// \note b.run(s) is just a shortcut of the following code.
     1638    /// \brief Runs the algorithm from the given node.
     1639    ///
     1640    /// This method runs the %BFS algorithm from node \c s
     1641    /// in order to compute the shortest path to each node.
     1642    ///
     1643    /// The algorithm computes
     1644    /// - the shortest path tree,
     1645    /// - the distance of each node from the root.
     1646    ///
     1647    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    15351648    ///\code
    15361649    ///   b.init();
     
    15441657    }
    15451658
    1546     /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
     1659    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15471660    ///
    15481661    /// This method runs the %BFS algorithm in order to
    1549     /// compute the %BFS path to each node. The algorithm computes
    1550     /// - The %BFS tree.
    1551     /// - The distance of each node from the root in the %BFS tree.
    1552     ///
    1553     ///\note b.run() is just a shortcut of the following code.
     1662    /// compute the shortest path to each node.
     1663    ///
     1664    /// The algorithm computes
     1665    /// - the shortest path tree (forest),
     1666    /// - the distance of each node from the root(s).
     1667    ///
     1668    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    15541669    ///\code
    15551670    ///  b.init();
    1556     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    1557     ///    if (!b.reached(it)) {
    1558     ///      b.addSource(it);
     1671    ///  for (NodeIt n(gr); n != INVALID; ++n) {
     1672    ///    if (!b.reached(n)) {
     1673    ///      b.addSource(n);
    15591674    ///      b.start();
    15601675    ///    }
     
    15701685      }
    15711686    }
     1687
    15721688    ///@}
    15731689
     
    15751691    /// The result of the %BFS algorithm can be obtained using these
    15761692    /// functions.\n
    1577     /// Before the use of these functions,
    1578     /// either run() or start() must be called.
     1693    /// Either \ref lemon::BfsVisit::run() "run()" or
     1694    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1695    /// using them.
    15791696    ///@{
    15801697
    1581     /// \brief Checks if a node is reachable from the root.
     1698    /// \brief Checks if a node is reachable from the root(s).
    15821699    ///
    15831700    /// Returns \c true if \c v is reachable from the root(s).
    1584     /// \warning The source nodes are inditated as unreachable.
    15851701    /// \pre Either \ref run() or \ref start()
    15861702    /// must be called before using this function.
    1587     ///
    15881703    bool reached(Node v) { return (*_reached)[v]; }
     1704
    15891705    ///@}
     1706
    15901707  };
    15911708
     
    15931710
    15941711#endif
    1595 
  • lemon/dfs.h

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

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

    r244 r247  
    2828#include <lemon/bin_heap.h>
    2929#include <lemon/bits/path_dump.h>
    30 #include <lemon/bits/invalid.h>
     30#include <lemon/core.h>
    3131#include <lemon/error.h>
    3232#include <lemon/maps.h>
  • lemon/dijkstra.h

    r220 r247  
    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.