Changeset 2225:bb3d5e6f9fcb in lemon-0.x for lemon

Timestamp:

09/29/06 13:36:30 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2965

Message:

Doc fix

Location:

lemon

Files:

• hao_orlin.h (modified) (19 diffs)
• min_cut.h (modified) (1 diff)

lemon/hao_orlin.h

@@ -1 +1 @@
 /* -*- 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).
  *
@@ -30 +32 @@
 /// \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:
@@ -71 +87 @@
 
     const Graph* _graph;
+
     const CapacityMap* _capacity;
 
@@ -81 +98 @@
 
     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;
-
-    ResGraph* _res_graph;
-
-    typedef typename Graph::template NodeMap<ResEdge> CurrentArcMap;
-    CurrentArcMap* _current_arc;  
+                            FlowMap, Tolerance> OutResGraph;
+    typedef typename OutResGraph::Edge OutResEdge;
+    
+    OutResGraph* _out_res_graph;
+
+    typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
+    OutCurrentEdgeMap* _out_current_edge;  
+
+    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;  
 
 
@@ -125 +149 @@
   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(), 
@@ -134 +163 @@
 
     ~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) {
@@ -162 +200 @@
   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;
@@ -174 +307 @@
         }
         --_highest_active;
-      } else {
-        ResOutEdgeIt e(*_res_graph, i);
-        while (e != INVALID && !(*_wake)[_res_graph->target(e)]) {
-          ++e;
+      } 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)[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);
         }
-
-        if (e == INVALID){
-          ++_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);
-        }
-      }
-    }
-
-    bool selectNewSink(){
+      }
+    }
+
+    template <typename ResGraph>
+    bool selectNewSink(ResGraph& res_graph) {
+      typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
+
       Node old_target = _target;
       (*_wake)[_target] = false;
@@ -250 +378 @@
       }
 
-      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;
         }
       }
@@ -272 +412 @@
     }
 
-    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 {
@@ -287 +431 @@
     }
 
-    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];
-        }
-      }
-      (*_excess)[a] += delta;
-    }
-    
-    Value cutValue() {
+    Value cutValue(bool out) {
       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];
-          }     
-        }
+      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];
+            }   
+          }
+        }
       }
       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() {
@@ -354 +504 @@
         _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();
@@ -369 +528 @@
 
     /// \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) {
@@ -383 +542 @@
 
     /// \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) {
@@ -461 +565 @@
     }
 
+    /// \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;
         }
@@ -472 +591 @@
     }
 
+    /// \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;
         }
@@ -483 +606 @@
     }
 
+    /// \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);
-    }
-    
-    /// \brief Returns the value of the minimum value cut with node \c
-    /// source on the source side.
+      init(s); 
+      calculateOut(t);
+      calculateIn(t);
+    }
+
+    /// @}
+    
+    /// \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;
@@ -503 +637 @@
     ///
     /// 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>
@@ -513 +647 @@
       return minCut();
     }
+
+    /// @}
     
   }; //class HaoOrlin 

lemon/min_cut.h

@@ -831 +831 @@
   /// \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