Changes in / [418:ad483acf1654:417:6ff53afe98b5] in lemon-main

Files:

• doc/groups.dox (modified) (13 diffs)
• lemon/Makefile.am (modified) (2 diffs)
• lemon/bfs.h (modified) (28 diffs)
• lemon/circulation.h (deleted)
• lemon/dfs.h (modified) (28 diffs)
• lemon/dijkstra.h (modified) (25 diffs)
• lemon/hao_orlin.h (deleted)
• scripts/unify-sources.sh (modified) (2 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (4 diffs)
• test/circulation_test.cc (deleted)
• test/dijkstra_test.cc (modified) (1 diff)
• test/hao_orlin_test.cc (deleted)

doc/groups.dox

@@ -16 +16 @@
  *
  */
-
-namespace lemon {
 
 /**
@@ -164 +162 @@
 
 This group describes maps that are specifically designed to assign
-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".
+values to the nodes and arcs of graphs.
 */
 
@@ -178 +173 @@
 maps from other maps.
 
-Most of them are \ref concepts::ReadMap "read-only maps".
+Most of them are \ref lemon::concepts::ReadMap "read-only maps".
 They can make arithmetic and logical operations between one or two maps
 (negation, shifting, addition, multiplication, logical 'and', 'or',
@@ -280 +275 @@
 \brief Common graph search algorithms.
 
-This group describes the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+This group describes the common graph search algorithms like
+Breadth-First Search (BFS) and Depth-First Search (DFS).
 */
 
@@ -289 +284 @@
 \brief Algorithms for finding shortest paths.
 
-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 non-negative.
- - \ref BellmanFord "Bellman-Ford" 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 "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
-   for solving the \e all-pairs \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
-   arc-disjoint paths between two nodes having minimum total length.
+This group describes the algorithms for finding shortest paths in graphs.
 */
 
@@ -313 +295 @@
 feasible circulations.
 
-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]
+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]
 
 LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel 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.
+- \ref lemon::EdmondsKarp "Edmonds-Karp"
+- \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.
 */
 
@@ -345 +326 @@
 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 Cycle-canceling algorithms.
- - \ref CapacityScaling Successive shortest path algorithm with optional
-   capacity scaling.
- - \ref CostScaling Push-relabel and augment-relabel algorithms based on
-   cost scaling.
- - \ref NetworkSimplex Primal network simplex algorithm with various
-   pivot strategies.
 */
 
@@ -382 +336 @@
 This group describes the algorithms for finding minimum cut in graphs.
 
-The \e minimum \e cut \e problem is to find a non-empty and non-complete
-\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
+The minimum cut problem is to find a non-empty and non-complete
+\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
 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}cap(uv) \f]
+\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
 
 LEMON contains several algorithms related to minimum cut problems:
 
-- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
-  in directed graphs.
-- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
-  calculating minimum cut in undirected graphs.
-- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
-  all-pairs minimum cut in undirected graphs.
+- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
+  in directed graphs
+- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
+  calculate minimum cut in undirected graphs
+- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
+  pairs minimum cut in undirected graphs
 
 If you want to find minimum cut just between two distinict nodes,
-see the \ref max_flow "maximum flow problem".
+please see the \ref max_flow "Maximum Flow page".
 */
 
@@ -440 +394 @@
 graphs.  The matching problems in bipartite graphs are generally
 easier than in general graphs. The goal of the matching optimization
-can be finding maximum cardinality, maximum weight or minimum cost
+can be the finding maximum cardinality, maximum weight or minimum cost
 matching. The search can be constrained to find perfect or
 maximum cardinality matching.
 
-The matching algorithms implemented in LEMON:
-- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref PrBipartiteMatching Push-relabel 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.
+LEMON contains the next algorithms:
+- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
+  augmenting path algorithm for calculate maximum cardinality matching in
+  bipartite graphs
+- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
+  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
 
 \image html bipartite_matching.png
@@ -473 +429 @@
 
 This group describes the algorithms for finding a minimum cost spanning
-tree in a graph.
+tree in a graph
 */
 
@@ -664 +620 @@
 \anchor demoprograms
 
-@defgroup demos Demo Programs
+@defgroup demos Demo programs
 
 Some demo programs are listed here. Their full source codes can be found in
@@ -674 +630 @@
 
 /**
-@defgroup tools Standalone Utility Applications
+@defgroup tools Standalone utility applications
 
 Some utility applications are listed here.
@@ -682 +638 @@
 */
 
-}

lemon/Makefile.am

@@ -22 +22 @@
         lemon/bfs.h \
         lemon/bin_heap.h \
-        lemon/circulation.h \
         lemon/color.h \
         lemon/concept_check.h \
@@ -38 +37 @@
         lemon/hypercube_graph.h \
         lemon/kruskal.h \
