COIN-OR::LEMON - Graph Library

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


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

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/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 
Note: See TracChangeset for help on using the changeset viewer.