COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [413:d8b87e9b90c3:412:7030149efed2] in lemon-1.2


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r406 r388  
    1717 */
    1818
    19 namespace lemon {
    20 
    2119/**
    2220@defgroup datas Data Structures
    … …  
    9189
    9290This group describes maps that are specifically designed to assign
    93 values to the nodes and arcs/edges of graphs.
    94 
    95 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    96 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     91values to the nodes and arcs of graphs.
    9792*/
    9893
    … …  
    105100maps from other maps.
    106101
    107 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    108103They can make arithmetic and logical operations between one or two maps
    109104(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    207202\brief Common graph search algorithms.
    208203
    209 This group describes the common graph search algorithms, namely
    210 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     204This group describes the common graph search algorithms like
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
    211206*/
    212207
    … …  
    216211\brief Algorithms for finding shortest paths.
    217212
    218 This group describes the algorithms for finding shortest paths in digraphs.
    219 
    220  - \ref Dijkstra algorithm for finding shortest paths from a source node
    221    when all arc lengths are non-negative.
    222  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    223    from a source node when arc lenghts can be either positive or negative,
    224    but the digraph should not contain directed cycles with negative total
    225    length.
    226  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    227    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    228    lenghts can be either positive or negative, but the digraph should
    229    not contain directed cycles with negative total length.
    230  - \ref Suurballe A successive shortest path algorithm for finding
    231    arc-disjoint paths between two nodes having minimum total length.
     213This group describes the algorithms for finding shortest paths in graphs.
    232214*/
    233215
    … …  
    240222feasible circulations.
    241223
    242 The \e maximum \e flow \e problem is to find a flow of maximum value between
    243 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    244 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    245 \f$s, t \in V\f$ source and target nodes.
    246 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
    247 following optimization problem.
    248 
    249 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    250 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    251     \qquad \forall v\in V\setminus\{s,t\} \f]
    252 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
     229
     230\f[ 0 \le f_a \le c_a \f]
     231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
     232\qquad \forall u \in V \setminus \{s,t\}\f]
     233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    253234
    254235LEMON contains several algorithms for solving maximum flow problems:
    255 - \ref EdmondsKarp Edmonds-Karp algorithm.
    256 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    257 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    258 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    259 
    260 In most cases the \ref Preflow "Preflow" algorithm provides the
    261 fastest method for computing a maximum flow. All implementations
    262 provides functions to also query the minimum cut, which is the dual
    263 problem of the maximum flow.
     236- \ref lemon::EdmondsKarp "Edmonds-Karp"
     237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
     238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
     239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
     240
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
    264245*/
    265246
    … …  
    272253This group describes the algorithms for finding minimum cost flows and
    273254circulations.
    274 
    275 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    276 minimum total cost from a set of supply nodes to a set of demand nodes
    277 in a network with capacity constraints and arc costs.
    278 Formally, let \f$G=(V,A)\f$ be a digraph,
    279 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    280 upper bounds for the flow values on the arcs,
    281 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    282 on the arcs, and
    283 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    284 of the nodes.
    285 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    286 the following optimization problem.
    287 
    288 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    289 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    290     supply(v) \qquad \forall v\in V \f]
    291 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    292 
    293 LEMON contains several algorithms for solving minimum cost flow problems:
    294  - \ref CycleCanceling Cycle-canceling algorithms.
    295  - \ref CapacityScaling Successive shortest path algorithm with optional
    296    capacity scaling.
    297  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    298    cost scaling.
    299  - \ref NetworkSimplex Primal network simplex algorithm with various
    300    pivot strategies.
    301255*/
    302256
    … …  
    309263This group describes the algorithms for finding minimum cut in graphs.
    310264
    311 The \e minimum \e cut \e problem is to find a non-empty and non-complete
    312 \f$X\f$ subset of the nodes with minimum overall capacity on
    313 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
    314 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     265The minimum cut problem is to find a non-empty and non-complete
     266\f$X\f$ subset of the vertices with minimum overall capacity on
     267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    315269cut is the \f$X\f$ solution of the next optimization problem:
    316270
    317271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    318     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    319273
    320274LEMON contains several algorithms related to minimum cut problems:
    321275
    322 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    323   in directed graphs.
    324 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    325   calculating minimum cut in undirected graphs.
    326 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
    327   all-pairs minimum cut in undirected graphs.
     276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
     277  in directed graphs
     278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
     279  calculate minimum cut in undirected graphs
     280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
     281  pairs minimum cut in undirected graphs
    328282
    329283If you want to find minimum cut just between two distinict nodes,
    330 see the \ref max_flow "maximum flow problem".
     284please see the \ref max_flow "Maximum Flow page".
    331285*/
    332286
    … …  
    367321graphs.  The matching problems in bipartite graphs are generally
    368322easier than in general graphs. The goal of the matching optimization
    369 can be finding maximum cardinality, maximum weight or minimum cost
     323can be the finding maximum cardinality, maximum weight or minimum cost
    370324matching. The search can be constrained to find perfect or
    371325maximum cardinality matching.
    372326
    373 The matching algorithms implemented in LEMON:
    374 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    375   for calculating maximum cardinality matching in bipartite graphs.
    376 - \ref PrBipartiteMatching Push-relabel algorithm
    377   for calculating maximum cardinality matching in bipartite graphs.
    378 - \ref MaxWeightedBipartiteMatching
    379   Successive shortest path algorithm for calculating maximum weighted
    380   matching and maximum weighted bipartite matching in bipartite graphs.
    381 - \ref MinCostMaxBipartiteMatching
    382   Successive shortest path algorithm for calculating minimum cost maximum
    383   matching in bipartite graphs.
    384 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    385   maximum cardinality matching in general graphs.
    386 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
    387   maximum weighted matching in general graphs.
    388 - \ref MaxWeightedPerfectMatching
    389   Edmond's blossom shrinking algorithm for calculating maximum weighted
    390   perfect matching in general graphs.
     327LEMON contains the next algorithms:
     328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     329  augmenting path algorithm for calculate maximum cardinality matching in
     330  bipartite graphs
     331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     332  algorithm for calculate maximum cardinality matching in bipartite graphs
     333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     334  Successive shortest path algorithm for calculate maximum weighted matching
     335  and maximum weighted bipartite matching in bipartite graph
     336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     337  Successive shortest path algorithm for calculate minimum cost maximum
     338  matching in bipartite graph
     339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     340  for calculate maximum cardinality matching in general graph
     341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     342  shrinking algorithm for calculate maximum weighted matching in general
     343  graph
     344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     345  Edmond's blossom shrinking algorithm for calculate maximum weighted
     346  perfect matching in general graph
    391347
    392348\image html bipartite_matching.png
    … …  
    400356
    401357This group describes the algorithms for finding a minimum cost spanning
    402 tree in a graph.
     358tree in a graph
    403359*/
    404360
    … …  
    591547\anchor demoprograms
    592548
    593 @defgroup demos Demo Programs
     549@defgroup demos Demo programs
    594550
    595551Some demo programs are listed here. Their full source codes can be found in
    … …  
    601557
    602558/**
    603 @defgroup tools Standalone Utility Applications
     559@defgroup tools Standalone utility applications
    604560
    605561Some utility applications are listed here.
    … …  
    609565*/
    610566
    611 }

  • lemon/bfs.h

    r405 r329  
    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

    r405 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

    r408 r397  
    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.