-        lemon/hao_orlin.h \
         lemon/lgf_reader.h \
         lemon/lgf_writer.h \

lemon/bfs.h

@@ -52 +52 @@
     ///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 +81 @@
     ///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<bool> ReachedMap;
     ///Instantiates a ReachedMap.
@@ -120 +119 @@
   ///
   ///\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<GR>".
+  ///See \ref BfsDefaultTraits for the documentation of
+  ///a Bfs traits class.
 #ifdef DOXYGEN
   template <typename GR,
@@ -146 +151 @@
     typedef PredMapPath<Digraph, PredMap> Path;
 
-    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
+    ///The traits class.
     typedef TR Traits;
 
@@ -208 +213 @@
     typedef Bfs Create;
 
-    ///\name Named Template Parameters
+    ///\name Named template parameters
 
     ///@{
@@ -226 +231 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///PredMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
@@ -246 +250 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///DistMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
@@ -266 +269 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///ReachedMap type.
-    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
@@ -286 +288 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
@@ -339 +340 @@
 
     ///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 <tt> (*this) </tt>
     Bfs &predMap(PredMap &m)
@@ -357 +357 @@
 
     ///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 <tt> (*this) </tt>
     Bfs &reachedMap(ReachedMap &m)
@@ -375 +374 @@
 
     ///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 <tt> (*this) </tt>
     Bfs &processedMap(ProcessedMap &m)
@@ -394 +392 @@
     ///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 <tt> (*this) </tt>
     Bfs &distMap(DistMap &m)
@@ -411 +408 @@
   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 +557 @@
     }
 
-    ///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 +731 @@
 
     ///\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 +742 @@
     ///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 +752 @@
     ///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 +763 @@
     ///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 +777 @@
     ///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 +794 @@
     ///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 +804 @@
     ///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 +957 @@
   /// This auxiliary class is created to implement the
   /// \ref bfs() "function-type 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 +1178 @@
   ///  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 +1364 @@
     typedef BfsVisit Create;
 
-    /// \name Named Template Parameters
+    /// \name Named template parameters
 
     ///@{
@@ -1407 +1406 @@
     ///
     /// 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 <tt> (*this) </tt>
     BfsVisit &reachedMap(ReachedMap &m) {
@@ -1423 +1421 @@
   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 +1730 @@
 
     /// \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]; }

lemon/dfs.h

@@ -120 +120 @@
   ///
   ///\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<GR>".
+  ///See \ref DfsDefaultTraits for the documentation of
+  ///a Dfs traits class.
 #ifdef DOXYGEN
   template <typename GR,
@@ -146 +152 @@
     typedef PredMapPath<Digraph, PredMap> Path;
 
-    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
+    ///The traits class.
     typedef TR Traits;
 
@@ -225 +231 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///PredMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
@@ -245 +250 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///DistMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
@@ -265 +269 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///ReachedMap type.
-    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
@@ -285 +288 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
@@ -337 +339 @@
 
     ///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 <tt> (*this) </tt>
     Dfs &predMap(PredMap &m)
@@ -355 +356 @@
 
     ///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 <tt> (*this) </tt>
     Dfs &reachedMap(ReachedMap &m)
@@ -373 +373 @@
 
     ///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 <tt> (*this) </tt>
     Dfs &processedMap(ProcessedMap &m)
@@ -392 +391 @@
     ///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 <tt> (*this) </tt>
     Dfs &distMap(DistMap &m)
@@ -409 +407 @@
   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 +439 @@
     ///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 +507 @@
     }
 
-    ///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 +638 @@
     ///
     ///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 <tt>d.run()</tt> is just a shortcut of the following code.
@@ -663 +664 @@
 
     ///\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 +675 @@
     ///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 +695 @@
 
     ///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 +710 @@
     ///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 +727 @@
     ///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 +737 @@
     ///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 +890 @@
   /// This auxiliary class is created to implement the
   /// \ref dfs() "function-type 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 +1111 @@
   ///  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 +1310 @@
     typedef DfsVisit Create;
 
-    /// \name Named Template Parameters
+    /// \name Named template parameters
 
     ///@{
@@ -1351 +1352 @@
     ///
     /// 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 <tt> (*this) </tt>
     DfsVisit &reachedMap(ReachedMap &m) {
@@ -1367 +1367 @@
   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 +1392 @@
     }
 
-    /// \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 +1590 @@
     ///
     /// 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 <tt>d.run()</tt> is just a shortcut of the following code.
@@ -1613 +1616 @@
 
     /// \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]; }

lemon/dijkstra.h

@@ -55 +55 @@
   };
 
