Index: doc/groups.dox
===================================================================
 doc/groups.dox (revision 388)
+++ doc/groups.dox (revision 406)
@@ 17,4 +17,6 @@
*/
+namespace lemon {
+
/**
@defgroup datas Data Structures
@@ 89,5 +91,8 @@
This group describes maps that are specifically designed to assign
values to the nodes and arcs of graphs.
+values to the nodes and arcs/edges of graphs.
+
+If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
+\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
*/
@@ 100,5 +105,5 @@
maps from other maps.
Most of them are \ref lemon::concepts::ReadMap "readonly maps".
+Most of them are \ref concepts::ReadMap "readonly maps".
They can make arithmetic and logical operations between one or two maps
(negation, shifting, addition, multiplication, logical 'and', 'or',
@@ 202,6 +207,6 @@
\brief Common graph search algorithms.
This group describes the common graph search algorithms like
BreadthFirst Search (BFS) and DepthFirst Search (DFS).
+This group describes the common graph search algorithms, namely
+\e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS).
*/
@@ 211,5 +216,18 @@
\brief Algorithms for finding shortest paths.
This group describes the algorithms for finding shortest paths in graphs.
+This group describes the algorithms for finding shortest paths in digraphs.
+
+  \ref Dijkstra algorithm for finding shortest paths from a source node
+ when all arc lengths are nonnegative.
+  \ref BellmanFord "BellmanFord" algorithm for finding shortest paths
+ from a source node when arc lenghts can be either positive or negative,
+ but the digraph should not contain directed cycles with negative total
+ length.
+  \ref FloydWarshall "FloydWarshall" and \ref Johnson "Johnson" algorithms
+ for solving the \e allpairs \e shortest \e paths \e problem when arc
+ lenghts can be either positive or negative, but the digraph should
+ not contain directed cycles with negative total length.
+  \ref Suurballe A successive shortest path algorithm for finding
+ arcdisjoint paths between two nodes having minimum total length.
*/
@@ 222,25 +240,26 @@
feasible circulations.
The maximum flow problem is to find a flow between a single source and
a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
function and given \f$s, t \in V\f$ source and target node. The
maximum flow is the \f$f_a\f$ solution of the next optimization problem:

\f[ 0 \le f_a \le c_a \f]
\f[ \sum_{v\in\delta^{}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
\qquad \forall u \in V \setminus \{s,t\}\f]
\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv}  \sum_{v\in\delta^{}(s)}f_{vu}\f]
+The \e maximum \e flow \e problem is to find a flow of maximum value between
+a single source and a single target. Formally, there is a \f$G=(V,A)\f$
+digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
+\f$s, t \in V\f$ source and target nodes.
+A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
+following optimization problem.
+
+\f[ \max\sum_{a\in\delta_{out}(s)}f(a)  \sum_{a\in\delta_{in}(s)}f(a) \f]
+\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
+ \qquad \forall v\in V\setminus\{s,t\} \f]
+\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
LEMON contains several algorithms for solving maximum flow problems:
 \ref lemon::EdmondsKarp "EdmondsKarp"
 \ref lemon::Preflow "Goldberg's Preflow algorithm"
 \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
 \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
fastest method to compute the maximum flow. All impelementations
provides functions to query the minimum cut, which is the dual linear
programming problem of the maximum flow.
+ \ref EdmondsKarp EdmondsKarp algorithm.
+ \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm.
+ \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
+ \ref GoldbergTarjan Preflow pushrelabel algorithm with dynamic trees.
+
+In most cases the \ref Preflow "Preflow" algorithm provides the
+fastest method for computing a maximum flow. All implementations
+provides functions to also query the minimum cut, which is the dual
+problem of the maximum flow.
*/
@@ 253,4 +272,31 @@
This group describes the algorithms for finding minimum cost flows and
circulations.
+
+The \e minimum \e cost \e flow \e problem is to find a feasible flow of
+minimum total cost from a set of supply nodes to a set of demand nodes
+in a network with capacity constraints and arc costs.
+Formally, let \f$G=(V,A)\f$ be a digraph,
+\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
+upper bounds for the flow values on the arcs,
+\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
+on the arcs, and
+\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
+of the nodes.
+A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
+the following optimization problem.
+
+\f[ \min\sum_{a\in A} f(a) cost(a) \f]
+\f[ \sum_{a\in\delta_{out}(v)} f(a)  \sum_{a\in\delta_{in}(v)} f(a) =
+ supply(v) \qquad \forall v\in V \f]
+\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
+
+LEMON contains several algorithms for solving minimum cost flow problems:
+  \ref CycleCanceling Cyclecanceling algorithms.
+  \ref CapacityScaling Successive shortest path algorithm with optional
+ capacity scaling.
+  \ref CostScaling Pushrelabel and augmentrelabel algorithms based on
+ cost scaling.
+  \ref NetworkSimplex Primal network simplex algorithm with various
+ pivot strategies.
*/
@@ 263,24 +309,24 @@
This group describes the algorithms for finding minimum cut in graphs.
The minimum cut problem is to find a nonempty and noncomplete
\f$X\f$ subset of the vertices with minimum overall capacity on
outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
+The \e minimum \e cut \e problem is to find a nonempty and noncomplete
+\f$X\f$ subset of the nodes with minimum overall capacity on
+outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
+\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
cut is the \f$X\f$ solution of the next optimization problem:
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
+ \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
LEMON contains several algorithms related to minimum cut problems:
 \ref lemon::HaoOrlin "HaoOrlin algorithm" to calculate minimum cut
 in directed graphs
 \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" to
 calculate minimum cut in undirected graphs
 \ref lemon::GomoryHuTree "GomoryHu tree computation" to calculate all
 pairs minimum cut in undirected graphs
