Index: doc/groups.dox
===================================================================
--- doc/groups.dox	(revision 422)
+++ doc/groups.dox	(revision 403)
@@ -17,6 +17,4 @@
  */
 
-namespace lemon {
-
 /**
 @defgroup datas Data Structures
@@ -91,8 +89,5 @@
 
 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.
 */
 
@@ -105,5 +100,5 @@
 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',
@@ -207,6 +202,6 @@
 \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).
 */
 
@@ -216,18 +211,5 @@
 \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.
 */
 
@@ -240,26 +222,25 @@
 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.
 */
 
@@ -272,31 +253,4 @@
 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.
 */
 
@@ -309,24 +263,24 @@
 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".
 */
 
@@ -367,26 +321,28 @@
 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
@@ -400,5 +356,5 @@
 
 This group describes the algorithms for finding a minimum cost spanning
-tree in a graph.
+tree in a graph
 */
 
@@ -591,5 +547,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
@@ -601,5 +557,5 @@
 
 /**
-@defgroup tools Standalone Utility Applications
+@defgroup tools Standalone utility applications
 
 Some utility applications are listed here.
@@ -609,3 +565,2 @@
 */
 
-}
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 419)
+++ lemon/Makefile.am	(revision 425)
@@ -37,4 +37,5 @@
 	lemon/hypercube_graph.h \
 	lemon/kruskal.h \
+	lemon/hao_orlin.h \
 	lemon/lgf_reader.h \
 	lemon/lgf_writer.h \
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h	(revision 421)
+++ lemon/bfs.h	(revision 341)
@@ -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<bool> 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<GR>".
+  ///See \ref BfsDefaultTraits for the documentation of
+  ///a Bfs traits class.
 #ifdef DOXYGEN
   template <typename GR,
@@ -146,5 +151,5 @@
     typedef PredMapPath<Digraph, PredMap> 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 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,5 +250,4 @@
     ///\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,5 +269,4 @@
     ///\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,5 +288,4 @@
     ///\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,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 <tt> (*this) </tt>
     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 <tt> (*this) </tt>
     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 <tt> (*this) </tt>
     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 <tt> (*this) </tt>
     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() "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,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 <tt> (*this) </tt>
     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 421)
+++ 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<GR>".
+  ///See \ref DfsDefaultTraits for the documentation of
+  ///a Dfs traits class.
 #ifdef DOXYGEN
   template <typename GR,
@@ -146,5 +152,5 @@
     typedef PredMapPath<Digraph, PredMap> Path;
 
-    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
+    ///The traits class.
     typedef TR Traits;
 
@@ -225,5 +231,4 @@
     ///\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,5 +250,4 @@
     ///\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,5 +269,4 @@
     ///\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,5 +288,4 @@
     ///\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,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 <tt> (*this) </tt>
     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 <tt> (*this) </tt>
     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 <tt> (*this) </tt>
     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 <tt> (*this) </tt>
     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 <tt>d.run()</tt> 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() "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,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 <tt> (*this) </tt>
     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 <tt>d.run()</tt> 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 424)
+++ lemon/dijkstra.h	(revision 412)
@@ -180,11 +180,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<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,5 +227,5 @@
     typedef typename TR::OperationTraits OperationTraits;
 
-    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
+    ///The traits class.
     typedef TR Traits;
 
@@ -302,5 +309,4 @@
     ///\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,5 +329,4 @@
     ///\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,5 +349,4 @@
     ///\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,12 +389,8 @@
     };
     ///\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,16 +412,10 @@
     };
     ///\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,8 +487,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 <tt> (*this) </tt>
     Dijkstra &predMap(PredMap &m)
@@ -511,8 +504,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 <tt> (*this) </tt>
     Dijkstra &processedMap(ProcessedMap &m)
@@ -530,8 +522,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 <tt> (*this) </tt>
     Dijkstra &distMap(DistMap &m)
@@ -548,9 +539,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 <tt> (*this) </tt>
     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
@@ -579,17 +568,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()
     {
@@ -667,14 +659,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(); }
 
@@ -797,8 +790,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.
 
     ///@{
@@ -808,8 +802,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); }
 
@@ -818,9 +812,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]; }
 
@@ -829,12 +823,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]; }
 
