# HG changeset patch
# User kpeter
# Date 1203305453 0
# Node ID 7058c9690e7d95ecf157d2fd577ca449ff0bd899
# Parent  a9758ea1f01c4b11a1631fbc1dda11279ef8ed5d
Improvements in CapacityScaling.

Main changes:
- Use -potenital[] instead of potential[] to conform to the usual
terminology.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Doc improvements.

diff -r a9758ea1f01c -r 7058c9690e7d lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Mon Feb 18 03:30:12 2008 +0000
+++ b/lemon/capacity_scaling.h	Mon Feb 18 03:30:53 2008 +0000
@@ -22,52 +22,51 @@
 /// \ingroup min_cost_flow
 ///
 /// \file
-/// \brief The capacity scaling algorithm for finding a minimum cost flow.
+/// \brief Capacity scaling algorithm for finding a minimum cost flow.
+
+#include <vector>
 
 #include <lemon/graph_adaptor.h>
 #include <lemon/bin_heap.h>
-#include <vector>
 
 namespace lemon {
 
   /// \addtogroup min_cost_flow
   /// @{
 
-  /// \brief Implementation of the capacity scaling version of the
-  /// successive shortest path algorithm for finding a minimum cost
-  /// flow.
+  /// \brief Implementation of the capacity scaling algorithm for
+  /// finding a minimum cost flow.
   ///
   /// \ref CapacityScaling implements the capacity scaling version
   /// of the successive shortest path algorithm for finding a minimum
   /// cost flow.
   ///
-  /// \param Graph The directed graph type the algorithm runs on.
-  /// \param LowerMap The type of the lower bound map.
-  /// \param CapacityMap The type of the capacity (upper bound) map.
-  /// \param CostMap The type of the cost (length) map.
-  /// \param SupplyMap The type of the supply map.
+  /// \tparam Graph The directed graph type the algorithm runs on.
+  /// \tparam LowerMap The type of the lower bound map.
+  /// \tparam CapacityMap The type of the capacity (upper bound) map.
+  /// \tparam CostMap The type of the cost (length) map.
+  /// \tparam SupplyMap The type of the supply map.
   ///
   /// \warning
-  /// - 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.
+  /// - Edge capacities and costs should be \e non-negative \e integers.
+  /// - Supply values should be \e signed \e integers.
+  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
+  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
+  ///   convertible to each other.
+  /// - All value types must be convertible to \c CostMap::Value, which
+  ///   must be signed type.
   ///
   /// \author Peter Kovacs
 
   template < typename Graph,
              typename LowerMap = typename Graph::template EdgeMap<int>,
-             typename CapacityMap = LowerMap,
+             typename CapacityMap = typename Graph::template EdgeMap<int>,
              typename CostMap = typename Graph::template EdgeMap<int>,
-             typename SupplyMap = typename Graph::template NodeMap
-                                  <typename CapacityMap::Value> >
+             typename SupplyMap = typename Graph::template NodeMap<int> >
   class CapacityScaling
   {
     GRAPH_TYPEDEFS(typename Graph);
 
-    typedef typename LowerMap::Value Lower;
     typedef typename CapacityMap::Value Capacity;
     typedef typename CostMap::Value Cost;
     typedef typename SupplyMap::Value Supply;
@@ -77,23 +76,21 @@
 
   public:
 
-    /// Type to enable or disable capacity scaling.
-    enum ScalingEnum {
-      WITH_SCALING = 0,
-      WITHOUT_SCALING = -1
-    };
-
     /// 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;
 
-  protected:
+  private:
 
     /// \brief Special implementation of the \ref Dijkstra algorithm
-    /// for finding shortest paths in the residual network of the graph
-    /// with respect to the reduced edge costs and modifying the
-    /// node potentials according to the distance of the nodes.
+    /// for finding shortest paths in the residual network.
+    ///
+    /// \ref ResidualDijkstra is a special implementation of the
+    /// \ref Dijkstra algorithm for finding shortest paths in the
+    /// residual network of the graph with respect to the reduced edge
+    /// costs and modifying the node potentials according to the
+    /// distance of the nodes.
     class ResidualDijkstra
     {
       typedef typename Graph::template NodeMap<Cost> CostNodeMap;
@@ -102,75 +99,70 @@
       typedef typename Graph::template NodeMap<int> HeapCrossRef;
       typedef BinHeap<Cost, HeapCrossRef> Heap;
 
-    protected:
+    private:
 
-      /// The directed graph the algorithm runs on.
-      const Graph &graph;
+      // The directed graph the algorithm runs on
+      const Graph &_graph;
 
-      /// The flow map.
-      const FlowMap &flow;
-      /// The residual capacity map.
-      const CapacityEdgeMap &res_cap;
-      /// The cost map.
-      const CostMap &cost;
-      /// The excess map.
-      const SupplyNodeMap &excess;
+      // The main maps
+      const FlowMap &_flow;
+      const CapacityEdgeMap &_res_cap;
+      const CostMap &_cost;
+      const SupplyNodeMap &_excess;
+      PotentialMap &_potential;
 
-      /// The potential map.
-      PotentialMap &potential;
-
-      /// The distance map.
-      CostNodeMap dist;
-      /// The map of predecessors edges.
-      PredMap &pred;
-      /// The processed (i.e. permanently labeled) nodes.
-      std::vector<Node> proc_nodes;
+      // The distance map
+      CostNodeMap _dist;
+      // The pred edge map
+      PredMap &_pred;
+      // The processed (i.e. permanently labeled) nodes
+      std::vector<Node> _proc_nodes;
 
     public:
 
       /// The constructor of the class.
-      ResidualDijkstra( const Graph &_graph,
-                        const FlowMap &_flow,
-                        const CapacityEdgeMap &_res_cap,
-                        const CostMap &_cost,
-                        const SupplyMap &_excess,
-                        PotentialMap &_potential,
-                        PredMap &_pred ) :
-        graph(_graph), flow(_flow), res_cap(_res_cap), cost(_cost),
-        excess(_excess), potential(_potential), dist(_graph),
-        pred(_pred)
+      ResidualDijkstra( const Graph &graph,
+                        const FlowMap &flow,
+                        const CapacityEdgeMap &res_cap,
+                        const CostMap &cost,
+                        const SupplyMap &excess,
+                        PotentialMap &potential,
+                        PredMap &pred ) :
+        _graph(graph), _flow(flow), _res_cap(res_cap), _cost(cost),
+        _excess(excess), _potential(potential), _dist(graph),
+        _pred(pred)
       {}
 
       /// Runs the algorithm from the given source node.
       Node run(Node s, Capacity delta) {
-        HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
+        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
         Heap heap(heap_cross_ref);
         heap.push(s, 0);
-        pred[s] = INVALID;
-        proc_nodes.clear();
+        _pred[s] = INVALID;
+        _proc_nodes.clear();
 
         // Processing nodes
-        while (!heap.empty() && excess[heap.top()] > -delta) {
+        while (!heap.empty() && _excess[heap.top()] > -delta) {
           Node u = heap.top(), v;
-          Cost d = heap.prio() - potential[u], nd;
-          dist[u] = heap.prio();
+          Cost d = heap.prio() + _potential[u], nd;
+          _dist[u] = heap.prio();
           heap.pop();
-          proc_nodes.push_back(u);
+          _proc_nodes.push_back(u);
 
           // Traversing outgoing edges
-          for (OutEdgeIt e(graph, u); e != INVALID; ++e) {
-            if (res_cap[e] >= delta) {
-              v = graph.target(e);
+          for (OutEdgeIt e(_graph, u); e != INVALID; ++e) {
+            if (_res_cap[e] >= delta) {
+              v = _graph.target(e);
               switch(heap.state(v)) {
               case Heap::PRE_HEAP:
-                heap.push(v, d + cost[e] + potential[v]);
-                pred[v] = e;
+                heap.push(v, d + _cost[e] - _potential[v]);
+                _pred[v] = e;
                 break;
               case Heap::IN_HEAP:
-                nd = d + cost[e] + potential[v];
+                nd = d + _cost[e] - _potential[v];
                 if (nd < heap[v]) {
                   heap.decrease(v, nd);
-                  pred[v] = e;
+                  _pred[v] = e;
                 }
                 break;
               case Heap::POST_HEAP:
@@ -180,19 +172,19 @@
           }
 
           // Traversing incoming edges
-          for (InEdgeIt e(graph, u); e != INVALID; ++e) {
-            if (flow[e] >= delta) {
-              v = graph.source(e);
+          for (InEdgeIt e(_graph, u); e != INVALID; ++e) {
+            if (_flow[e] >= delta) {
+              v = _graph.source(e);
               switch(heap.state(v)) {
               case Heap::PRE_HEAP:
-                heap.push(v, d - cost[e] + potential[v]);
-                pred[v] = e;
+                heap.push(v, d - _cost[e] - _potential[v]);
+                _pred[v] = e;
                 break;
               case Heap::IN_HEAP:
-                nd = d - cost[e] + potential[v];
+                nd = d - _cost[e] - _potential[v];
                 if (nd < heap[v]) {
                   heap.decrease(v, nd);
-                  pred[v] = e;
+                  _pred[v] = e;
                 }
                 break;
               case Heap::POST_HEAP:
@@ -205,55 +197,53 @@
 
         // Updating potentials of processed nodes
         Node t = heap.top();
-        Cost dt = heap.prio();
-        for (int i = 0; i < proc_nodes.size(); ++i)
-          potential[proc_nodes[i]] -= dist[proc_nodes[i]] - dt;
+        Cost t_dist = heap.prio();
+        for (int i = 0; i < int(_proc_nodes.size()); ++i)
+          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 
         return t;
       }
 
     }; //class ResidualDijkstra
 
-  protected:
+  private:
 
-    /// The directed graph the algorithm runs on.
-    const Graph &graph;
-    /// The original lower bound map.
-    const LowerMap *lower;
-    /// The modified capacity map.
-    CapacityEdgeMap capacity;
-    /// The cost map.
-    const CostMap &cost;
-    /// The modified supply map.
-    SupplyNodeMap supply;
-    bool valid_supply;
+    // The directed graph the algorithm runs on
+    const Graph &_graph;
+    // The original lower bound map
+    const LowerMap *_lower;
+    // The modified capacity map
+    CapacityEdgeMap _capacity;
+    // The original cost map
+    const CostMap &_cost;
+    // The modified supply map
+    SupplyNodeMap _supply;
+    bool _valid_supply;
 
-    /// The edge map of the current flow.
-    FlowMap flow;
-    /// The potential node map.
-    PotentialMap potential;
+    // Edge map of the current flow
+    FlowMap _flow;
+    // Node map of the current potentials
+    PotentialMap _potential;
 
-    /// 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;
-    /// The deficit nodes (i.e. the nodes with negative excess).
-    std::vector<Node> deficit_nodes;
+    // The residual capacity map
+    CapacityEdgeMap _res_cap;
+    // The excess map
+    SupplyNodeMap _excess;
+    // The excess nodes (i.e. nodes with positive excess)
+    std::vector<Node> _excess_nodes;
+    // The deficit nodes (i.e. nodes with negative excess)
+    std::vector<Node> _deficit_nodes;
 
-    /// The scaling status (enabled or disabled).
-    ScalingEnum scaling;
-    /// The \c delta parameter used for capacity scaling.
-    Capacity delta;
-    /// The maximum number of phases.
-    int phase_num;
+    // The delta parameter used for capacity scaling
+    Capacity _delta;
+    // 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;
-    /// The map of predecessors edges.
-    PredMap pred;
+    // The pred edge map
+    PredMap _pred;
+    // Implementation of the Dijkstra algorithm for finding augmenting
+    // shortest paths in the residual network
+    ResidualDijkstra _dijkstra;
 
   public :
 
@@ -261,159 +251,158 @@
     ///
     /// General constructor of the class (with lower bounds).
     ///
-    /// \param _graph The directed graph the algorithm runs on.
-    /// \param _lower The lower bounds of the edges.
-    /// \param _capacity The capacities (upper bounds) of the edges.
-    /// \param _cost The cost (length) values of the edges.
-    /// \param _supply The supply values of the nodes (signed).
-    CapacityScaling( const Graph &_graph,
-                     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), potential(_graph, 0),
-      res_cap(_graph), excess(_graph), pred(_graph),
-      dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
+    /// \param graph The directed graph the algorithm runs on.
+    /// \param lower The lower bounds of the edges.
+    /// \param capacity The capacities (upper bounds) of the edges.
+    /// \param cost The cost (length) values of the edges.
+    /// \param supply The supply values of the nodes (signed).
+    CapacityScaling( const Graph &graph,
+                     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), _potential(graph, 0),
+      _res_cap(graph), _excess(graph), _pred(graph),
+      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     {
       // Removing non-zero lower bounds
-      capacity = subMap(_capacity, _lower);
-      res_cap = capacity;
+      _capacity = subMap(capacity, lower);
+      _res_cap = _capacity;
       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];
-        supply[n] = s;
+      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];
+        _supply[n] = s;
         sum += s;
       }
-      valid_supply = sum == 0;
+      _valid_supply = sum == 0;
     }
 
     /// \brief General constructor of the class (without lower bounds).
     ///
     /// General constructor of the class (without lower bounds).
     ///
-    /// \param _graph The directed graph the algorithm runs on.
-    /// \param _capacity The capacities (upper bounds) of the edges.
-    /// \param _cost The cost (length) values of the edges.
-    /// \param _supply The supply values of the nodes (signed).
-    CapacityScaling( const Graph &_graph,
-                     const CapacityMap &_capacity,
-                     const CostMap &_cost,
-                     const SupplyMap &_supply ) :
-      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
-      supply(_supply), flow(_graph, 0), potential(_graph, 0),
-      res_cap(_capacity), excess(_graph), pred(_graph),
-      dijkstra(graph, flow, res_cap, cost, excess, potential)
+    /// \param graph The directed graph the algorithm runs on.
+    /// \param capacity The capacities (upper bounds) of the edges.
+    /// \param cost The cost (length) values of the edges.
+    /// \param supply The supply values of the nodes (signed).
+    CapacityScaling( const Graph &graph,
+                     const CapacityMap &capacity,
+                     const CostMap &cost,
+                     const SupplyMap &supply ) :
+      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
+      _supply(supply), _flow(graph, 0), _potential(graph, 0),
+      _res_cap(capacity), _excess(graph), _pred(graph),
+      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     {
       // Checking the sum of supply values
       Supply sum = 0;
-      for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
-      valid_supply = sum == 0;
+      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
+      _valid_supply = sum == 0;
     }
 
     /// \brief Simple constructor of the class (with lower bounds).
     ///
     /// Simple constructor of the class (with lower bounds).
     ///
-    /// \param _graph The directed graph the algorithm runs on.
-    /// \param _lower The lower bounds of the edges.
-    /// \param _capacity The capacities (upper bounds) of the edges.
-    /// \param _cost The cost (length) values of the edges.
-    /// \param _s The source node.
-    /// \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).
-    CapacityScaling( const Graph &_graph,
-                     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), potential(_graph, 0),
-      res_cap(_graph), excess(_graph), pred(_graph),
-      dijkstra(graph, flow, res_cap, cost, excess, potential)
+    /// \param graph The directed graph the algorithm runs on.
+    /// \param lower The lower bounds of the edges.
+    /// \param capacity The capacities (upper bounds) of the edges.
+    /// \param cost The cost (length) values of the edges.
+    /// \param s The source node.
+    /// \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).
+    CapacityScaling( const Graph &graph,
+                     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), _potential(graph, 0),
+      _res_cap(graph), _excess(graph), _pred(graph),
+      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     {
       // Removing non-zero lower bounds
-      capacity = subMap(_capacity, _lower);
-      res_cap = capacity;
-      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;
+      _capacity = subMap(capacity, lower);
+      _res_cap = _capacity;
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        Supply sum = 0;
+        if (n == s) sum =  flow_value;
+        if (n == t) sum = -flow_value;
+        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
+          sum += lower[e];
+        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
+          sum -= lower[e];
+        _supply[n] = sum;
       }
-      valid_supply = true;
+      _valid_supply = true;
     }
 
     /// \brief Simple constructor of the class (without lower bounds).
     ///
     /// Simple constructor of the class (without lower bounds).
     ///
-    /// \param _graph The directed graph the algorithm runs on.
-    /// \param _capacity The capacities (upper bounds) of the edges.
-    /// \param _cost The cost (length) values of the edges.
-    /// \param _s The source node.
-    /// \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).
-    CapacityScaling( const Graph &_graph,
-                     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), potential(_graph, 0),
-      res_cap(_capacity), excess(_graph), pred(_graph),
-      dijkstra(graph, flow, res_cap, cost, excess, potential)
+    /// \param graph The directed graph the algorithm runs on.
+    /// \param capacity The capacities (upper bounds) of the edges.
+    /// \param cost The cost (length) values of the edges.
+    /// \param s The source node.
+    /// \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).
+    CapacityScaling( const Graph &graph,
+                     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), _potential(graph, 0),
+      _res_cap(capacity), _excess(graph), _pred(graph),
+      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     {
-      supply[_s] =  _flow_value;
-      supply[_t] = -_flow_value;
-      valid_supply = true;
+      _supply[s] =  flow_value;
+      _supply[t] = -flow_value;
+      _valid_supply = true;
     }
 
     /// \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.
+    /// \param scaling Enable or disable capacity scaling.
     /// If the maximum edge capacity and/or the amount of total supply
-    /// is small, the algorithm could be slightly faster without
+    /// is rather 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();
+    bool run(bool scaling = true) {
+      return init(scaling) && start();
     }
 
-    /// \brief Returns a const reference to the flow map.
+    /// \brief Returns a const reference to the edge map storing the
+    /// found flow.
     ///
-    /// Returns a const reference to the flow map.
+    /// Returns a const reference to the edge map storing the found flow.
     ///
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return flow;
+      return _flow;
     }
 
-    /// \brief Returns a const reference to the potential map (the dual
-    /// solution).
+    /// \brief Returns a const reference to the node map storing the
+    /// found potentials (the dual solution).
     ///
-    /// Returns a const reference to the potential map (the dual
-    /// solution).
+    /// Returns a const reference to the node map storing the found
+    /// potentials (the dual solution).
     ///
     /// \pre \ref run() must be called before using this function.
     const PotentialMap& potentialMap() const {
-      return potential;
+      return _potential;
     }
 
     /// \brief Returns the total cost of the found flow.
@@ -424,47 +413,45 @@
     /// \pre \ref run() must be called before using this function.
     Cost totalCost() const {
       Cost c = 0;
-      for (EdgeIt e(graph); e != INVALID; ++e)
-        c += flow[e] * cost[e];
+      for (EdgeIt e(_graph); e != INVALID; ++e)
+        c += _flow[e] * _cost[e];
       return c;
     }
 
-  protected:
+  private:
 
     /// Initializes the algorithm.
-    bool init(int scaling_mode) {
-      if (!valid_supply) return false;
-      excess = supply;
+    bool init(bool scaling) {
+      if (!_valid_supply) return false;
+      _excess = _supply;
 
       // Initilaizing delta value
-      if (scaling_mode == WITH_SCALING) {
+      if (scaling) {
         // With scaling
         Supply max_sup = 0, max_dem = 0;
-        for (NodeIt n(graph); n != INVALID; ++n) {
-          if ( supply[n] > max_sup) max_sup =  supply[n];
-          if (-supply[n] > max_dem) max_dem = -supply[n];
+        for (NodeIt n(_graph); n != INVALID; ++n) {
+          if ( _supply[n] > max_sup) max_sup =  _supply[n];
+          if (-_supply[n] > max_dem) max_dem = -_supply[n];
         }
         if (max_dem < max_sup) max_sup = max_dem;
-        phase_num = 0;
-        for (delta = 1; 2 * delta <= max_sup; delta *= 2)
-          ++phase_num;
+        _phase_num = 0;
+        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
+          ++_phase_num;
       } else {
         // Without scaling
-        delta = 1;
+        _delta = 1;
       }
       return true;
     }
 
-    /// Executes the algorithm.
     bool start() {
-      if (delta > 1)
+      if (_delta > 1)
         return startWithScaling();
       else
         return startWithoutScaling();
     }
 
-    /// \brief Executes the capacity scaling version of the successive
-    /// shortest path algorithm.
+    /// Executes the capacity scaling algorithm.
     bool startWithScaling() {
       // Processing capacity scaling phases
       Node s, t;
@@ -472,39 +459,39 @@
       int factor = 4;
       while (true) {
         // Saturating all edges not satisfying the optimality condition
-        for (EdgeIt e(graph); e != INVALID; ++e) {
-          Node u = graph.source(e), v = graph.target(e);
-          Cost c = cost[e] - potential[u] + potential[v];
-          if (c < 0 && res_cap[e] >= delta) {
-            excess[u] -= res_cap[e];
-            excess[v] += res_cap[e];
-            flow[e] = capacity[e];
-            res_cap[e] = 0;
+        for (EdgeIt e(_graph); e != INVALID; ++e) {
+          Node u = _graph.source(e), v = _graph.target(e);
+          Cost c = _cost[e] + _potential[u] - _potential[v];
+          if (c < 0 && _res_cap[e] >= _delta) {
+            _excess[u] -= _res_cap[e];
+            _excess[v] += _res_cap[e];
+            _flow[e] = _capacity[e];
+            _res_cap[e] = 0;
           }
-          else if (c > 0 && flow[e] >= delta) {
-            excess[u] += flow[e];
-            excess[v] -= flow[e];
-            flow[e] = 0;
-            res_cap[e] = capacity[e];
+          else if (c > 0 && _flow[e] >= _delta) {
+            _excess[u] += _flow[e];
+            _excess[v] -= _flow[e];
+            _flow[e] = 0;
+            _res_cap[e] = _capacity[e];
           }
         }
 
         // Finding excess nodes and deficit nodes
-        excess_nodes.clear();
-        deficit_nodes.clear();
-        for (NodeIt n(graph); n != INVALID; ++n) {
-          if (excess[n] >=  delta) excess_nodes.push_back(n);
-          if (excess[n] <= -delta) deficit_nodes.push_back(n);
+        _excess_nodes.clear();
+        _deficit_nodes.clear();
+        for (NodeIt n(_graph); n != INVALID; ++n) {
+          if (_excess[n] >=  _delta) _excess_nodes.push_back(n);
+          if (_excess[n] <= -_delta) _deficit_nodes.push_back(n);
         }
         int next_node = 0;
 
         // Finding augmenting shortest paths
-        while (next_node < excess_nodes.size()) {
+        while (next_node < int(_excess_nodes.size())) {
           // Checking deficit nodes
-          if (delta > 1) {
+          if (_delta > 1) {
             bool delta_deficit = false;
-            for (int i = 0; i < deficit_nodes.size(); ++i) {
-              if (excess[deficit_nodes[i]] <= -delta) {
+            for (int i = 0; i < int(_deficit_nodes.size()); ++i) {
+              if (_excess[_deficit_nodes[i]] <= -_delta) {
                 delta_deficit = true;
                 break;
               }
@@ -513,9 +500,9 @@
           }
 
           // Running Dijkstra
-          s = excess_nodes[next_node];
-          if ((t = dijkstra.run(s, delta)) == INVALID) {
-            if (delta > 1) {
+          s = _excess_nodes[next_node];
+          if ((t = _dijkstra.run(s, _delta)) == INVALID) {
+            if (_delta > 1) {
               ++next_node;
               continue;
             }
@@ -523,107 +510,106 @@
           }
 
           // Augmenting along a shortest path from s to t.
-          Capacity d = excess[s] < -excess[t] ? excess[s] : -excess[t];
+          Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
           Node u = t;
           Edge e;
-          if (d > delta) {
-            while ((e = pred[u]) != INVALID) {
+          if (d > _delta) {
+            while ((e = _pred[u]) != INVALID) {
               Capacity rc;
-              if (u == graph.target(e)) {
-                rc = res_cap[e];
-                u = graph.source(e);
+              if (u == _graph.target(e)) {
+                rc = _res_cap[e];
+                u = _graph.source(e);
               } else {
-                rc = flow[e];
-                u = graph.target(e);
+                rc = _flow[e];
+                u = _graph.target(e);
               }
               if (rc < d) d = rc;
             }
           }
           u = t;
-          while ((e = pred[u]) != INVALID) {
-            if (u == graph.target(e)) {
-              flow[e] += d;
-              res_cap[e] -= d;
-              u = graph.source(e);
+          while ((e = _pred[u]) != INVALID) {
+            if (u == _graph.target(e)) {
+              _flow[e] += d;
+              _res_cap[e] -= d;
+              u = _graph.source(e);
             } else {
-              flow[e] -= d;
-              res_cap[e] += d;
-              u = graph.target(e);
+              _flow[e] -= d;
+              _res_cap[e] += d;
+              u = _graph.target(e);
             }
           }
-          excess[s] -= d;
-          excess[t] += d;
+          _excess[s] -= d;
+          _excess[t] += d;
 
-          if (excess[s] < delta) ++next_node;
+          if (_excess[s] < _delta) ++next_node;
         }
 
-        if (delta == 1) break;
-        if (++phase_cnt > phase_num / 4) factor = 2;
-        delta = delta <= factor ? 1 : delta / factor;
+        if (_delta == 1) break;
+        if (++phase_cnt > _phase_num / 4) factor = 2;
+        _delta = _delta <= factor ? 1 : _delta / factor;
       }
 
       // Handling non-zero lower bounds
-      if (lower) {
-        for (EdgeIt e(graph); e != INVALID; ++e)
-          flow[e] += (*lower)[e];
+      if (_lower) {
+        for (EdgeIt e(_graph); e != INVALID; ++e)
+          _flow[e] += (*_lower)[e];
       }
       return true;
     }
 
-    /// \brief Executes the successive shortest path algorithm without
-    /// capacity scaling.
+    /// Executes the successive shortest path algorithm.
     bool startWithoutScaling() {
       // Finding excess nodes
-      for (NodeIt n(graph); n != INVALID; ++n)
-        if (excess[n] > 0) excess_nodes.push_back(n);
-      if (excess_nodes.size() == 0) return true;
+      for (NodeIt n(_graph); n != INVALID; ++n)
+        if (_excess[n] > 0) _excess_nodes.push_back(n);
+      if (_excess_nodes.size() == 0) return true;
       int next_node = 0;
 
       // Finding shortest paths
       Node s, t;
-      while ( excess[excess_nodes[next_node]] > 0 ||
-              ++next_node < excess_nodes.size() )
+      while ( _excess[_excess_nodes[next_node]] > 0 ||
+              ++next_node < int(_excess_nodes.size()) )
       {
         // Running Dijkstra
-        s = excess_nodes[next_node];
-        if ((t = dijkstra.run(s, 1)) == INVALID)
+        s = _excess_nodes[next_node];
+        if ((t = _dijkstra.run(s, 1)) == INVALID)
           return false;
 
         // Augmenting along a shortest path from s to t
-        Capacity d = excess[s] < -excess[t] ? excess[s] : -excess[t];
+        Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
         Node u = t;
         Edge e;
-        while ((e = pred[u]) != INVALID) {
+        while ((e = _pred[u]) != INVALID) {
           Capacity rc;
-          if (u == graph.target(e)) {
-            rc = res_cap[e];
-            u = graph.source(e);
+          if (u == _graph.target(e)) {
+            rc = _res_cap[e];
+            u = _graph.source(e);
           } else {
-            rc = flow[e];
-            u = graph.target(e);
+            rc = _flow[e];
+            u = _graph.target(e);
           }
           if (rc < d) d = rc;
         }
         u = t;
-        while ((e = pred[u]) != INVALID) {
-          if (u == graph.target(e)) {
-            flow[e] += d;
-            res_cap[e] -= d;
-            u = graph.source(e);
+        while ((e = _pred[u]) != INVALID) {
+          if (u == _graph.target(e)) {
+            _flow[e] += d;
+            _res_cap[e] -= d;
+            u = _graph.source(e);
           } else {
-            flow[e] -= d;
-            res_cap[e] += d;
-            u = graph.target(e);
+            _flow[e] -= d;
+            _res_cap[e] += d;
+            u = _graph.target(e);
           }
         }
-        excess[s] -= d;
-        excess[t] += d;
+        _excess[s] -= d;
+        _excess[t] += d;
       }
 
       // Handling non-zero lower bounds
-      if (lower) {
-        for (EdgeIt e(graph); e != INVALID; ++e)
-          flow[e] += (*lower)[e];
+      if (_lower) {
+        for (EdgeIt e(_graph); e != INVALID; ++e)
+          _flow[e] += (*_lower)[e];
       }
       return true;
     }