Changeset 2556:74c2c81055e1 in lemon-0.x for lemon/network_simplex.h

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.

File:

• lemon/network_simplex.h (modified) (42 diffs)

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;