Changeset 2556:74c2c81055e1 in lemon-0.x

Timestamp:

01/13/08 11:32:14 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

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

Message:

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

Location:

lemon

Files:

• capacity_scaling.h (modified) (19 diffs)
• cycle_canceling.h (modified) (21 diffs)
• min_cost_flow.h (modified) (4 diffs)
• min_cost_max_flow.h (modified) (7 diffs)
• network_simplex.h (modified) (42 diffs)

lemon/capacity_scaling.h

@@ -23 +23 @@
 ///
 /// \file
-/// \brief The capacity scaling algorithm for finding a minimum cost
-/// flow.
+/// \brief The capacity scaling algorithm for finding a minimum cost flow.
 
 #include <lemon/graph_adaptor.h>
@@ -50 +49 @@
   ///
   /// \warning
-  /// - Edge capacities and costs should be nonnegative integers.
+  /// - Edge capacities and costs should be non-negative integers.
   ///   However \c CostMap::Value should be signed type.
   /// - Supply values should be signed integers.
@@ -67 +66 @@
   class CapacityScaling
   {
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    GRAPH_TYPEDEFS(typename Graph);
 
     typedef typename LowerMap::Value Lower;
@@ -78 +72 @@
     typedef typename CostMap::Value Cost;
     typedef typename SupplyMap::Value Supply;
-    typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
-    typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
+    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
+    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
     typedef typename Graph::template NodeMap<Edge> PredMap;
 
   public:
 
-    /// \brief Type to enable or disable capacity scaling.
+    /// Type to enable or disable capacity scaling.
     enum ScalingEnum {
       WITH_SCALING = 0,
@@ -90 +84 @@
     };
 
-    /// \brief The type of the flow map.
-    typedef CapacityRefMap FlowMap;
-    /// \brief The type of the potential map.
+    /// The type of the flow map.
+    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
+    /// The type of the potential map.
     typedef typename Graph::template NodeMap<Cost> PotentialMap;
 
@@ -111 +105 @@
     protected:
 
-      /// \brief The directed graph the algorithm runs on.
+      /// The directed graph the algorithm runs on.
       const Graph &graph;
 
-      /// \brief The flow map.
+      /// The flow map.
       const FlowMap &flow;
-      /// \brief The residual capacity map.
-      const CapacityRefMap &res_cap;
-      /// \brief The cost map.
+      /// The residual capacity map.
+      const CapacityEdgeMap &res_cap;
+      /// The cost map.
       const CostMap &cost;
-      /// \brief The excess map.
-      const SupplyRefMap &excess;
-
-      /// \brief The potential map.
+      /// The excess map.
+      const SupplyNodeMap &excess;
+
+      /// The potential map.
       PotentialMap &potential;
 
-      /// \brief The distance map.
+      /// The distance map.
       CostNodeMap dist;
-      /// \brief The map of predecessors edges.
+      /// The map of predecessors edges.
       PredMap &pred;
-      /// \brief The processed (i.e. permanently labeled) nodes.
+      /// The processed (i.e. permanently labeled) nodes.
       std::vector<Node> proc_nodes;
 
     public:
 
-      /// \brief The constructor of the class.
+      /// The constructor of the class.
       ResidualDijkstra( const Graph &_graph,
                         const FlowMap &_flow,
-                        const CapacityRefMap &_res_cap,
+                        const CapacityEdgeMap &_res_cap,
                         const CostMap &_cost,
                         const SupplyMap &_excess,
@@ -148 +142 @@
       {}
 
-      /// \brief Runs the algorithm from the given source node.
+      /// Runs the algorithm from the given source node.
       Node run(Node s, Capacity delta) {
         HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
@@ -223 +217 @@
   protected:
 
-    /// \brief The directed graph the algorithm runs on.
+    /// The directed graph the algorithm runs on.
     const Graph &graph;
-    /// \brief The original lower bound map.
+    /// The original lower bound map.
     const LowerMap *lower;
-    /// \brief The modified capacity map.
-    CapacityRefMap capacity;
-    /// \brief The cost map.
+    /// The modified capacity map.
+    CapacityEdgeMap capacity;
+    /// The cost map.
     const CostMap &cost;
-    /// \brief The modified supply map.
-    SupplyRefMap supply;
-    /// \brief The sum of supply values equals zero.
+    /// The modified supply map.
+    SupplyNodeMap supply;
     bool valid_supply;
 
-    /// \brief The edge map of the current flow.
+    /// The edge map of the current flow.
     FlowMap flow;
-    /// \brief The potential node map.
+    /// The potential node map.
     PotentialMap potential;
 
-    /// \brief The residual capacity map.
-    CapacityRefMap res_cap;
-    /// \brief The excess map.
-    SupplyRefMap excess;
-    /// \brief The excess nodes (i.e. nodes with positive excess).
+    /// The residual capacity map.
+    CapacityEdgeMap res_cap;
+    /// The excess map.
+    SupplyNodeMap excess;
+    /// The excess nodes (i.e. the nodes with positive excess).
     std::vector<Node> excess_nodes;
-    /// \brief The index of the next excess node.
-    int next_node;
-
-    /// \brief The scaling status (enabled or disabled).
+    /// The deficit nodes (i.e. the nodes with negative excess).
+    std::vector<Node> deficit_nodes;
+
+    /// The scaling status (enabled or disabled).
     ScalingEnum scaling;
-    /// \brief The delta parameter used for capacity scaling.
+    /// The \c delta parameter used for capacity scaling.
     Capacity delta;
-    /// \brief The maximum number of phases.
-    Capacity phase_num;
-    /// \brief The deficit nodes.
-    std::vector<Node> deficit_nodes;
+    /// The maximum number of phases.
+    int phase_num;
 
     /// \brief Implementation of the \ref Dijkstra algorithm for
     /// finding augmenting shortest paths in the residual network.
     ResidualDijkstra dijkstra;
-    /// \brief The map of predecessors edges.
+    /// The map of predecessors edges.
     PredMap pred;
 
@@ -286 +277 @@
       dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
     {
-      // Removing nonzero lower bounds
+      // Removing non-zero lower bounds
       capacity = subMap(_capacity, _lower);
       res_cap = capacity;
@@ -336 +327 @@
     /// \param _t The target node.
     /// \param _flow_value The required amount of flow from node \c _s
-    /// to node \c _t (i.e. the supply of \c _s and the demand of
-    /// \c _t).
+    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
     CapacityScaling( const Graph &_graph,
                      const LowerMap &_lower,
@@ -349 +339 @@
       dijkstra(graph, flow, res_cap, cost, excess, potential)
     {
-      // Removing nonzero lower bounds
+      // Removing non-zero lower bounds
       capacity = subMap(_capacity, _lower);
       res_cap = capacity;
@@ -375 +365 @@
     /// \param _t The target node.
     /// \param _flow_value The required amount of flow from node \c _s
-    /// to node \c _t (i.e. the supply of \c _s and the demand of
-    /// \c _t).
+    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
     CapacityScaling( const Graph &_graph,
                      const CapacityMap &_capacity,
@@ -392 +381 @@
     }
 
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm.
+    ///
+    /// \param scaling_mode The scaling mode. In case of WITH_SCALING
+    /// capacity scaling is enabled in the algorithm (this is the
+    /// default) otherwise it is disabled.
+    /// If the maximum edge capacity and/or the amount of total supply
+    /// is small, the algorithm could be slightly faster without
+    /// scaling.
+    ///
+    /// \return \c true if a feasible flow can be found.
+    bool run(int scaling_mode = WITH_SCALING) {
+      return init(scaling_mode) && start();
+    }
+
     /// \brief Returns a const reference to the flow map.
     ///
@@ -425 +430 @@
     }
 
-    /// \brief Runs the algorithm.
-    ///
-    /// Runs the algorithm.
-    ///
-    /// \param scaling_mode The scaling mode. In case of WITH_SCALING
-    /// capacity scaling is enabled in the algorithm (this is the
-    /// default value) otherwise it is disabled.
-    /// If the maximum edge capacity and/or the amount of total supply
-    /// is small, the algorithm could be faster without scaling.
-    ///
-    /// \return \c true if a feasible flow can be found.
-    bool run(int scaling_mode = WITH_SCALING) {
-      return init(scaling_mode) && start();
-    }
-
   protected:
 
-    /// \brief Initializes the algorithm.
+    /// Initializes the algorithm.
     bool init(int scaling_mode) {
       if (!valid_supply) return false;
@@ -466 +456 @@
     }
 
-    /// \brief Executes the algorithm.
+    /// Executes the algorithm.
     bool start() {
       if (delta > 1)
@@ -507 +497 @@
           if (excess[n] <= -delta) deficit_nodes.push_back(n);
         }
-        next_node = 0;
+        int next_node = 0;
 
         // Finding augmenting shortest paths
@@ -573 +563 @@
       }
 
-      // Handling nonzero lower bounds
+      // Handling non-zero lower bounds
       if (lower) {
         for (EdgeIt e(graph); e != INVALID; ++e)
@@ -585 +575 @@
     bool startWithoutScaling() {
       // Finding excess nodes
-      for (NodeIt n(graph); n != INVALID; ++n) {
+      for (NodeIt n(graph); n != INVALID; ++n)
         if (excess[n] > 0) excess_nodes.push_back(n);
-      }
       if (excess_nodes.size() == 0) return true;
-      next_node = 0;
+      int next_node = 0;
 
       // Finding shortest paths
@@ -632 +621 @@
       }
 
-      // Handling nonzero lower bounds
+      // Handling non-zero lower bounds
       if (lower) {
         for (EdgeIt e(graph); e != INVALID; ++e)

lemon/cycle_canceling.h

@@ -35 +35 @@
 #ifdef LIMITED_CYCLE_CANCELING
   #include <lemon/bellman_ford.h>
-  /// \brief The maximum number of iterations for the first execution
-  /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
-  /// It should be at least 2.
-  #define STARTING_LIMIT        2
-  /// \brief The iteration limit for the
-  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
-  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
-  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
-  #define ALPHA_MUL             3
-  /// \brief The iteration limit for the
-  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
-  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
-  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
-  #define ALPHA_DIV             2
+  // The maximum number of iterations for the first execution of the
+  // Bellman-Ford algorithm. It should be at least 2.
+  #define STARTING_LIMIT        2
+  // The iteration limit for the Bellman-Ford algorithm is multiplied by
+  // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+  // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
+  #define ALPHA_MUL             3
+  #define ALPHA_DIV             2
 
 //#define _ONLY_ONE_CYCLE_
 //#define _NO_BACK_STEP_
-//#define _DEBUG_ITER_
 #endif
 
@@ -60 +53 @@
 #endif
 
+//#define _DEBUG_ITER_
+
 namespace lemon {
 
@@ -65 +60 @@
   /// @{
 
-  /// \brief Implementation of a cycle-canceling algorithm for finding
-  /// a minimum cost flow.
+  /// \brief Implementation of a cycle-canceling algorithm for
+  /// finding a minimum cost flow.
   ///
-  /// \ref lemon::CycleCanceling "CycleCanceling" implements a
-  /// cycle-canceling algorithm for finding a minimum cost flow.
+  /// \ref CycleCanceling implements a cycle-canceling algorithm for
+  /// finding a minimum cost flow.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -78 +73 @@
   ///
   /// \warning
-  /// - Edge capacities and costs should be nonnegative integers.
-  ///   However \c CostMap::Value should be signed type.
+  /// - Edge capacities and costs should be non-negative integers.
+  ///   However \c CostMap::Value should be signed type.
   /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
-  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
-  ///   convertible to \c SupplyMap::Value.
+  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
+  ///   convertible to \c SupplyMap::Value.
   ///
   /// \author Peter Kovacs
@@ -95 +90 @@
   class CycleCanceling
   {
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    GRAPH_TYPEDEFS(typename Graph);
 
     typedef typename LowerMap::Value Lower;
@@ -106 +96 @@
     typedef typename CostMap::Value Cost;
     typedef typename SupplyMap::Value Supply;
-    typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
-    typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
+    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
+    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
 
     typedef ResGraphAdaptor< const Graph, Capacity,
-                             CapacityRefMap, CapacityRefMap > ResGraph;
+                             CapacityEdgeMap, CapacityEdgeMap > ResGraph;
     typedef typename ResGraph::Node ResNode;
     typedef typename ResGraph::NodeIt ResNodeIt;
@@ -118 +108 @@
   public:
 
-    /// \brief The type of the flow map.
-    typedef CapacityRefMap FlowMap;
+    /// The type of the flow map.
+    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
 
   protected:
 
-    /// \brief Map adaptor class for handling residual edge costs.
+    /// Map adaptor class for handling residual edge costs.
     class ResCostMap : public MapBase<ResEdge, Cost>
     {
@@ -135 +125 @@
 
       Cost operator[](const ResEdge &e) const {
-        return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
+        return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
       }
 
@@ -142 +132 @@
   protected:
 
-    /// \brief The directed graph the algorithm runs on.
+    /// The directed graph the algorithm runs on.
     const Graph &graph;
-    /// \brief The original lower bound map.
+    /// The original lower bound map.
     const LowerMap *lower;
-    /// \brief The modified capacity map.
-    CapacityRefMap capacity;
-    /// \brief The cost map.
+    /// The modified capacity map.
+    CapacityEdgeMap capacity;
+    /// The cost map.
     const CostMap &cost;
-    /// \brief The modified supply map.
-    SupplyRefMap supply;
-    /// \brief The sum of supply values equals zero.
+    /// The modified supply map.
+    SupplyNodeMap supply;
     bool valid_supply;
 
-    /// \brief The current flow.
+    /// The current flow.
     FlowMap flow;
-    /// \brief The residual graph.
+    /// The residual graph.
     ResGraph res_graph;
-    /// \brief The residual cost map.
+    /// The residual cost map.
     ResCostMap res_cost;
 
@@ -174 +163 @@
     /// \param _supply The supply values of the nodes (signed).
     CycleCanceling( const Graph &_graph,
-                    const LowerMap &_lower,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    const SupplyMap &_supply ) :
+                    const LowerMap &_lower,
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    const SupplyMap &_supply ) :
       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
       supply(_graph), flow(_graph, 0),
       res_graph(_graph, capacity, flow), res_cost(cost)
     {
-      // Removing nonzero lower bounds
+      // Removing non-zero lower bounds
       capacity = subMap(_capacity, _lower);
       Supply sum = 0;
       for (NodeIt n(graph); n != INVALID; ++n) {
-        Supply s = _supply[n];
-        for (InEdgeIt e(graph, n); e != INVALID; ++e)
-          s += _lower[e];
-        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
-          s -= _lower[e];
-        sum += (supply[n] = s);
+        Supply s = _supply[n];
+        for (InEdgeIt e(graph, n); e != INVALID; ++e)
+          s += _lower[e];
+        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
+          s -= _lower[e];
+        sum += (supply[n] = s);
       }
       valid_supply = sum == 0;
@@ -205 +194 @@
     /// \param _supply The supply values of the nodes (signed).
     CycleCanceling( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    const SupplyMap &_supply ) :
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    const SupplyMap &_supply ) :
       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
       supply(_supply), flow(_graph, 0),
@@ -218 +207 @@
     }
 
-
     /// \brief Simple constructor of the class (with lower bounds).
     ///
@@ -230 +218 @@
     /// \param _t The target node.
     /// \param _flow_value The required amount of flow from node \c _s
-    /// to node \c _t (i.e. the supply of \c _s and the demand of
-    /// \c _t).
+    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
     CycleCanceling( const Graph &_graph,
-                    const LowerMap &_lower,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    Node _s, Node _t,
-                    Supply _flow_value ) :
+                    const LowerMap &_lower,
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    Node _s, Node _t,
+                    Supply _flow_value ) :
       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
       supply(_graph), flow(_graph, 0),
       res_graph(_graph, capacity, flow), res_cost(cost)
     {
-      // Removing nonzero lower bounds
+      // Removing non-zero lower bounds
       capacity = subMap(_capacity, _lower);
       for (NodeIt n(graph); n != INVALID; ++n) {
-        Supply s = 0;
-        if (n == _s) s =  _flow_value;
-        if (n == _t) s = -_flow_value;
-        for (InEdgeIt e(graph, n); e != INVALID; ++e)
-          s += _lower[e];
-        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
-          s -= _lower[e];
-        supply[n] = s;
+        Supply s = 0;
+        if (n == _s) s =  _flow_value;
+        if (n == _t) s = -_flow_value;
+        for (InEdgeIt e(graph, n); e != INVALID; ++e)
+          s += _lower[e];
+        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
+          s -= _lower[e];
+        supply[n] = s;
       }
       valid_supply = true;
@@ -267 +254 @@
     /// \param _t The target node.
     /// \param _flow_value The required amount of flow from node \c _s
-    /// to node \c _t (i.e. the supply of \c _s and the demand of
-    /// \c _t).
+    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
     CycleCanceling( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    Node _s, Node _t,
-                    Supply _flow_value ) :
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    Node _s, Node _t,
+                    Supply _flow_value ) :
       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
       supply(_graph, 0), flow(_graph, 0),
@@ -283 +269 @@
     }
 
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm.
+    ///
+    /// \return \c true if a feasible flow can be found.
+    bool run() {
+      return init() && start();
+    }
+
     /// \brief Returns a const reference to the flow map.
     ///
@@ -301 +296 @@
       Cost c = 0;
       for (EdgeIt e(graph); e != INVALID; ++e)
-        c += flow[e] * cost[e];
+        c += flow[e] * cost[e];
       return c;
     }
 
-    /// \brief Runs the algorithm.
-    ///
-    /// Runs the algorithm.
-    ///
-    /// \return \c true if a feasible flow can be found.
-    bool run() {
-      return init() && start();
-    }
-
   protected:
 
-    /// \brief Initializes the algorithm.
+    /// Initializes the algorithm.
     bool init() {
       // Checking the sum of supply values
@@ -324 +310 @@
 
       // Finding a feasible flow
-      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap,
-                   SupplyMap >
-        circulation( graph, constMap<Edge>((Capacity)0), capacity,
-                     supply );
+      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
+                   SupplyMap >
+        circulation( graph, constMap<Edge>((Capacity)0), capacity,
+                     supply );
       circulation.flowMap(flow);
       return circulation.run();
@@ -334 +320 @@
 #ifdef LIMITED_CYCLE_CANCELING
     /// \brief Executes a cycle-canceling algorithm using
-    /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
-    /// iteration count.
+    /// \ref Bellman-Ford algorithm with limited iteration count.
     bool start() {
       typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
@@ -348 +333 @@
       bool optimal = false;
       while (!optimal) {
-        BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
-        bf.predMap(pred);
-        bf.init(0);
-        int iter_num = 0;
-        bool cycle_found = false;
-        while (!cycle_found) {
+        BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
+        bf.predMap(pred);
+        bf.init(0);
+        int iter_num = 0;
+        bool cycle_found = false;
+        while (!cycle_found) {
 #ifdef _NO_BACK_STEP_
-          int curr_iter_num = length_bound <= node_num ?
-                              length_bound - iter_num : node_num - iter_num;
+          int curr_iter_num = length_bound <= node_num ?
+                              length_bound - iter_num : node_num - iter_num;
 #else
-          int curr_iter_num = iter_num + length_bound <= node_num ?
-                              length_bound : node_num - iter_num;
-#endif
-          iter_num += curr_iter_num;
-          int real_iter_num = curr_iter_num;
-          for (int i = 0; i < curr_iter_num; ++i) {
-            if (bf.processNextWeakRound()) {
-              real_iter_num = i;
-              break;
-            }
-          }
-          if (real_iter_num < curr_iter_num) {
-            optimal = true;
-            break;
-          } else {
-            // Searching for node disjoint negative cycles
-            for (ResNodeIt n(res_graph); n != INVALID; ++n)
-              visited[n] = 0;
-            int id = 0;
-            for (ResNodeIt n(res_graph); n != INVALID; ++n) {
-              if (visited[n] > 0) continue;
-              visited[n] = ++id;
-              ResNode u = pred[n] == INVALID ?
-                          INVALID : res_graph.source(pred[n]);
-              while (u != INVALID && visited[u] == 0) {
-                visited[u] = id;
-                u = pred[u] == INVALID ?
-                    INVALID : res_graph.source(pred[u]);
-              }
-              if (u != INVALID && visited[u] == id) {
-                // Finding the negative cycle
-                cycle_found = true;
-                cycle.clear();
-                ResEdge e = pred[u];
-                cycle.push_back(e);
-                Capacity d = res_graph.rescap(e);
-                while (res_graph.source(e) != u) {
-                  cycle.push_back(e = pred[res_graph.source(e)]);
-                  if (res_graph.rescap(e) < d)
-                    d = res_graph.rescap(e);
-                }
-#ifdef _DEBUG_ITER_
-                ++cycle_num;
-#endif
-                // Augmenting along the cycle
-                for (int i = 0; i < cycle.size(); ++i)
-                  res_graph.augment(cycle[i], d);
+          int curr_iter_num = iter_num + length_bound <= node_num ?
+                              length_bound : node_num - iter_num;
+#endif
+          iter_num += curr_iter_num;
+          int real_iter_num = curr_iter_num;
+          for (int i = 0; i < curr_iter_num; ++i) {
+            if (bf.processNextWeakRound()) {
+              real_iter_num = i;
+              break;
+            }
+          }
+          if (real_iter_num < curr_iter_num) {
+            optimal = true;
+            break;
+          } else {
+            // Searching for node disjoint negative cycles
+            for (ResNodeIt n(res_graph); n != INVALID; ++n)
+              visited[n] = 0;
+            int id = 0;
+            for (ResNodeIt n(res_graph); n != INVALID; ++n) {
+              if (visited[n] > 0) continue;
+              visited[n] = ++id;
+              ResNode u = pred[n] == INVALID ?
+                          INVALID : res_graph.source(pred[n]);
+              while (u != INVALID && visited[u] == 0) {
+                visited[u] = id;
+                u = pred[u] == INVALID ?
+                    INVALID : res_graph.source(pred[u]);
+              }
+              if (u != INVALID && visited[u] == id) {
+                // Finding the negative cycle
+                cycle_found = true;
+                cycle.clear();
+                ResEdge e = pred[u];
+                cycle.push_back(e);
+                Capacity d = res_graph.rescap(e);
+                while (res_graph.source(e) != u) {
+                  cycle.push_back(e = pred[res_graph.source(e)]);
+                  if (res_graph.rescap(e) < d)
+                    d = res_graph.rescap(e);
+                }
+#ifdef _DEBUG_ITER_
+                ++cycle_num;
+#endif
+                // Augmenting along the cycle
+                for (int i = 0; i < cycle.size(); ++i)
+                  res_graph.augment(cycle[i], d);
 #ifdef _ONLY_ONE_CYCLE_
-                break;
-#endif
-              }
-            }
-          }
-
-          if (!cycle_found)
-            length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
-        }
+                break;
+#endif
+              }
+            }
+          }
+
+          if (!cycle_found)
+            length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
+        }
       }
 
 #ifdef _DEBUG_ITER_
       std::cout << "Limited cycle-canceling algorithm finished. "
-                << "Found " << cycle_num << " negative cycles."
-                << std::endl;
-#endif
-
-      // Handling nonzero lower bounds
+                << "Found " << cycle_num << " negative cycles."
+                << std::endl;
+#endif
+
+      // Handling non-zero lower bounds
       if (lower) {
-        for (EdgeIt e(graph); e != INVALID; ++e)
-          flow[e] += (*lower)[e];
+        for (EdgeIt e(graph); e != INVALID; ++e)
+          flow[e] += (*lower)[e];
       }
       return true;
@@ -434 +419 @@
 #ifdef MIN_MEAN_CYCLE_CANCELING
     /// \brief Executes the minimum mean cycle-canceling algorithm
-    /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
+    /// using \ref MinMeanCycle.
     bool start() {
       typedef Path<ResGraph> ResPath;
@@ -445 +430 @@
       mmc.cyclePath(cycle).init();
       if (mmc.findMinMean()) {
-        while (mmc.cycleLength() < 0) {
-#ifdef _DEBUG_ITER_
-          ++iter;
-#endif
-          // Finding the cycle
-          mmc.findCycle();
-
-          // Finding the largest flow amount that can be augmented
-          // along the cycle
-          Capacity delta = 0;
-          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
-            if (delta == 0 || res_graph.rescap(e) < delta)
-              delta = res_graph.rescap(e);
-          }
-
-          // Augmenting along the cycle
-          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
-            res_graph.augment(e, delta);
-
-          // Finding the minimum cycle mean for the modified residual
-          // graph
-          mmc.reset();
-          if (!mmc.findMinMean()) break;
-        }
+        while (mmc.cycleLength() < 0) {
+#ifdef _DEBUG_ITER_
+          ++cycle_num;
+#endif
+          // Finding the cycle
+          mmc.findCycle();
+
+          // Finding the largest flow amount that can be augmented
+          // along the cycle
+          Capacity delta = 0;
+          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
+            if (delta == 0 || res_graph.rescap(e) < delta)
+              delta = res_graph.rescap(e);
+          }
+
+          // Augmenting along the cycle
+          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
+            res_graph.augment(e, delta);
+
+          // Finding the minimum cycle mean for the modified residual
+          // graph
+          mmc.reset();
+          if (!mmc.findMinMean()) break;
+        }
       }
 
 #ifdef _DEBUG_ITER_
       std::cout << "Minimum mean cycle-canceling algorithm finished. "
-                << "Found " << cycle_num << " negative cycles."
-                << std::endl;
-#endif
-
-      // Handling nonzero lower bounds
+                << "Found " << cycle_num << " negative cycles."
+                << std::endl;
+#endif
+
+      // Handling non-zero lower bounds
       if (lower) {
-        for (EdgeIt e(graph); e != INVALID; ++e)
-          flow[e] += (*lower)[e];
+        for (EdgeIt e(graph); e != INVALID; ++e)
+          flow[e] += (*lower)[e];
       }
       return true;

lemon/min_cost_flow.h

@@ -34 +34 @@
   /// \brief An efficient algorithm for finding a minimum cost flow.
   ///
-  /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
-  /// algorithm for finding a minimum cost flow.
+  /// \ref MinCostFlow provides an efficient algorithm for finding
+  /// a minimum cost flow.
   ///
-  /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
-  /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
-  /// efficient implementation for the minimum cost flow problem in the
-  /// LEMON library according to our benchmark tests.
+  /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
+  /// which is the most efficient implementation for the minimum cost
+  /// flow problem in the LEMON library according to our benchmark
+  /// tests.
   ///
   /// \note There are three implementations for the minimum cost flow
-  /// problem, that can be used in the same way.
-  /// - \ref lemon::CapacityScaling "CapacityScaling"
-  /// - \ref lemon::CycleCanceling "CycleCanceling"
-  /// - \ref lemon::NetworkSimplex "NetworkSimplex"
+  /// problem, that can be used exactly the same way.
+  /// - \ref CapacityScaling
+  /// - \ref CycleCanceling
+  /// - \ref NetworkSimplex
+  ///
+  /// \note For the detailed documentation of this class see
+  /// \ref NetworkSimplex.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -55 +58 @@
   ///
   /// \warning
-  /// - Edge capacities and costs should be nonnegative integers.
-  ///   However \c CostMap::Value should be signed type.
+  /// - Edge capacities and costs should be non-negative integers.
+  ///   However \c CostMap::Value should be signed type.
   /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
-  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
-  ///   convertible to \c SupplyMap::Value.
+  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
+  ///   convertible to \c SupplyMap::Value.
   ///
   /// \author Peter Kovacs
@@ -71 +74 @@
                                   <typename CapacityMap::Value> >
   class MinCostFlow :
-    public NetworkSimplex< Graph,
-                           LowerMap,
-                           CapacityMap,
-                           CostMap,
-                           SupplyMap >
+    public NetworkSimplex< Graph, LowerMap, CapacityMap,
+                           CostMap, SupplyMap >
   {
     typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
-                            CostMap, SupplyMap >
-      MinCostFlowImpl;
+                            CostMap, SupplyMap > MinCostFlowImpl;
     typedef typename Graph::Node Node;
     typedef typename SupplyMap::Value Supply;
@@ -85 +84 @@
   public:
 
-    /// \brief General constructor of the class (with lower bounds).
-    MinCostFlow( const Graph &_graph,
-                 const LowerMap &_lower,
-                 const CapacityMap &_capacity,
-                 const CostMap &_cost,
-                 const SupplyMap &_supply ) :
-      MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
+    /// General constructor of the class (with lower bounds).
+    MinCostFlow( const Graph &graph,
+                 const LowerMap &lower,
+                 const CapacityMap &capacity,
+                 const CostMap &cost,
+                 const SupplyMap &supply ) :
+      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
 
-    /// \brief General constructor of the class (without lower bounds).
-    MinCostFlow( const Graph &_graph,
-                 const CapacityMap &_capacity,
-                 const CostMap &_cost,
-                 const SupplyMap &_supply ) :
-      MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
+    /// General constructor of the class (without lower bounds).
+    MinCostFlow( const Graph &graph,
+                 const CapacityMap &capacity,
+                 const CostMap &_ost,
+                 const SupplyMap &supply ) :
+      MinCostFlowImpl(graph, capacity, cost, supply) {}
 
-    /// \brief Simple constructor of the class (with lower bounds).
-    MinCostFlow( const Graph &_graph,
-                 const LowerMap &_lower,
-                 const CapacityMap &_capacity,
-                 const CostMap &_cost,
-                 Node _s, Node _t,
-                 Supply _flow_value ) :
-      MinCostFlowImpl( _graph, _lower, _capacity, _cost,
-                       _s, _t, _flow_value ) {}
+    /// Simple constructor of the class (with lower bounds).
+    MinCostFlow( const Graph &graph,
+                 const LowerMap &lower,
+                 const CapacityMap &capacity,
+                 const CostMap &_ost,
+                 Node s, Node t,
+                 Supply flow_value ) :
+      MinCostFlowImpl( graph, lower, capacity, cost,
+                       s, t, flow_value ) {}
 
-    /// \brief Simple constructor of the class (without lower bounds).
-    MinCostFlow( const Graph &_graph,
-                 const CapacityMap &_capacity,
-                 const CostMap &_cost,
-                 Node _s, Node _t,
-                 Supply _flow_value ) :
-      MinCostFlowImpl( _graph, _capacity, _cost,
-                       _s, _t, _flow_value ) {}
+    /// Simple constructor of the class (without lower bounds).
+    MinCostFlow( const Graph &graph,
+                 const CapacityMap &capacity,
+                 const CostMap &cost,
+                 Node s, Node t,
+                 Supply flow_value ) :
+      MinCostFlowImpl( graph, capacity, cost,
+                       s, t, flow_value ) {}
 
   }; //class MinCostFlow

lemon/min_cost_max_flow.h

@@ -23 +23 @@
 ///
 /// \file
-/// \brief An efficient algorithm for finding a minimum cost maximum
-/// flow.
+/// \brief An efficient algorithm for finding a minimum cost maximum flow.
 
 #include <lemon/preflow.h>
@@ -35 +34 @@
   /// @{
 
-  /// \brief An efficient algorithm for finding a minimum cost maximum
-  /// flow.
+  /// \brief An efficient algorithm for finding a minimum cost
+  /// maximum flow.
   ///
-  /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient
-  /// algorithm for finding a maximum flow having minimal total cost
-  /// from a given source node to a given target node in a directed
-  /// graph.
+  /// \ref MinCostMaxFlow implements an efficient algorithm for
+  /// finding a maximum flow having minimal total cost from a given
+  /// source node to a given target node in a directed graph.
   ///
-  /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses
-  /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum
-  /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" 
-  /// algorithm for finding a minimum cost flow of that value.
+  /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
+  /// the maximum flow value and \ref NetworkSimplex algorithm for
+  /// finding a minimum cost flow of that value.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -53 +50 @@
   ///
   /// \warning
-  /// - Edge capacities and costs should be nonnegative integers.
-  ///   However \c CostMap::Value should be signed type.
+  /// - Edge capacities and costs should be non-negative integers.
+  ///   However \c CostMap::Value should be signed type.
   ///
   /// \author Peter Kovacs
 
   template < typename Graph,
-             typename CapacityMap = typename Graph::template EdgeMap<int>,
-             typename CostMap = typename Graph::template EdgeMap<int> >
+             typename CapacityMap = typename Graph::template EdgeMap<int>,
+             typename CostMap = typename Graph::template EdgeMap<int> >
   class MinCostMaxFlow
   {
@@ -67 +64 @@
 
     typedef typename CapacityMap::Value Capacity;
+    typedef typename CostMap::Value Cost;
     typedef typename Graph::template NodeMap<Capacity> SupplyMap;
     typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
-                            CostMap, SupplyMap >
+                            CostMap, SupplyMap >
       MinCostFlowImpl;
 
   public:
 
-    /// \brief The type of the flow map.
+    /// The type of the flow map.
     typedef typename Graph::template EdgeMap<Capacity> FlowMap;
-    typedef typename CostMap::Value Cost;
 
   private:
 
-    /// \brief The directed graph the algorithm runs on.
+    /// The directed graph the algorithm runs on.
     const Graph &graph;
-    /// \brief The modified capacity map.
+    /// The modified capacity map.
     const CapacityMap &capacity;
-    /// \brief The cost map.
+    /// The cost map.
     const CostMap &cost;
-    /// \brief The source node.
+    /// The edge map of the found flow.
+    FlowMap flow;
+    /// The source node.
     Node source;
-    /// \brief The target node.
+    /// The target node.
     Node target;
-    /// \brief The edge map of the found flow.
-    FlowMap flow;
 
-    typedef Preflow<Graph, CapacityMap> PreflowImpl;
-    /// \brief \ref lemon::Preflow "Preflow" class for finding the
-    /// maximum flow value.
-    PreflowImpl preflow;
+    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
+    /// \brief \ref Preflow class for finding the maximum flow value.
+    MaxFlowImpl preflow;
 
   public:
@@ -110 +106 @@
     /// \param _t The target node.
     MinCostMaxFlow( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    Node _s, Node _t ) :
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    Node _s, Node _t ) :
       graph(_graph), capacity(_capacity), cost(_cost),
       source(_s), target(_t), flow(_graph),
@@ -136 +132 @@
       Cost c = 0;
       for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
-        c += flow[e] * cost[e];
+        c += flow[e] * cost[e];
       return c;
     }
@@ -145 +141 @@
       preflow.runMinCut();
       MinCostFlowImpl mcf_impl( graph, capacity, cost,
-                                source, target, preflow.flowValue() );
+                                source, target, preflow.flowValue() );
       mcf_impl.run();
       flow = mcf_impl.flowMap();

lemon/network_simplex.h

@@ -23 +23 @@
 ///
 /// \file
-/// \brief The network simplex algorithm for finding a minimum cost
-/// flow.
+/// \brief The network simplex algorithm for finding a minimum cost flow.
 
 #include <limits>
@@ -41 +40 @@
 
 
-/// \brief State constant for edges at their lower bounds.
-#define LOWER   1
-/// \brief State constant for edges in the spanning tree.
-#define TREE    0
-/// \brief State constant for edges at their upper bounds.
-#define UPPER   -1
+// State constant for edges at their lower bounds.
+#define LOWER   1
+// State constant for edges in the spanning tree.
+#define TREE    0
+// State constant for edges at their upper bounds.
+#define UPPER   -1
 
 #ifdef EDGE_BLOCK_PIVOT
   #include <cmath>
-  /// \brief Lower bound for the size of blocks.
-  #define MIN_BLOCK_SIZE        10
+  #define MIN_BLOCK_SIZE        10
 #endif
 
 #ifdef CANDIDATE_LIST_PIVOT
   #include <vector>
-  #define LIST_LENGTH_DIV           50
-  #define MINOR_LIMIT_DIV           200
+  #define LIST_LENGTH_DIV       50
+  #define MINOR_LIMIT_DIV       200
 #endif
 
@@ -64 +62 @@
   #include <algorithm>
   #define LIST_LENGTH_DIV       100
-  #define LOWER_DIV             4
+  #define LOWER_DIV             4
 #endif
 
@@ -75 +73 @@
   /// finding a minimum cost flow.
   ///
-  /// \ref lemon::NetworkSimplex "NetworkSimplex" implements the
-  /// network simplex algorithm for finding a minimum cost flow.
+  /// \ref NetworkSimplex implements the network simplex algorithm for
+  /// finding a minimum cost flow.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -85 +83 @@
   ///
   /// \warning
-  /// - Edge capacities and costs should be nonnegative integers.
-  ///   However \c CostMap::Value should be signed type.
+  /// - Edge capacities and costs should be non-negative integers.
+  ///   However \c CostMap::Value should be signed type.
   /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
-  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
-  ///   convertible to \c SupplyMap::Value.
+  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
+  ///   convertible to \c SupplyMap::Value.
   ///
   /// \author Peter Kovacs
@@ -108 +106 @@
 
     typedef SmartGraph SGraph;
-    typedef typename SGraph::Node Node;
-    typedef typename SGraph::NodeIt NodeIt;
-    typedef typename SGraph::Edge Edge;
-    typedef typename SGraph::EdgeIt EdgeIt;
-    typedef typename SGraph::InEdgeIt InEdgeIt;
-    typedef typename SGraph::OutEdgeIt OutEdgeIt;
+    GRAPH_TYPEDEFS(typename SGraph);
 
     typedef typename SGraph::template EdgeMap<Lower> SLowerMap;
@@ -132 +125 @@
   public:
 
-    /// \brief The type of the flow map.
+    /// The type of the flow map.
     typedef typename Graph::template EdgeMap<Capacity> FlowMap;
-    /// \brief The type of the potential map.
+    /// The type of the potential map.
     typedef typename Graph::template NodeMap<Cost> PotentialMap;
 
   protected:
 
-    /// \brief Map adaptor class for handling reduced edge costs.
+    /// Map adaptor class for handling reduced edge costs.
     class ReducedCostMap : public MapBase<Edge, Cost>
     {
@@ -151 +144 @@
 
       ReducedCostMap( const SGraph &_gr,
-                      const SCostMap &_cm,
-                      const SPotentialMap &_pm ) :
-        gr(_gr), cost_map(_cm), pot_map(_pm) {}
+                      const SCostMap &_cm,
+                      const SPotentialMap &_pm ) :
+        gr(_gr), cost_map(_cm), pot_map(_pm) {}
 
       Cost operator[](const Edge &e) const {
-        return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
+        return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
       }
 
@@ -163 +156 @@
   protected:
 
-    /// \brief The directed graph the algorithm runs on.
+    /// The directed graph the algorithm runs on.
     SGraph graph;
-    /// \brief The original graph.
+    /// The original graph.
     const Graph &graph_ref;
-    /// \brief The original lower bound map.
+    /// The original lower bound map.
     const LowerMap *lower;
-    /// \brief The capacity map.
+    /// The capacity map.
     SCapacityMap capacity;
-    /// \brief The cost map.
+    /// The cost map.
     SCostMap cost;
-    /// \brief The supply map.
+    /// The supply map.
     SSupplyMap supply;
-    /// \brief The reduced cost map.
+    /// The reduced cost map.
     ReducedCostMap red_cost;
-    /// \brief The sum of supply values equals zero.
     bool valid_supply;
 
-    /// \brief The edge map of the current flow.
+    /// The edge map of the current flow.
     SCapacityMap flow;
-    /// \brief The edge map of the found flow on the original graph.
+    /// The potential node map.
+    SPotentialMap potential;
     FlowMap flow_result;
-    /// \brief The potential node map.
-    SPotentialMap potential;
-    /// \brief The potential node map on the original graph.
     PotentialMap potential_result;
 
-    /// \brief Node reference for the original graph.
+    /// Node reference for the original graph.
     NodeRefMap node_ref;
-    /// \brief Edge reference for the original graph.
+    /// Edge reference for the original graph.
     EdgeRefMap edge_ref;
 
-    /// \brief The depth node map of the spanning tree structure.
+    /// The \c depth node map of the spanning tree structure.
     IntNodeMap depth;
-    /// \brief The parent node map of the spanning tree structure.
+    /// The \c parent node map of the spanning tree structure.
     NodeNodeMap parent;
-    /// \brief The pred_edge node map of the spanning tree structure.
+    /// The \c pred_edge node map of the spanning tree structure.
     EdgeNodeMap pred_edge;
-    /// \brief The thread node map of the spanning tree structure.
+    /// The \c thread node map of the spanning tree structure.
     NodeNodeMap thread;
-    /// \brief The forward node map of the spanning tree structure.
+    /// The \c forward node map of the spanning tree structure.
     BoolNodeMap forward;
-    /// \brief The state edge map.
+    /// The state edge map.
     IntEdgeMap state;
-
+    /// The root node of the starting spanning tree.
+    Node root;
+
+    // The entering edge of the current pivot iteration.
+    Edge in_edge;
+    // Temporary nodes used in the current pivot iteration.
+    Node join, u_in, v_in, u_out, v_out;
+    Node right, first, second, last;
+    Node stem, par_stem, new_stem;
+    // The maximum augment amount along the found cycle in the current
+    // pivot iteration.
+    Capacity delta;
 
 #ifdef EDGE_BLOCK_PIVOT
-    /// \brief The size of blocks for the "Edge Block" pivot rule.
+    /// The size of blocks for the "Edge Block" pivot rule.
     int block_size;
 #endif
@@ -235 +236 @@
 #endif
 
-    // Root node of the starting spanning tree.
-    Node root;
-    // The entering edge of the current pivot iteration.
-    Edge in_edge;
-    // Temporary nodes used in the current pivot iteration.
-    Node join, u_in, v_in, u_out, v_out;
-    Node right, first, second, last;
-    Node stem, par_stem, new_stem;
-    // The maximum augment amount along the cycle in the current pivot
-    // iteration.
-    Capacity delta;
-
   public :
 
@@ -259 +248 @@
     /// \param _supply The supply values of the nodes (signed).
     NetworkSimplex( const Graph &_graph,
-                    const LowerMap &_lower,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    const SupplyMap &_supply ) :
+                    const LowerMap &_lower,
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    const SupplyMap &_supply ) :
       graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
       supply(graph), flow(graph), flow_result(_graph), potential(graph),
@@ -273 +262 @@
       Supply sum = 0;
       for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
-        sum += _supply[n];
+        sum += _supply[n];
       if (!(valid_supply = sum == 0)) return;
 
@@ -280 +269 @@
       graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
       copyGraph(graph, graph_ref)
-        .edgeMap(cost, _cost)
-        .nodeRef(node_ref)
-        .edgeRef(edge_ref)
-        .run();
-
-      // Removing nonzero lower bounds
+        .edgeMap(cost, _cost)
+        .nodeRef(node_ref)
+        .edgeRef(edge_ref)
+        .run();
+
+      // Removing non-zero lower bounds
       for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
-        capacity[edge_ref[e]] = _capacity[e] - _lower[e];
+        capacity[edge_ref[e]] = _capacity[e] - _lower[e];
       }
       for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
-        Supply s = _supply[n];
-        for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
-          s += _lower[e];
-        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
-          s -= _lower[e];
-        supply[node_ref[n]] = s;
+        Supply s = _supply[n];
+        for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
+          s += _lower[e];
+        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
+          s -= _lower[e];
+        supply[node_ref[n]] = s;
       }
     }
