COIN-OR::LEMON - Graph Library

Ignore:
Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r421 r341  
    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.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8584    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8685    ///Instantiates a ReachedMap.
     
    120119  ///
    121120  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default type is \ref ListDigraph.
     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.
    123128#ifdef DOXYGEN
    124129  template <typename GR,
     
    146151    typedef PredMapPath<Digraph, PredMap> Path;
    147152
    148     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     153    ///The traits class.
    149154    typedef TR Traits;
    150155
     
    208213    typedef Bfs Create;
    209214
    210     ///\name Named Template Parameters
     215    ///\name Named template parameters
    211216
    212217    ///@{
     
    226231    ///\ref named-templ-param "Named parameter" for setting
    227232    ///PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    229233    template <class T>
    230234    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    246250    ///\ref named-templ-param "Named parameter" for setting
    247251    ///DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    249252    template <class T>
    250253    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266269    ///\ref named-templ-param "Named parameter" for setting
    267270    ///ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269271    template <class T>
    270272    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    286288    ///\ref named-templ-param "Named parameter" for setting
    287289    ///ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    289290    template <class T>
    290291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    339340
    340341    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    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(Node) "run()"
    360     ///or \ref init(), an instance will be allocated automatically.
    361     ///The destructor deallocates this automatically allocated map,
    362     ///of course.
     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.
    363362    ///\return <tt> (*this) </tt>
    364363    Bfs &reachedMap(ReachedMap &m)
     
    375374
    376375    ///Sets the map that indicates which nodes are processed.
    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.
     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.
    381379    ///\return <tt> (*this) </tt>
    382380    Bfs &processedMap(ProcessedMap &m)
     
    394392    ///Sets the map that stores the distances of the nodes calculated by
    395393    ///the algorithm.
    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.
     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.
    400397    ///\return <tt> (*this) </tt>
    401398    Bfs &distMap(DistMap &m)
     
    411408  public:
    412409
    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.
     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.
    420419
    421420    ///@{
    422421
    423     ///\brief Initializes the internal data structures.
    424     ///
    425422    ///Initializes the internal data structures.
     423
     424    ///Initializes the internal data structures.
     425    ///
    426426    void init()
    427427    {
     
    557557    }
    558558
    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.
     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.
    563564    bool emptyQueue() const { return _queue_tail==_queue_head; }
    564565
    565566    ///Returns the number of the nodes to be processed.
    566567
    567     ///Returns the number of the nodes to be processed
    568     ///in the queue.
     568    ///Returns the number of the nodes to be processed in the queue.
    569569    int queueSize() const { return _queue_head-_queue_tail; }
    570570
     
    731731
    732732    ///\name Query Functions
    733     ///The results of the BFS algorithm can be obtained using these
     733    ///The result of the %BFS algorithm can be obtained using these
    734734    ///functions.\n
    735     ///Either \ref run(Node) "run()" or \ref start() should be called
    736     ///before using them.
     735    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     736    ///"start()" must be called before using them.
    737737
    738738    ///@{
     
    742742    ///Returns the shortest path to a node.
    743743    ///
    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.
     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.
    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 reached from the root(s), then
     754    ///\warning If node \c v is not reachable from the root(s), then
    755755    ///the return value of this function is undefined.
    756756    ///
    757     ///\pre Either \ref run(Node) "run()" or \ref init()
    758     ///must be called before using this function.
     757    ///\pre Either \ref run() or \ref start() must be called before
     758    ///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 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.
     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.
    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(Node) "run()" or \ref init()
    772     ///must be called before using this function.
     771    ///\pre Either \ref run() or \ref start() must be called before
     772    ///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 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.
     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.
    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(Node) "run()" or \ref init()
    786     ///must be called before using this function.
     785    ///\pre Either \ref run() or \ref start() must be called before
     786    ///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(Node) "run()" or \ref init()
     796    ///\pre Either \ref 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(Node) "run()" or \ref init()
     806    ///\pre Either \ref 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 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()
     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()
    815814    ///must be called before using this function.
    816815    bool reached(Node v) const { return (*_reached)[v]; }
     
    958957  /// This auxiliary class is created to implement the
    959958  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    960   /// It does not have own \ref run(Node) "run()" method, it uses the
    961   /// functions and features of the plain \ref Bfs.
     959  /// It does not have own \ref run() method, it uses the functions
     960  /// and features of the plain \ref Bfs.
    962961  ///
    963962  /// This class should only be used through the \ref bfs() function,
     
    11791178  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801179  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
     1180  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
    11821181  ///to the end of the parameter list.
    11831182  ///\sa BfsWizard
     
    13651364    typedef BfsVisit Create;
    13661365
    1367     /// \name Named Template Parameters
     1366    /// \name Named template parameters
    13681367
    13691368    ///@{
     
    14071406    ///
    14081407    /// Sets the map that indicates which nodes are reached.
    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.
     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.
    14131411    /// \return <tt> (*this) </tt>
    14141412    BfsVisit &reachedMap(ReachedMap &m) {
     
    14231421  public:
    14241422
    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.
     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.
    14321433
    14331434    /// @{
     
    17291730
    17301731    /// \name Query Functions
    1731     /// The results of the BFS algorithm can be obtained using these
     1732    /// The result of the %BFS algorithm can be obtained using these
    17321733    /// functions.\n
    1733     /// Either \ref run(Node) "run()" or \ref start() should be called
    1734     /// before using them.
    1735 
     1734    /// Either \ref lemon::BfsVisit::run() "run()" or
     1735    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1736    /// using them.
    17361737    ///@{
    17371738
    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()
     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()
    17431743    /// must be called before using this function.
    17441744    bool reached(Node v) { return (*_reached)[v]; }
  • lemon/dfs.h

    r421 r319  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default type is \ref ListDigraph.
     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.
    123129#ifdef DOXYGEN
    124130  template <typename GR,
     
    146152    typedef PredMapPath<Digraph, PredMap> Path;
    147153
    148     ///The \ref DfsDefaultTraits "traits class" of the algorithm.
     154    ///The traits class.
    149155    typedef TR Traits;
    150156
     
    225231    ///\ref named-templ-param "Named parameter" for setting
    226232    ///PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    228233    template <class T>
    229234    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    245250    ///\ref named-templ-param "Named parameter" for setting
    246251    ///DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    248252    template <class T>
    249253    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265269    ///\ref named-templ-param "Named parameter" for setting
    266270    ///ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268271    template <class T>
    269272    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    285288    ///\ref named-templ-param "Named parameter" for setting
    286289    ///ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    288290    template <class T>
    289291    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    337339
    338340    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    343344    ///\return <tt> (*this) </tt>
    344345    Dfs &predMap(PredMap &m)
     
    355356
    356357    ///Sets the map that indicates which nodes are reached.
    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.
     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.
    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(Node) "run()"
    376     ///or \ref init(), an instance will be allocated automatically.
    377     ///The destructor deallocates this automatically allocated map,
    378     ///of course.
     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.
    379378    ///\return <tt> (*this) </tt>
    380379    Dfs &processedMap(ProcessedMap &m)
     
    392391    ///Sets the map that stores the distances of the nodes calculated by
    393392    ///the algorithm.
    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.
     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.
    398396    ///\return <tt> (*this) </tt>
    399397    Dfs &distMap(DistMap &m)
     
    409407  public:
    410408
    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.
     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.
    419418
    420419    ///@{
    421420
    422     ///\brief Initializes the internal data structures.
    423     ///
    424421    ///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     ///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.)
     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.
    445446    void addSource(Node s)
    446447    {
     
    506507    }
    507508
    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).
     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).
    512514    bool emptyQueue() const { return _stack_head<0; }
    513515
    514516    ///Returns the number of the nodes to be processed.
    515517
    516     ///Returns the number of the nodes to be processed
    517     ///in the queue (stack).
     518    ///Returns the number of the nodes to be processed in the queue (stack).
    518519    int queueSize() const { return _stack_head+1; }
    519520
     
    637638    ///
    638639    ///The algorithm computes
    639     ///- the %DFS tree (forest),
    640     ///- the distance of each node from the root(s) in the %DFS tree.
     640    ///- the %DFS tree,
     641    ///- the distance of each node from the root in the %DFS tree.
    641642    ///
    642643    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    663664
    664665    ///\name Query Functions
    665     ///The results of the DFS algorithm can be obtained using these
     666    ///The result of the %DFS algorithm can be obtained using these
    666667    ///functions.\n
    667     ///Either \ref run(Node) "run()" or \ref start() should be called
    668     ///before using them.
     668    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
     669    ///"start()" must be called before using them.
    669670
    670671    ///@{
     
    674675    ///Returns the DFS path to a node.
    675676    ///
    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.
     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.
    680681    Path path(Node t) const { return Path(*G, *_pred, t); }
    681682
    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
     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
    687688    ///the return value of this function is undefined.
    688689    ///
    689     ///\pre Either \ref run(Node) "run()" or \ref init()
    690     ///must be called before using this function.
     690    ///\pre Either \ref run() or \ref start() must be called before
     691    ///using this function.
    691692    int dist(Node v) const { return (*_dist)[v]; }
    692693
     
    694695
    695696    ///This function returns the 'previous arc' of the %DFS tree for the
    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.
     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.
    699700    ///
    700701    ///The %DFS tree used here is equal to the %DFS tree used in
    701702    ///\ref predNode().
    702703    ///
    703     ///\pre Either \ref run(Node) "run()" or \ref init()
    704     ///must be called before using this function.
     704    ///\pre Either \ref run() or \ref start() must be called before using
     705    ///this function.
    705706    Arc predArc(Node v) const { return (*_pred)[v];}
    706707
     
    709710    ///This function returns the 'previous node' of the %DFS
    710711    ///tree for the node \c v, i.e. it returns the last but one node
    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.
     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.
    713714    ///
    714715    ///The %DFS tree used here is equal to the %DFS tree used in
    715716    ///\ref predArc().
    716717    ///
    717     ///\pre Either \ref run(Node) "run()" or \ref init()
    718     ///must be called before using this function.
     718    ///\pre Either \ref run() or \ref start() must be called before
     719    ///using this function.
    719720    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    720721                                  G->source((*_pred)[v]); }
     
    726727    ///distances of the nodes calculated by the algorithm.
    727728    ///
    728     ///\pre Either \ref run(Node) "run()" or \ref init()
     729    ///\pre Either \ref run() or \ref init()
    729730    ///must be called before using this function.
    730731    const DistMap &distMap() const { return *_dist;}
     
    736737    ///arcs, which form the DFS tree.
    737738    ///
    738     ///\pre Either \ref run(Node) "run()" or \ref init()
     739    ///\pre Either \ref run() or \ref init()
    739740    ///must be called before using this function.
    740741    const PredMap &predMap() const { return *_pred;}
    741742
    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()
     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()
    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(Node) "run()" method, it uses the
    893   /// functions and features of the plain \ref Dfs.
     892  /// It does not have own \ref run() method, it uses the functions
     893  /// 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   ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
     1113
     1114  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
    11141115  ///to the end of the parameter list.
    11151116  ///\sa DfsWizard
     
    13091310    typedef DfsVisit Create;
    13101311
    1311     /// \name Named Template Parameters
     1312    /// \name Named template parameters
    13121313
    13131314    ///@{
     
    13511352    ///
    13521353    /// Sets the map that indicates which nodes are reached.
    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.
     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.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671367  public:
    13681368
    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.
     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.
    13771379
    13781380    /// @{
     
    13901392    }
    13911393
    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.)
     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.
    14001403    void addSource(Node s)
    14011404    {
     
    15871590    ///
    15881591    /// The algorithm computes
    1589     /// - the %DFS tree (forest),
    1590     /// - the distance of each node from the root(s) in the %DFS tree.
     1592    /// - the %DFS tree,
     1593    /// - the distance of each node from the root in the %DFS tree.
    15911594    ///
    15921595    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16131616
    16141617    /// \name Query Functions
    1615     /// The results of the DFS algorithm can be obtained using these
     1618    /// The result of the %DFS algorithm can be obtained using these
    16161619    /// functions.\n
    1617     /// Either \ref run(Node) "run()" or \ref start() should be called
    1618     /// before using them.
    1619 
     1620    /// Either \ref lemon::DfsVisit::run() "run()" or
     1621    /// \ref lemon::DfsVisit::start() "start()" must be called before
     1622    /// using them.
    16201623    ///@{
    16211624
    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()
     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()
    16271629    /// must be called before using this function.
    16281630    bool reached(Node v) { return (*_reached)[v]; }
  • lemon/dijkstra.h

    r424 r412  
    180180  ///
    181181  ///\tparam GR The type of the digraph the algorithm runs on.
    182   ///The default type is \ref ListDigraph.
    183   ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
    184   ///the lengths of the arcs.
    185   ///It is read once for each arc, so the map may involve in
     182  ///The default value is \ref ListDigraph.
     183  ///The value of GR is not used directly by \ref Dijkstra, it is only
     184  ///passed to \ref DijkstraDefaultTraits.
     185  ///\tparam LM A readable arc map that determines the lengths of the
     186  ///arcs. It is read once for each arc, so the map may involve in
    186187  ///relatively time consuming process to compute the arc lengths if
    187188  ///it is necessary. The default map type is \ref
    188   ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
     189  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     190  ///The value of LM is not used directly by \ref Dijkstra, it is only
     191  ///passed to \ref DijkstraDefaultTraits.
     192  ///\tparam TR Traits class to set various data types used by the algorithm.
     193  ///The default traits class is \ref DijkstraDefaultTraits
     194  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
     195  ///for the documentation of a Dijkstra traits class.
    189196#ifdef DOXYGEN
    190197  template <typename GR, typename LM, typename TR>
     
    220227    typedef typename TR::OperationTraits OperationTraits;
    221228
    222     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
     229    ///The traits class.
    223230    typedef TR Traits;
    224231
     
    302309    ///\ref named-templ-param "Named parameter" for setting
    303310    ///PredMap type.
    304     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    305311    template <class T>
    306312    struct SetPredMap
     
    323329    ///\ref named-templ-param "Named parameter" for setting
    324330    ///DistMap type.
    325     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    326331    template <class T>
    327332    struct SetDistMap
     
    344349    ///\ref named-templ-param "Named parameter" for setting
    345350    ///ProcessedMap type.
    346     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    347351    template <class T>
    348352    struct SetProcessedMap
     
    385389    };
    386390    ///\brief \ref named-templ-param "Named parameter" for setting
    387     ///heap and cross reference types
     391    ///heap and cross reference type
    388392    ///
    389393    ///\ref named-templ-param "Named parameter" for setting heap and cross
    390     ///reference types. If this named parameter is used, then external
    391     ///heap and cross reference objects must be passed to the algorithm
    392     ///using the \ref heap() function before calling \ref run(Node) "run()"
    393     ///or \ref init().
    394     ///\sa SetStandardHeap
     394    ///reference type.
    395395    template <class H, class CR = typename Digraph::template NodeMap<int> >
    396396    struct SetHeap
     
    412412    };
    413413    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference types with automatic allocation
     414    ///heap and cross reference type with automatic allocation
    415415    ///
    416416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference types with automatic allocation.
    418     ///They should have standard constructor interfaces to be able to
    419     ///automatically created by the algorithm (i.e. the digraph should be
    420     ///passed to the constructor of the cross reference and the cross
    421     ///reference should be passed to the constructor of the heap).
    422     ///However external heap and cross reference objects could also be
    423     ///passed to the algorithm using the \ref heap() function before
    424     ///calling \ref run(Node) "run()" or \ref init().
    425     ///\sa SetHeap
     417    ///reference type. It can allocate the heap and the cross reference
     418    ///object if the cross reference's constructor waits for the digraph as
     419    ///parameter and the heap's constructor waits for the cross reference.
    426420    template <class H, class CR = typename Digraph::template NodeMap<int> >
    427421    struct SetStandardHeap
     
    493487
    494488    ///Sets the map that stores the predecessor arcs.
    495     ///If you don't use this function before calling \ref run(Node) "run()"
    496     ///or \ref init(), an instance will be allocated automatically.
    497     ///The destructor deallocates this automatically allocated map,
    498     ///of course.
     489    ///If you don't use this function before calling \ref run(),
     490    ///it will allocate one. The destructor deallocates this
     491    ///automatically allocated map, of course.
    499492    ///\return <tt> (*this) </tt>
    500493    Dijkstra &predMap(PredMap &m)
     
    511504
    512505    ///Sets the map that indicates which nodes are processed.
    513     ///If you don't use this function before calling \ref run(Node) "run()"
    514     ///or \ref init(), an instance will be allocated automatically.
    515     ///The destructor deallocates this automatically allocated map,
    516     ///of course.
     506    ///If you don't use this function before calling \ref run(),
     507    ///it will allocate one. The destructor deallocates this
     508    ///automatically allocated map, of course.
    517509    ///\return <tt> (*this) </tt>
    518510    Dijkstra &processedMap(ProcessedMap &m)
     
    530522    ///Sets the map that stores the distances of the nodes calculated by the
    531523    ///algorithm.
    532     ///If you don't use this function before calling \ref run(Node) "run()"
    533     ///or \ref init(), an instance will be allocated automatically.
    534     ///The destructor deallocates this automatically allocated map,
    535     ///of course.
     524    ///If you don't use this function before calling \ref run(),
     525    ///it will allocate one. The destructor deallocates this
     526    ///automatically allocated map, of course.
    536527    ///\return <tt> (*this) </tt>
    537528    Dijkstra &distMap(DistMap &m)
     
    548539
    549540    ///Sets the heap and the cross reference used by algorithm.
    550     ///If you don't use this function before calling \ref run(Node) "run()"
    551     ///or \ref init(), heap and cross reference instances will be
    552     ///allocated automatically.
    553     ///The destructor deallocates these automatically allocated objects,
    554     ///of course.
     541    ///If you don't use this function before calling \ref run(),
     542    ///it will allocate one. The destructor deallocates this
     543    ///automatically allocated heap and cross reference, of course.
    555544    ///\return <tt> (*this) </tt>
    556545    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
     
    579568  public:
    580569
    581     ///\name Execution Control
    582     ///The simplest way to execute the %Dijkstra algorithm is to use
    583     ///one of the member functions called \ref run(Node) "run()".\n
    584     ///If you need more control on the execution, first you have to call
    585     ///\ref init(), then you can add several source nodes with
    586     ///\ref addSource(). Finally the actual path computation can be
    587     ///performed with one of the \ref start() functions.
     570    ///\name Execution control
     571    ///The simplest way to execute the algorithm is to use one of the
     572    ///member functions called \ref lemon::Dijkstra::run() "run()".
     573    ///\n
     574    ///If you need more control on the execution, first you must call
     575    ///\ref lemon::Dijkstra::init() "init()", then you can add several
     576    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
     577    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
     578    ///actual path computation.
    588579
    589580    ///@{
    590581
    591     ///\brief Initializes the internal data structures.
    592     ///
    593582    ///Initializes the internal data structures.
     583
     584    ///Initializes the internal data structures.
     585    ///
    594586    void init()
    595587    {
     
    667659    }
    668660
    669     ///Returns \c false if there are nodes to be processed.
    670 
    671     ///Returns \c false if there are nodes to be processed
    672     ///in the priority heap.
     661    ///\brief Returns \c false if there are nodes
     662    ///to be processed.
     663    ///
     664    ///Returns \c false if there are nodes
     665    ///to be processed in the priority heap.
    673666    bool emptyQueue() const { return _heap->empty(); }
    674667
    675     ///Returns the number of the nodes to be processed.
    676 
    677     ///Returns the number of the nodes to be processed
    678     ///in the priority heap.
     668    ///Returns the number of the nodes to be processed in the priority heap
     669
     670    ///Returns the number of the nodes to be processed in the priority heap.
     671    ///
    679672    int queueSize() const { return _heap->size(); }
    680673
     
    797790
    798791    ///\name Query Functions
    799     ///The results of the %Dijkstra algorithm can be obtained using these
     792    ///The result of the %Dijkstra algorithm can be obtained using these
    800793    ///functions.\n
    801     ///Either \ref run(Node) "run()" or \ref start() should be called
    802     ///before using them.
     794    ///Either \ref lemon::Dijkstra::run() "run()" or
     795    ///\ref lemon::Dijkstra::start() "start()" must be called before
     796    ///using them.
    803797
    804798    ///@{
     
    808802    ///Returns the shortest path to a node.
    809803    ///
    810     ///\warning \c t should be reached from the root(s).
    811     ///
    812     ///\pre Either \ref run(Node) "run()" or \ref init()
    813     ///must be called before using this function.
     804    ///\warning \c t should be reachable from the root(s).
     805    ///
     806    ///\pre Either \ref run() or \ref start() must be called before
     807    ///using this function.
    814808    Path path(Node t) const { return Path(*G, *_pred, t); }
    815809
     
    818812    ///Returns the distance of a node from the root(s).
    819813    ///
    820     ///\warning If node \c v is not reached from the root(s), then
     814    ///\warning If node \c v is not reachable from the root(s), then
    821815    ///the return value of this function is undefined.
    822816    ///
    823     ///\pre Either \ref run(Node) "run()" or \ref init()
    824     ///must be called before using this function.
     817    ///\pre Either \ref run() or \ref start() must be called before
     818    ///using this function.
    825819    Value dist(Node v) const { return (*_dist)[v]; }
    826820
     
    829823    ///This function returns the 'previous arc' of the shortest path
    830824    ///tree for the node \c v, i.e. it returns the last arc of a
    831     ///shortest path from a root to \c v. It is \c INVALID if \c v
    832     ///is not reached from the root(s) or if \c v is a root.
     825    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     826    ///is not reachable from the root(s) or if \c v is a root.
    833827    ///
    834828    ///The shortest path tree used here is equal to the shortest path
    835829    ///tree used in \ref predNode().
    836830    ///
    837     ///\pre Either \ref run(Node) "run()" or \ref init()
    838     ///must be called before using this function.
     831    ///\pre Either \ref run() or \ref start() must be called before
     832    ///using this function.
    839833    Arc predArc(Node v) const { return (*_pred)[v]; }
    840834
     
    843837    ///This function returns the 'previous node' of the shortest path
    844838    ///tree for the node \c v, i.e. it returns the last but one node
    845     ///from a shortest path from a root to \c v. It is \c INVALID
    846     ///if \c v is not reached from the root(s) or if \c v is a root.
     839    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     840    ///if \c v is not reachable from the root(s) or if \c v is a root.
    847841    ///
    848842    ///The shortest path tree used here is equal to the shortest path
    849843    ///tree used in \ref predArc().
    850844    ///
    851     ///\pre Either \ref run(Node) "run()" or \ref init()
    852     ///must be called before using this function.
     845    ///\pre Either \ref run() or \ref start() must be called before
     846    ///using this function.
    853847    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    854848                                  G->source((*_pred)[v]); }
     
    860854    ///of the nodes calculated by the algorithm.
    861855    ///
    862     ///\pre Either \ref run(Node) "run()" or \ref init()
     856    ///\pre Either \ref run() or \ref init()
    863857    ///must be called before using this function.
    864858    const DistMap &distMap() const { return *_dist;}
     
    870864    ///arcs, which form the shortest path tree.
    871865    ///
    872     ///\pre Either \ref run(Node) "run()" or \ref init()
     866    ///\pre Either \ref run() or \ref init()
    873867    ///must be called before using this function.
    874868    const PredMap &predMap() const { return *_pred;}
    875869
    876     ///Checks if a node is reached from the root(s).
    877 
    878     ///Returns \c true if \c v is reached from the root(s).
    879     ///
    880     ///\pre Either \ref run(Node) "run()" or \ref init()
     870    ///Checks if a node is reachable from the root(s).
     871
     872    ///Returns \c true if \c v is reachable from the root(s).
     873    ///\pre Either \ref run() or \ref start()
    881874    ///must be called before using this function.
    882875    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     
    887880    ///Returns \c true if \c v is processed, i.e. the shortest
    888881    ///path to \c v has already found.
    889     ///
    890     ///\pre Either \ref run(Node) "run()" or \ref init()
     882    ///\pre Either \ref run() or \ref init()
    891883    ///must be called before using this function.
    892884    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    897889    ///Returns the current distance of a node from the root(s).
    898890    ///It may be decreased in the following processes.
    899     ///
    900     ///\pre Either \ref run(Node) "run()" or \ref init()
     891    ///\pre Either \ref run() or \ref init()
    901892    ///must be called before using this function and
    902893    ///node \c v must be reached but not necessarily processed.
     
    10811072  /// This auxiliary class is created to implement the
    10821073  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1083   /// It does not have own \ref run(Node) "run()" method, it uses the
    1084   /// functions and features of the plain \ref Dijkstra.
     1074  /// It does not have own \ref run() method, it uses the functions
     1075  /// and features of the plain \ref Dijkstra.
    10851076  ///
    10861077  /// This class should only be used through the \ref dijkstra() function,
     
    12771268  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12781269  ///\endcode
    1279   ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
     1270  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
    12801271  ///to the end of the parameter list.
    12811272  ///\sa DijkstraWizard
Note: See TracChangeset for help on using the changeset viewer.