+ \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut
+ in directed graphs.
+ \ref NagamochiIbaraki "NagamochiIbaraki algorithm" for
+ calculating minimum cut in undirected graphs.
+ \ref GomoryHuTree "GomoryHu tree computation" for calculating
+ allpairs minimum cut in undirected graphs.
If you want to find minimum cut just between two distinict nodes,
please see the \ref max_flow "Maximum Flow page".
+see the \ref max_flow "maximum flow problem".
*/
@@ 321,28 +367,26 @@
graphs. The matching problems in bipartite graphs are generally
easier than in general graphs. The goal of the matching optimization
can be the finding maximum cardinality, maximum weight or minimum cost
+can be finding maximum cardinality, maximum weight or minimum cost
matching. The search can be constrained to find perfect or
maximum cardinality matching.
LEMON contains the next algorithms:
 \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" HopcroftKarp
 augmenting path algorithm for calculate maximum cardinality matching in
 bipartite graphs
 \ref lemon::PrBipartiteMatching "PrBipartiteMatching" PushRelabel
 algorithm for calculate maximum cardinality matching in bipartite graphs
 \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
 Successive shortest path algorithm for calculate maximum weighted matching
 and maximum weighted bipartite matching in bipartite graph
 \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
 Successive shortest path algorithm for calculate minimum cost maximum
 matching in bipartite graph
 \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
 for calculate maximum cardinality matching in general graph
 \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
 shrinking algorithm for calculate maximum weighted matching in general
 graph
 \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
 Edmond's blossom shrinking algorithm for calculate maximum weighted
 perfect matching in general graph
+The matching algorithms implemented in LEMON:
+ \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm
+ for calculating maximum cardinality matching in bipartite graphs.
+ \ref PrBipartiteMatching Pushrelabel algorithm
+ for calculating maximum cardinality matching in bipartite graphs.
+ \ref MaxWeightedBipartiteMatching
+ Successive shortest path algorithm for calculating maximum weighted
+ matching and maximum weighted bipartite matching in bipartite graphs.
+ \ref MinCostMaxBipartiteMatching
+ Successive shortest path algorithm for calculating minimum cost maximum
+ matching in bipartite graphs.
+ \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
+ maximum cardinality matching in general graphs.
+ \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
+ maximum weighted matching in general graphs.
+ \ref MaxWeightedPerfectMatching
+ Edmond's blossom shrinking algorithm for calculating maximum weighted
+ perfect matching in general graphs.
\image html bipartite_matching.png
@@ 356,5 +400,5 @@
This group describes the algorithms for finding a minimum cost spanning
tree in a graph
+tree in a graph.
*/
@@ 547,5 +591,5 @@
\anchor demoprograms
@defgroup demos Demo programs
+@defgroup demos Demo Programs
Some demo programs are listed here. Their full source codes can be found in
@@ 557,5 +601,5 @@
/**
@defgroup tools Standalone utility applications
+@defgroup tools Standalone Utility Applications
Some utility applications are listed here.
@@ 565,2 +609,3 @@
*/
+}
Index: lemon/bfs.h
===================================================================
 lemon/bfs.h (revision 405)
+++ lemon/bfs.h (revision 329)
@@ 52,5 +52,5 @@
///Instantiates a PredMap.
 ///This function instantiates a PredMap.
+ ///This function instantiates a PredMap.
///\param g is the digraph, to which we would like to define the
///PredMap.
@@ 81,6 +81,5 @@
///The type of the map that indicates which nodes are reached.
 ///The type of the map that indicates which nodes are reached.
 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
@@ 120,5 +119,11 @@
///
///\tparam GR The type of the digraph the algorithm runs on.
 ///The default type is \ref ListDigraph.
+ ///The default value is \ref ListDigraph. The value of GR is not used
+ ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
+ ///\tparam TR Traits class to set various data types used by the algorithm.
+ ///The default traits class is
+ ///\ref BfsDefaultTraits "BfsDefaultTraits".
+ ///See \ref BfsDefaultTraits for the documentation of
+ ///a Bfs traits class.
#ifdef DOXYGEN
template Path;
 ///The \ref BfsDefaultTraits "traits class" of the algorithm.