@@ -308 +297 @@
     /// \param _supply The supply values of the nodes (signed).
     NetworkSimplex( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    const SupplyMap &_supply ) :
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    const SupplyMap &_supply ) :
       graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
       supply(graph), flow(graph), flow_result(_graph), potential(graph),
@@ -321 +310 @@
       Supply sum = 0;
       for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
-        sum += _supply[n];
+        sum += _supply[n];
       if (!(valid_supply = sum == 0)) return;
 
       // Copying graph_ref to graph
       copyGraph(graph, graph_ref)
-        .edgeMap(capacity, _capacity)
-        .edgeMap(cost, _cost)
-        .nodeMap(supply, _supply)
-        .nodeRef(node_ref)
-        .edgeRef(edge_ref)
-        .run();
+        .edgeMap(capacity, _capacity)
+        .edgeMap(cost, _cost)
+        .nodeMap(supply, _supply)
+        .nodeRef(node_ref)
+        .edgeRef(edge_ref)
+        .run();
     }
 
@@ -345 +334 @@
     /// \param _t The target node.
     /// \param _flow_value The required amount of flow from node \c _s
-    /// to node \c _t (i.e. the supply of \c _s and the demand of
-    /// \c _t).
+    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
     NetworkSimplex( const Graph &_graph,
-                    const LowerMap &_lower,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    typename Graph::Node _s,
-                    typename Graph::Node _t,
-                    typename SupplyMap::Value _flow_value ) :
+                    const LowerMap &_lower,
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    typename Graph::Node _s,
+                    typename Graph::Node _t,
+                    typename SupplyMap::Value _flow_value ) :
       graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
       supply(graph), flow(graph), flow_result(_graph), potential(graph),