+  /// \brief Widest path operation traits for the Dijkstra algorithm class.
+  ///
+  /// This operation traits class defines all computational operations and
+  /// constants which are used in the Dijkstra algorithm for widest path
+  /// computation.
+  ///
+  /// \see DijkstraDefaultOperationTraits
+  template <typename Value>
+  struct DijkstraWidestPathOperationTraits {
+    /// \brief Gives back the maximum value of the type.
+    static Value zero() {
+      return std::numeric_limits<Value>::max();
+    }
+    /// \brief Gives back the minimum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return std::min(left, right);
+    }
+    /// \brief Gives back true only if the first value is less than the second.
+    static bool less(const Value& left, const Value& right) {
+      return left < right;
+    }
+  };
+
   ///Default traits class of Dijkstra class.
 
@@ -180 +203 @@
   ///
   ///\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<int>".
+  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
+  ///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<GR,LM>". See \ref DijkstraDefaultTraits
+  ///for the documentation of a Dijkstra traits class.
 #ifdef DOXYGEN
   template <typename GR, typename LM, typename TR>
@@ -220 +250 @@
     typedef typename TR::OperationTraits OperationTraits;
 
-    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
+    ///The traits class.
     typedef TR Traits;
 
@@ -302 +332 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///PredMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap
@@ -323 +352 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///DistMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap
@@ -344 +372 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap
@@ -385 +412 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///heap and cross reference types
+    ///heap and cross reference type
     ///
     ///\ref named-templ-param "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 <class H, class CR = typename Digraph::template NodeMap<int> >
     struct SetHeap
@@ -412 +435 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///heap and cross reference types with automatic allocation
+    ///heap and cross reference type with automatic allocation
     ///
     ///\ref named-templ-param "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 <class H, class CR = typename Digraph::template NodeMap<int> >
     struct SetStandardHeap
@@ -493 +510 @@
 
     ///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 <tt> (*this) </tt>
     Dijkstra &predMap(PredMap &m)
@@ -511 +527 @@
 
     ///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 <tt> (*this) </tt>
     Dijkstra &processedMap(ProcessedMap &m)
@@ -530 +545 @@
     ///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 <tt> (*this) </tt>
     Dijkstra &distMap(DistMap &m)
@@ -548 +562 @@
 
     ///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 <tt> (*this) </tt>
     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
@@ -579 +591 @@
   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()
     {
@@ -667 +682 @@
     }
 
-    ///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(); }
 
@@ -797 +813 @@
 
     ///\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.
 
     ///@{
@@ -808 +825 @@
     ///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); }
 
@@ -818 +835 @@
     ///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]; }
 
@@ -829 +846 @@
     ///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]; }
 
@@ -843 +860 @@
     ///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]); }
@@ -860 +877 @@
     ///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;}
@@ -870 +887 @@
     ///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] !=
@@ -887 +903 @@
     ///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] ==
@@ -897 +912 @@
     ///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.
@@ -1081 +1095 @@
   /// This auxiliary class is created to implement the
   /// \ref dijkstra() "function-type 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,
@@ -1277 +1291 @@
   ///  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

scripts/unify-sources.sh

@@ -131 +131 @@
     echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
 
-    if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ]
+    if [ $FAILED_FILES -gt 0 ]
+    then
+        return 1
+    elif [ $WARNED_FILES -gt 0 ]
     then
         if [ "$WARNING" == 'INTERACTIVE' ]
         then
-            echo -n "Are the files with errors/warnings acceptable? (yes/no) "
+            echo -n "Are the files with warnings acceptable? (yes/no) "
             while read answer
             do
@@ -145 +148 @@
                     return 1
                 fi
-                echo -n "Are the files with errors/warnings acceptable? (yes/no) "
+                echo -n "Are the files with warnings acceptable? (yes/no) "
             done
         elif [ "$WARNING" == 'WERROR' ]

test/CMakeLists.txt

@@ -14 +14 @@
   graph_test
   graph_utils_test
-  hao_orlin_test
   heap_test
   kruskal_test

test/Makefile.am

@@ -10 +10 @@
 check_PROGRAMS += \
         test/bfs_test \
-        test/circulation_test \
         test/counter_test \
         test/dfs_test \
@@ -23 +22 @@
         test/heap_test \
         test/kruskal_test \
-        test/hao_orlin_test \
         test/maps_test \
         test/max_matching_test \
@@ -39 +37 @@
 
 test_bfs_test_SOURCES = test/bfs_test.cc
-test_circulation_test_SOURCES = test/circulation_test.cc
 test_counter_test_SOURCES = test/counter_test.cc
 test_dfs_test_SOURCES = test/dfs_test.cc
@@ -52 +49 @@
 test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
-test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
 test_max_matching_test_SOURCES = test/max_matching_test.cc

test/dijkstra_test.cc

@@ -90 +90 @@
       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
       ::SetStandardProcessedMap
-      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
+      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
       ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >