COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 421:6b9057cdcd8b in lemon for lemon/bfs.h


Ignore:
Timestamp:
11/30/08 19:17:51 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Doc improvements for Bfs, Dfs, Dijkstra (#185)

  • More precise references to overloaded member functions.
  • Hide the doc of the traits class parameters.
  • Better doc for named groups.
  • More precise doc for the case of multiple sources in Dfs.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bfs.h

    r341 r421  
    5252    ///Instantiates a PredMap.
    5353
    54     ///This function instantiates a PredMap. 
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///PredMap.
    … …  
    8181    ///The type of the map that indicates which nodes are reached.
    8282
    83     ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8485    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8586    ///Instantiates a ReachedMap.
    … …  
    119120  ///
    120121  ///\tparam GR The type of the digraph the algorithm runs on.
    121   ///The default value is \ref ListDigraph. The value of GR is not used
    122   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    123   ///\tparam TR Traits class to set various data types used by the algorithm.
    124   ///The default traits class is
    125   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    126   ///See \ref BfsDefaultTraits for the documentation of
    127   ///a Bfs traits class.
     122  ///The default type is \ref ListDigraph.
    128123#ifdef DOXYGEN
    129124  template <typename GR,
    … …  
    151146    typedef PredMapPath<Digraph, PredMap> Path;
    152147
    153     ///The traits class.
     148    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    154149    typedef TR Traits;
    155150
    … …  
    213208    typedef Bfs Create;
    214209
    215     ///\name Named template parameters
     210    ///\name Named Template Parameters
    216211
    217212    ///@{
    … …  
    231226    ///\ref named-templ-param "Named parameter" for setting
    232227    ///PredMap type.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233229    template <class T>
    234230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    250246    ///\ref named-templ-param "Named parameter" for setting
    251247    ///DistMap type.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252249    template <class T>
    253250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    269266    ///\ref named-templ-param "Named parameter" for setting
    270267    ///ReachedMap type.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271269    template <class T>
    272270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    288286    ///\ref named-templ-param "Named parameter" for setting
    289287    ///ProcessedMap type.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290289    template <class T>
    291290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    340339
    341340    ///Sets the map that stores the predecessor arcs.
    342     ///If you don't use this function before calling \ref run(),
    343     ///it will allocate one. The destructor deallocates this
    344     ///automatically allocated map, of course.
     341    ///If you don't use this function before calling \ref run(Node) "run()"
     342    ///or \ref init(), an instance will be allocated automatically.
     343    ///The destructor deallocates this automatically allocated map,
     344    ///of course.
    345345    ///\return <tt> (*this) </tt>
    346346    Bfs &predMap(PredMap &m)
    … …  
    357357
    358358    ///Sets the map that indicates which nodes are reached.
    359     ///If you don't use this function before calling \ref run(),
    360     ///it will allocate one. The destructor deallocates this
    361     ///automatically allocated map, of course.
     359    ///If you don't use this function before calling \ref run(Node) "run()"
     360    ///or \ref init(), an instance will be allocated automatically.
     361    ///The destructor deallocates this automatically allocated map,
     362    ///of course.
    362363    ///\return <tt> (*this) </tt>
    363364    Bfs &reachedMap(ReachedMap &m)
    … …  
    374375
    375376    ///Sets the map that indicates which nodes are processed.
    376     ///If you don't use this function before calling \ref run(),
    377     ///it will allocate one. The destructor deallocates this
    378     ///automatically allocated map, of course.
     377    ///If you don't use this function before calling \ref run(Node) "run()"
     378    ///or \ref init(), an instance will be allocated automatically.
     379    ///The destructor deallocates this automatically allocated map,
     380    ///of course.
    379381    ///\return <tt> (*this) </tt>
    380382    Bfs &processedMap(ProcessedMap &m)
    … …  
    392394    ///Sets the map that stores the distances of the nodes calculated by
    393395    ///the algorithm.
    394     ///If you don't use this function before calling \ref run(),
    395     ///it will allocate one. The destructor deallocates this
    396     ///automatically allocated map, of course.
     396    ///If you don't use this function before calling \ref run(Node) "run()"
     397    ///or \ref init(), an instance will be allocated automatically.
     398    ///The destructor deallocates this automatically allocated map,
     399    ///of course.
    397400    ///\return <tt> (*this) </tt>
    398401    Bfs &distMap(DistMap &m)
    … …  
    408411  public:
    409412
    410     ///\name Execution control
    411     ///The simplest way to execute the algorithm is to use
    412     ///one of the member functions called \ref lemon::Bfs::run() "run()".
    413     ///\n
    414     ///If you need more control on the execution, first you must call
    415     ///\ref lemon::Bfs::init() "init()", then you can add several source
    416     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
    417     ///Finally \ref lemon::Bfs::start() "start()" will perform the
    418     ///actual path computation.
     413    ///\name Execution Control
     414    ///The simplest way to execute the BFS algorithm is to use one of the
     415    ///member functions called \ref run(Node) "run()".\n
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
     418    ///\ref addSource(). Finally the actual path computation can be
     419    ///performed with one of the \ref start() functions.
    419420
    420421    ///@{
    421422
     423    ///\brief Initializes the internal data structures.
     424    ///
    422425    ///Initializes the internal data structures.
    423 
    424     ///Initializes the internal data structures.
    425     ///
    426426    void init()
    427427    {
    … …  
    557557    }
    558558
    559     ///\brief Returns \c false if there are nodes
    560     ///to be processed.
    561     ///
    562     ///Returns \c false if there are nodes
    563     ///to be processed in the queue.
     559    ///Returns \c false if there are nodes to be processed.
     560
     561    ///Returns \c false if there are nodes to be processed
     562    ///in the queue.
    564563    bool emptyQueue() const { return _queue_tail==_queue_head; }
    565564
    566565    ///Returns the number of the nodes to be processed.
    567566
    568     ///Returns the number of the nodes to be processed in the queue.
     567    ///Returns the number of the nodes to be processed
     568    ///in the queue.
    569569    int queueSize() const { return _queue_head-_queue_tail; }
    570570
    … …  
    731731
    732732    ///\name Query Functions
    733     ///The result of the %BFS algorithm can be obtained using these
     733    ///The results of the BFS algorithm can be obtained using these
    734734    ///functions.\n
    735     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    736     ///"start()" must be called before using them.
     735    ///Either \ref run(Node) "run()" or \ref start() should be called
     736    ///before using them.
    737737
    738738    ///@{
    … …  
    742742    ///Returns the shortest path to a node.
    743743    ///
    744     ///\warning \c t should be reachable from the root(s).
    745     ///
    746     ///\pre Either \ref run() or \ref start() must be called before
    747     ///using this function.
     744    ///\warning \c t should be reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
     747    ///must be called before using this function.
    748748    Path path(Node t) const { return Path(*G, *_pred, t); }
    749749
    … …  
    752752    ///Returns the distance of a node from the root(s).
    753753    ///
    754     ///\warning If node \c v is not reachable from the root(s), then
     754    ///\warning If node \c v is not reached from the root(s), then
    755755    ///the return value of this function is undefined.
    756756    ///
    757     ///\pre Either \ref run() or \ref start() must be called before
    758     ///using this function.
     757    ///\pre Either \ref run(Node) "run()" or \ref init()
     758    ///must be called before using this function.
    759759    int dist(Node v) const { return (*_dist)[v]; }
    760760
    … …  
    763763    ///This function returns the 'previous arc' of the shortest path
    764764    ///tree for the node \c v, i.e. it returns the last arc of a
    765     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    766     ///is not reachable from the root(s) or if \c v is a root.
     765    ///shortest path from a root to \c v. It is \c INVALID if \c v
     766    ///is not reached from the root(s) or if \c v is a root.
    767767    ///
    768768    ///The shortest path tree used here is equal to the shortest path
    769769    ///tree used in \ref predNode().
    770770    ///
    771     ///\pre Either \ref run() or \ref start() must be called before
    772     ///using this function.
     771    ///\pre Either \ref run(Node) "run()" or \ref init()
     772    ///must be called before using this function.
    773773    Arc predArc(Node v) const { return (*_pred)[v];}
    774774
    … …  
    777777    ///This function returns the 'previous node' of the shortest path
    778778    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    780     ///if \c v is not reachable from the root(s) or if \c v is a root.
     779    ///from a shortest path from a root to \c v. It is \c INVALID
     780    ///if \c v is not reached from the root(s) or if \c v is a root.
    781781    ///
    782782    ///The shortest path tree used here is equal to the shortest path
    783783    ///tree used in \ref predArc().
    784784    ///
    785     ///\pre Either \ref run() or \ref start() must be called before
    786     ///using this function.
     785    ///\pre Either \ref run(Node) "run()" or \ref init()
     786    ///must be called before using this function.
    787787    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    788788                                  G->source((*_pred)[v]); }
    … …  
    794794    ///of the nodes calculated by the algorithm.
    795795    ///
    796     ///\pre Either \ref run() or \ref init()
     796    ///\pre Either \ref run(Node) "run()" or \ref init()
    797797    ///must be called before using this function.
    798798    const DistMap &distMap() const { return *_dist;}
    … …  
    804804    ///arcs, which form the shortest path tree.
    805805    ///
    806     ///\pre Either \ref run() or \ref init()
     806    ///\pre Either \ref run(Node) "run()" or \ref init()
    807807    ///must be called before using this function.
    808808    const PredMap &predMap() const { return *_pred;}
    809809
    810     ///Checks if a node is reachable from the root(s).
    811 
    812     ///Returns \c true if \c v is reachable from the root(s).
    813     ///\pre Either \ref run() or \ref start()
     810    ///Checks if a node is reached from the root(s).
     811
     812    ///Returns \c true if \c v is reached from the root(s).
     813    ///
     814    ///\pre Either \ref run(Node) "run()" or \ref init()
    814815    ///must be called before using this function.
    815816    bool reached(Node v) const { return (*_reached)[v]; }
    … …  
    957958  /// This auxiliary class is created to implement the
    958959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    959   /// It does not have own \ref run() method, it uses the functions
    960   /// and features of the plain \ref Bfs.
     960  /// It does not have own \ref run(Node) "run()" method, it uses the
     961  /// functions and features of the plain \ref Bfs.
    961962  ///
    962963  /// This class should only be used through the \ref bfs() function,
    … …  
    11781179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11791180  ///\endcode
    1180   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11811182  ///to the end of the parameter list.
    11821183  ///\sa BfsWizard
    … …  
    13641365    typedef BfsVisit Create;
    13651366
    1366     /// \name Named template parameters
     1367    /// \name Named Template Parameters
    13671368
    13681369    ///@{
    … …  
    14061407    ///
    14071408    /// Sets the map that indicates which nodes are reached.
    1408     /// If you don't use this function before calling \ref run(),
    1409     /// it will allocate one. The destructor deallocates this
    1410     /// automatically allocated map, of course.
     1409    /// If you don't use this function before calling \ref run(Node) "run()"
     1410    /// or \ref init(), an instance will be allocated automatically.
     1411    /// The destructor deallocates this automatically allocated map,
     1412    /// of course.
    14111413    /// \return <tt> (*this) </tt>
    14121414    BfsVisit &reachedMap(ReachedMap &m) {
    … …  
    14211423  public:
    14221424
    1423     /// \name Execution control
    1424     /// The simplest way to execute the algorithm is to use
    1425     /// one of the member functions called \ref lemon::BfsVisit::run()
    1426     /// "run()".
    1427     /// \n
    1428     /// If you need more control on the execution, first you must call
    1429     /// \ref lemon::BfsVisit::init() "init()", then you can add several
    1430     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
    1431     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
    1432     /// actual path computation.
     1425    /// \name Execution Control
     1426    /// The simplest way to execute the BFS algorithm is to use one of the
     1427    /// member functions called \ref run(Node) "run()".\n
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
     1430    /// \ref addSource(). Finally the actual path computation can be
     1431    /// performed with one of the \ref start() functions.
    14331432
    14341433    /// @{
    … …  
    17301729
    17311730    /// \name Query Functions
    1732     /// The result of the %BFS algorithm can be obtained using these
     1731    /// The results of the BFS algorithm can be obtained using these
    17331732    /// functions.\n
    1734     /// Either \ref lemon::BfsVisit::run() "run()" or
    1735     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1736     /// using them.
     1733    /// Either \ref run(Node) "run()" or \ref start() should be called
     1734    /// before using them.
     1735
    17371736    ///@{
    17381737
    1739     /// \brief Checks if a node is reachable from the root(s).
    1740     ///
    1741     /// Returns \c true if \c v is reachable from the root(s).
    1742     /// \pre Either \ref run() or \ref start()
     1738    /// \brief Checks if a node is reached from the root(s).
     1739    ///
     1740    /// Returns \c true if \c v is reached from the root(s).
     1741    ///
     1742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17431743    /// must be called before using this function.
    17441744    bool reached(Node v) { return (*_reached)[v]; }
Note: See TracChangeset for help on using the changeset viewer.