@@ -363 +351 @@
       // Copying graph_ref to graph
       copyGraph(graph, graph_ref)
-        .edgeMap(cost, _cost)
-        .nodeRef(node_ref)
-        .edgeRef(edge_ref)
-        .run();
-
-      // Removing nonzero lower bounds
+        .edgeMap(cost, _cost)
+        .nodeRef(node_ref)
+        .edgeRef(edge_ref)
+        .run();
+
+      // Removing non-zero lower bounds
       for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
-        capacity[edge_ref[e]] = _capacity[e] - _lower[e];
+        capacity[edge_ref[e]] = _capacity[e] - _lower[e];
       }
       for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
-        Supply s = 0;
-        if (n == _s) s =  _flow_value;
-        if (n == _t) s = -_flow_value;
-        for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
-          s += _lower[e];
-        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
-          s -= _lower[e];
-        supply[node_ref[n]] = s;
+        Supply s = 0;
+        if (n == _s) s =  _flow_value;
+        if (n == _t) s = -_flow_value;
+        for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
+          s += _lower[e];
+        for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
+          s -= _lower[e];
+        supply[node_ref[n]] = s;
       }
       valid_supply = true;
@@ -395 +383 @@
     /// \param _t The target node.
     /// \param _flow_value The required amount of flow from node \c _s
