COIN-OR::LEMON - Graph Library

Changeset 405:6b9057cdcd8b in lemon-1.2 for lemon


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.
Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r329 r405  
    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]; }
  • lemon/dfs.h

    r319 r405  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
    127   ///See \ref DfsDefaultTraits for the documentation of
    128   ///a Dfs traits class.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    231225    ///\ref named-templ-param "Named parameter" for setting
    232226    ///PredMap type.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233228    template <class T>
    234229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    250245    ///\ref named-templ-param "Named parameter" for setting
    251246    ///DistMap type.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252248    template <class T>
    253249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    269265    ///\ref named-templ-param "Named parameter" for setting
    270266    ///ReachedMap type.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271268    template <class T>
    272269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    288285    ///\ref named-templ-param "Named parameter" for setting
    289286    ///ProcessedMap type.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290288    template <class T>
    291289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    339337
    340338    ///Sets the map that stores the predecessor arcs.
    341     ///If you don't use this function before calling \ref run(),
    342     ///it will allocate one. The destructor deallocates this
    343     ///automatically allocated map, of course.
     339    ///If you don't use this function before calling \ref run(Node) "run()"
     340    ///or \ref init(), an instance will be allocated automatically.
     341    ///The destructor deallocates this automatically allocated map,
     342    ///of course.
    344343    ///\return <tt> (*this) </tt>
    345344    Dfs &predMap(PredMap &m)
     
    356355
    357356    ///Sets the map that indicates which nodes are reached.
    358     ///If you don't use this function before calling \ref run(),
    359     ///it will allocate one. The destructor deallocates this
    360     ///automatically allocated map, of course.
     357    ///If you don't use this function before calling \ref run(Node) "run()"
     358    ///or \ref init(), an instance will be allocated automatically.
     359    ///The destructor deallocates this automatically allocated map,
     360    ///of course.
    361361    ///\return <tt> (*this) </tt>
    362362    Dfs &reachedMap(ReachedMap &m)
     
    373373
    374374    ///Sets the map that indicates which nodes are processed.
    375     ///If you don't use this function before calling \ref run(),
    376     ///it will allocate one. The destructor deallocates this
    377     ///automatically allocated map, of course.
     375    ///If you don't use this function before calling \ref run(Node) "run()"
     376    ///or \ref init(), an instance will be allocated automatically.
     377    ///The destructor deallocates this automatically allocated map,
     378    ///of course.
    378379    ///\return <tt> (*this) </tt>
    379380    Dfs &processedMap(ProcessedMap &m)
     
    391392    ///Sets the map that stores the distances of the nodes calculated by
    392393    ///the algorithm.
    393     ///If you don't use this function before calling \ref run(),
    394     ///it will allocate one. The destructor deallocates this
    395     ///automatically allocated map, of course.
     394    ///If you don't use this function before calling \ref run(Node) "run()"
     395    ///or \ref init(), an instance will be allocated automatically.
     396    ///The destructor deallocates this automatically allocated map,
     397    ///of course.
    396398    ///\return <tt> (*this) </tt>
    397399    Dfs &distMap(DistMap &m)
     
    407409  public:
    408410
    409     ///\name Execution control
    410     ///The simplest way to execute the algorithm is to use
    411     ///one of the member functions called \ref lemon::Dfs::run() "run()".
    412     ///\n
    413     ///If you need more control on the execution, first you must call
    414     ///\ref lemon::Dfs::init() "init()", then you can add a source node
    415     ///with \ref lemon::Dfs::addSource() "addSource()".
    416     ///Finally \ref lemon::Dfs::start() "start()" will perform the
    417     ///actual path computation.
     411    ///\name Execution Control
     412    ///The simplest way to execute the DFS algorithm is to use one of the
     413    ///member functions called \ref run(Node) "run()".\n
     414    ///If you need more control on the execution, first you have to call
     415    ///\ref init(), then you can add a source node with \ref addSource()
     416    ///and perform the actual computation with \ref start().
     417    ///This procedure can be repeated if there are nodes that have not
     418    ///been reached.
    418419
    419420    ///@{
    420421
     422    ///\brief Initializes the internal data structures.
     423    ///
    421424    ///Initializes the internal data structures.
    422 
    423     ///Initializes the internal data structures.
    424     ///
    425425    void init()
    426426    {
     
    439439    ///Adds a new source node to the set of nodes to be processed.
    440440    ///
    441     ///\pre The stack must be empty. (Otherwise the algorithm gives
    442     ///false results.)
    443     ///
    444     ///\warning Distances will be wrong (or at least strange) in case of
    445     ///multiple sources.
     441    ///\pre The stack must be empty. Otherwise the algorithm gives
     442    ///wrong results. (One of the outgoing arcs of all the source nodes
     443    ///except for the last one will not be visited and distances will
     444    ///also be wrong.)
    446445    void addSource(Node s)
    447446    {
     
    507506    }
    508507
    509     ///\brief Returns \c false if there are nodes
    510     ///to be processed.
    511     ///
    512     ///Returns \c false if there are nodes
    513     ///to be processed in the queue (stack).
     508    ///Returns \c false if there are nodes to be processed.
     509
     510    ///Returns \c false if there are nodes to be processed
     511    ///in the queue (stack).
    514512    bool emptyQueue() const { return _stack_head<0; }
    515513
    516514    ///Returns the number of the nodes to be processed.
    517515
    518     ///Returns the number of the nodes to be processed in the queue (stack).
     516    ///Returns the number of the nodes to be processed
     517    ///in the queue (stack).
    519518    int queueSize() const { return _stack_head+1; }
    520519
     
    638637    ///
    639638    ///The algorithm computes
    640     ///- the %DFS tree,
    641     ///- the distance of each node from the root in the %DFS tree.
     639    ///- the %DFS tree (forest),
     640    ///- the distance of each node from the root(s) in the %DFS tree.
    642641    ///
    643642    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    664663
    665664    ///\name Query Functions
    666     ///The result of the %DFS algorithm can be obtained using these
     665    ///The results of the DFS algorithm can be obtained using these
    667666    ///functions.\n
    668     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
    669     ///"start()" must be called before using them.
     667    ///Either \ref run(Node) "run()" or \ref start() should be called
     668    ///before using them.
    670669
    671670    ///@{
     
    675674    ///Returns the DFS path to a node.
    676675    ///
    677     ///\warning \c t should be reachable from the root.
    678     ///
    679     ///\pre Either \ref run() or \ref start() must be called before
    680     ///using this function.
     676    ///\warning \c t should be reached from the root(s).
     677    ///
     678    ///\pre Either \ref run(Node) "run()" or \ref init()
     679    ///must be called before using this function.
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    683     ///The distance of a node from the root.
    684 
    685     ///Returns the distance of a node from the root.
    686     ///
    687     ///\warning If node \c v is not reachable from the root, then
     682    ///The distance of a node from the root(s).
     683
     684    ///Returns the distance of a node from the root(s).
     685    ///
     686    ///\warning If node \c v is not reached from the root(s), then
    688687    ///the return value of this function is undefined.
    689688    ///
    690     ///\pre Either \ref run() or \ref start() must be called before
    691     ///using this function.
     689    ///\pre Either \ref run(Node) "run()" or \ref init()
     690    ///must be called before using this function.
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
     
    695694
    696695    ///This function returns the 'previous arc' of the %DFS tree for the
    697     ///node \c v, i.e. it returns the last arc of a %DFS path from the
    698     ///root to \c v. It is \c INVALID
    699     ///if \c v is not reachable from the root(s) or if \c v is a root.
     696    ///node \c v, i.e. it returns the last arc of a %DFS path from a
     697    ///root to \c v. It is \c INVALID if \c v is not reached from the
     698    ///root(s) or if \c v is a root.
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702701    ///\ref predNode().
    703702    ///
    704     ///\pre Either \ref run() or \ref start() must be called before using
    705     ///this function.
     703    ///\pre Either \ref run(Node) "run()" or \ref init()
     704    ///must be called before using this function.
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
     
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///tree for the node \c v, i.e. it returns the last but one node
    712     ///from a %DFS path from the root to \c v. It is \c INVALID
    713     ///if \c v is not reachable from the root(s) or if \c v is a root.
     711    ///from a %DFS path from a root to \c v. It is \c INVALID
     712    ///if \c v is not reached from the root(s) or if \c v is a root.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716715    ///\ref predArc().
    717716    ///
    718     ///\pre Either \ref run() or \ref start() must be called before
    719     ///using this function.
     717    ///\pre Either \ref run(Node) "run()" or \ref init()
     718    ///must be called before using this function.
    720719    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    721720                                  G->source((*_pred)[v]); }
     
    727726    ///distances of the nodes calculated by the algorithm.
    728727    ///
    729     ///\pre Either \ref run() or \ref init()
     728    ///\pre Either \ref run(Node) "run()" or \ref init()
    730729    ///must be called before using this function.
    731730    const DistMap &distMap() const { return *_dist;}
     
    737736    ///arcs, which form the DFS tree.
    738737    ///
    739     ///\pre Either \ref run() or \ref init()
     738    ///\pre Either \ref run(Node) "run()" or \ref init()
    740739    ///must be called before using this function.
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    743     ///Checks if a node is reachable from the root(s).
    744 
    745     ///Returns \c true if \c v is reachable from the root(s).
    746     ///\pre Either \ref run() or \ref start()
     742    ///Checks if a node is reached from the root(s).
     743
     744    ///Returns \c true if \c v is reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
    747747    ///must be called before using this function.
    748748    bool reached(Node v) const { return (*_reached)[v]; }
     
    890890  /// This auxiliary class is created to implement the
    891891  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
    892   /// It does not have own \ref run() method, it uses the functions
    893   /// and features of the plain \ref Dfs.
     892  /// It does not have own \ref run(Node) "run()" method, it uses the
     893  /// functions and features of the plain \ref Dfs.
    894894  ///
    895895  /// This class should only be used through the \ref dfs() function,
     
    11111111  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    11121112  ///\endcode
    1113 
    1114   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1113  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
    11151114  ///to the end of the parameter list.
    11161115  ///\sa DfsWizard
     
    13101309    typedef DfsVisit Create;
    13111310
    1312     /// \name Named template parameters
     1311    /// \name Named Template Parameters
    13131312
    13141313    ///@{
     
    13521351    ///
    13531352    /// Sets the map that indicates which nodes are reached.
    1354     /// If you don't use this function before calling \ref run(),
    1355     /// it will allocate one. The destructor deallocates this
    1356     /// automatically allocated map, of course.
     1353    /// If you don't use this function before calling \ref run(Node) "run()"
     1354    /// or \ref init(), an instance will be allocated automatically.
     1355    /// The destructor deallocates this automatically allocated map,
     1356    /// of course.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671367  public:
    13681368
    1369     /// \name Execution control
    1370     /// The simplest way to execute the algorithm is to use
    1371     /// one of the member functions called \ref lemon::DfsVisit::run()
    1372     /// "run()".
    1373     /// \n
    1374     /// If you need more control on the execution, first you must call
    1375     /// \ref lemon::DfsVisit::init() "init()", then you can add several
    1376     /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
    1377     /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
    1378     /// actual path computation.
     1369    /// \name Execution Control
     1370    /// The simplest way to execute the DFS algorithm is to use one of the
     1371    /// member functions called \ref run(Node) "run()".\n
     1372    /// If you need more control on the execution, first you have to call
     1373    /// \ref init(), then you can add a source node with \ref addSource()
     1374    /// and perform the actual computation with \ref start().
     1375    /// This procedure can be repeated if there are nodes that have not
     1376    /// been reached.
    13791377
    13801378    /// @{
     
    13921390    }
    13931391
    1394     ///Adds a new source node.
    1395 
    1396     ///Adds a new source node to the set of nodes to be processed.
    1397     ///
    1398     ///\pre The stack must be empty. (Otherwise the algorithm gives
    1399     ///false results.)
    1400     ///
    1401     ///\warning Distances will be wrong (or at least strange) in case of
    1402     ///multiple sources.
     1392    /// \brief Adds a new source node.
     1393    ///
     1394    /// Adds a new source node to the set of nodes to be processed.
     1395    ///
     1396    /// \pre The stack must be empty. Otherwise the algorithm gives
     1397    /// wrong results. (One of the outgoing arcs of all the source nodes
     1398    /// except for the last one will not be visited and distances will
     1399    /// also be wrong.)
    14031400    void addSource(Node s)
    14041401    {
     
    15901587    ///
    15911588    /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1589    /// - the %DFS tree (forest),
     1590    /// - the distance of each node from the root(s) in the %DFS tree.
    15941591    ///
    15951592    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16161613
    16171614    /// \name Query Functions
    1618     /// The result of the %DFS algorithm can be obtained using these
     1615    /// The results of the DFS algorithm can be obtained using these
    16191616    /// functions.\n
    1620     /// Either \ref lemon::DfsVisit::run() "run()" or
    1621     /// \ref lemon::DfsVisit::start() "start()" must be called before
    1622     /// using them.
     1617    /// Either \ref run(Node) "run()" or \ref start() should be called
     1618    /// before using them.
     1619
    16231620    ///@{
    16241621
    1625     /// \brief Checks if a node is reachable from the root(s).
    1626     ///
    1627     /// Returns \c true if \c v is reachable from the root(s).
    1628     /// \pre Either \ref run() or \ref start()
     1622    /// \brief Checks if a node is reached from the root(s).
     1623    ///
     1624    /// Returns \c true if \c v is reached from the root(s).
     1625    ///
     1626    /// \pre Either \ref run(Node) "run()" or \ref init()
    16291627    /// must be called before using this function.
    16301628    bool reached(Node v) { return (*_reached)[v]; }
  • lemon/dijkstra.h

    r313 r405  
    203203  ///
    204204  ///\tparam GR The type of the digraph the algorithm runs on.
    205   ///The default value is \ref ListDigraph.
    206   ///The value of GR is not used directly by \ref Dijkstra, it is only
    207   ///passed to \ref DijkstraDefaultTraits.
    208   ///\tparam LM A readable arc map that determines the lengths of the
    209   ///arcs. It is read once for each arc, so the map may involve in
     205  ///The default type is \ref ListDigraph.
     206  ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
     207  ///the lengths of the arcs.
     208  ///It is read once for each arc, so the map may involve in
    210209  ///relatively time consuming process to compute the arc lengths if
    211210  ///it is necessary. The default map type is \ref
    212   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    213   ///The value of LM is not used directly by \ref Dijkstra, it is only
    214   ///passed to \ref DijkstraDefaultTraits.
    215   ///\tparam TR Traits class to set various data types used by the algorithm.
    216   ///The default traits class is \ref DijkstraDefaultTraits
    217   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
    218   ///for the documentation of a Dijkstra traits class.
     211  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    219212#ifdef DOXYGEN
    220213  template <typename GR, typename LM, typename TR>
     
    250243    typedef typename TR::OperationTraits OperationTraits;
    251244
    252     ///The traits class.
     245    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    253246    typedef TR Traits;
    254247
     
    332325    ///\ref named-templ-param "Named parameter" for setting
    333326    ///PredMap type.
     327    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    334328    template <class T>
    335329    struct SetPredMap
     
    352346    ///\ref named-templ-param "Named parameter" for setting
    353347    ///DistMap type.
     348    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    354349    template <class T>
    355350    struct SetDistMap
     
    372367    ///\ref named-templ-param "Named parameter" for setting
    373368    ///ProcessedMap type.
     369    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    374370    template <class T>
    375371    struct SetProcessedMap
     
    412408    };
    413409    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference type
     410    ///heap and cross reference types
    415411    ///
    416412    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference type.
     413    ///reference types. If this named parameter is used, then external
     414    ///heap and cross reference objects must be passed to the algorithm
     415    ///using the \ref heap() function before calling \ref run(Node) "run()"
     416    ///or \ref init().
     417    ///\sa SetStandardHeap
    418418    template <class H, class CR = typename Digraph::template NodeMap<int> >
    419419    struct SetHeap
     
    435435    };
    436436    ///\brief \ref named-templ-param "Named parameter" for setting
    437     ///heap and cross reference type with automatic allocation
     437    ///heap and cross reference types with automatic allocation
    438438    ///
    439439    ///\ref named-templ-param "Named parameter" for setting heap and cross
    440     ///reference type. It can allocate the heap and the cross reference
    441     ///object if the cross reference's constructor waits for the digraph as
    442     ///parameter and the heap's constructor waits for the cross reference.
     440    ///reference types with automatic allocation.
     441    ///They should have standard constructor interfaces to be able to
     442    ///automatically created by the algorithm (i.e. the digraph should be
     443    ///passed to the constructor of the cross reference and the cross
     444    ///reference should be passed to the constructor of the heap).
     445    ///However external heap and cross reference objects could also be
     446    ///passed to the algorithm using the \ref heap() function before
     447    ///calling \ref run(Node) "run()" or \ref init().
     448    ///\sa SetHeap
    443449    template <class H, class CR = typename Digraph::template NodeMap<int> >
    444450    struct SetStandardHeap
     
    510516
    511517    ///Sets the map that stores the predecessor arcs.
    512     ///If you don't use this function before calling \ref run(),
    513     ///it will allocate one. The destructor deallocates this
    514     ///automatically allocated map, of course.
     518    ///If you don't use this function before calling \ref run(Node) "run()"
     519    ///or \ref init(), an instance will be allocated automatically.
     520    ///The destructor deallocates this automatically allocated map,
     521    ///of course.
    515522    ///\return <tt> (*this) </tt>
    516523    Dijkstra &predMap(PredMap &m)
     
    527534
    528535    ///Sets the map that indicates which nodes are processed.
    529     ///If you don't use this function before calling \ref run(),
    530     ///it will allocate one. The destructor deallocates this
    531     ///automatically allocated map, of course.
     536    ///If you don't use this function before calling \ref run(Node) "run()"
     537    ///or \ref init(), an instance will be allocated automatically.
     538    ///The destructor deallocates this automatically allocated map,
     539    ///of course.
    532540    ///\return <tt> (*this) </tt>
    533541    Dijkstra &processedMap(ProcessedMap &m)
     
    545553    ///Sets the map that stores the distances of the nodes calculated by the
    546554    ///algorithm.
    547     ///If you don't use this function before calling \ref run(),
    548     ///it will allocate one. The destructor deallocates this
    549     ///automatically allocated map, of course.
     555    ///If you don't use this function before calling \ref run(Node) "run()"
     556    ///or \ref init(), an instance will be allocated automatically.
     557    ///The destructor deallocates this automatically allocated map,
     558    ///of course.
    550559    ///\return <tt> (*this) </tt>
    551560    Dijkstra &distMap(DistMap &m)
     
    562571
    563572    ///Sets the heap and the cross reference used by algorithm.
    564     ///If you don't use this function before calling \ref run(),
    565     ///it will allocate one. The destructor deallocates this
    566     ///automatically allocated heap and cross reference, of course.
     573    ///If you don't use this function before calling \ref run(Node) "run()"
     574    ///or \ref init(), heap and cross reference instances will be
     575    ///allocated automatically.
     576    ///The destructor deallocates these automatically allocated objects,
     577    ///of course.
    567578    ///\return <tt> (*this) </tt>
    568579    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
     
    591602  public:
    592603
    593     ///\name Execution control
    594     ///The simplest way to execute the algorithm is to use one of the
    595     ///member functions called \ref lemon::Dijkstra::run() "run()".
    596     ///\n
    597     ///If you need more control on the execution, first you must call
    598     ///\ref lemon::Dijkstra::init() "init()", then you can add several
    599     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
    600     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
    601     ///actual path computation.
     604    ///\name Execution Control
     605    ///The simplest way to execute the %Dijkstra algorithm is to use
     606    ///one of the member functions called \ref run(Node) "run()".\n
     607    ///If you need more control on the execution, first you have to call
     608    ///\ref init(), then you can add several source nodes with
     609    ///\ref addSource(). Finally the actual path computation can be
     610    ///performed with one of the \ref start() functions.
    602611
    603612    ///@{
    604613
     614    ///\brief Initializes the internal data structures.
     615    ///
    605616    ///Initializes the internal data structures.
    606 
    607     ///Initializes the internal data structures.
    608     ///
    609617    void init()
    610618    {
     
    682690    }
    683691
    684     ///\brief Returns \c false if there are nodes
    685     ///to be processed.
    686     ///
    687     ///Returns \c false if there are nodes
    688     ///to be processed in the priority heap.
     692    ///Returns \c false if there are nodes to be processed.
     693
     694    ///Returns \c false if there are nodes to be processed
     695    ///in the priority heap.
    689696    bool emptyQueue() const { return _heap->empty(); }
    690697
    691     ///Returns the number of the nodes to be processed in the priority heap
    692 
    693     ///Returns the number of the nodes to be processed in the priority heap.
    694     ///
     698    ///Returns the number of the nodes to be processed.
     699
     700    ///Returns the number of the nodes to be processed
     701    ///in the priority heap.
    695702    int queueSize() const { return _heap->size(); }
    696703
     
    813820
    814821    ///\name Query Functions
    815     ///The result of the %Dijkstra algorithm can be obtained using these
     822    ///The results of the %Dijkstra algorithm can be obtained using these
    816823    ///functions.\n
    817     ///Either \ref lemon::Dijkstra::run() "run()" or
    818     ///\ref lemon::Dijkstra::start() "start()" must be called before
    819     ///using them.
     824    ///Either \ref run(Node) "run()" or \ref start() should be called
     825    ///before using them.
    820826
    821827    ///@{
     
    825831    ///Returns the shortest path to a node.
    826832    ///
    827     ///\warning \c t should be reachable from the root(s).
    828     ///
    829     ///\pre Either \ref run() or \ref start() must be called before
    830     ///using this function.
     833    ///\warning \c t should be reached from the root(s).
     834    ///
     835    ///\pre Either \ref run(Node) "run()" or \ref init()
     836    ///must be called before using this function.
    831837    Path path(Node t) const { return Path(*G, *_pred, t); }
    832838
     
    835841    ///Returns the distance of a node from the root(s).
    836842    ///
    837     ///\warning If node \c v is not reachable from the root(s), then
     843    ///\warning If node \c v is not reached from the root(s), then
    838844    ///the return value of this function is undefined.
    839845    ///
    840     ///\pre Either \ref run() or \ref start() must be called before
    841     ///using this function.
     846    ///\pre Either \ref run(Node) "run()" or \ref init()
     847    ///must be called before using this function.
    842848    Value dist(Node v) const { return (*_dist)[v]; }
    843849
     
    846852    ///This function returns the 'previous arc' of the shortest path
    847853    ///tree for the node \c v, i.e. it returns the last arc of a
    848     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    849     ///is not reachable from the root(s) or if \c v is a root.
     854    ///shortest path from a root to \c v. It is \c INVALID if \c v
     855    ///is not reached from the root(s) or if \c v is a root.
    850856    ///
    851857    ///The shortest path tree used here is equal to the shortest path
    852858    ///tree used in \ref predNode().
    853859    ///
    854     ///\pre Either \ref run() or \ref start() must be called before
    855     ///using this function.
     860    ///\pre Either \ref run(Node) "run()" or \ref init()
     861    ///must be called before using this function.
    856862    Arc predArc(Node v) const { return (*_pred)[v]; }
    857863
     
    860866    ///This function returns the 'previous node' of the shortest path
    861867    ///tree for the node \c v, i.e. it returns the last but one node
    862     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    863     ///if \c v is not reachable from the root(s) or if \c v is a root.
     868    ///from a shortest path from a root to \c v. It is \c INVALID
     869    ///if \c v is not reached from the root(s) or if \c v is a root.
    864870    ///
    865871    ///The shortest path tree used here is equal to the shortest path
    866872    ///tree used in \ref predArc().
    867873    ///
    868     ///\pre Either \ref run() or \ref start() must be called before
    869     ///using this function.
     874    ///\pre Either \ref run(Node) "run()" or \ref init()
     875    ///must be called before using this function.
    870876    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    871877                                  G->source((*_pred)[v]); }
     
    877883    ///of the nodes calculated by the algorithm.
    878884    ///
    879     ///\pre Either \ref run() or \ref init()
     885    ///\pre Either \ref run(Node) "run()" or \ref init()
    880886    ///must be called before using this function.
    881887    const DistMap &distMap() const { return *_dist;}
     
    887893    ///arcs, which form the shortest path tree.
    888894    ///
    889     ///\pre Either \ref run() or \ref init()
     895    ///\pre Either \ref run(Node) "run()" or \ref init()
    890896    ///must be called before using this function.
    891897    const PredMap &predMap() const { return *_pred;}
    892898
    893     ///Checks if a node is reachable from the root(s).
    894 
    895     ///Returns \c true if \c v is reachable from the root(s).
    896     ///\pre Either \ref run() or \ref start()
     899    ///Checks if a node is reached from the root(s).
     900
     901    ///Returns \c true if \c v is reached from the root(s).
     902    ///
     903    ///\pre Either \ref run(Node) "run()" or \ref init()
    897904    ///must be called before using this function.
    898905    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     
    903910    ///Returns \c true if \c v is processed, i.e. the shortest
    904911    ///path to \c v has already found.
    905     ///\pre Either \ref run() or \ref init()
     912    ///
     913    ///\pre Either \ref run(Node) "run()" or \ref init()
    906914    ///must be called before using this function.
    907915    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    912920    ///Returns the current distance of a node from the root(s).
    913921    ///It may be decreased in the following processes.
    914     ///\pre Either \ref run() or \ref init()
     922    ///
     923    ///\pre Either \ref run(Node) "run()" or \ref init()
    915924    ///must be called before using this function and
    916925    ///node \c v must be reached but not necessarily processed.
     
    10951104  /// This auxiliary class is created to implement the
    10961105  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1097   /// It does not have own \ref run() method, it uses the functions
    1098   /// and features of the plain \ref Dijkstra.
     1106  /// It does not have own \ref run(Node) "run()" method, it uses the
     1107  /// functions and features of the plain \ref Dijkstra.
    10991108  ///
    11001109  /// This class should only be used through the \ref dijkstra() function,
     
    12911300  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12921301  ///\endcode
    1293   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1302  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
    12941303  ///to the end of the parameter list.
    12951304  ///\sa DijkstraWizard
Note: See TracChangeset for help on using the changeset viewer.