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 / [412:7030149efed2:413:d8b87e9b90c3] in lemon-1.2


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r388 r406  
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
    … …  
    8991
    9092This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     93values to the nodes and arcs/edges of graphs.
     94
     95If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     96\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    9297*/
    9398
    … …  
    100105maps from other maps.
    101106
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     107Most of them are \ref concepts::ReadMap "read-only maps".
    103108They can make arithmetic and logical operations between one or two maps
    104109(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    202207\brief Common graph search algorithms.
    203208
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     209This group describes the common graph search algorithms, namely
     210\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206211*/
    207212
    … …  
    211216\brief Algorithms for finding shortest paths.
    212217
    213 This group describes the algorithms for finding shortest paths in graphs.
     218This 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.
    214232*/
    215233
    … …  
    222240feasible circulations.
    223241
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum 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]
     242The \e maximum \e flow \e problem is to find a flow of maximum value between
     243a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     244digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     245\f$s, t \in V\f$ source and target nodes.
     246A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     247following 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]
    234253
    235254LEMON contains several algorithms for solving maximum flow problems:
    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 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
     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
     260In most cases the \ref Preflow "Preflow" algorithm provides the
     261fastest method for computing a maximum flow. All implementations
     262provides functions to also query the minimum cut, which is the dual
     263problem of the maximum flow.
    245264*/
    246265
    … …  
    253272This group describes the algorithms for finding minimum cost flows and
    254273circulations.
     274
     275The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     276minimum total cost from a set of supply nodes to a set of demand nodes
     277in a network with capacity constraints and arc costs.
     278Formally, let \f$G=(V,A)\f$ be a digraph,
     279\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     280upper bounds for the flow values on the arcs,
     281\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     282on the arcs, and
     283\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     284of the nodes.
     285A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     286the 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
     293LEMON 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.
    255301*/
    256302
    … …  
    263309This group describes the algorithms for finding minimum cut in graphs.
    264310
    265 The 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
    267 outgoing 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
     311The \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
     313outgoing 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
    269315cut is the \f$X\f$ solution of the next optimization problem:
    270316
    271317\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     318    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273319
    274320LEMON contains several algorithms related to minimum cut problems:
    275321
    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
     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.
    282328
    283329If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
     330see the \ref max_flow "maximum flow problem".
    285331*/
    286332
    … …  
    321367graphs.  The matching problems in bipartite graphs are generally
    322368easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     369can be finding maximum cardinality, maximum weight or minimum cost
    324370matching. The search can be constrained to find perfect or
    325371maximum cardinality matching.
    326372
    327 LEMON 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
     373The 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.
    347391
    348392\image html bipartite_matching.png
    … …  
    356400
    357401This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     402tree in a graph.
    359403*/
    360404
    … …  
    547591\anchor demoprograms
    548592
    549 @defgroup demos Demo programs
     593@defgroup demos Demo Programs
    550594
    551595Some demo programs are listed here. Their full source codes can be found in
    … …  
    557601
    558602/**
    559 @defgroup tools Standalone utility applications
     603@defgroup tools Standalone Utility Applications
    560604
    561605Some utility applications are listed here.
    … …  
    565609*/
    566610
     611}

  • lemon/bfs.h

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

  • lemon/dfs.h

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

  • lemon/dijkstra.h

    r397 r408  
    180180  ///
    181181  ///\tparam GR The type of the digraph the algorithm runs on.
    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
     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
    187186  ///relatively time consuming process to compute the arc lengths if
    188187  ///it is necessary. The default map type is \ref
    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.
     188  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    196189#ifdef DOXYGEN
    197190  template <typename GR, typename LM, typename TR>
    … …  
    227220    typedef typename TR::OperationTraits OperationTraits;
    228221
    229     ///The traits class.
     222    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    230223    typedef TR Traits;
    231224
    … …  
    309302    ///\ref named-templ-param "Named parameter" for setting
    310303    ///PredMap type.
     304    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    311305    template <class T>
    312306    struct SetPredMap
    … …  
    329323    ///\ref named-templ-param "Named parameter" for setting
    330324    ///DistMap type.
     325    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    331326    template <class T>
    332327    struct SetDistMap
    … …  
    349344    ///\ref named-templ-param "Named parameter" for setting
    350345    ///ProcessedMap type.
     346    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    351347    template <class T>
    352348    struct SetProcessedMap
    … …  
    389385    };
    390386    ///\brief \ref named-templ-param "Named parameter" for setting
    391     ///heap and cross reference type
     387    ///heap and cross reference types
    392388    ///
    393389    ///\ref named-templ-param "Named parameter" for setting heap and cross
    394     ///reference type.
     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
    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 type with automatic allocation
     414    ///heap and cross reference types with automatic allocation
    415415    ///
    416416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    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.
     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
    420426    template <class H, class CR = typename Digraph::template NodeMap<int> >
    421427    struct SetStandardHeap
    … …  
    487493
    488494    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    492499    ///\return <tt> (*this) </tt>
    493500    Dijkstra &predMap(PredMap &m)
    … …  
    504511
    505512    ///Sets the map that indicates which nodes are processed.
    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.
     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.
    509517    ///\return <tt> (*this) </tt>
    510518    Dijkstra &processedMap(ProcessedMap &m)
    … …  
    522530    ///Sets the map that stores the distances of the nodes calculated by the
    523531    ///algorithm.
    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.
     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.
    527536    ///\return <tt> (*this) </tt>
    528537    Dijkstra &distMap(DistMap &m)
    … …  
    539548
    540549    ///Sets the heap and the cross reference used by algorithm.
    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.
     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.
    544555    ///\return <tt> (*this) </tt>
    545556    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
    … …  
    568579  public:
    569580
    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.
     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.
    579588
    580589    ///@{
    581590
     591    ///\brief Initializes the internal data structures.
     592    ///
    582593    ///Initializes the internal data structures.
    583 
    584     ///Initializes the internal data structures.
    585     ///
    586594    void init()
    587595    {
    … …  
    659667    }
    660668
    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.
     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.
    666673    bool emptyQueue() const { return _heap->empty(); }
    667674
    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     ///
     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.
    672679    int queueSize() const { return _heap->size(); }
    673680
    … …  
    790797
    791798    ///\name Query Functions
    792     ///The result of the %Dijkstra algorithm can be obtained using these
     799    ///The results of the %Dijkstra algorithm can be obtained using these
    793800    ///functions.\n
    794     ///Either \ref lemon::Dijkstra::run() "run()" or
    795     ///\ref lemon::Dijkstra::start() "start()" must be called before
    796     ///using them.
     801    ///Either \ref run(Node) "run()" or \ref start() should be called
     802    ///before using them.
    797803
    798804    ///@{
    … …  
    802808    ///Returns the shortest path to a node.
    803809    ///
    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.
     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.
    808814    Path path(Node t) const { return Path(*G, *_pred, t); }
    809815
    … …  
    812818    ///Returns the distance of a node from the root(s).
    813819    ///
    814     ///\warning If node \c v is not reachable from the root(s), then
     820    ///\warning If node \c v is not reached from the root(s), then
    815821    ///the return value of this function is undefined.
    816822    ///
    817     ///\pre Either \ref run() or \ref start() must be called before
    818     ///using this function.
     823    ///\pre Either \ref run(Node) "run()" or \ref init()
     824    ///must be called before using this function.
    819825    Value dist(Node v) const { return (*_dist)[v]; }
    820826
    … …  
    823829    ///This function returns the 'previous arc' of the shortest path
    824830    ///tree for the node \c v, i.e. it returns the last arc of a
    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.
     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.
    827833    ///
    828834    ///The shortest path tree used here is equal to the shortest path
    829835    ///tree used in \ref predNode().
    830836    ///
    831     ///\pre Either \ref run() or \ref start() must be called before
    832     ///using this function.
     837    ///\pre Either \ref run(Node) "run()" or \ref init()
     838    ///must be called before using this function.
    833839    Arc predArc(Node v) const { return (*_pred)[v]; }
    834840
    … …  
    837843    ///This function returns the 'previous node' of the shortest path
    838844    ///tree for the node \c v, i.e. it returns the last but one node
    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.
     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.
    841847    ///
    842848    ///The shortest path tree used here is equal to the shortest path
    843849    ///tree used in \ref predArc().
    844850    ///
    845     ///\pre Either \ref run() or \ref start() must be called before
    846     ///using this function.
     851    ///\pre Either \ref run(Node) "run()" or \ref init()
     852    ///must be called before using this function.
    847853    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    848854                                  G->source((*_pred)[v]); }
    … …  
    854860    ///of the nodes calculated by the algorithm.
    855861    ///
    856     ///\pre Either \ref run() or \ref init()
     862    ///\pre Either \ref run(Node) "run()" or \ref init()
    857863    ///must be called before using this function.
    858864    const DistMap &distMap() const { return *_dist;}
    … …  
    864870    ///arcs, which form the shortest path tree.
    865871    ///
    866     ///\pre Either \ref run() or \ref init()
     872    ///\pre Either \ref run(Node) "run()" or \ref init()
    867873    ///must be called before using this function.
    868874    const PredMap &predMap() const { return *_pred;}
    869875
    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()
     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()
    874881    ///must be called before using this function.
    875882    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
    … …  
    880887    ///Returns \c true if \c v is processed, i.e. the shortest
    881888    ///path to \c v has already found.
    882     ///\pre Either \ref run() or \ref init()
     889    ///
     890    ///\pre Either \ref run(Node) "run()" or \ref init()
    883891    ///must be called before using this function.
    884892    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
    … …  
    889897    ///Returns the current distance of a node from the root(s).
    890898    ///It may be decreased in the following processes.
    891     ///\pre Either \ref run() or \ref init()
     899    ///
     900    ///\pre Either \ref run(Node) "run()" or \ref init()
    892901    ///must be called before using this function and
    893902    ///node \c v must be reached but not necessarily processed.
    … …  
    10721081  /// This auxiliary class is created to implement the
    10731082  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1074   /// It does not have own \ref run() method, it uses the functions
    1075   /// and features of the plain \ref Dijkstra.
     1083  /// It does not have own \ref run(Node) "run()" method, it uses the
     1084  /// functions and features of the plain \ref Dijkstra.
    10761085  ///
    10771086  /// This class should only be used through the \ref dijkstra() function,
    … …  
    12681277  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12691278  ///\endcode
    1270   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1279  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
    12711280  ///to the end of the parameter list.
    12721281  ///\sa DijkstraWizard
Note: See TracChangeset for help on using the changeset viewer.