COIN-OR::LEMON - Graph Library

Changeset 244:c30731a37f91 in lemon for lemon/bfs.h


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

Many improvements in bfs.h, dfs.h and dijkstra.h

  • Add run() function to Bfs and run(s,t) function to DfsVisit?.
  • Add debug checking to addSource() function of Dfs and DfsVisit?.
  • Add a few missing named parameters (according to \todo notes).
  • Small fixes in the code (e.g. missing derivations).
  • Many doc improvements.
  • Remove \todo and \warning comments which are no longer valid.
  • Remove \author commands (see ticket #39).
  • Fixes in the the doc (e.g. wrong references).
  • Hide the doc of most of the private and protected members.
  • Use public typedefs instead of template parameters in public functions.
  • Use better parameter names for some functions.
  • Other small changes to make the doc more uniform.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

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