-    /// to node \c _t (i.e. the supply of \c _s and the demand of
-    /// \c _t).
+    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
     NetworkSimplex( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    typename Graph::Node _s,
-                    typename Graph::Node _t,
-                    typename SupplyMap::Value _flow_value ) :
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    typename Graph::Node _s,
+                    typename Graph::Node _t,
+                    typename SupplyMap::Value _flow_value ) :
       graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
       supply(graph, 0), flow(graph), flow_result(_graph), potential(graph),
@@ -412 +399 @@
       // Copying graph_ref to graph
       copyGraph(graph, graph_ref)
-        .edgeMap(capacity, _capacity)
-        .edgeMap(cost, _cost)
-        .nodeRef(node_ref)
-        .edgeRef(edge_ref)
-        .run();
+        .edgeMap(capacity, _capacity)
+        .edgeMap(cost, _cost)
+        .nodeRef(node_ref)
+        .edgeRef(edge_ref)
+        .run();
       supply[node_ref[_s]] =  _flow_value;
       supply[node_ref[_t]] = -_flow_value;
       valid_supply = true;
+    }
+
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm.
+    ///
+    /// \return \c true if a feasible flow can be found.
+    bool run() {
+      return init() && start();
     }
 
@@ -451 +447 @@
       Cost c = 0;
       for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