+ ///The traits class.
typedef TR Traits;
@@ 208,5 +213,5 @@
typedef Bfs Create;
 ///\name Named Template Parameters
+ ///\name Named template parameters
///@{
@@ 226,5 +231,4 @@
///\ref namedtemplparam "Named parameter" for setting
///PredMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > {
@@ 246,5 +250,4 @@
///\ref namedtemplparam "Named parameter" for setting
///DistMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > {
@@ 266,5 +269,4 @@
///\ref namedtemplparam "Named parameter" for setting
///ReachedMap type.
 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > {
@@ 286,5 +288,4 @@
///\ref namedtemplparam "Named parameter" for setting
///ProcessedMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > {
@@ 339,8 +340,7 @@
///Sets the map that stores the predecessor arcs.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Bfs &predMap(PredMap &m)
@@ 357,8 +357,7 @@
///Sets the map that indicates which nodes are reached.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Bfs &reachedMap(ReachedMap &m)
@@ 375,8 +374,7 @@
///Sets the map that indicates which nodes are processed.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Bfs &processedMap(ProcessedMap &m)
@@ 394,8 +392,7 @@
///Sets the map that stores the distances of the nodes calculated by
///the algorithm.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Bfs &distMap(DistMap &m)
@@ 411,17 +408,20 @@
public:
 ///\name Execution Control
 ///The simplest way to execute the BFS algorithm is to use one of the
 ///member functions called \ref run(Node) "run()".\n
 ///If you need more control on the execution, first you have to call
 ///\ref init(), then you can add several source nodes with
 ///\ref addSource(). Finally the actual path computation can be
 ///performed with one of the \ref start() functions.
+ ///\name Execution control
+ ///The simplest way to execute the algorithm is to use
+ ///one of the member functions called \ref lemon::Bfs::run() "run()".
+ ///\n
+ ///If you need more control on the execution, first you must call
+ ///\ref lemon::Bfs::init() "init()", then you can add several source
+ ///nodes with \ref lemon::Bfs::addSource() "addSource()".
+ ///Finally \ref lemon::Bfs::start() "start()" will perform the
+ ///actual path computation.
///@{
 ///\brief Initializes the internal data structures.
 ///
///Initializes the internal data structures.
+
+ ///Initializes the internal data structures.
+ ///
void init()
{
@@ 557,14 +557,14 @@
}
 ///Returns \c false if there are nodes to be processed.

 ///Returns \c false if there are nodes to be processed
 ///in the queue.
+ ///\brief Returns \c false if there are nodes
+ ///to be processed.
+ ///
+ ///Returns \c false if there are nodes
+ ///to be processed in the queue.
bool emptyQueue() const { return _queue_tail==_queue_head; }
///Returns the number of the nodes to be processed.
 ///Returns the number of the nodes to be processed
 ///in the queue.
+ ///Returns the number of the nodes to be processed in the queue.
int queueSize() const { return _queue_head_queue_tail; }
@@ 731,8 +731,8 @@
///\name Query Functions
 ///The results of the BFS algorithm can be obtained using these
+ ///The result of the %BFS algorithm can be obtained using these
///functions.\n
 ///Either \ref run(Node) "run()" or \ref start() should be called
 ///before using them.
+ ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
+ ///"start()" must be called before using them.
///@{
@@ 742,8 +742,8 @@
///Returns the shortest path to a node.
///
 ///\warning \c t should be reached from the root(s).
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\warning \c t should be reachable from the root(s).
+ ///
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Path path(Node t) const { return Path(*G, *_pred, t); }
@@ 752,9 +752,9 @@
///Returns the distance of a node from the root(s).
///
 ///\warning If node \c v is not reached from the root(s), then
+ ///\warning If node \c v is not reachable from the root(s), then
///the return value of this function is undefined.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
int dist(Node v) const { return (*_dist)[v]; }
@@ 763,12 +763,12 @@
///This function returns the 'previous arc' of the shortest path
///tree for the node \c v, i.e. it returns the last arc of a
 ///shortest path from a root to \c v. It is \c INVALID if \c v
 ///is not reached from the root(s) or if \c v is a root.
+ ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
+ ///is not reachable from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
///tree used in \ref predNode().
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Arc predArc(Node v) const { return (*_pred)[v];}
@@ 777,12 +777,12 @@
///This function returns the 'previous node' of the shortest path
///tree for the node \c v, i.e. it returns the last but one node
 ///from a shortest path from a root to \c v. It is \c INVALID
 ///if \c v is not reached from the root(s) or if \c v is a root.
+ ///from a shortest path from the root(s) to \c v. It is \c INVALID
+ ///if \c v is not reachable from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
///tree used in \ref predArc().
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
G>source((*_pred)[v]); }
@@ 794,5 +794,5 @@
///of the nodes calculated by the algorithm.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
const DistMap &distMap() const { return *_dist;}
@@ 804,13 +804,12 @@
///arcs, which form the shortest path tree.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
const PredMap &predMap() const { return *_pred;}
 ///Checks if a node is reached from the root(s).

 ///Returns \c true if \c v is reached from the root(s).
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///Checks if a node is reachable from the root(s).
+
+ ///Returns \c true if \c v is reachable from the root(s).
+ ///\pre Either \ref run() or \ref start()
///must be called before using this function.
bool reached(Node v) const { return (*_reached)[v]; }
@@ 958,6 +957,6 @@
/// This auxiliary class is created to implement the
/// \ref bfs() "functiontype interface" of \ref Bfs algorithm.
 /// It does not have own \ref run(Node) "run()" method, it uses the
 /// functions and features of the plain \ref Bfs.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Bfs.