@@ -843,12 +837,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]); }
@@ -860,5 +854,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;}
@@ -870,13 +864,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] !=
@@ -887,6 +880,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] ==
@@ -897,6 +889,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.
@@ -1081,6 +1072,6 @@
   /// 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,5 +1268,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
Index: lemon/hao_orlin.h
===================================================================
--- lemon/hao_orlin.h	(revision 425)
+++ lemon/hao_orlin.h	(revision 425)
@@ -0,0 +1,985 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_HAO_ORLIN_H
+#define LEMON_HAO_ORLIN_H
+
+#include <vector>
+#include <list>
+#include <limits>
+
+#include <lemon/maps.h>
+#include <lemon/core.h>
+#include <lemon/tolerance.h>
+
+/// \file
+/// \ingroup min_cut
+/// \brief Implementation of the Hao-Orlin algorithm.
+///
+/// Implementation of the Hao-Orlin algorithm class for testing network
+/// reliability.
+
+namespace lemon {
+
+  /// \ingroup min_cut
+  ///
+  /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
+  ///
+  /// Hao-Orlin calculates a minimum cut in a directed graph
+  /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
+  /// consists of two phases: in the first phase it determines a
+  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
+  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
+  /// out-degree) and in the second phase it determines a minimum cut
+  /// with \f$ source \f$ on the sink-side (i.e. a set
+  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal
+  /// out-degree). Obviously, the smaller of these two cuts will be a
+  /// minimum cut of \f$ D \f$. The algorithm is a modified
+  /// push-relabel preflow algorithm and our implementation calculates
+  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
+  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
+  /// purpose of such algorithm is testing network reliability. For an
+  /// undirected graph you can run just the first phase of the
+  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
+  /// which solves the undirected problem in
+  /// \f$ O(nm + n^2 \log(n)) \f$ time: it is implemented in the
+  /// NagamochiIbaraki algorithm class.
+  ///
+  /// \param _Digraph is the graph type of the algorithm.
+  /// \param _CapacityMap is an edge map of capacities which should
+  /// be any numreric type. The default type is _Digraph::ArcMap<int>.
+  /// \param _Tolerance is the handler of the inexact computation. The
+  /// default type for this is Tolerance<CapacityMap::Value>.
+#ifdef DOXYGEN
+  template <typename _Digraph, typename _CapacityMap, typename _Tolerance>
+#else
+  template <typename _Digraph,
+            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
+            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
+#endif
+  class HaoOrlin {
+  private:
+
+    typedef _Digraph Digraph;
+    typedef _CapacityMap CapacityMap;
+    typedef _Tolerance Tolerance;
+
+    typedef typename CapacityMap::Value Value;
+
+    TEMPLATE_GRAPH_TYPEDEFS(Digraph);
+
+    const Digraph& _graph;
+    const CapacityMap* _capacity;
+
+    typedef typename Digraph::template ArcMap<Value> FlowMap;
+    FlowMap* _flow;
+
+    Node _source;
+
+    int _node_num;
+
+    // Bucketing structure
+    std::vector<Node> _first, _last;
+    typename Digraph::template NodeMap<Node>* _next;
+    typename Digraph::template NodeMap<Node>* _prev;
+    typename Digraph::template NodeMap<bool>* _active;
+    typename Digraph::template NodeMap<int>* _bucket;
+
+    std::vector<bool> _dormant;
+
+    std::list<std::list<int> > _sets;
+    std::list<int>::iterator _highest;
+
+    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+    ExcessMap* _excess;
+
+    typedef typename Digraph::template NodeMap<bool> SourceSetMap;
+    SourceSetMap* _source_set;
+
+    Value _min_cut;
+
+    typedef typename Digraph::template NodeMap<bool> MinCutMap;
+    MinCutMap* _min_cut_map;
+
+    Tolerance _tolerance;
+
+  public:
+
+    /// \brief Constructor
+    ///
+    /// Constructor of the algorithm class.
+    HaoOrlin(const Digraph& graph, const CapacityMap& capacity,
+             const Tolerance& tolerance = Tolerance()) :
+      _graph(graph), _capacity(&capacity), _flow(0), _source(),
+      _node_num(), _first(), _last(), _next(0), _prev(0),
+      _active(0), _bucket(0), _dormant(), _sets(), _highest(),
+      _excess(0), _source_set(0), _min_cut(), _min_cut_map(0),
+      _tolerance(tolerance) {}
+
+    ~HaoOrlin() {
+      if (_min_cut_map) {
+        delete _min_cut_map;
+      }
+      if (_source_set) {
+        delete _source_set;
+      }
+      if (_excess) {
+        delete _excess;
+      }
+      if (_next) {
+        delete _next;
+      }
+      if (_prev) {
+        delete _prev;
+      }
+      if (_active) {
+        delete _active;
+      }
+      if (_bucket) {
+        delete _bucket;
+      }
+      if (_flow) {
+        delete _flow;
+      }
+    }
+
+  private:
+
+    void activate(const Node& i) {
+      _active->set(i, true);
+
+      int bucket = (*_bucket)[i];
+
+      if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
+      //unlace
+      _next->set((*_prev)[i], (*_next)[i]);
+      if ((*_next)[i] != INVALID) {
+        _prev->set((*_next)[i], (*_prev)[i]);
+      } else {
+        _last[bucket] = (*_prev)[i];
+      }
+      //lace
+      _next->set(i, _first[bucket]);
+      _prev->set(_first[bucket], i);
+      _prev->set(i, INVALID);
+      _first[bucket] = i;
+    }
+
+    void deactivate(const Node& i) {
+      _active->set(i, false);
+      int bucket = (*_bucket)[i];
+
+      if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;
+
+      //unlace
+      _prev->set((*_next)[i], (*_prev)[i]);
+      if ((*_prev)[i] != INVALID) {
+        _next->set((*_prev)[i], (*_next)[i]);
+      } else {
+        _first[bucket] = (*_next)[i];
+      }
+      //lace
+      _prev->set(i, _last[bucket]);
+      _next->set(_last[bucket], i);
+      _next->set(i, INVALID);
+      _last[bucket] = i;
+    }
+
+    void addItem(const Node& i, int bucket) {
+      (*_bucket)[i] = bucket;
+      if (_last[bucket] != INVALID) {
+        _prev->set(i, _last[bucket]);
+        _next->set(_last[bucket], i);
+        _next->set(i, INVALID);
+        _last[bucket] = i;
+      } else {
+        _prev->set(i, INVALID);
+        _first[bucket] = i;
+        _next->set(i, INVALID);
+        _last[bucket] = i;
+      }
+    }
+
+    void findMinCutOut() {
+
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _excess->set(n, 0);
+      }
+
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _flow->set(a, 0);
+      }
+
+      int bucket_num = 1;
+
+      {
+        typename Digraph::template NodeMap<bool> reached(_graph, false);
+
+        reached.set(_source, true);
+
+        bool first_set = true;
+
+        for (NodeIt t(_graph); t != INVALID; ++t) {
+          if (reached[t]) continue;
+          _sets.push_front(std::list<int>());
+          _sets.front().push_front(bucket_num);
+          _dormant[bucket_num] = !first_set;
+
+          _bucket->set(t, bucket_num);
+          _first[bucket_num] = _last[bucket_num] = t;
+          _next->set(t, INVALID);
+          _prev->set(t, INVALID);
+
+          ++bucket_num;
+
+          std::vector<Node> queue;
+          queue.push_back(t);
+          reached.set(t, true);
+
+          while (!queue.empty()) {
+            _sets.front().push_front(bucket_num);
+            _dormant[bucket_num] = !first_set;
+            _first[bucket_num] = _last[bucket_num] = INVALID;
+
+            std::vector<Node> nqueue;
+            for (int i = 0; i < int(queue.size()); ++i) {
+              Node n = queue[i];
+              for (InArcIt a(_graph, n); a != INVALID; ++a) {
+                Node u = _graph.source(a);
+                if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
+                  reached.set(u, true);
+                  addItem(u, bucket_num);
+                  nqueue.push_back(u);
+                }
+              }
+            }
+            queue.swap(nqueue);
+            ++bucket_num;
+          }
+          _sets.front().pop_front();
+          --bucket_num;
+          first_set = false;
+        }
+
+        _bucket->set(_source, 0);
+        _dormant[0] = true;
+      }
+      _source_set->set(_source, true);
+
+      Node target = _last[_sets.back().back()];
+      {
+        for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
+          if (_tolerance.positive((*_capacity)[a])) {
+            Node u = _graph.target(a);
+            _flow->set(a, (*_capacity)[a]);
+            _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
+            if (!(*_active)[u] && u != _source) {
+              activate(u);
+            }
+          }
+        }
+
+        if ((*_active)[target]) {
+          deactivate(target);
+        }
+
+        _highest = _sets.back().begin();
+        while (_highest != _sets.back().end() &&
+               !(*_active)[_first[*_highest]]) {
+          ++_highest;
+        }
+      }
+
+      while (true) {
+        while (_highest != _sets.back().end()) {
+          Node n = _first[*_highest];
+          Value excess = (*_excess)[n];
+          int next_bucket = _node_num;
+
+          int under_bucket;
+          if (++std::list<int>::iterator(_highest) == _sets.back().end()) {
+            under_bucket = -1;
+          } else {
+            under_bucket = *(++std::list<int>::iterator(_highest));
+          }
+
+          for (OutArcIt a(_graph, n); a != INVALID; ++a) {
+            Node v = _graph.target(a);
+            if (_dormant[(*_bucket)[v]]) continue;
+            Value rem = (*_capacity)[a] - (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            if ((*_bucket)[v] == under_bucket) {
+              if (!(*_active)[v] && v != target) {
+                activate(v);
+              }
+              if (!_tolerance.less(rem, excess)) {
+                _flow->set(a, (*_flow)[a] + excess);
+                _excess->set(v, (*_excess)[v] + excess);
+                excess = 0;
+                goto no_more_push;
+              } else {
+                excess -= rem;
+                _excess->set(v, (*_excess)[v] + rem);
+                _flow->set(a, (*_capacity)[a]);
+              }
+            } else if (next_bucket > (*_bucket)[v]) {
+              next_bucket = (*_bucket)[v];
+            }
+          }
+
+          for (InArcIt a(_graph, n); a != INVALID; ++a) {
+            Node v = _graph.source(a);
+            if (_dormant[(*_bucket)[v]]) continue;
+            Value rem = (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            if ((*_bucket)[v] == under_bucket) {
+              if (!(*_active)[v] && v != target) {
+                activate(v);
+              }
+              if (!_tolerance.less(rem, excess)) {
+                _flow->set(a, (*_flow)[a] - excess);
+                _excess->set(v, (*_excess)[v] + excess);
+                excess = 0;
+                goto no_more_push;
+              } else {
+                excess -= rem;
+                _excess->set(v, (*_excess)[v] + rem);
+                _flow->set(a, 0);
+              }
+            } else if (next_bucket > (*_bucket)[v]) {
+              next_bucket = (*_bucket)[v];
+            }
+          }
+
+        no_more_push:
+
+          _excess->set(n, excess);
+
+          if (excess != 0) {
+            if ((*_next)[n] == INVALID) {
+              typename std::list<std::list<int> >::iterator new_set =
+                _sets.insert(--_sets.end(), std::list<int>());
+              new_set->splice(new_set->end(), _sets.back(),
+                              _sets.back().begin(), ++_highest);
+              for (std::list<int>::iterator it = new_set->begin();
+                   it != new_set->end(); ++it) {
+                _dormant[*it] = true;
+              }
+              while (_highest != _sets.back().end() &&
+                     !(*_active)[_first[*_highest]]) {
+                ++_highest;
+              }
+            } else if (next_bucket == _node_num) {
+              _first[(*_bucket)[n]] = (*_next)[n];
+              _prev->set((*_next)[n], INVALID);
+
+              std::list<std::list<int> >::iterator new_set =
+                _sets.insert(--_sets.end(), std::list<int>());
+
+              new_set->push_front(bucket_num);
+              _bucket->set(n, bucket_num);
+              _first[bucket_num] = _last[bucket_num] = n;
+              _next->set(n, INVALID);
+              _prev->set(n, INVALID);
+              _dormant[bucket_num] = true;
+              ++bucket_num;
+
+              while (_highest != _sets.back().end() &&
+                     !(*_active)[_first[*_highest]]) {
+                ++_highest;
+              }
+            } else {
+              _first[*_highest] = (*_next)[n];
+              _prev->set((*_next)[n], INVALID);
+
+              while (next_bucket != *_highest) {
+                --_highest;
+              }
+
+              if (_highest == _sets.back().begin()) {
+                _sets.back().push_front(bucket_num);
+                _dormant[bucket_num] = false;
+                _first[bucket_num] = _last[bucket_num] = INVALID;
+                ++bucket_num;
+              }
+              --_highest;
+
+              _bucket->set(n, *_highest);
+              _next->set(n, _first[*_highest]);
+              if (_first[*_highest] != INVALID) {
+                _prev->set(_first[*_highest], n);
+              } else {
+                _last[*_highest] = n;
+              }
+              _first[*_highest] = n;
+            }
+          } else {
+
+            deactivate(n);
+            if (!(*_active)[_first[*_highest]]) {
+              ++_highest;
+              if (_highest != _sets.back().end() &&
+                  !(*_active)[_first[*_highest]]) {
+                _highest = _sets.back().end();
+              }
+            }
+          }
+        }
+
+        if ((*_excess)[target] < _min_cut) {
+          _min_cut = (*_excess)[target];
+          for (NodeIt i(_graph); i != INVALID; ++i) {
+            _min_cut_map->set(i, true);
+          }
+          for (std::list<int>::iterator it = _sets.back().begin();
+               it != _sets.back().end(); ++it) {
+            Node n = _first[*it];
+            while (n != INVALID) {
+              _min_cut_map->set(n, false);
+              n = (*_next)[n];
+            }
+          }
+        }
+
+        {
+          Node new_target;
+          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
+            if ((*_next)[target] == INVALID) {
+              _last[(*_bucket)[target]] = (*_prev)[target];
+              new_target = (*_prev)[target];
+            } else {
+              _prev->set((*_next)[target], (*_prev)[target]);
+              new_target = (*_next)[target];
+            }
+            if ((*_prev)[target] == INVALID) {
+              _first[(*_bucket)[target]] = (*_next)[target];
+            } else {
+              _next->set((*_prev)[target], (*_next)[target]);
+            }
+          } else {
+            _sets.back().pop_back();
+            if (_sets.back().empty()) {
+              _sets.pop_back();
+              if (_sets.empty())
+                break;
+              for (std::list<int>::iterator it = _sets.back().begin();
+                   it != _sets.back().end(); ++it) {
+                _dormant[*it] = false;
+              }
+            }
+            new_target = _last[_sets.back().back()];
+          }
+
+          _bucket->set(target, 0);
+
+          _source_set->set(target, true);
+          for (OutArcIt a(_graph, target); a != INVALID; ++a) {
+            Value rem = (*_capacity)[a] - (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            Node v = _graph.target(a);
+            if (!(*_active)[v] && !(*_source_set)[v]) {
+              activate(v);
+            }
+            _excess->set(v, (*_excess)[v] + rem);
+            _flow->set(a, (*_capacity)[a]);
+          }
+
+          for (InArcIt a(_graph, target); a != INVALID; ++a) {
+            Value rem = (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            Node v = _graph.source(a);
+            if (!(*_active)[v] && !(*_source_set)[v]) {
+              activate(v);
+            }
+            _excess->set(v, (*_excess)[v] + rem);
+            _flow->set(a, 0);
+          }
+
+          target = new_target;
+          if ((*_active)[target]) {
+            deactivate(target);
+          }
+
+          _highest = _sets.back().begin();
+          while (_highest != _sets.back().end() &&
+                 !(*_active)[_first[*_highest]]) {
+            ++_highest;
+          }
+        }
+      }
+    }
+
+    void findMinCutIn() {
+
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _excess->set(n, 0);
+      }
+
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _flow->set(a, 0);
+      }
+
+      int bucket_num = 1;
+
+      {
+        typename Digraph::template NodeMap<bool> reached(_graph, false);
+
+        reached.set(_source, true);
+
+        bool first_set = true;
+
+        for (NodeIt t(_graph); t != INVALID; ++t) {
+          if (reached[t]) continue;
+          _sets.push_front(std::list<int>());
+          _sets.front().push_front(bucket_num);
+          _dormant[bucket_num] = !first_set;
+
+          _bucket->set(t, bucket_num);
+          _first[bucket_num] = _last[bucket_num] = t;
+          _next->set(t, INVALID);
+          _prev->set(t, INVALID);
+
+          ++bucket_num;
+
+          std::vector<Node> queue;
+          queue.push_back(t);
+          reached.set(t, true);
+
+          while (!queue.empty()) {
+            _sets.front().push_front(bucket_num);
+            _dormant[bucket_num] = !first_set;
+            _first[bucket_num] = _last[bucket_num] = INVALID;
+
+            std::vector<Node> nqueue;
+            for (int i = 0; i < int(queue.size()); ++i) {
+              Node n = queue[i];
+              for (OutArcIt a(_graph, n); a != INVALID; ++a) {
+                Node u = _graph.target(a);
+                if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
+                  reached.set(u, true);
+                  addItem(u, bucket_num);
+                  nqueue.push_back(u);
+                }
+              }
+            }
+            queue.swap(nqueue);
+            ++bucket_num;
+          }
+          _sets.front().pop_front();
+          --bucket_num;
+          first_set = false;
+        }
+
+        _bucket->set(_source, 0);
+        _dormant[0] = true;
+      }
+      _source_set->set(_source, true);
+
+      Node target = _last[_sets.back().back()];
+      {
+        for (InArcIt a(_graph, _source); a != INVALID; ++a) {
+          if (_tolerance.positive((*_capacity)[a])) {
+            Node u = _graph.source(a);
+            _flow->set(a, (*_capacity)[a]);
+            _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
+            if (!(*_active)[u] && u != _source) {
+              activate(u);
+            }
+          }
+        }
+        if ((*_active)[target]) {
+          deactivate(target);
+        }
+
+        _highest = _sets.back().begin();
+        while (_highest != _sets.back().end() &&
+               !(*_active)[_first[*_highest]]) {
+          ++_highest;
+        }
+      }
+
+
+      while (true) {
+        while (_highest != _sets.back().end()) {
+          Node n = _first[*_highest];
+          Value excess = (*_excess)[n];
+          int next_bucket = _node_num;
+
+          int under_bucket;
+          if (++std::list<int>::iterator(_highest) == _sets.back().end()) {
+            under_bucket = -1;
+          } else {
+            under_bucket = *(++std::list<int>::iterator(_highest));
+          }
+
+          for (InArcIt a(_graph, n); a != INVALID; ++a) {
+            Node v = _graph.source(a);
+            if (_dormant[(*_bucket)[v]]) continue;
+            Value rem = (*_capacity)[a] - (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            if ((*_bucket)[v] == under_bucket) {
+              if (!(*_active)[v] && v != target) {
+                activate(v);
+              }
+              if (!_tolerance.less(rem, excess)) {
+                _flow->set(a, (*_flow)[a] + excess);
+                _excess->set(v, (*_excess)[v] + excess);
+                excess = 0;
+                goto no_more_push;
+              } else {
+                excess -= rem;
+                _excess->set(v, (*_excess)[v] + rem);
+                _flow->set(a, (*_capacity)[a]);
+              }
+            } else if (next_bucket > (*_bucket)[v]) {
+              next_bucket = (*_bucket)[v];
+            }
+          }
+
+          for (OutArcIt a(_graph, n); a != INVALID; ++a) {
+            Node v = _graph.target(a);
+            if (_dormant[(*_bucket)[v]]) continue;
+            Value rem = (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            if ((*_bucket)[v] == under_bucket) {
+              if (!(*_active)[v] && v != target) {
+                activate(v);
+              }
+              if (!_tolerance.less(rem, excess)) {
+                _flow->set(a, (*_flow)[a] - excess);
+                _excess->set(v, (*_excess)[v] + excess);
+                excess = 0;
+                goto no_more_push;
+              } else {
+                excess -= rem;
+                _excess->set(v, (*_excess)[v] + rem);
+                _flow->set(a, 0);
+              }
+            } else if (next_bucket > (*_bucket)[v]) {
+              next_bucket = (*_bucket)[v];
+            }
+          }
+
+        no_more_push:
+
+          _excess->set(n, excess);
+
+          if (excess != 0) {
+            if ((*_next)[n] == INVALID) {
+              typename std::list<std::list<int> >::iterator new_set =
+                _sets.insert(--_sets.end(), std::list<int>());
+              new_set->splice(new_set->end(), _sets.back(),
+                              _sets.back().begin(), ++_highest);
+              for (std::list<int>::iterator it = new_set->begin();
+                   it != new_set->end(); ++it) {
+                _dormant[*it] = true;
+              }
+              while (_highest != _sets.back().end() &&
+                     !(*_active)[_first[*_highest]]) {
+                ++_highest;
+              }
+            } else if (next_bucket == _node_num) {
+              _first[(*_bucket)[n]] = (*_next)[n];
+              _prev->set((*_next)[n], INVALID);
+
+              std::list<std::list<int> >::iterator new_set =
+                _sets.insert(--_sets.end(), std::list<int>());
+
+              new_set->push_front(bucket_num);
+              _bucket->set(n, bucket_num);
+              _first[bucket_num] = _last[bucket_num] = n;
+              _next->set(n, INVALID);
+              _prev->set(n, INVALID);
+              _dormant[bucket_num] = true;
+              ++bucket_num;
+
+              while (_highest != _sets.back().end() &&
+                     !(*_active)[_first[*_highest]]) {
+                ++_highest;
+              }
+            } else {
+              _first[*_highest] = (*_next)[n];
+              _prev->set((*_next)[n], INVALID);
+
+              while (next_bucket != *_highest) {
+                --_highest;
+              }
+              if (_highest == _sets.back().begin()) {
+                _sets.back().push_front(bucket_num);
+                _dormant[bucket_num] = false;
+                _first[bucket_num] = _last[bucket_num] = INVALID;
+                ++bucket_num;
+              }
+              --_highest;
+
+              _bucket->set(n, *_highest);
+              _next->set(n, _first[*_highest]);
+              if (_first[*_highest] != INVALID) {
+                _prev->set(_first[*_highest], n);
+              } else {
+                _last[*_highest] = n;
+              }
+              _first[*_highest] = n;
+            }
+          } else {
+
+            deactivate(n);
+            if (!(*_active)[_first[*_highest]]) {
+              ++_highest;
+              if (_highest != _sets.back().end() &&
+                  !(*_active)[_first[*_highest]]) {
+                _highest = _sets.back().end();
+              }
+            }
+          }
+        }
+
+        if ((*_excess)[target] < _min_cut) {
+          _min_cut = (*_excess)[target];
+          for (NodeIt i(_graph); i != INVALID; ++i) {
+            _min_cut_map->set(i, false);
+          }
+          for (std::list<int>::iterator it = _sets.back().begin();
+               it != _sets.back().end(); ++it) {
+            Node n = _first[*it];
+            while (n != INVALID) {
+              _min_cut_map->set(n, true);
+              n = (*_next)[n];
+            }
+          }
+        }
+
+        {
+          Node new_target;
+          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
+            if ((*_next)[target] == INVALID) {
+              _last[(*_bucket)[target]] = (*_prev)[target];
+              new_target = (*_prev)[target];
+            } else {
+              _prev->set((*_next)[target], (*_prev)[target]);
+              new_target = (*_next)[target];
+            }
+            if ((*_prev)[target] == INVALID) {
+              _first[(*_bucket)[target]] = (*_next)[target];
+            } else {
+              _next->set((*_prev)[target], (*_next)[target]);
+            }
+          } else {
+            _sets.back().pop_back();
+            if (_sets.back().empty()) {
+              _sets.pop_back();
+              if (_sets.empty())
+                break;
+              for (std::list<int>::iterator it = _sets.back().begin();
+                   it != _sets.back().end(); ++it) {
+                _dormant[*it] = false;
+              }
+            }
+            new_target = _last[_sets.back().back()];
+          }
+
+          _bucket->set(target, 0);
+
+          _source_set->set(target, true);
+          for (InArcIt a(_graph, target); a != INVALID; ++a) {
+            Value rem = (*_capacity)[a] - (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            Node v = _graph.source(a);
+            if (!(*_active)[v] && !(*_source_set)[v]) {
+              activate(v);
+            }
+            _excess->set(v, (*_excess)[v] + rem);
+            _flow->set(a, (*_capacity)[a]);
+          }
+
+          for (OutArcIt a(_graph, target); a != INVALID; ++a) {
+            Value rem = (*_flow)[a];
+            if (!_tolerance.positive(rem)) continue;
+            Node v = _graph.target(a);
+            if (!(*_active)[v] && !(*_source_set)[v]) {
+              activate(v);
+            }
+            _excess->set(v, (*_excess)[v] + rem);
+            _flow->set(a, 0);
+          }
+
+          target = new_target;
+          if ((*_active)[target]) {
+            deactivate(target);
+          }
+
+          _highest = _sets.back().begin();
+          while (_highest != _sets.back().end() &&
+                 !(*_active)[_first[*_highest]]) {
+            ++_highest;
+          }
+        }
+      }
+    }
+
+  public:
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// \n
+    /// If you need more control on the execution,
+    /// first you must call \ref init(), then the \ref calculateIn() or
+    /// \ref calculateIn() functions.
+
+    /// @{
+
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures. It creates
+    /// the maps, residual graph adaptors and some bucket structures
+    /// for the algorithm.
+    void init() {
+      init(NodeIt(_graph));
+    }
+
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures. It creates
+    /// the maps, residual graph adaptor and some bucket structures
+    /// for the algorithm. Node \c source  is used as the push-relabel
+    /// algorithm's source.
+    void init(const Node& source) {
+      _source = source;
+
+      _node_num = countNodes(_graph);
+
+      _first.resize(_node_num + 1);
+      _last.resize(_node_num + 1);
+
+      _dormant.resize(_node_num + 1);
+
+      if (!_flow) {
+        _flow = new FlowMap(_graph);
+      }
+      if (!_next) {
+        _next = new typename Digraph::template NodeMap<Node>(_graph);
+      }
+      if (!_prev) {
+        _prev = new typename Digraph::template NodeMap<Node>(_graph);
+      }
+      if (!_active) {
+        _active = new typename Digraph::template NodeMap<bool>(_graph);
+      }
+      if (!_bucket) {
+        _bucket = new typename Digraph::template NodeMap<int>(_graph);
+      }
+      if (!_excess) {
+        _excess = new ExcessMap(_graph);
+      }
+      if (!_source_set) {
+        _source_set = new SourceSetMap(_graph);
+      }
+      if (!_min_cut_map) {
+        _min_cut_map = new MinCutMap(_graph);
+      }
+
+      _min_cut = std::numeric_limits<Value>::max();
+    }
+
+
+    /// \brief Calculates a minimum cut with \f$ source \f$ on the
+    /// source-side.
+    ///
+    /// Calculates a minimum cut with \f$ source \f$ on the
+    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source
+    /// \in X \f$ and minimal out-degree).
+    void calculateOut() {
+      findMinCutOut();
+    }
+
+    /// \brief Calculates a minimum cut with \f$ source \f$ on the
+    /// target-side.
+    ///
+    /// Calculates a minimum cut with \f$ source \f$ on the
+    /// target-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source
+    /// \in X \f$ and minimal out-degree).
+    void calculateIn() {
+      findMinCutIn();
+    }
+
+
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm. It finds nodes \c source and \c target
+    /// arbitrarily and then calls \ref init(), \ref calculateOut()
+    /// and \ref calculateIn().
+    void run() {
+      init();
+      calculateOut();
+      calculateIn();
+    }
+
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm. It uses the given \c source node, finds a
+    /// proper \c target and then calls the \ref init(), \ref
+    /// calculateOut() and \ref calculateIn().
+    void run(const Node& s) {
+      init(s);
+      calculateOut();
+      calculateIn();
+    }
+
+    /// @}
+
+    /// \name Query Functions
+    /// The result of the %HaoOrlin algorithm
+    /// can be obtained using these functions.
+    /// \n
+    /// Before using these functions, either \ref run(), \ref
+    /// calculateOut() or \ref calculateIn() must be called.
+
+    /// @{
+
+    /// \brief Returns the value of the minimum value cut.
+    ///
+    /// Returns the value of the minimum value cut.
+    Value minCutValue() const {
+      return _min_cut;
+    }
+
+
+    /// \brief Returns a minimum cut.
+    ///
+    /// Sets \c nodeMap to the characteristic vector of a minimum
+    /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
+    /// with minimal out-degree (i.e. \c nodeMap will be true exactly
+    /// for the nodes of \f$ X \f$).  \pre nodeMap should be a
+    /// bool-valued node-map.
+    template <typename NodeMap>
+    Value minCutMap(NodeMap& nodeMap) const {
+      for (NodeIt it(_graph); it != INVALID; ++it) {
+        nodeMap.set(it, (*_min_cut_map)[it]);
+      }
+      return _min_cut;
+    }
+
+    /// @}
+
+  }; //class HaoOrlin
+
+
+} //namespace lemon
+
+#endif //LEMON_HAO_ORLIN_H