-        c += flow_result[e] * cost[edge_ref[e]];
+        c += flow_result[e] * cost[edge_ref[e]];
       return c;
-    }
-
-    /// \brief Runs the algorithm.
-    ///
-    /// Runs the algorithm.
-    ///
-    /// \return \c true if a feasible flow can be found.
-    bool run() {
-      return init() && start();
     }
 
@@ -473 +460 @@
       // Initializing state and flow maps
       for (EdgeIt e(graph); e != INVALID; ++e) {
-        flow[e] = 0;
-        state[e] = LOWER;
+        flow[e] = 0;
+        state[e] = LOWER;
       }
 
@@ -492 +479 @@
       Cost max_cost = std::numeric_limits<Cost>::max() / 4;
       for (NodeIt u(graph); u != INVALID; ++u) {
-        if (u == root) continue;
-        thread[last] = u;
-        last = u;
-        parent[u] = root;
-        depth[u] = 1;
-        sum += supply[u];
-        if (supply[u] >= 0) {
-          e = graph.addEdge(u, root);
-          flow[e] = supply[u];
-          forward[u] = true;
-          potential[u] = max_cost;
-        } else {
-          e = graph.addEdge(root, u);
-          flow[e] = -supply[u];
-          forward[u] = false;
-          potential[u] = -max_cost;
-        }
-        cost[e] = max_cost;
-        capacity[e] = std::numeric_limits<Capacity>::max();
-        state[e] = TREE;
-        pred_edge[u] = e;
+        if (u == root) continue;
+        thread[last] = u;
+        last = u;
+        parent[u] = root;
+        depth[u] = 1;
+        sum += supply[u];
+        if (supply[u] >= 0) {
+          e = graph.addEdge(u, root);
+          flow[e] = supply[u];
+          forward[u] = true;
+          potential[u] = max_cost;
+        } else {
+          e = graph.addEdge(root, u);
+          flow[e] = -supply[u];
+          forward[u] = false;
+          potential[u] = -max_cost;
+        }
+        cost[e] = max_cost;
+        capacity[e] = std::numeric_limits<Capacity>::max();
+        state[e] = TREE;
+        pred_edge[u] = e;
       }
       thread[last] = root;
