# HG changeset patch
# User deba
# Date 1159529790 0
# Node ID bb3d5e6f9fcbbbaa0109d522285bd12fe50bfc37
# Parent  f973894da54e5a17bcd8d74d3951057ea04a06d8
Doc fix

diff -r f973894da54e -r bb3d5e6f9fcb lemon/hao_orlin.h
--- a/lemon/hao_orlin.h	Fri Sep 29 11:26:29 2006 +0000
+++ b/lemon/hao_orlin.h	Fri Sep 29 11:36:30 2006 +0000
@@ -1,7 +1,9 @@
 /* -*- C++ -*-
- * lemon/hao_orlin.h - Part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
  *
  * Permission to use, modify and distribute this software is granted
@@ -29,30 +31,44 @@
 
 /// \file
 /// \ingroup flowalgs
-/// Implementation of the Hao-Orlin algorithms class for testing network 
+/// \brief Implementation of the Hao-Orlin algorithm.
+///
+/// Implementation of the HaoOrlin algorithms class for testing network 
 /// reliability.
 
 namespace lemon {
 
-  /// \addtogroup flowalgs
-  /// @{                                                   
-
-  /// %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
+  /// \ingroup flowalgs
+  ///
+  /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
   ///
   /// Hao-Orlin calculates the minimum cut in directed graphs. It
-  /// separates the nodes of the graph into two disjoint sets and the
-  /// summary of the edge capacities go from the first set to the
-  /// second set is the minimum.  The algorithm is a modified
-  /// push-relabel preflow algorithm and it calculates the minimum cat
-  /// in \f$ O(n^3) \f$ time. The purpose of such algorithm is testing
-  /// network reliability. For sparse undirected graph you can use the
-  /// algorithm of Nagamochi and Ibraki which solves the undirected
-  /// problem in \f$ O(n^3) \f$ time. 
+  /// separates the nodes of the graph into two disjoint sets, 
+  /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum
+  /// cut if the summary of the edge capacities which source is in
+  /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the
+  /// minimum.  The algorithm is a modified push-relabel preflow
+  /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$
+  /// time. The purpose of such algorithm is testing network
+  /// reliability. For sparse undirected graph you can use the
+  /// algorithm of Nagamochi and Ibaraki which solves the undirected
+  /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the
+  /// MinCut algorithm class.
+  ///
+  /// \param _Graph 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 _Graph::EdgeMap<int>.
+  /// \param _Tolerance is the handler of the inexact computation. The
+  /// default type for it is Tolerance<typename CapacityMap::Value>.
   ///
   /// \author Attila Bernath and Balazs Dezso
+#ifdef DOXYGEN
+  template <typename _Graph, typename _CapacityMap, typename _Tolerance>
+#else
   template <typename _Graph,
 	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,
             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
+#endif
   class HaoOrlin {
   protected:
 
@@ -70,6 +86,7 @@
     typedef typename Graph::InEdgeIt InEdgeIt;
 
     const Graph* _graph;
+
     const CapacityMap* _capacity;
 
     typedef typename Graph::template EdgeMap<Value> FlowMap;
@@ -80,18 +97,25 @@
     int _node_num;
 
     typedef ResGraphAdaptor<const Graph, Value, CapacityMap, 
-                            FlowMap, Tolerance> ResGraph;
-    typedef typename ResGraph::Node ResNode;
-    typedef typename ResGraph::NodeIt ResNodeIt;
-    typedef typename ResGraph::EdgeIt ResEdgeIt;
-    typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
-    typedef typename ResGraph::Edge ResEdge;
-    typedef typename ResGraph::InEdgeIt ResInEdgeIt;
+                            FlowMap, Tolerance> OutResGraph;
+    typedef typename OutResGraph::Edge OutResEdge;
+    
+    OutResGraph* _out_res_graph;
 
-    ResGraph* _res_graph;
+    typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
+    OutCurrentEdgeMap* _out_current_edge;  
 
-    typedef typename Graph::template NodeMap<ResEdge> CurrentArcMap;
-    CurrentArcMap* _current_arc;  
+    typedef RevGraphAdaptor<const Graph> RevGraph;
+    RevGraph* _rev_graph;
+
+    typedef ResGraphAdaptor<const RevGraph, Value, CapacityMap, 
+                            FlowMap, Tolerance> InResGraph;
+    typedef typename InResGraph::Edge InResEdge;
+    
+    InResGraph* _in_res_graph;
+
+    typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
+    InCurrentEdgeMap* _in_current_edge;  
 
 
     typedef IterableBoolMap<Graph, Node> WakeMap;
@@ -124,23 +148,37 @@
 
   public: 
 
+    /// \brief Constructor
+    ///
+    /// Constructor of the algorithm class. 
     HaoOrlin(const Graph& graph, const CapacityMap& capacity, 
              const Tolerance& tolerance = Tolerance()) :
       _graph(&graph), _capacity(&capacity), 
-      _preflow(0), _source(), _target(), _res_graph(0), _current_arc(0),
+      _preflow(0), _source(), _target(), 
+      _out_res_graph(0), _out_current_edge(0),
+      _rev_graph(0), _in_res_graph(0), _in_current_edge(0),
       _wake(0),_dist(0), _excess(0), _source_set(0), 
       _highest_active(), _active_nodes(), _dormant_max(), _dormant(), 
       _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}
 
     ~HaoOrlin() {
-      if (_res_graph) {
-        delete _res_graph;
-      }
       if (_min_cut_map) {
         delete _min_cut_map;
       } 
-      if (_current_arc) {
-        delete _current_arc;
+      if (_in_current_edge) {
+        delete _in_current_edge;
+      }
+      if (_in_res_graph) {
+        delete _in_res_graph;
+      }
+      if (_rev_graph) {
+        delete _rev_graph;
+      }
+      if (_out_current_edge) {
+        delete _out_current_edge;
+      }
+      if (_out_res_graph) {
+        delete _out_res_graph;
       }
       if (_source_set) {
         delete _source_set;
@@ -161,8 +199,103 @@
     
   private:
     
-    void relabel(Node i) {
-      int k = (*_dist)[i];
+    template <typename ResGraph, typename EdgeMap>
+    void findMinCut(const Node& target, bool out, 
+                    ResGraph& res_graph, EdgeMap& current_edge) {
+      typedef typename ResGraph::Edge ResEdge;
+      typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
+
+      for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
+        (*_preflow)[it] = 0;      
+      }
+      for (NodeIt it(*_graph); it != INVALID; ++it) {
+        (*_wake)[it] = true;
+        (*_dist)[it] = 1;
+        (*_excess)[it] = 0;
+        (*_source_set)[it] = false;
+
+        res_graph.firstOut(current_edge[it], it);
+      }
+
+      _target = target;
+      (*_dist)[target] = 0;
+
+      for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
+        Value delta = res_graph.rescap(it);
+        if (!_tolerance.positive(delta)) continue;
+        
+        (*_excess)[res_graph.source(it)] -= delta;
+        res_graph.augment(it, delta);
+        Node a = res_graph.target(it);
+        if (!_tolerance.positive((*_excess)[a]) && 
+            (*_wake)[a] && a != _target) {
+          _active_nodes[(*_dist)[a]].push_front(a);
+          if (_highest_active < (*_dist)[a]) {
+            _highest_active = (*_dist)[a];
+          }
+        }
+        (*_excess)[a] += delta;
+      }
+
+      _dormant[0].push_front(_source);
+      (*_source_set)[_source] = true;
+      _dormant_max = 0;
+      (*_wake)[_source] = false;
+
+      _level_size[0] = 1;
+      _level_size[1] = _node_num - 1;
+
+      do {
+	Node n;
+	while ((n = findActiveNode()) != INVALID) {
+	  ResEdge e;
+	  while (_tolerance.positive((*_excess)[n]) && 
+                 (e = findAdmissibleEdge(n, res_graph, current_edge)) 
+                 != INVALID){
+	    Value delta;
+	    if ((*_excess)[n] < res_graph.rescap(e)) {
+	      delta = (*_excess)[n];
+	    } else {
+	      delta = res_graph.rescap(e);
+	      res_graph.nextOut(current_edge[n]);
+	    }
+            if (!_tolerance.positive(delta)) continue;
+	    res_graph.augment(e, delta);
+	    (*_excess)[res_graph.source(e)] -= delta;
+	    Node a = res_graph.target(e);
+	    if (!_tolerance.positive((*_excess)[a]) && a != _target) {
+	      _active_nodes[(*_dist)[a]].push_front(a);
+	    }
+	    (*_excess)[a] += delta;
+	  }
+	  if (_tolerance.positive((*_excess)[n])) {
+	    relabel(n, res_graph, current_edge);
+          }
+	}
+
+	Value current_value = cutValue(out);
+ 	if (_min_cut > current_value){
+          if (out) {
+            for (NodeIt it(*_graph); it != INVALID; ++it) {
+              _min_cut_map->set(it, !(*_wake)[it]);
+            } 
+          } else {
+            for (NodeIt it(*_graph); it != INVALID; ++it) {
+              _min_cut_map->set(it, (*_wake)[it]);
+            } 
+          }
+
+	  _min_cut = current_value;
+ 	}
+
+      } while (selectNewSink(res_graph));
+    }
+
+    template <typename ResGraph, typename EdgeMap>
+    void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
+      typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
+
+      int k = (*_dist)[n];
       if (_level_size[k] == 1) {
 	++_dormant_max;
 	for (NodeIt it(*_graph); it != INVALID; ++it) {
@@ -173,39 +306,34 @@
 	  }
 	}
 	--_highest_active;
-      } else {
-	ResOutEdgeIt e(*_res_graph, i);
-	while (e != INVALID && !(*_wake)[_res_graph->target(e)]) {
-	  ++e;
-	}
-
-	if (e == INVALID){
+      } else {	
+        int new_dist = _node_num;
+        for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
+          Node t = res_graph.target(e);
+          if ((*_wake)[t] && new_dist > (*_dist)[t]) {
+            new_dist = (*_dist)[t];
+          }
+        }
+        if (new_dist == _node_num) {
 	  ++_dormant_max;
-	  (*_wake)[i] = false;
-	  _dormant[_dormant_max].push_front(i);
-	  --_level_size[(*_dist)[i]];
-	} else{	    
-	  Node j = _res_graph->target(e);
-	  int new_dist = (*_dist)[j];
-	  ++e;
-	  while (e != INVALID){
-	    Node j = _res_graph->target(e);
-	    if ((*_wake)[j] && new_dist > (*_dist)[j]) {
-	      new_dist = (*_dist)[j];
-            }
-	    ++e;
-	  }
-	  --_level_size[(*_dist)[i]];
-	  (*_dist)[i] = new_dist + 1;
-	  _highest_active = (*_dist)[i];
-	  _active_nodes[_highest_active].push_front(i);
-	  ++_level_size[(*_dist)[i]];
-	  _res_graph->firstOut((*_current_arc)[i], i);
+	  (*_wake)[n] = false;
+	  _dormant[_dormant_max].push_front(n);
+	  --_level_size[(*_dist)[n]];
+	} else {	    
+	  --_level_size[(*_dist)[n]];
+	  (*_dist)[n] = new_dist + 1;
+	  _highest_active = (*_dist)[n];
+	  _active_nodes[_highest_active].push_front(n);
+	  ++_level_size[(*_dist)[n]];
+	  res_graph.firstOut(current_edge[n], n);
 	}
       }
     }
 
-    bool selectNewSink(){
+    template <typename ResGraph>
+    bool selectNewSink(ResGraph& res_graph) {
+      typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
+
       Node old_target = _target;
       (*_wake)[_target] = false;
       --_level_size[(*_dist)[_target]];
@@ -249,9 +377,21 @@
 	}
       }
 
-      for (ResOutEdgeIt e(*_res_graph, old_target); e!=INVALID; ++e){
-	if (!(*_source_set)[_res_graph->target(e)]){
-	  push(e, _res_graph->rescap(e));
+      for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
+	if (!(*_source_set)[res_graph.target(e)]) {
+          Value delta = res_graph.rescap(e);
+          if (!_tolerance.positive(delta)) continue;
+          res_graph.augment(e, delta);
+          (*_excess)[res_graph.source(e)] -= delta;
+          Node a = res_graph.target(e);
+          if (!_tolerance.positive((*_excess)[a]) && 
+              (*_wake)[a] && a != _target) {
+            _active_nodes[(*_dist)[a]].push_front(a);
+            if (_highest_active < (*_dist)[a]) {
+              _highest_active = (*_dist)[a];
+            }
+          }
+          (*_excess)[a] += delta;
 	}
       }
       
@@ -271,54 +411,64 @@
       }
     }
 
-    ResEdge findAdmissibleEdge(const Node& n){
-      ResEdge e = (*_current_arc)[n];
+    template <typename ResGraph, typename EdgeMap>
+    typename ResGraph::Edge findAdmissibleEdge(const Node& n, 
+                                               ResGraph& res_graph, 
+                                               EdgeMap& current_edge) {
+      typedef typename ResGraph::Edge ResEdge;
+      ResEdge e = current_edge[n];
       while (e != INVALID && 
-             ((*_dist)[n] <= (*_dist)[_res_graph->target(e)] || 
-              !(*_wake)[_res_graph->target(e)])) {
-	_res_graph->nextOut(e);
+             ((*_dist)[n] <= (*_dist)[res_graph.target(e)] || 
+              !(*_wake)[res_graph.target(e)])) {
+	res_graph.nextOut(e);
       }
       if (e != INVALID) {
-	(*_current_arc)[n] = e;	
+	current_edge[n] = e;	
 	return e;
       } else {
 	return INVALID;
       }
     }
 
-    void push(ResEdge& e,const Value& delta){
-      _res_graph->augment(e, delta);
-      if (!_tolerance.positive(delta)) return;
-      
-      (*_excess)[_res_graph->source(e)] -= delta;
-      Node a = _res_graph->target(e);
-      if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) {
-	_active_nodes[(*_dist)[a]].push_front(a);
-	if (_highest_active < (*_dist)[a]) {
-	  _highest_active = (*_dist)[a];
+    Value cutValue(bool out) {
+      Value value = 0;
+      if (out) {
+        for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
+          for (InEdgeIt e(*_graph, it); e != INVALID; ++e) {
+            if (!(*_wake)[_graph->source(e)]){
+              value += (*_capacity)[e];
+            }	
+          }
+        }
+      } else {
+        for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
+          for (OutEdgeIt e(*_graph, it); e != INVALID; ++e) {
+            if (!(*_wake)[_graph->target(e)]){
+              value += (*_capacity)[e];
+            }	
+          }
         }
       }
-      (*_excess)[a] += delta;
+      return value;
     }
-    
-    Value cutValue() {
-      Value value = 0;
-      for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
-	for (InEdgeIt e(*_graph, it); e != INVALID; ++e) {
-	  if (!(*_wake)[_graph->source(e)]){
-	    value += (*_capacity)[e];
-	  }	
-	}
-      }
-      return value;
-    }    
+
 
   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 adaptor and some bucket structures
+    /// the maps, residual graph adaptors and some bucket structures
     /// for the algorithm. 
     void init() {
       init(NodeIt(*_graph));
@@ -353,25 +503,34 @@
       if (!_source_set) {
         _source_set = new SourceSetMap(*_graph);
       }
-      if (!_current_arc) {
-        _current_arc = new CurrentArcMap(*_graph);
+      if (!_out_res_graph) {
+        _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
+      }
+      if (!_out_current_edge) {
+        _out_current_edge = new OutCurrentEdgeMap(*_graph);
+      }
+      if (!_rev_graph) {
+        _rev_graph = new RevGraph(*_graph);
+      }
+      if (!_in_res_graph) {
+        _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
+      }
+      if (!_in_current_edge) {
+        _in_current_edge = new InCurrentEdgeMap(*_graph);
       }
       if (!_min_cut_map) {
         _min_cut_map = new MinCutMap(*_graph);
       }
-      if (!_res_graph) {
-        _res_graph = new ResGraph(*_graph, *_capacity, *_preflow);
-      }
 
       _min_cut = std::numeric_limits<Value>::max();
     }
 
 
     /// \brief Calculates the minimum cut with the \c source node
-    /// in the first partition.
+    /// in the \f$ V_{out} \f$.
     ///
     /// Calculates the minimum cut with the \c source node
-    /// in the first partition.
+    /// in the \f$ V_{out} \f$.
     void calculateOut() {
       for (NodeIt it(*_graph); it != INVALID; ++it) {
         if (it != _source) {
@@ -382,75 +541,20 @@
     }
 
     /// \brief Calculates the minimum cut with the \c source node
-    /// in the first partition.
+    /// in the \f$ V_{out} \f$.
     ///
     /// Calculates the minimum cut with the \c source node
-    /// in the first partition. The \c target is the initial target
+    /// in the \f$ V_{out} \f$. The \c target is the initial target
     /// for the push-relabel algorithm.
     void calculateOut(const Node& target) {
-      for (NodeIt it(*_graph); it != INVALID; ++it) {
-        (*_wake)[it] = true;
-        (*_dist)[it] = 1;
-        (*_excess)[it] = 0;
-        (*_source_set)[it] = false;
-
-        _res_graph->firstOut((*_current_arc)[it], it);
-      }
-
-      _target = target;
-      (*_dist)[target] = 0;
-
-      for (ResOutEdgeIt it(*_res_graph, _source); it != INVALID; ++it) {
-	push(it, _res_graph->rescap(it));
-      }
-
-      _dormant[0].push_front(_source);
-      (*_source_set)[_source] = true;
-      _dormant_max = 0;
-      (*_wake)[_source]=false;
-
-      _level_size[0] = 1;
-      _level_size[1] = _node_num - 1;
-
-      do {
-	Node n;
-	while ((n = findActiveNode()) != INVALID) {
-	  ResEdge e;
-	  while (_tolerance.positive((*_excess)[n]) && 
-                 (e = findAdmissibleEdge(n)) != INVALID){
-	    Value delta;
-	    if ((*_excess)[n] < _res_graph->rescap(e)) {
-	      delta = (*_excess)[n];
-	    } else {
-	      delta = _res_graph->rescap(e);
-	      _res_graph->nextOut((*_current_arc)[n]);
-	    }
-            if (!_tolerance.positive(delta)) continue;
-	    _res_graph->augment(e, delta);
-	    (*_excess)[_res_graph->source(e)] -= delta;
-	    Node a = _res_graph->target(e);
-	    if (!_tolerance.positive((*_excess)[a]) && a != _target) {
-	      _active_nodes[(*_dist)[a]].push_front(a);
-	    }
-	    (*_excess)[a] += delta;
-	  }
-	  if (_tolerance.positive((*_excess)[n])) {
-	    relabel(n);
-          }
-	}
-
-	Value current_value = cutValue();
- 	if (_min_cut > current_value){
-	  for (NodeIt it(*_graph); it != INVALID; ++it) {
-            _min_cut_map->set(it, !(*_wake)[it]);
-	  }
-
-	  _min_cut = current_value;
- 	}
-
-      } while (selectNewSink());
+      findMinCut(target, true, *_out_res_graph, *_out_current_edge);
     }
 
+    /// \brief Calculates the minimum cut with the \c source node
+    /// in the \f$ V_{in} \f$.
+    ///
+    /// Calculates the minimum cut with the \c source node
+    /// in the \f$ V_{in} \f$.
     void calculateIn() {
       for (NodeIt it(*_graph); it != INVALID; ++it) {
         if (it != _source) {
@@ -460,40 +564,70 @@
       }
     }
 
+    /// \brief Calculates the minimum cut with the \c source node
+    /// in the \f$ V_{in} \f$.
+    ///
+    /// Calculates the minimum cut with the \c source node
+    /// in the \f$ V_{in} \f$. The \c target is the initial target
+    /// for the push-relabel algorithm.
+    void calculateIn(const Node& target) {
+      findMinCut(target, false, *_in_res_graph, *_in_current_edge);
+    }
+
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm. It finds a proper \c source and \c target
+    /// and then calls the \ref init(), \ref calculateOut() and \ref
+    /// calculateIn().
     void run() {
       init();
       for (NodeIt it(*_graph); it != INVALID; ++it) {
         if (it != _source) {
-          startOut(it);
-          //          startIn(it);
+          calculateOut(it);
+          calculateIn(it);
           return;
         }
       }
     }
 
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm. It finds a proper \c target and then calls
+    /// the \ref init(), \ref calculateOut() and \ref calculateIn().
     void run(const Node& s) {
       init(s);
       for (NodeIt it(*_graph); it != INVALID; ++it) {
         if (it != _source) {
-          startOut(it);
-          //          startIn(it);
+          calculateOut(it);
+          calculateIn(it);
           return;
         }
       }
     }
 
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm. It just calls the \ref init() and then
+    /// \ref calculateOut() and \ref calculateIn().
     void run(const Node& s, const Node& t) {
-      init(s);
-      startOut(t);
-      startIn(t);
+      init(s); 
+      calculateOut(t);
+      calculateIn(t);
     }
+
+    /// @}
     
-    /// \brief Returns the value of the minimum value cut with node \c
-    /// source on the source side.
+    /// \name Query Functions The result of the %HaoOrlin algorithm
+    /// can be obtained using these functions.
+    /// \n
+    /// Before the use of 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 with node \c source
-    /// on the source side. This function can be called after running
-    /// \ref findMinCut.
+    /// Returns the value of the minimum value cut.
     Value minCut() const {
       return _min_cut;
     }
@@ -502,8 +636,8 @@
     /// \brief Returns a minimum value cut.
     ///
     /// Sets \c nodeMap to the characteristic vector of a minimum
-    /// value cut with node \c source on the source side. This
-    /// function can be called after running \ref findMinCut.  
+    /// value cut. The nodes in \f$ V_{out} \f$ will be set true and
+    /// the nodes in \f$ V_{in} \f$ will be set false. 
     /// \pre nodeMap should be a bool-valued node-map.
     template <typename NodeMap>
     Value minCut(NodeMap& nodeMap) const {
@@ -512,6 +646,8 @@
       }
       return minCut();
     }
+
+    /// @}
     
   }; //class HaoOrlin 
 
diff -r f973894da54e -r bb3d5e6f9fcb lemon/min_cut.h
--- a/lemon/min_cut.h	Fri Sep 29 11:26:29 2006 +0000
+++ b/lemon/min_cut.h	Fri Sep 29 11:36:30 2006 +0000
@@ -830,18 +830,19 @@
 
   /// \ingroup topology
   ///
-  /// \brief Calculates the min cut in an undirected graph.
+  /// \brief Calculates the minimum cut in an undirected graph.
   ///
-  /// Calculates the min cut in an undirected graph. 
-  /// The algorithm separates the graph's nodes into two partitions with the 
-  /// min sum of edge capacities between the two partitions. The
-  /// algorithm can be used to test the network reliability specifically
-  /// to test how many links have to be destroyed in the network to split it 
-  /// at least two distinict subnetwork.
+  /// Calculates the minimum cut in an undirected graph with the
+  /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
+  /// nodes into two partitions with the minimum sum of edge capacities
+  /// between the two partitions. The algorithm can be used to test
+  /// the network reliability specifically to test how many links have
+  /// to be destroyed in the network to split it at least two
+  /// distinict subnetwork.
   ///
   /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
-  /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
-  /// the neutral capacity map is used then it uses BucketHeap which
+  /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
+  /// \f$. When capacity map is neutral then it uses BucketHeap which
   /// results \f$ O(ne) \f$ time complexity.
 #ifdef DOXYGEN
   template <typename _Graph, typename _CapacityMap, typename _Traits>