///
/// This class should only be used through the \ref bfs() function,
@@ 1179,5 +1178,5 @@
/// bool reached = bfs(g).path(p).dist(d).run(s,t);
///\endcode
 ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
+ ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
///to the end of the parameter list.
///\sa BfsWizard
@@ 1365,5 +1364,5 @@
typedef BfsVisit Create;
 /// \name Named Template Parameters
+ /// \name Named template parameters
///@{
@@ 1407,8 +1406,7 @@
///
/// Sets the map that indicates which nodes are reached.
 /// If you don't use this function before calling \ref run(Node) "run()"
 /// or \ref init(), an instance will be allocated automatically.
 /// The destructor deallocates this automatically allocated map,
 /// of course.
+ /// If you don't use this function before calling \ref run(),
+ /// it will allocate one. The destructor deallocates this
+ /// automatically allocated map, of course.
/// \return (*this)
BfsVisit &reachedMap(ReachedMap &m) {
@@ 1423,11 +1421,14 @@
public:
 /// \name Execution Control
 /// The simplest way to execute the BFS algorithm is to use one of the
 /// member functions called \ref run(Node) "run()".\n
 /// If you need more control on the execution, first you have to call
 /// \ref init(), then you can add several source nodes with
 /// \ref addSource(). Finally the actual path computation can be
 /// performed with one of the \ref start() functions.
+ /// \name Execution control
+ /// The simplest way to execute the algorithm is to use
+ /// one of the member functions called \ref lemon::BfsVisit::run()
+ /// "run()".
+ /// \n
+ /// If you need more control on the execution, first you must call
+ /// \ref lemon::BfsVisit::init() "init()", then you can add several
+ /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
+ /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
+ /// actual path computation.
/// @{
@@ 1729,16 +1730,15 @@
/// \name Query Functions
 /// The results of the BFS algorithm can be obtained using these
+ /// The result of the %BFS algorithm can be obtained using these
/// functions.\n
 /// Either \ref run(Node) "run()" or \ref start() should be called
 /// before using them.

+ /// Either \ref lemon::BfsVisit::run() "run()" or
+ /// \ref lemon::BfsVisit::start() "start()" must be called before
+ /// using them.
///@{
 /// \brief Checks if a node is reached from the root(s).
 ///
 /// Returns \c true if \c v is reached from the root(s).
 ///
 /// \pre Either \ref run(Node) "run()" or \ref init()
+ /// \brief Checks if a node is reachable from the root(s).
+ ///
+ /// Returns \c true if \c v is reachable from the root(s).
+ /// \pre Either \ref run() or \ref start()
/// must be called before using this function.
bool reached(Node v) { return (*_reached)[v]; }
Index: lemon/dfs.h
===================================================================
 lemon/dfs.h (revision 405)
+++ lemon/dfs.h (revision 319)
@@ 120,5 +120,11 @@
///
///\tparam GR The type of the digraph the algorithm runs on.
 ///The default type is \ref ListDigraph.
+ ///The default value is \ref ListDigraph. The value of GR is not used
+ ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
+ ///\tparam TR Traits class to set various data types used by the algorithm.
+ ///The default traits class is
+ ///\ref DfsDefaultTraits "DfsDefaultTraits".
+ ///See \ref DfsDefaultTraits for the documentation of
+ ///a Dfs traits class.
#ifdef DOXYGEN
template Path;
 ///The \ref DfsDefaultTraits "traits class" of the algorithm.
+ ///The traits class.
typedef TR Traits;
@@ 225,5 +231,4 @@
///\ref namedtemplparam "Named parameter" for setting
///PredMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetPredMap : public Dfs > {
@@ 245,5 +250,4 @@
///\ref namedtemplparam "Named parameter" for setting
///DistMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > {
@@ 265,5 +269,4 @@
///\ref namedtemplparam "Named parameter" for setting
///ReachedMap type.
 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template
struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > {
@@ 285,5 +288,4 @@
///\ref namedtemplparam "Named parameter" for setting
///ProcessedMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > {
@@ 337,8 +339,7 @@
///Sets the map that stores the predecessor arcs.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dfs &predMap(PredMap &m)
@@ 355,8 +356,7 @@
///Sets the map that indicates which nodes are reached.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dfs &reachedMap(ReachedMap &m)
@@ 373,8 +373,7 @@
///Sets the map that indicates which nodes are processed.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dfs &processedMap(ProcessedMap &m)
@@ 392,8 +391,7 @@
///Sets the map that stores the distances of the nodes calculated by
///the algorithm.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dfs &distMap(DistMap &m)
@@ 409,18 +407,20 @@
public:
 ///\name Execution Control
 ///The simplest way to execute the DFS algorithm is to use one of the
 ///member functions called \ref run(Node) "run()".\n
 ///If you need more control on the execution, first you have to call
 ///\ref init(), then you can add a source node with \ref addSource()
 ///and perform the actual computation with \ref start().
 ///This procedure can be repeated if there are nodes that have not
 ///been reached.
+ ///\name Execution control
+ ///The simplest way to execute the algorithm is to use
+ ///one of the member functions called \ref lemon::Dfs::run() "run()".
+ ///\n
+ ///If you need more control on the execution, first you must call
+ ///\ref lemon::Dfs::init() "init()", then you can add a source node
+ ///with \ref lemon::Dfs::addSource() "addSource()".
+ ///Finally \ref lemon::Dfs::start() "start()" will perform the
+ ///actual path computation.
///@{
 ///\brief Initializes the internal data structures.
 ///
///Initializes the internal data structures.
+
+ ///Initializes the internal data structures.
+ ///
void init()
{
@@ 439,8 +439,9 @@
///Adds a new source node to the set of nodes to be processed.
///
 ///\pre The stack must be empty. Otherwise the algorithm gives
 ///wrong results. (One of the outgoing arcs of all the source nodes
 ///except for the last one will not be visited and distances will
 ///also be wrong.)
+ ///\pre The stack must be empty. (Otherwise the algorithm gives
+ ///false results.)
+ ///
+ ///\warning Distances will be wrong (or at least strange) in case of
+ ///multiple sources.
void addSource(Node s)
{
@@ 506,14 +507,14 @@
}
 ///Returns \c false if there are nodes to be processed.

 ///Returns \c false if there are nodes to be processed
 ///in the queue (stack).
+ ///\brief Returns \c false if there are nodes
+ ///to be processed.
+ ///
+ ///Returns \c false if there are nodes
+ ///to be processed in the queue (stack).
bool emptyQueue() const { return _stack_head<0; }
///Returns the number of the nodes to be processed.
 ///Returns the number of the nodes to be processed
 ///in the queue (stack).
+ ///Returns the number of the nodes to be processed in the queue (stack).
int queueSize() const { return _stack_head+1; }
@@ 637,6 +638,6 @@
///
///The algorithm computes
 /// the %DFS tree (forest),
 /// the distance of each node from the root(s) in the %DFS tree.
+ /// the %DFS tree,
+ /// the distance of each node from the root in the %DFS tree.
///
///\note d.run() is just a shortcut of the following code.
@@ 663,8 +664,8 @@
///\name Query Functions
 ///The results of the DFS algorithm can be obtained using these
+ ///The result of the %DFS algorithm can be obtained using these
///functions.\n
 ///Either \ref run(Node) "run()" or \ref start() should be called
 ///before using them.
+ ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
+ ///"start()" must be called before using them.
///@{
@@ 674,19 +675,19 @@
///Returns the DFS path to a node.
///
 ///\warning \c t should be reached from the root(s).
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\warning \c t should be reachable from the root.
+ ///
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Path path(Node t) const { return Path(*G, *_pred, t); }
 ///The distance of a node from the root(s).

 ///Returns the distance of a node from the root(s).
 ///
 ///\warning If node \c v is not reached from the root(s), then
+ ///The distance of a node from the root.
+
+ ///Returns the distance of a node from the root.
+ ///
+ ///\warning If node \c v is not reachable from the root, then
///the return value of this function is undefined.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
int dist(Node v) const { return (*_dist)[v]; }
@@ 694,13 +695,13 @@
///This function returns the 'previous arc' of the %DFS tree for the
 ///node \c v, i.e. it returns the last arc of a %DFS path from a
 ///root to \c v. It is \c INVALID if \c v is not reached from the
 ///root(s) or if \c v is a root.
+ ///node \c v, i.e. it returns the last arc of a %DFS path from the
+ ///root to \c v. It is \c INVALID
+ ///if \c v is not reachable from the root(s) or if \c v is a root.
///
///The %DFS tree used here is equal to the %DFS tree used in
///\ref predNode().
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before using
+ ///this function.
Arc predArc(Node v) const { return (*_pred)[v];}
@@ 709,12 +710,12 @@
///This function returns the 'previous node' of the %DFS
///tree for the node \c v, i.e. it returns the last but one node
 ///from a %DFS path from a root to \c v. It is \c INVALID
 ///if \c v is not reached from the root(s) or if \c v is a root.
+ ///from a %DFS path from the root to \c v. It is \c INVALID
+ ///if \c v is not reachable from the root(s) or if \c v is a root.
///
///The %DFS tree used here is equal to the %DFS tree used in
///\ref predArc().
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
G>source((*_pred)[v]); }
@@ 726,5 +727,5 @@
///distances of the nodes calculated by the algorithm.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
const DistMap &distMap() const { return *_dist;}
@@ 736,13 +737,12 @@
///arcs, which form the DFS tree.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
const PredMap &predMap() const { return *_pred;}
 ///Checks if a node is reached from the root(s).

 ///Returns \c true if \c v is reached from the root(s).
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///Checks if a node is reachable from the root(s).
+
+ ///Returns \c true if \c v is reachable from the root(s).
+ ///\pre Either \ref run() or \ref start()
///must be called before using this function.
bool reached(Node v) const { return (*_reached)[v]; }
@@ 890,6 +890,6 @@
/// This auxiliary class is created to implement the
/// \ref dfs() "functiontype interface" of \ref Dfs algorithm.
 /// It does not have own \ref run(Node) "run()" method, it uses the
 /// functions and features of the plain \ref Dfs.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Dfs.
///
/// This class should only be used through the \ref dfs() function,
@@ 1111,5 +1111,6 @@
/// bool reached = dfs(g).path(p).dist(d).run(s,t);
///\endcode
 ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
+
+ ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
///to the end of the parameter list.
///\sa DfsWizard
@@ 1309,5 +1310,5 @@
typedef DfsVisit Create;
 /// \name Named Template Parameters
+ /// \name Named template parameters
///@{
@@ 1351,8 +1352,7 @@
///
/// Sets the map that indicates which nodes are reached.
 /// If you don't use this function before calling \ref run(Node) "run()"
 /// or \ref init(), an instance will be allocated automatically.
 /// The destructor deallocates this automatically allocated map,
 /// of course.
+ /// If you don't use this function before calling \ref run(),
+ /// it will allocate one. The destructor deallocates this
+ /// automatically allocated map, of course.
/// \return (*this)
DfsVisit &reachedMap(ReachedMap &m) {
@@ 1367,12 +1367,14 @@
public:
 /// \name Execution Control
 /// The simplest way to execute the DFS algorithm is to use one of the
 /// member functions called \ref run(Node) "run()".\n
 /// If you need more control on the execution, first you have to call
 /// \ref init(), then you can add a source node with \ref addSource()
 /// and perform the actual computation with \ref start().
 /// This procedure can be repeated if there are nodes that have not
 /// been reached.
+ /// \name Execution control
+ /// The simplest way to execute the algorithm is to use
+ /// one of the member functions called \ref lemon::DfsVisit::run()
+ /// "run()".
+ /// \n
+ /// If you need more control on the execution, first you must call
+ /// \ref lemon::DfsVisit::init() "init()", then you can add several
+ /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
+ /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
+ /// actual path computation.
/// @{
@@ 1390,12 +1392,13 @@
}
 /// \brief Adds a new source node.
 ///
 /// Adds a new source node to the set of nodes to be processed.
 ///
 /// \pre The stack must be empty. Otherwise the algorithm gives
 /// wrong results. (One of the outgoing arcs of all the source nodes
 /// except for the last one will not be visited and distances will
 /// also be wrong.)
+ ///Adds a new source node.
+
+ ///Adds a new source node to the set of nodes to be processed.
+ ///
+ ///\pre The stack must be empty. (Otherwise the algorithm gives
+ ///false results.)
+ ///
+ ///\warning Distances will be wrong (or at least strange) in case of
+ ///multiple sources.
void addSource(Node s)
{
@@ 1587,6 +1590,6 @@
///
/// The algorithm computes
 ///  the %DFS tree (forest),
 ///  the distance of each node from the root(s) in the %DFS tree.
+ ///  the %DFS tree,
+ ///  the distance of each node from the root in the %DFS tree.
///
/// \note d.run() is just a shortcut of the following code.
@@ 1613,16 +1616,15 @@
/// \name Query Functions
 /// The results of the DFS algorithm can be obtained using these
+ /// The result of the %DFS algorithm can be obtained using these
/// functions.\n
 /// Either \ref run(Node) "run()" or \ref start() should be called
 /// before using them.

+ /// Either \ref lemon::DfsVisit::run() "run()" or
+ /// \ref lemon::DfsVisit::start() "start()" must be called before
+ /// using them.
///@{
 /// \brief Checks if a node is reached from the root(s).
 ///
 /// Returns \c true if \c v is reached from the root(s).
 ///
 /// \pre Either \ref run(Node) "run()" or \ref init()
+ /// \brief Checks if a node is reachable from the root(s).
+ ///
+ /// Returns \c true if \c v is reachable from the root(s).
+ /// \pre Either \ref run() or \ref start()
/// must be called before using this function.
bool reached(Node v) { return (*_reached)[v]; }
Index: lemon/dijkstra.h
===================================================================
 lemon/dijkstra.h (revision 405)
+++ lemon/dijkstra.h (revision 313)
@@ 203,11 +203,18 @@
///
///\tparam GR The type of the digraph the algorithm runs on.
 ///The default type is \ref ListDigraph.
 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
 ///the lengths of the arcs.
 ///It is read once for each arc, so the map may involve in
+ ///The default value is \ref ListDigraph.
+ ///The value of GR is not used directly by \ref Dijkstra, it is only
+ ///passed to \ref DijkstraDefaultTraits.
+ ///\tparam LM A readable arc map that determines the lengths of the
+ ///arcs. It is read once for each arc, so the map may involve in
///relatively time consuming process to compute the arc lengths if
///it is necessary. The default map type is \ref
 ///concepts::Digraph::ArcMap "GR::ArcMap".
+ ///concepts::Digraph::ArcMap "Digraph::ArcMap".
+ ///The value of LM is not used directly by \ref Dijkstra, it is only
+ ///passed to \ref DijkstraDefaultTraits.
+ ///\tparam TR Traits class to set various data types used by the algorithm.
+ ///The default traits class is \ref DijkstraDefaultTraits
+ ///"DijkstraDefaultTraits". See \ref DijkstraDefaultTraits
+ ///for the documentation of a Dijkstra traits class.
#ifdef DOXYGEN
template
@@ 243,5 +250,5 @@
typedef typename TR::OperationTraits OperationTraits;
 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
+ ///The traits class.
typedef TR Traits;
@@ 325,5 +332,4 @@
///\ref namedtemplparam "Named parameter" for setting
///PredMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetPredMap
@@ 346,5 +352,4 @@
///\ref namedtemplparam "Named parameter" for setting
///DistMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap
@@ 367,5 +372,4 @@
///\ref namedtemplparam "Named parameter" for setting
///ProcessedMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap
@@ 408,12 +412,8 @@
};
///\brief \ref namedtemplparam "Named parameter" for setting
 ///heap and cross reference types
+ ///heap and cross reference type
///
///\ref namedtemplparam "Named parameter" for setting heap and cross
 ///reference types. If this named parameter is used, then external
 ///heap and cross reference objects must be passed to the algorithm
 ///using the \ref heap() function before calling \ref run(Node) "run()"
 ///or \ref init().
 ///\sa SetStandardHeap
+ ///reference type.
template >
struct SetHeap
@@ 435,16 +435,10 @@
};
///\brief \ref namedtemplparam "Named parameter" for setting
 ///heap and cross reference types with automatic allocation
+ ///heap and cross reference type with automatic allocation
///
///\ref namedtemplparam "Named parameter" for setting heap and cross
 ///reference types with automatic allocation.
 ///They should have standard constructor interfaces to be able to
 ///automatically created by the algorithm (i.e. the digraph should be
 ///passed to the constructor of the cross reference and the cross
 ///reference should be passed to the constructor of the heap).
 ///However external heap and cross reference objects could also be
 ///passed to the algorithm using the \ref heap() function before
 ///calling \ref run(Node) "run()" or \ref init().
 ///\sa SetHeap
+ ///reference type. It can allocate the heap and the cross reference
+ ///object if the cross reference's constructor waits for the digraph as
+ ///parameter and the heap's constructor waits for the cross reference.
template >
struct SetStandardHeap
@@ 516,8 +510,7 @@
///Sets the map that stores the predecessor arcs.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dijkstra &predMap(PredMap &m)
@@ 534,8 +527,7 @@
///Sets the map that indicates which nodes are processed.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dijkstra &processedMap(ProcessedMap &m)
@@ 553,8 +545,7 @@
///Sets the map that stores the distances of the nodes calculated by the
///algorithm.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), an instance will be allocated automatically.
 ///The destructor deallocates this automatically allocated map,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated map, of course.
///\return (*this)
Dijkstra &distMap(DistMap &m)
@@ 571,9 +562,7 @@
///Sets the heap and the cross reference used by algorithm.
 ///If you don't use this function before calling \ref run(Node) "run()"
 ///or \ref init(), heap and cross reference instances will be
 ///allocated automatically.
 ///The destructor deallocates these automatically allocated objects,
 ///of course.
+ ///If you don't use this function before calling \ref run(),
+ ///it will allocate one. The destructor deallocates this
+ ///automatically allocated heap and cross reference, of course.
///\return (*this)
Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
@@ 602,17 +591,20 @@
public:
 ///\name Execution Control
 ///The simplest way to execute the %Dijkstra algorithm is to use
 ///one of the member functions called \ref run(Node) "run()".\n
 ///If you need more control on the execution, first you have to call
 ///\ref init(), then you can add several source nodes with
 ///\ref addSource(). Finally the actual path computation can be
 ///performed with one of the \ref start() functions.
+ ///\name Execution control
+ ///The simplest way to execute the algorithm is to use one of the
+ ///member functions called \ref lemon::Dijkstra::run() "run()".
+ ///\n
+ ///If you need more control on the execution, first you must call
+ ///\ref lemon::Dijkstra::init() "init()", then you can add several
+ ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
+ ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
+ ///actual path computation.
///@{
 ///\brief Initializes the internal data structures.
 ///
///Initializes the internal data structures.
+
+ ///Initializes the internal data structures.
+ ///
void init()
{
@@ 690,14 +682,15 @@
}
 ///Returns \c false if there are nodes to be processed.

 ///Returns \c false if there are nodes to be processed
 ///in the priority heap.
+ ///\brief Returns \c false if there are nodes
+ ///to be processed.
+ ///
+ ///Returns \c false if there are nodes
+ ///to be processed in the priority heap.
bool emptyQueue() const { return _heap>empty(); }
 ///Returns the number of the nodes to be processed.

 ///Returns the number of the nodes to be processed
 ///in the priority heap.
+ ///Returns the number of the nodes to be processed in the priority heap
+
+ ///Returns the number of the nodes to be processed in the priority heap.
+ ///
int queueSize() const { return _heap>size(); }
@@ 820,8 +813,9 @@
///\name Query Functions
 ///The results of the %Dijkstra algorithm can be obtained using these
+ ///The result of the %Dijkstra algorithm can be obtained using these
///functions.\n
 ///Either \ref run(Node) "run()" or \ref start() should be called
 ///before using them.
+ ///Either \ref lemon::Dijkstra::run() "run()" or
+ ///\ref lemon::Dijkstra::start() "start()" must be called before
+ ///using them.
///@{
@@ 831,8 +825,8 @@
///Returns the shortest path to a node.
///
 ///\warning \c t should be reached from the root(s).
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\warning \c t should be reachable from the root(s).
+ ///
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Path path(Node t) const { return Path(*G, *_pred, t); }
@@ 841,9 +835,9 @@
///Returns the distance of a node from the root(s).
///
 ///\warning If node \c v is not reached from the root(s), then
+ ///\warning If node \c v is not reachable from the root(s), then
///the return value of this function is undefined.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Value dist(Node v) const { return (*_dist)[v]; }
@@ 852,12 +846,12 @@
///This function returns the 'previous arc' of the shortest path
///tree for the node \c v, i.e. it returns the last arc of a
 ///shortest path from a root to \c v. It is \c INVALID if \c v
 ///is not reached from the root(s) or if \c v is a root.
+ ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
+ ///is not reachable from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
///tree used in \ref predNode().
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Arc predArc(Node v) const { return (*_pred)[v]; }
@@ 866,12 +860,12 @@
///This function returns the 'previous node' of the shortest path
///tree for the node \c v, i.e. it returns the last but one node
 ///from a shortest path from a root to \c v. It is \c INVALID
 ///if \c v is not reached from the root(s) or if \c v is a root.
+ ///from a shortest path from the root(s) to \c v. It is \c INVALID
+ ///if \c v is not reachable from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
///tree used in \ref predArc().
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
G>source((*_pred)[v]); }
@@ 883,5 +877,5 @@
///of the nodes calculated by the algorithm.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
const DistMap &distMap() const { return *_dist;}
@@ 893,13 +887,12 @@
///arcs, which form the shortest path tree.
///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
const PredMap &predMap() const { return *_pred;}
 ///Checks if a node is reached from the root(s).

 ///Returns \c true if \c v is reached from the root(s).
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///Checks if a node is reachable from the root(s).
+
+ ///Returns \c true if \c v is reachable from the root(s).
+ ///\pre Either \ref run() or \ref start()
///must be called before using this function.
bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
@@ 910,6 +903,5 @@
///Returns \c true if \c v is processed, i.e. the shortest
///path to \c v has already found.
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function.
bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
@@ 920,6 +912,5 @@
///Returns the current distance of a node from the root(s).
///It may be decreased in the following processes.
 ///
 ///\pre Either \ref run(Node) "run()" or \ref init()
+ ///\pre Either \ref run() or \ref init()
///must be called before using this function and
///node \c v must be reached but not necessarily processed.
@@ 1104,6 +1095,6 @@
/// This auxiliary class is created to implement the
/// \ref dijkstra() "functiontype interface" of \ref Dijkstra algorithm.
 /// It does not have own \ref run(Node) "run()" method, it uses the
 /// functions and features of the plain \ref Dijkstra.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Dijkstra.
///
/// This class should only be used through the \ref dijkstra() function,
@@ 1300,5 +1291,5 @@
/// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
///\endcode
 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
+ ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
///to the end of the parameter list.
///\sa DijkstraWizard