@@ -521 +508 @@
       block_size = 2 * int(sqrt(countEdges(graph)));
       if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
-//      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
-//                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif
 #ifdef CANDIDATE_LIST_PIVOT
@@ -544 +529 @@
     bool findEnteringEdge(EdgeIt &next_edge) {
       for (EdgeIt e = next_edge; e != INVALID; ++e) {
-        if (state[e] * red_cost[e] < 0) {
-          in_edge = e;
-          next_edge = ++e;
-          return true;
-        }
+        if (state[e] * red_cost[e] < 0) {
+          in_edge = e;
+          next_edge = ++e;
+          return true;
+        }
       }
       for (EdgeIt e(graph); e != next_edge; ++e) {
-        if (state[e] * red_cost[e] < 0) {
-          in_edge = e;
-          next_edge = ++e;
-          return true;
-        }
+        if (state[e] * red_cost[e] < 0) {
+          in_edge = e;
+          next_edge = ++e;
+          return true;
+        }
       }
       return false;
@@ -567 +552 @@
       Cost min = 0;
       for (EdgeIt e(graph); e != INVALID; ++e) {
-        if (state[e] * red_cost[e] < min) {
-          min = state[e] * red_cost[e];
-          in_edge = e;
-        }
+        if (state[e] * red_cost[e] < min) {
+          min = state[e] * red_cost[e];
+          in_edge = e;
+        }
       }
       return min < 0;
@@ -585 +570 @@
       int cnt = 0;
       for (EdgeIt e = next_edge; e != INVALID; ++e) {
-        if ((curr = state[e] * red_cost[e]) < min) {
-          min = curr;
-          min_edge = e;
-        }
-        if (++cnt == block_size) {
-          if (min < 0) break;
-          cnt = 0;
-        }
+        if ((curr = state[e] * red_cost[e]) < min) {
+          min = curr;
+          min_edge = e;
+        }
+        if (++cnt == block_size) {
+          if (min < 0) break;
+          cnt = 0;
+        }
       }
       if (!(min < 0)) {
-        for (EdgeIt e(graph); e != next_edge; ++e) {
-          if ((curr = state[e] * red_cost[e]) < min) {
-            min = curr;
-            min_edge = e;
-          }
-          if (++cnt == block_size) {
-            if (min < 0) break;
-            cnt = 0;
-          }
-        }
+        for (EdgeIt e(graph); e != next_edge; ++e) {
+          if ((curr = state[e] * red_cost[e]) < min) {
+            min = curr;
+            min_edge = e;
+          }
+          if (++cnt == block_size) {
+            if (min < 0) break;
+            cnt = 0;
+          }
+        }
       }
       in_edge = min_edge;
       if ((next_edge = ++min_edge) == INVALID)
-        next_edge = EdgeIt(graph);
+        next_edge = EdgeIt(graph);
       return min < 0;
     }
@@ -620 +605 @@
 
       if (minor_count >= minor_limit || candidates.size() == 0) {
-        // Major iteration
-        candidates.clear();
-        for (EdgeIt e(graph); e != INVALID; ++e) {
-          if (state[e] * red_cost[e] < 0) {
-            candidates.push_back(e);
-            if (candidates.size() == list_length) break;
-          }
-        }
-        if (candidates.size() == 0) return false;
+        // Major iteration
+        candidates.clear();
+        for (EdgeIt e(graph); e != INVALID; ++e) {
+          if (state[e] * red_cost[e] < 0) {
+            candidates.push_back(e);
+            if (candidates.size() == list_length) break;
+          }
+        }
+        if (candidates.size() == 0) return false;
       }
 
@@ -637 +622 @@
       for (int i = 0; i < candidates.size(); ++i) {
         e = candidates[i];
-        if (state[e] * red_cost[e] < min) {
-          min = state[e] * red_cost[e];
-          in_edge = e;
-        }
+        if (state[e] * red_cost[e] < min) {
+          min = state[e] * red_cost[e];
+          in_edge = e;
+        }
       }
       return true;
@@ -656 +641 @@
     public:
       SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
-        st(_st), rc(_rc) {}
+        st(_st), rc(_rc) {}
       bool operator()(const Edge &e1, const Edge &e2) {
-        return st[e1] * rc[e1] < st[e2] * rc[e2];
+        return st[e1] * rc[e1] < st[e2] * rc[e2];
       }
     };
@@ -669 +654 @@
       // Minor iteration
       while (list_index < candidates.size()) {
-        in_edge = candidates[list_index++];
-        if (state[in_edge] * red_cost[in_edge] < 0) return true;
+        in_edge = candidates[list_index++];
+        if (state[in_edge] * red_cost[in_edge] < 0) return true;
       }
 
@@ -677 +662 @@
       Cost curr, min = 0;
       for (EdgeIt e(graph); e != INVALID; ++e) {
-        if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
-          candidates.push_back(e);
-          if (curr < min) min = curr;
-          if (candidates.size() == list_length) break;
-        }
+        if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
+          candidates.push_back(e);
+          if (curr < min) min = curr;
+          if (candidates.size() == list_length) break;
+        }
       }
       if (candidates.size() == 0) return false;
@@ -697 +682 @@
       Node v = graph.target(in_edge);
       while (u != v) {
-        if (depth[u] == depth[v]) {
-          u = parent[u];
-          v = parent[v];
-        }
-        else if (depth[u] > depth[v]) u = parent[u];
-        else v = parent[v];
+        if (depth[u] == depth[v]) {
+          u = parent[u];
+          v = parent[v];
+        }
+        else if (depth[u] > depth[v]) u = parent[u];
+        else v = parent[v];
       }
       return u;
@@ -713 +698 @@
       // of the cycle
       if (state[in_edge] == LOWER) {
-        first = graph.source(in_edge);
-        second  = graph.target(in_edge);
+        first = graph.source(in_edge);
+        second  = graph.target(in_edge);
       } else {
-        first = graph.target(in_edge);
-        second  = graph.source(in_edge);
+        first = graph.target(in_edge);
+        second  = graph.source(in_edge);
       }
       delta = capacity[in_edge];
@@ -727 +712 @@
       // root node
       for (Node u = first; u != join; u = parent[u]) {
-        e = pred_edge[u];
-        d = forward[u] ? flow[e] : capacity[e] - flow[e];
-        if (d < delta) {
-          delta = d;
-          u_out = u;
-          u_in = first;
-          v_in = second;
-          result = true;
-        }
+        e = pred_edge[u];
+        d = forward[u] ? flow[e] : capacity[e] - flow[e];
+        if (d < delta) {
+          delta = d;
+          u_out = u;
+          u_in = first;
+          v_in = second;
+          result = true;
+        }
       }
       // Searching the cycle along the path form the second node to the
       // root node
       for (Node u = second; u != join; u = parent[u]) {
-        e = pred_edge[u];
-        d = forward[u] ? capacity[e] - flow[e] : flow[e];
-        if (d <= delta) {
-          delta = d;
-          u_out = u;
-          u_in = second;
-          v_in = first;
-          result = true;
-        }
+        e = pred_edge[u];
+        d = forward[u] ? capacity[e] - flow[e] : flow[e];
+        if (d <= delta) {
+          delta = d;
+          u_out = u;
+          u_in = second;
+          v_in = first;
+          result = true;
+        }
       }
       return result;
     }
 
-    /// \brief Changes flow and state edge maps.
+    /// \brief Changes \c flow and \c state edge maps.
     void changeFlows(bool change) {
       // Augmenting along the cycle
       if (delta > 0) {
-        Capacity val = state[in_edge] * delta;
-        flow[in_edge] += val;
-        for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
-          flow[pred_edge[u]] += forward[u] ? -val : val;
-        }
-        for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
-          flow[pred_edge[u]] += forward[u] ? val : -val;
-        }
+        Capacity val = state[in_edge] * delta;
+        flow[in_edge] += val;
+        for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
+          flow[pred_edge[u]] += forward[u] ? -val : val;
+        }
+        for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
+          flow[pred_edge[u]] += forward[u] ? val : -val;
+        }
       }
       // Updating the state of the entering and leaving edges
       if (change) {
-        state[in_edge] = TREE;
-        state[pred_edge[u_out]] =
-          (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
+        state[in_edge] = TREE;
+        state[pred_edge[u_out]] =
+          (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
       } else {
-        state[in_edge] = -state[in_edge];
-      }
-    }
-
-    /// \brief Updates thread and parent node maps.
+        state[in_edge] = -state[in_edge];
+      }
+    }
+
+    /// \brief Updates \c thread and \c parent node maps.
     void updateThreadParent() {
       Node u;
@@ -784 +769 @@
       bool par_first = false;
       if (join == v_out) {
-        for (u = join; u != u_in && u != v_in; u = thread[u]) ;
-        if (u == v_in) {
-          par_first = true;
-          while (thread[u] != u_out) u = thread[u];
-          first = u;
-        }
+        for (u = join; u != u_in && u != v_in; u = thread[u]) ;
+        if (u == v_in) {
+          par_first = true;
+          while (thread[u] != u_out) u = thread[u];
+          first = u;
+        }
       }
 
@@ -797 +782 @@
       right = thread[u];
       if (thread[v_in] == u_out) {
-        for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
-        if (last == u_out) last = thread[last];
+        for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
+        if (last == u_out) last = thread[last];
       }
       else last = thread[v_in];
@@ -806 +791 @@
       par_stem = v_in;
       while (stem != u_out) {
-        thread[u] = new_stem = parent[stem];
-
-        // Finding the node just before the stem node (u) according to
-        // the original thread index
-        for (u = new_stem; thread[u] != stem; u = thread[u]) ;
-        thread[u] = right;
-
-        // Changing the parent node of stem and shifting stem and
-        // par_stem nodes
-        parent[stem] = par_stem;
-        par_stem = stem;
-        stem = new_stem;
-
-        // Finding the last successor of stem (u) and the node after it
-        // (right) according to the thread index
-        for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
-        right = thread[u];
+        thread[u] = new_stem = parent[stem];
+
+        // Finding the node just before the stem node (u) according to
+        // the original thread index
+        for (u = new_stem; thread[u] != stem; u = thread[u]) ;
+        thread[u] = right;
+
+        // Changing the parent node of stem and shifting stem and
+        // par_stem nodes
+        parent[stem] = par_stem;
+        par_stem = stem;
+        stem = new_stem;
+
+        // Finding the last successor of stem (u) and the node after it
+        // (right) according to the thread index
+        for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
+        right = thread[u];
       }
       parent[u_out] = par_stem;
@@ -828 +813 @@
 
       if (join == v_out && par_first) {
-        if (first != v_in) thread[first] = right;
+        if (first != v_in) thread[first] = right;
       } else {
-        for (u = v_out; thread[u] != u_out; u = thread[u]) ;
-        thread[u] = right;
-      }
-    }
-
-    /// \brief Updates pred_edge and forward node maps.
+        for (u = v_out; thread[u] != u_out; u = thread[u]) ;
+        thread[u] = right;
+      }
+    }
+
+    /// \brief Updates \c pred_edge and \c forward node maps.
     void updatePredEdge() {
       Node u = u_out, v;
       while (u != u_in) {
-        v = parent[u];
-        pred_edge[u] = pred_edge[v];
-        forward[u] = !forward[v];
-        u = v;
+        v = parent[u];
+        pred_edge[u] = pred_edge[v];
+        forward[u] = !forward[v];
+        u = v;
       }
       pred_edge[u_in] = in_edge;
@@ -848 +833 @@
     }
 
-    /// \brief Updates depth and potential node maps.
+    /// \brief Updates \c depth and \c potential node maps.
     void updateDepthPotential() {
       depth[u_in] = depth[v_in] + 1;
       potential[u_in] = forward[u_in] ?
-        potential[v_in] + cost[pred_edge[u_in]] :
-        potential[v_in] - cost[pred_edge[u_in]];
+        potential[v_in] + cost[pred_edge[u_in]] :
+        potential[v_in] - cost[pred_edge[u_in]];
 
       Node u = thread[u_in], v;
       while (true) {
-        v = parent[u];
-        if (v == INVALID) break;
-        depth[u] = depth[v] + 1;
-        potential[u] = forward[u] ?
-          potential[v] + cost[pred_edge[u]] :
-          potential[v] - cost[pred_edge[u]];
-        if (depth[u] <= depth[v_in]) break;
-        u = thread[u];
+        v = parent[u];
+        if (v == INVALID) break;
+        depth[u] = depth[v] + 1;
+        potential[u] = forward[u] ?
+          potential[v] + cost[pred_edge[u]] :
+          potential[v] - cost[pred_edge[u]];
+        if (depth[u] <= depth[v_in]) break;
+        u = thread[u];
       }
     }
@@ -881 +866 @@
 #endif
       {
-        join = findJoinNode();
-        bool change = findLeavingEdge();
-        changeFlows(change);
-        if (change) {
-          updateThreadParent();
-          updatePredEdge();
-          updateDepthPotential();
-        }
+        join = findJoinNode();
+        bool change = findLeavingEdge();
+        changeFlows(change);
+        if (change) {
+          updateThreadParent();
+          updatePredEdge();
+          updateDepthPotential();
+        }
 #ifdef _DEBUG_ITER_
-        ++iter_num;
+        ++iter_num;
 #endif
       }
@@ -896 +881 @@
 #ifdef _DEBUG_ITER_
       std::cout << "Network Simplex algorithm finished. " << iter_num
-                << " pivot iterations performed." << std::endl;
+                << " pivot iterations performed." << std::endl;
 #endif
 
@@ -902 +887 @@
       // artificial edges
       for (InEdgeIt e(graph, root); e != INVALID; ++e)
-        if (flow[e] > 0) return false;
+        if (flow[e] > 0) return false;
       for (OutEdgeIt e(graph, root); e != INVALID; ++e)
-        if (flow[e] > 0) return false;
+        if (flow[e] > 0) return false;
 
       // Copying flow values to flow_result
       if (lower) {
-        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
-          flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
+        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
+          flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
       } else {
-        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
-          flow_result[e] = flow[edge_ref[e]];
+        for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
+          flow_result[e] = flow[edge_ref[e]];
       }
       // Copying potential values to potential_result
       for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
-        potential_result[n] = potential[node_ref[n]];
+        potential_result[n] = potential[node_ref[n]];
 
       return true;