LEMON/LEMON-official Changeset - r903:f3bc4e9b5f3a

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r903:f3bc4e9b5f3a

« 889:a7e93d

935:2914b6 »

r903:f3bc4e9b5f3a

Sat, 20 Feb 2010 18:39:03

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

New heuristics for MCF algorithms (#340) and some implementation improvements. - A useful heuristic is added to NetworkSimplex to make the initial pivots faster. - A powerful global update heuristic is added to CostScaling and the implementation is reworked with various improvements. - Better relabeling in CostScaling to improve numerical stability and make the code faster. - A small improvement is made in CapacityScaling for better delta computation. - Add notes to the classes about the usage of vector<char> instead of vector<bool> for efficiency reasons.

0 4 0

default

4 files changed with 377 insertions and 161 deletions:

lemon/capacity_scaling.h

lemon/cost_scaling.h

246

130

lemon/cycle_canceling.h

lemon/network_simplex.h

118

↑ Collapse diff ↑

lemon/capacity_scaling.h

Show inline comments

@@ -89,99 +89,100 @@
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CapacityScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// The type of the heap used for internal Dijkstra computations
 		    typedef typename TR::Heap Heap;
 		    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> BoolVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    CostVector _pi;
 		    ValueVector _excess;
 		    IntVector _excess_nodes;
 		    IntVector _deficit_nodes;
 		    Value _delta;
 		    int _factor;
 		    IntVector _pred;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
@@ -719,105 +720,105 @@
+		        }
 		      } else {
 		        for (int j = 0; j != _res_arc_num; ++j) {
 		          _res_cap[j] = _forward[j] ? _upper[j] : 0;
+		        }
+		      }
 		      // Handle negative costs
 		      for (int i = 0; i != _root; ++i) {
 		        last_out = _first_out[i+1] - 1;
 		        for (int j = _first_out[i]; j != last_out; ++j) {
 		          Value rc = _res_cap[j];
 		          if (_cost[j] < 0 && rc > 0) {
 		            if (rc >= MAX) return UNBOUNDED;
 		            _excess[i] -= rc;
 		            _excess[_target[j]] += rc;
 		            _res_cap[j] = 0;
 		            _res_cap[_reverse[j]] += rc;
+		          }
+		        }
+		      }
 		      // Handle GEQ supply type
 		      if (_sum_supply < 0) {
 		        _pi[_root] = 0;
 		        _excess[_root] = -_sum_supply;
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int ra = _reverse[a];
 		          _res_cap[a] = -_sum_supply + 1;
 		          _res_cap[ra] = 0;
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
+		        }
 		      } else {
 		        _pi[_root] = 0;
 		        _excess[_root] = 0;
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int ra = _reverse[a];
 		          _res_cap[a] = 1;
 		          _res_cap[ra] = 0;
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
+		        }
+		      }
 		      // Initialize delta value
 		      if (_factor > 1) {
 		        // With scaling
 		        Value max_sup = 0, max_dem = 0;
 		        for (int i = 0; i != _node_num; ++i) {
 		        Value max_sup = 0, max_dem = 0, max_cap = 0;
 		        for (int i = 0; i != _root; ++i) {
 		          Value ex = _excess[i];
 		          if ( ex > max_sup) max_sup =  ex;
 		          if (-ex > max_dem) max_dem = -ex;
+		        }
 		        Value max_cap = 0;
 		        for (int j = 0; j != _res_arc_num; ++j) {
 		          if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
 		          int last_out = _first_out[i+1] - 1;
 		          for (int j = _first_out[i]; j != last_out; ++j) {
 		            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+		          }
+		        }
 		        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
 		        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
 		      } else {
 		        // Without scaling
 		        _delta = 1;
+		      }
 		      return OPTIMAL;
+		    }
 		    ProblemType start() {
 		      // Execute the algorithm
 		      ProblemType pt;
 		      if (_delta > 1)
 		        pt = startWithScaling();
 		      else
 		        pt = startWithoutScaling();
 		      // Handle non-zero lower bounds
 		      if (_have_lower) {
 		        int limit = _first_out[_root];
 		        for (int j = 0; j != limit; ++j) {
 		          if (!_forward[j]) _res_cap[j] += _lower[j];
+		        }
+		      }
 		      // Shift potentials if necessary
 		      Cost pr = _pi[_root];
 		      if (_sum_supply < 0 || pr > 0) {
 		        for (int i = 0; i != _node_num; ++i) {
 		          _pi[i] -= pr;
+		        }
+		      }
 		      return pt;
+		    }
 		    // Execute the capacity scaling algorithm
 		    ProblemType startWithScaling() {
 		      // Perform capacity scaling phases
 		      int s, t;
 		      ResidualDijkstra _dijkstra(*this);
 		      while (true) {
 		        // Saturate all arcs not satisfying the optimality condition
 		        int last_out;
 		        for (int u = 0; u != _node_num; ++u) {
 		          last_out = _sum_supply < 0 ?

lemon/cost_scaling.h

Show inline comments

@@ -152,171 +152,179 @@
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the internal method.
 		    ///
 		    /// Enum type containing constants for selecting the internal method
 		    /// for the \ref run() function.
 		    ///
 		    /// \ref CostScaling provides three internal methods that differ mainly
 		    /// in their base operations, which are used in conjunction with the
 		    /// relabel operation.
 		    /// By default, the so called \ref PARTIAL_AUGMENT
 		    /// "Partial Augment-Relabel" method is used, which proved to be
 		    /// the most efficient and the most robust on various test inputs.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum Method {
 		      /// Local push operations are used, i.e. flow is moved only on one
 		      /// admissible arc at once.
 		      PUSH,
 		      /// Augment operations are used, i.e. flow is moved on admissible
 		      /// paths from a node with excess to a node with deficit.
 		      AUGMENT,
 		      /// Partial augment operations are used, i.e. flow is moved on
 		      /// admissible paths started from a node with excess, but the
 		      /// lengths of these paths are limited. This method can be viewed
 		      /// as a combined version of the previous two operations.
 		      PARTIAL_AUGMENT
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> BoolVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<LargeCost> LargeCostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
+		      }
 		    private:
 		      std::vector<Value>& _v;
 		    };
 		    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
 		    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_node_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    int _sup_node_num;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _scost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    LargeCostVector _cost;
 		    LargeCostVector _pi;
 		    ValueVector _excess;
 		    IntVector _next_out;
 		    std::deque<int> _active_nodes;
 		    // Data for scaling
 		    LargeCost _epsilon;
 		    int _alpha;
 		    IntVector _buckets;
 		    IntVector _bucket_next;
 		    IntVector _bucket_prev;
 		    IntVector _rank;
 		    int _max_rank;
 		    // Data for a StaticDigraph structure
 		    typedef std::pair<int, int> IntPair;
 		    StaticDigraph _sgr;
 		    std::vector<IntPair> _arc_vec;
 		    std::vector<LargeCost> _cost_vec;
 		    LargeCostArcMap _cost_map;
 		    LargeCostNodeMap _pi_map;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeCost type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type, which is used for internal computations in the algorithm.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    template <typename T>
 		    struct SetLargeCost
 		      : public CostScaling<GR, V, C, SetLargeCostTraits<T> > {
 		      typedef  CostScaling<GR, V, C, SetLargeCostTraits<T> > Create;
 		    };
 		    /// @}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
@@ -757,414 +765,522 @@
+		        }
+		      }
 		      Value ex, max_cap = 0;
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        ex = _excess[i];
 		        _excess[i] = 0;
 		        if (ex < 0) max_cap -= ex;
+		      }
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        if (_upper[j] >= MAX) _upper[j] = max_cap;
+		      }
 		      // Initialize the large cost vector and the epsilon parameter
 		      _epsilon = 0;
 		      LargeCost lc;
 		      for (int i = 0; i != _root; ++i) {
 		        last_out = _first_out[i+1];
 		        for (int j = _first_out[i]; j != last_out; ++j) {
 		          lc = static_cast<LargeCost>(_scost[j]) * _res_node_num * _alpha;
 		          _cost[j] = lc;
 		          if (lc > _epsilon) _epsilon = lc;
+		        }
+		      }
 		      _epsilon /= _alpha;
 		      // Initialize maps for Circulation and remove non-zero lower bounds
 		      ConstMap<Arc, Value> low(0);
 		      typedef typename Digraph::template ArcMap<Value> ValueArcMap;
 		      typedef typename Digraph::template NodeMap<Value> ValueNodeMap;
 		      ValueArcMap cap(_graph), flow(_graph);
 		      ValueNodeMap sup(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        sup[n] = _supply[_node_id[n]];
+		      }
 		      if (_have_lower) {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          int j = _arc_idf[a];
 		          Value c = _lower[j];
 		          cap[a] = _upper[j] - c;
 		          sup[_graph.source(a)] -= c;
 		          sup[_graph.target(a)] += c;
+		        }
 		      } else {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          cap[a] = _upper[_arc_idf[a]];
+		        }
+		      }
 		      _sup_node_num = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if (sup[n] > 0) ++_sup_node_num;
+		      }
 		      // Find a feasible flow using Circulation
 		      Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>
 		        circ(_graph, low, cap, sup);
 		      if (!circ.flowMap(flow).run()) return INFEASIBLE;
 		      // Set residual capacities and handle GEQ supply type
 		      if (_sum_supply < 0) {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          Value fa = flow[a];
 		          _res_cap[_arc_idf[a]] = cap[a] - fa;
 		          _res_cap[_arc_idb[a]] = fa;
 		          sup[_graph.source(a)] -= fa;
 		          sup[_graph.target(a)] += fa;
+		        }
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          _excess[_node_id[n]] = sup[n];
+		        }
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int u = _target[a];
 		          int ra = _reverse[a];
 		          _res_cap[a] = -_sum_supply + 1;
 		          _res_cap[ra] = -_excess[u];
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
 		          _excess[u] = 0;
+		        }
 		      } else {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          Value fa = flow[a];
 		          _res_cap[_arc_idf[a]] = cap[a] - fa;
 		          _res_cap[_arc_idb[a]] = fa;
+		        }
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int ra = _reverse[a];
-		          _res_cap[a] = 1;
+		          _res_cap[a] = 0;
 		          _res_cap[ra] = 0;
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
+		        }
+		      }
 		      return OPTIMAL;
+		    }
 		    // Execute the algorithm and transform the results
 		    void start(Method method) {
 		      // Maximum path length for partial augment
 		      const int MAX_PATH_LENGTH = 4;
 		      // Initialize data structures for buckets
 		      _max_rank = _alpha * _res_node_num;
 		      _buckets.resize(_max_rank);
 		      _bucket_next.resize(_res_node_num + 1);
 		      _bucket_prev.resize(_res_node_num + 1);
 		      _rank.resize(_res_node_num + 1);
 		      // Execute the algorithm
 		      switch (method) {
 		        case PUSH:
 		          startPush();
 		          break;
 		        case AUGMENT:
 		          startAugment();
 		          break;
 		        case PARTIAL_AUGMENT:
 		          startAugment(MAX_PATH_LENGTH);
 		          break;
+		      }
 		      // Compute node potentials for the original costs
 		      _arc_vec.clear();
 		      _cost_vec.clear();
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        if (_res_cap[j] > 0) {
 		          _arc_vec.push_back(IntPair(_source[j], _target[j]));
 		          _cost_vec.push_back(_scost[j]);
+		        }
+		      }
 		      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
 		      typename BellmanFord<StaticDigraph, LargeCostArcMap>
 		        ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map);
 		      bf.distMap(_pi_map);
 		      bf.init(0);
 		      bf.start();
 		      // Handle non-zero lower bounds
 		      if (_have_lower) {
 		        int limit = _first_out[_root];
 		        for (int j = 0; j != limit; ++j) {
 		          if (!_forward[j]) _res_cap[j] += _lower[j];
+		        }
+		      }
+		    }
 		    // Initialize a cost scaling phase
 		    void initPhase() {
 		      // Saturate arcs not satisfying the optimality condition
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        int last_out = _first_out[u+1];
 		        LargeCost pi_u = _pi[u];
 		        for (int a = _first_out[u]; a != last_out; ++a) {
 		          int v = _target[a];
 		          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
 		            Value delta = _res_cap[a];
 		            _excess[u] -= delta;
 		            _excess[v] += delta;
 		            _res_cap[a] = 0;
 		            _res_cap[_reverse[a]] += delta;
+		          }
+		        }
+		      }
 		      // Find active nodes (i.e. nodes with positive excess)
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        if (_excess[u] > 0) _active_nodes.push_back(u);
+		      }
 		      // Initialize the next arcs
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        _next_out[u] = _first_out[u];
+		      }
+		    }
 		    // Early termination heuristic
 		    bool earlyTermination() {
 		      const double EARLY_TERM_FACTOR = 3.0;
 		      // Build a static residual graph
 		      _arc_vec.clear();
 		      _cost_vec.clear();
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        if (_res_cap[j] > 0) {
 		          _arc_vec.push_back(IntPair(_source[j], _target[j]));
 		          _cost_vec.push_back(_cost[j] + 1);
+		        }
+		      }
 		      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
 		      // Run Bellman-Ford algorithm to check if the current flow is optimal
 		      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
 		      bf.init(0);
 		      bool done = false;
 		      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
 		      for (int i = 0; i < K && !done; ++i) {
 		        done = bf.processNextWeakRound();
+		      }
 		      return done;
+		    }
 		    // Global potential update heuristic
 		    void globalUpdate() {
 		      int bucket_end = _root + 1;
 		      // Initialize buckets
 		      for (int r = 0; r != _max_rank; ++r) {
 		        _buckets[r] = bucket_end;
+		      }
 		      Value total_excess = 0;
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        if (_excess[i] < 0) {
 		          _rank[i] = 0;
 		          _bucket_next[i] = _buckets[0];
 		          _bucket_prev[_buckets[0]] = i;
 		          _buckets[0] = i;
 		        } else {
 		          total_excess += _excess[i];
 		          _rank[i] = _max_rank;
+		        }
+		      }
 		      if (total_excess == 0) return;
 		      // Search the buckets
 		      int r = 0;
 		      for ( ; r != _max_rank; ++r) {
 		        while (_buckets[r] != bucket_end) {
 		          // Remove the first node from the current bucket
 		          int u = _buckets[r];
 		          _buckets[r] = _bucket_next[u];
 		          // Search the incomming arcs of u
 		          LargeCost pi_u = _pi[u];
 		          int last_out = _first_out[u+1];
 		          for (int a = _first_out[u]; a != last_out; ++a) {
 		            int ra = _reverse[a];
 		            if (_res_cap[ra] > 0) {
 		              int v = _source[ra];
 		              int old_rank_v = _rank[v];
 		              if (r < old_rank_v) {
 		                // Compute the new rank of v
 		                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
 		                int new_rank_v = old_rank_v;
 		                if (nrc < LargeCost(_max_rank))
 		                  new_rank_v = r + 1 + int(nrc);
 		                // Change the rank of v
 		                if (new_rank_v < old_rank_v) {
 		                  _rank[v] = new_rank_v;
 		                  _next_out[v] = _first_out[v];
 		                  // Remove v from its old bucket
 		                  if (old_rank_v < _max_rank) {
 		                    if (_buckets[old_rank_v] == v) {
 		                      _buckets[old_rank_v] = _bucket_next[v];
 		                    } else {
 		                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
 		                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
+		                    }
+		                  }
 		                  // Insert v to its new bucket
 		                  _bucket_next[v] = _buckets[new_rank_v];
 		                  _bucket_prev[_buckets[new_rank_v]] = v;
 		                  _buckets[new_rank_v] = v;
+		                }
+		              }
+		            }
+		          }
 		          // Finish search if there are no more active nodes
 		          if (_excess[u] > 0) {
 		            total_excess -= _excess[u];
 		            if (total_excess <= 0) break;
+		          }
+		        }
 		        if (total_excess <= 0) break;
+		      }
 		      // Relabel nodes
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        int k = std::min(_rank[u], r);
 		        if (k > 0) {
 		          _pi[u] -= _epsilon * k;
 		          _next_out[u] = _first_out[u];
+		        }
+		      }
+		    }
 		    /// Execute the algorithm performing augment and relabel operations
 		    void startAugment(int max_length = std::numeric_limits<int>::max()) {
 		      // Paramters for heuristics
 		      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
 		      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
 		      const int EARLY_TERM_EPSILON_LIMIT = 1000;
 		      const double GLOBAL_UPDATE_FACTOR = 3.0;
 		      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
 		        (_res_node_num + _sup_node_num * _sup_node_num));
 		      int next_update_limit = global_update_freq;
 		      int relabel_cnt = 0;
 		      // Perform cost scaling phases
 		      IntVector pred_arc(_res_node_num);
 		      std::vector<int> path_nodes;
 		      std::vector<int> path;
 		      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+		      {
 		        // "Early Termination" heuristic: use Bellman-Ford algorithm
 		        // to check if the current flow is optimal
 		        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
 		          _arc_vec.clear();
 		          _cost_vec.clear();
 		          for (int j = 0; j != _res_arc_num; ++j) {
 		            if (_res_cap[j] > 0) {
 		              _arc_vec.push_back(IntPair(_source[j], _target[j]));
 		              _cost_vec.push_back(_cost[j] + 1);
+		            }
+		          }
 		          _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
 		          BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
 		          bf.init(0);
 		          bool done = false;
 		          int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
 		          for (int i = 0; i < K && !done; ++i)
 		            done = bf.processNextWeakRound();
 		          if (done) break;
+		        }
 		        // Saturate arcs not satisfying the optimality condition
 		        for (int a = 0; a != _res_arc_num; ++a) {
 		          if (_res_cap[a] > 0 &&
 		              _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
 		            Value delta = _res_cap[a];
 		            _excess[_source[a]] -= delta;
 		            _excess[_target[a]] += delta;
 		            _res_cap[a] = 0;
 		            _res_cap[_reverse[a]] += delta;
+		          }
 		        // Early termination heuristic
 		        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
 		          if (earlyTermination()) break;
+		        }
 		        // Find active nodes (i.e. nodes with positive excess)
 		        for (int u = 0; u != _res_node_num; ++u) {
 		          if (_excess[u] > 0) _active_nodes.push_back(u);
+		        }
 		        // Initialize the next arcs
 		        for (int u = 0; u != _res_node_num; ++u) {
 		          _next_out[u] = _first_out[u];
+		        }
 		        // Initialize current phase
 		        initPhase();
 		        // Perform partial augment and relabel operations
 		        while (true) {
 		          // Select an active node (FIFO selection)
 		          while (_active_nodes.size() > 0 &&
 		                 _excess[_active_nodes.front()] <= 0) {
 		            _active_nodes.pop_front();
+		          }
 		          if (_active_nodes.size() == 0) break;
 		          int start = _active_nodes.front();
 		          path_nodes.clear();
 		          path_nodes.push_back(start);
 		          // Find an augmenting path from the start node
 		          path.clear();
 		          int tip = start;
 		          while (_excess[tip] >= 0 &&
 		                 int(path_nodes.size()) <= max_length) {
 		          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
 		            int u;
 		            LargeCost min_red_cost, rc;
 		            int last_out = _sum_supply < 0 ?
-		              _first_out[tip+1] : _first_out[tip+1] - 1;
+		            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
 		            int last_out = _first_out[tip+1];
 		            for (int a = _next_out[tip]; a != last_out; ++a) {
 		              if (_res_cap[a] > 0 &&
 		                  _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
 		                u = _target[a];
 		                pred_arc[u] = a;
 		              u = _target[a];
 		              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
 		                path.push_back(a);
 		                _next_out[tip] = a;
 		                tip = u;
 		                path_nodes.push_back(tip);
 		                goto next_step;
+		              }
+		            }
 		            // Relabel tip node
-		            min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
 		            min_red_cost = std::numeric_limits<LargeCost>::max();
 		            if (tip != start) {
 		              int ra = _reverse[path.back()];
 		              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
+		            }
 		            for (int a = _first_out[tip]; a != last_out; ++a) {
-		              rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
+		              rc = _cost[a] + pi_tip - _pi[_target[a]];
 		              if (_res_cap[a] > 0 && rc < min_red_cost) {
 		                min_red_cost = rc;
+		              }
+		            }
 		            _pi[tip] -= min_red_cost + _epsilon;
 		            // Reset the next arc of tip
 		            _next_out[tip] = _first_out[tip];
 		            ++relabel_cnt;
 		            // Step back
 		            if (tip != start) {
 		              path_nodes.pop_back();
 		              tip = path_nodes.back();
 		              tip = _source[path.back()];
 		              path.pop_back();
+		            }
 		          next_step: ;
+		          }
 		          // Augment along the found path (as much flow as possible)
 		          Value delta;
 		          int u, v = path_nodes.front(), pa;
 		          for (int i = 1; i < int(path_nodes.size()); ++i) {
 		          int pa, u, v = start;
 		          for (int i = 0; i != int(path.size()); ++i) {
 		            pa = path[i];
 		            u = v;
 		            v = path_nodes[i];
 		            pa = pred_arc[v];
 		            v = _target[pa];
 		            delta = std::min(_res_cap[pa], _excess[u]);
 		            _res_cap[pa] -= delta;
 		            _res_cap[_reverse[pa]] += delta;
 		            _excess[u] -= delta;
 		            _excess[v] += delta;
 		            if (_excess[v] > 0 && _excess[v] <= delta)
 		              _active_nodes.push_back(v);
+		          }
 		          // Global update heuristic
 		          if (relabel_cnt >= next_update_limit) {
 		            globalUpdate();
 		            next_update_limit += global_update_freq;
+		          }
+		        }
+		      }
+		    }
 		    /// Execute the algorithm performing push and relabel operations
 		    void startPush() {
 		      // Paramters for heuristics
 		      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
 		      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
 		      const int EARLY_TERM_EPSILON_LIMIT = 1000;
 		      const double GLOBAL_UPDATE_FACTOR = 2.0;
 		      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
 		        (_res_node_num + _sup_node_num * _sup_node_num));
 		      int next_update_limit = global_update_freq;
 		      int relabel_cnt = 0;
 		      // Perform cost scaling phases
 		      BoolVector hyper(_res_node_num, false);
 		      LargeCostVector hyper_cost(_res_node_num);
 		      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+		      {
 		        // "Early Termination" heuristic: use Bellman-Ford algorithm
 		        // to check if the current flow is optimal
 		        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
 		          _arc_vec.clear();
 		          _cost_vec.clear();
 		          for (int j = 0; j != _res_arc_num; ++j) {
 		            if (_res_cap[j] > 0) {
 		              _arc_vec.push_back(IntPair(_source[j], _target[j]));
 		              _cost_vec.push_back(_cost[j] + 1);
+		            }
+		          }
 		          _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
 		          BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
 		          bf.init(0);
 		          bool done = false;
 		          int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
 		          for (int i = 0; i < K && !done; ++i)
 		            done = bf.processNextWeakRound();
 		          if (done) break;
 		        // Early termination heuristic
 		        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
 		          if (earlyTermination()) break;
+		        }
 		        // Saturate arcs not satisfying the optimality condition
 		        for (int a = 0; a != _res_arc_num; ++a) {
 		          if (_res_cap[a] > 0 &&
 		              _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
 		            Value delta = _res_cap[a];
 		            _excess[_source[a]] -= delta;
 		            _excess[_target[a]] += delta;
 		            _res_cap[a] = 0;
 		            _res_cap[_reverse[a]] += delta;
+		          }
+		        }
 		        // Find active nodes (i.e. nodes with positive excess)
 		        for (int u = 0; u != _res_node_num; ++u) {
 		          if (_excess[u] > 0) _active_nodes.push_back(u);
+		        }
 		        // Initialize the next arcs
 		        for (int u = 0; u != _res_node_num; ++u) {
 		          _next_out[u] = _first_out[u];
+		        }
 		        // Initialize current phase
 		        initPhase();
 		        // Perform push and relabel operations
 		        while (_active_nodes.size() > 0) {
 		          LargeCost min_red_cost, rc;
+		          LargeCost min_red_cost, rc, pi_n;
 		          Value delta;
 		          int n, t, a, last_out = _res_arc_num;
 		        next_node:
 		          // Select an active node (FIFO selection)
 		        next_node:
 		          n = _active_nodes.front();
 		          last_out = _sum_supply < 0 ?
 		            _first_out[n+1] : _first_out[n+1] - 1;
+		          last_out = _first_out[n+1];
 		          pi_n = _pi[n];
 		          // Perform push operations if there are admissible arcs
 		          if (_excess[n] > 0) {
 		            for (a = _next_out[n]; a != last_out; ++a) {
 		              if (_res_cap[a] > 0 &&
-		                  _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+		                  _cost[a] + pi_n - _pi[_target[a]] < 0) {
 		                delta = std::min(_res_cap[a], _excess[n]);
 		                t = _target[a];
 		                // Push-look-ahead heuristic
 		                Value ahead = -_excess[t];
 		                int last_out_t = _sum_supply < 0 ?
 		                  _first_out[t+1] : _first_out[t+1] - 1;
 		                int last_out_t = _first_out[t+1];
 		                LargeCost pi_t = _pi[t];
 		                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
 		                  if (_res_cap[ta] > 0 &&
-		                      _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0)
+		                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
 		                    ahead += _res_cap[ta];
 		                  if (ahead >= delta) break;
+		                }
 		                if (ahead < 0) ahead = 0;
 		                // Push flow along the arc
 		                if (ahead < delta) {
+		                if (ahead < delta && !hyper[t]) {
 		                  _res_cap[a] -= ahead;
 		                  _res_cap[_reverse[a]] += ahead;
 		                  _excess[n] -= ahead;
 		                  _excess[t] += ahead;
 		                  _active_nodes.push_front(t);
 		                  hyper[t] = true;
 		                  hyper_cost[t] = _cost[a] + pi_n - pi_t;
 		                  _next_out[n] = a;
 		                  goto next_node;
 		                } else {
 		                  _res_cap[a] -= delta;
 		                  _res_cap[_reverse[a]] += delta;
 		                  _excess[n] -= delta;
 		                  _excess[t] += delta;
 		                  if (_excess[t] > 0 && _excess[t] <= delta)
 		                    _active_nodes.push_back(t);
+		                }
 		                if (_excess[n] == 0) {
 		                  _next_out[n] = a;
 		                  goto remove_nodes;
+		                }
+		              }
+		            }
 		            _next_out[n] = a;
+		          }
 		          // Relabel the node if it is still active (or hyper)
 		          if (_excess[n] > 0 || hyper[n]) {
-		            min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
+		             min_red_cost = hyper[n] ? -hyper_cost[n] :
 		               std::numeric_limits<LargeCost>::max();
 		            for (int a = _first_out[n]; a != last_out; ++a) {
-		              rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
+		              rc = _cost[a] + pi_n - _pi[_target[a]];
 		              if (_res_cap[a] > 0 && rc < min_red_cost) {
 		                min_red_cost = rc;
+		              }
+		            }
 		            _pi[n] -= min_red_cost + _epsilon;
 		            _next_out[n] = _first_out[n];
 		            hyper[n] = false;
 		            // Reset the next arc
-		            _next_out[n] = _first_out[n];
+		            ++relabel_cnt;
+		          }
 		          // Remove nodes that are not active nor hyper
 		        remove_nodes:
 		          while ( _active_nodes.size() > 0 &&
 		                  _excess[_active_nodes.front()] <= 0 &&
 		                  !hyper[_active_nodes.front()] ) {
 		            _active_nodes.pop_front();
+		          }
 		          // Global update heuristic
 		          if (relabel_cnt >= next_update_limit) {
 		            globalUpdate();
 		            for (int u = 0; u != _res_node_num; ++u)
 		              hyper[u] = false;
 		            next_update_limit += global_update_freq;
+		          }
+		        }
+		      }
+		    }
 		  }; //class CostScaling
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_COST_SCALING_H

lemon/cycle_canceling.h

Show inline comments

@@ -99,151 +99,152 @@
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the used method.
 		    ///
 		    /// Enum type containing constants for selecting the used method
 		    /// for the \ref run() function.
 		    ///
 		    /// \ref CycleCanceling provides three different cycle-canceling
 		    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
 		    /// is used, which proved to be the most efficient and the most robust
 		    /// on various test inputs.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum Method {
 		      /// A simple cycle-canceling method, which uses the
 		      /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
 		      /// number for detecting negative cycles in the residual network.
 		      SIMPLE_CYCLE_CANCELING,
 		      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
 		      /// well-known strongly polynomial method
 		      /// \ref goldberg89cyclecanceling. It improves along a
 		      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
 		      /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
 		      MINIMUM_MEAN_CYCLE_CANCELING,
 		      /// The "Cancel And Tighten" algorithm, which can be viewed as an
 		      /// improved version of the previous method
 		      /// \ref goldberg89cyclecanceling.
 		      /// It is faster both in theory and in practice, its running time
 		      /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
 		      CANCEL_AND_TIGHTEN
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> CharVector;
 		    typedef std::vector<double> DoubleVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
+		      }
 		    private:
 		      std::vector<Value>& _v;
 		    };
 		    typedef StaticVectorMap<StaticDigraph::Node, Cost> CostNodeMap;
 		    typedef StaticVectorMap<StaticDigraph::Arc, Cost> CostArcMap;
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_node_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
-		    CharVector _forward;
+		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    CostVector _pi;
 		    // Data for a StaticDigraph structure
 		    typedef std::pair<int, int> IntPair;
 		    StaticDigraph _sgr;
 		    std::vector<IntPair> _arc_vec;
 		    std::vector<Cost> _cost_vec;
 		    IntVector _id_vec;
 		    CostArcMap _cost_map;
 		    CostNodeMap _pi_map;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CycleCanceling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      _cost_map(_cost_vec), _pi_map(_pi),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CycleCanceling must be signed");
@@ -888,98 +889,98 @@
+		          }
+		        }
+		      }
+		    }
 		    // Execute the "Minimum Mean Cycle Canceling" method
 		    void startMinMeanCycleCanceling() {
 		      typedef SimplePath<StaticDigraph> SPath;
 		      typedef typename SPath::ArcIt SPathArcIt;
 		      typedef typename Howard<StaticDigraph, CostArcMap>
 		        ::template SetPath<SPath>::Create MMC;
 		      SPath cycle;
 		      MMC mmc(_sgr, _cost_map);
 		      mmc.cycle(cycle);
 		      buildResidualNetwork();
 		      while (mmc.findMinMean() && mmc.cycleLength() < 0) {
 		        // Find the cycle
 		        mmc.findCycle();
 		        // Compute delta value
 		        Value delta = INF;
 		        for (SPathArcIt a(cycle); a != INVALID; ++a) {
 		          Value d = _res_cap[_id_vec[_sgr.id(a)]];
 		          if (d < delta) delta = d;
+		        }
 		        // Augment along the cycle
 		        for (SPathArcIt a(cycle); a != INVALID; ++a) {
 		          int j = _id_vec[_sgr.id(a)];
 		          _res_cap[j] -= delta;
 		          _res_cap[_reverse[j]] += delta;
+		        }
 		        // Rebuild the residual network
 		        buildResidualNetwork();
+		      }
+		    }
 		    // Execute the "Cancel And Tighten" method
 		    void startCancelAndTighten() {
 		      // Constants for the min mean cycle computations
 		      const double LIMIT_FACTOR = 1.0;
 		      const int MIN_LIMIT = 5;
 		      // Contruct auxiliary data vectors
 		      DoubleVector pi(_res_node_num, 0.0);
 		      IntVector level(_res_node_num);
 		      CharVector reached(_res_node_num);
 		      CharVector processed(_res_node_num);
 		      BoolVector reached(_res_node_num);
 		      BoolVector processed(_res_node_num);
 		      IntVector pred_node(_res_node_num);
 		      IntVector pred_arc(_res_node_num);
 		      std::vector<int> stack(_res_node_num);
 		      std::vector<int> proc_vector(_res_node_num);
 		      // Initialize epsilon
 		      double epsilon = 0;
 		      for (int a = 0; a != _res_arc_num; ++a) {
 		        if (_res_cap[a] > 0 && -_cost[a] > epsilon)
 		          epsilon = -_cost[a];
+		      }
 		      // Start phases
 		      Tolerance<double> tol;
 		      tol.epsilon(1e-6);
 		      int limit = int(LIMIT_FACTOR * std::sqrt(double(_res_node_num)));
 		      if (limit < MIN_LIMIT) limit = MIN_LIMIT;
 		      int iter = limit;
 		      while (epsilon * _res_node_num >= 1) {
 		        // Find and cancel cycles in the admissible network using DFS
 		        for (int u = 0; u != _res_node_num; ++u) {
 		          reached[u] = false;
 		          processed[u] = false;
+		        }
 		        int stack_head = -1;
 		        int proc_head = -1;
 		        for (int start = 0; start != _res_node_num; ++start) {
 		          if (reached[start]) continue;
 		          // New start node
 		          reached[start] = true;
 		          pred_arc[start] = -1;
 		          pred_node[start] = -1;
 		          // Find the first admissible outgoing arc
 		          double p = pi[start];
 		          int a = _first_out[start];
 		          int last_out = _first_out[start+1];
 		          for (; a != last_out && (_res_cap[a] == 0 ||
 		               !tol.negative(_cost[a] + p - pi[_target[a]])); ++a) ;
 		          if (a == last_out) {
 		            processed[start] = true;
 		            proc_vector[++proc_head] = start;
 		            continue;
+		          }
 		          stack[++stack_head] = a;
 		          while (stack_head >= 0) {

lemon/network_simplex.h

Show inline comments

@@ -119,522 +119,523 @@
 		    /// \brief Constants for selecting the pivot rule.
 		    ///
 		    /// Enum type containing constants for selecting the pivot rule for
 		    /// the \ref run() function.
 		    ///
 		    /// \ref NetworkSimplex provides five different pivot rule
 		    /// implementations that significantly affect the running time
 		    /// of the algorithm.
 		    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
 		    /// proved to be the most efficient and the most robust on various
 		    /// test inputs.
 		    /// However, another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum PivotRule {
 		      /// The \e First \e Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
 		      /// The \e Best \e Eligible pivot rule.
 		      /// The best eligible arc is selected in every iteration.
 		      BEST_ELIGIBLE,
 		      /// The \e Block \e Search pivot rule.
 		      /// A specified number of arcs are examined in every iteration
 		      /// in a wraparound fashion and the best eligible arc is selected
 		      /// from this block.
 		      BLOCK_SEARCH,
 		      /// The \e Candidate \e List pivot rule.
 		      /// In a major iteration a candidate list is built from eligible arcs
 		      /// in a wraparound fashion and in the following minor iterations
 		      /// the best eligible arc is selected from this list.
 		      CANDIDATE_LIST,
 		      /// The \e Altering \e Candidate \e List pivot rule.
 		      /// It is a modified version of the Candidate List method.
 		      /// It keeps only the several best eligible arcs from the former
 		      /// candidate list and extends this list in every iteration.
 		      ALTERING_LIST
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> CharVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		    // State constants for arcs
 		    enum ArcStateEnum {
 		      STATE_UPPER = -1,
 		      STATE_TREE  =  0,
 		      STATE_LOWER =  1
 		    };
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _all_arc_num;
 		    int _search_arc_num;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    SupplyType _stype;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_id;
 		    IntVector _source;
 		    IntVector _target;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    ValueVector _cap;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _flow;
 		    CostVector _pi;
 		    // Data for storing the spanning tree structure
 		    IntVector _parent;
 		    IntVector _pred;
 		    IntVector _thread;
 		    IntVector _rev_thread;
 		    IntVector _succ_num;
 		    IntVector _last_succ;
 		    IntVector _dirty_revs;
 		    CharVector _forward;
 		    CharVector _state;
 		    BoolVector _forward;
 		    BoolVector _state;
 		    int _root;
 		    // Temporary data used in the current pivot iteration
 		    int in_arc, join, u_in, v_in, u_out, v_out;
 		    int first, second, right, last;
 		    int stem, par_stem, new_stem;
 		    Value delta;
 		    const Value MAX;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  private:
 		    // Implementation of the First Eligible pivot rule
 		    class FirstEligiblePivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
-		      const CharVector &_state;
+		      const BoolVector &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _search_arc_num;
 		      // Pivot rule data
 		      int _next_arc;
 		    public:
 		      // Constructor
 		      FirstEligiblePivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c;
-		        for (int e = _next_arc; e < _search_arc_num; ++e) {
+		        for (int e = _next_arc; e != _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _in_arc = e;
 		            _next_arc = e + 1;
 		            return true;
+		          }
+		        }
-		        for (int e = 0; e < _next_arc; ++e) {
+		        for (int e = 0; e != _next_arc; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _in_arc = e;
 		            _next_arc = e + 1;
 		            return true;
+		          }
+		        }
 		        return false;
+		      }
 		    }; //class FirstEligiblePivotRule
 		    // Implementation of the Best Eligible pivot rule
 		    class BestEligiblePivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
-		      const CharVector &_state;
+		      const BoolVector &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _search_arc_num;
 		    public:
 		      // Constructor
 		      BestEligiblePivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
-		        for (int e = 0; e < _search_arc_num; ++e) {
+		        for (int e = 0; e != _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            _in_arc = e;
+		          }
+		        }
 		        return min < 0;
+		      }
 		    }; //class BestEligiblePivotRule
 		    // Implementation of the Block Search pivot rule
 		    class BlockSearchPivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
-		      const CharVector &_state;
+		      const BoolVector &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _search_arc_num;
 		      // Pivot rule data
 		      int _block_size;
 		      int _next_arc;
 		    public:
 		      // Constructor
 		      BlockSearchPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
-		        const double BLOCK_SIZE_FACTOR = 0.5;
+		        const double BLOCK_SIZE_FACTOR = 1.0;
 		        const int MIN_BLOCK_SIZE = 10;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
 		                                    std::sqrt(double(_search_arc_num))),
 		                                MIN_BLOCK_SIZE );
+		      }
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
 		        int cnt = _block_size;
 		        int e;
-		        for (e = _next_arc; e < _search_arc_num; ++e) {
+		        for (e = _next_arc; e != _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            _in_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (min < 0) goto search_end;
 		            cnt = _block_size;
+		          }
+		        }
-		        for (e = 0; e < _next_arc; ++e) {
+		        for (e = 0; e != _next_arc; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            _in_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (min < 0) goto search_end;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (min >= 0) return false;
 		      search_end:
 		        _next_arc = e;
 		        return true;
+		      }
 		    }; //class BlockSearchPivotRule
 		    // Implementation of the Candidate List pivot rule
 		    class CandidateListPivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
-		      const CharVector &_state;
+		      const BoolVector &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _search_arc_num;
 		      // Pivot rule data
 		      IntVector _candidates;
 		      int _list_length, _minor_limit;
 		      int _curr_length, _minor_count;
 		      int _next_arc;
 		    public:
 		      /// Constructor
 		      CandidateListPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
 		        const double LIST_LENGTH_FACTOR = 0.25;
 		        const int MIN_LIST_LENGTH = 10;
 		        const double MINOR_LIMIT_FACTOR = 0.1;
 		        const int MIN_MINOR_LIMIT = 3;
 		        _list_length = std::max( int(LIST_LENGTH_FACTOR *
 		                                     std::sqrt(double(_search_arc_num))),
 		                                 MIN_LIST_LENGTH );
 		        _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
 		                                 MIN_MINOR_LIMIT );
 		        _curr_length = _minor_count = 0;
 		        _candidates.resize(_list_length);
+		      }
 		      /// Find next entering arc
 		      bool findEnteringArc() {
 		        Cost min, c;
 		        int e;
 		        if (_curr_length > 0 && _minor_count < _minor_limit) {
 		          // Minor iteration: select the best eligible arc from the
 		          // current candidate list
 		          ++_minor_count;
 		          min = 0;
 		          for (int i = 0; i < _curr_length; ++i) {
 		            e = _candidates[i];
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
 		              _in_arc = e;
+		            }
 		            else if (c >= 0) {
 		              _candidates[i--] = _candidates[--_curr_length];
+		            }
+		          }
 		          if (min < 0) return true;
+		        }
 		        // Major iteration: build a new candidate list
 		        min = 0;
 		        _curr_length = 0;
-		        for (e = _next_arc; e < _search_arc_num; ++e) {
+		        for (e = _next_arc; e != _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _candidates[_curr_length++] = e;
 		            if (c < min) {
 		              min = c;
 		              _in_arc = e;
+		            }
 		            if (_curr_length == _list_length) goto search_end;
+		          }
+		        }
-		        for (e = 0; e < _next_arc; ++e) {
+		        for (e = 0; e != _next_arc; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _candidates[_curr_length++] = e;
 		            if (c < min) {
 		              min = c;
 		              _in_arc = e;
+		            }
 		            if (_curr_length == _list_length) goto search_end;
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        _minor_count = 1;
 		        _next_arc = e;
 		        return true;
+		      }
 		    }; //class CandidateListPivotRule
 		    // Implementation of the Altering Candidate List pivot rule
 		    class AlteringListPivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
-		      const CharVector &_state;
+		      const BoolVector &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _search_arc_num;
 		      // Pivot rule data
 		      int _block_size, _head_length, _curr_length;
 		      int _next_arc;
 		      IntVector _candidates;
 		      CostVector _cand_cost;
 		      // Functor class to compare arcs during sort of the candidate list
 		      class SortFunc
+		      {
 		      private:
 		        const CostVector &_map;
 		      public:
 		        SortFunc(const CostVector &map) : _map(map) {}
 		        bool operator()(int left, int right) {
 		          return _map[left] > _map[right];
+		        }
 		      };
 		      SortFunc _sort_func;
 		    public:
 		      // Constructor
 		      AlteringListPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
+		      {
 		        // The main parameters of the pivot rule
 		        const double BLOCK_SIZE_FACTOR = 1.0;
 		        const int MIN_BLOCK_SIZE = 10;
 		        const double HEAD_LENGTH_FACTOR = 0.1;
 		        const int MIN_HEAD_LENGTH = 3;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
 		                                    std::sqrt(double(_search_arc_num))),
 		                                MIN_BLOCK_SIZE );
 		        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
 		                                 MIN_HEAD_LENGTH );
 		        _candidates.resize(_head_length + _block_size);
 		        _curr_length = 0;
+		      }
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        // Check the current candidate list
 		        int e;
-		        for (int i = 0; i < _curr_length; ++i) {
+		        for (int i = 0; i != _curr_length; ++i) {
 		          e = _candidates[i];
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] >= 0) {
 		            _candidates[i--] = _candidates[--_curr_length];
+		          }
+		        }
 		        // Extend the list
 		        int cnt = _block_size;
 		        int limit = _head_length;
-		        for (e = _next_arc; e < _search_arc_num; ++e) {
+		        for (e = _next_arc; e != _search_arc_num; ++e) {
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] < 0) {
 		            _candidates[_curr_length++] = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
-		        for (e = 0; e < _next_arc; ++e) {
+		        for (e = 0; e != _next_arc; ++e) {
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] < 0) {
 		            _candidates[_curr_length++] = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        // Make heap of the candidate list (approximating a partial sort)
 		        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                   _sort_func );
 		        // Pop the first element of the heap
 		        _in_arc = _candidates[0];
 		        _next_arc = e;
 		        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                  _sort_func );
 		        _curr_length = std::min(_head_length, _curr_length - 1);
 		        return true;
+		      }
 		    }; //class AlteringListPivotRule
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param arc_mixing Indicate if the arcs have to be stored in a
 		    /// mixed order in the internal data structure.
 		    /// In special cases, it could lead to better overall performance,
 		    /// but it is usually slower. Therefore it is disabled by default.
 		    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
 		      _graph(graph), _node_id(graph), _arc_id(graph),
 		      MAX(std::numeric_limits<Value>::max()),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() : MAX)
+		    {
 		      // Check the number types
@@ -1283,190 +1284,287 @@
 		      // (it also means that join and v_out coincide)
 		      if (old_rev_thread == v_in) {
 		        last = _thread[_last_succ[u_out]];
 		      } else {
 		        last = _thread[v_in];
+		      }
 		      // Update _thread and _parent along the stem nodes (i.e. the nodes
 		      // between u_in and u_out, whose parent have to be changed)
 		      _thread[v_in] = stem = u_in;
 		      _dirty_revs.clear();
 		      _dirty_revs.push_back(v_in);
 		      par_stem = v_in;
 		      while (stem != u_out) {
 		        // Insert the next stem node into the thread list
 		        new_stem = _parent[stem];
 		        _thread[u] = new_stem;
 		        _dirty_revs.push_back(u);
 		        // Remove the subtree of stem from the thread list
 		        w = _rev_thread[stem];
 		        _thread[w] = right;
 		        _rev_thread[right] = w;
 		        // Change the parent node and shift stem nodes
 		        _parent[stem] = par_stem;
 		        par_stem = stem;
 		        stem = new_stem;
 		        // Update u and right
 		        u = _last_succ[stem] == _last_succ[par_stem] ?
 		          _rev_thread[par_stem] : _last_succ[stem];
 		        right = _thread[u];
+		      }
 		      _parent[u_out] = par_stem;
 		      _thread[u] = last;
 		      _rev_thread[last] = u;
 		      _last_succ[u_out] = u;
 		      // Remove the subtree of u_out from the thread list except for
 		      // the case when old_rev_thread equals to v_in
 		      // (it also means that join and v_out coincide)
 		      if (old_rev_thread != v_in) {
 		        _thread[old_rev_thread] = right;
 		        _rev_thread[right] = old_rev_thread;
+		      }
 		      // Update _rev_thread using the new _thread values
-		      for (int i = 0; i < int(_dirty_revs.size()); ++i) {
+		      for (int i = 0; i != int(_dirty_revs.size()); ++i) {
 		        u = _dirty_revs[i];
 		        _rev_thread[_thread[u]] = u;
+		      }
 		      // Update _pred, _forward, _last_succ and _succ_num for the
 		      // stem nodes from u_out to u_in
 		      int tmp_sc = 0, tmp_ls = _last_succ[u_out];
 		      u = u_out;
 		      while (u != u_in) {
 		        w = _parent[u];
 		        _pred[u] = _pred[w];
 		        _forward[u] = !_forward[w];
 		        tmp_sc += _succ_num[u] - _succ_num[w];
 		        _succ_num[u] = tmp_sc;
 		        _last_succ[w] = tmp_ls;
 		        u = w;
+		      }
 		      _pred[u_in] = in_arc;
 		      _forward[u_in] = (u_in == _source[in_arc]);
 		      _succ_num[u_in] = old_succ_num;
 		      // Set limits for updating _last_succ form v_in and v_out
 		      // towards the root
 		      int up_limit_in = -1;
 		      int up_limit_out = -1;
 		      if (_last_succ[join] == v_in) {
 		        up_limit_out = join;
 		      } else {
 		        up_limit_in = join;
+		      }
 		      // Update _last_succ from v_in towards the root
 		      for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
 		           u = _parent[u]) {
 		        _last_succ[u] = _last_succ[u_out];
+		      }
 		      // Update _last_succ from v_out towards the root
 		      if (join != old_rev_thread && v_in != old_rev_thread) {
 		        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
 		             u = _parent[u]) {
 		          _last_succ[u] = old_rev_thread;
+		        }
 		      } else {
 		        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
 		             u = _parent[u]) {
 		          _last_succ[u] = _last_succ[u_out];
+		        }
+		      }
 		      // Update _succ_num from v_in to join
 		      for (u = v_in; u != join; u = _parent[u]) {
 		        _succ_num[u] += old_succ_num;
+		      }
 		      // Update _succ_num from v_out to join
 		      for (u = v_out; u != join; u = _parent[u]) {
 		        _succ_num[u] -= old_succ_num;
+		      }
+		    }
 		    // Update potentials
 		    void updatePotential() {
 		      Cost sigma = _forward[u_in] ?
 		        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
 		        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
 		      // Update potentials in the subtree, which has been moved
 		      int end = _thread[_last_succ[u_in]];
 		      for (int u = u_in; u != end; u = _thread[u]) {
 		        _pi[u] += sigma;
+		      }
+		    }
 		    // Heuristic initial pivots
 		    bool initialPivots() {
 		      Value curr, total = 0;
 		      std::vector<Node> supply_nodes, demand_nodes;
 		      for (NodeIt u(_graph); u != INVALID; ++u) {
 		        curr = _supply[_node_id[u]];
 		        if (curr > 0) {
 		          total += curr;
 		          supply_nodes.push_back(u);
+		        }
 		        else if (curr < 0) {
 		          demand_nodes.push_back(u);
+		        }
+		      }
 		      if (_sum_supply > 0) total -= _sum_supply;
 		      if (total <= 0) return true;
 		      IntVector arc_vector;
 		      if (_sum_supply >= 0) {
 		        if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {
 		          // Perform a reverse graph search from the sink to the source
 		          typename GR::template NodeMap<bool> reached(_graph, false);
 		          Node s = supply_nodes[0], t = demand_nodes[0];
 		          std::vector<Node> stack;
 		          reached[t] = true;
 		          stack.push_back(t);
 		          while (!stack.empty()) {
 		            Node u, v = stack.back();
 		            stack.pop_back();
 		            if (v == s) break;
 		            for (InArcIt a(_graph, v); a != INVALID; ++a) {
 		              if (reached[u = _graph.source(a)]) continue;
 		              int j = _arc_id[a];
 		              if (_cap[j] >= total) {
 		                arc_vector.push_back(j);
 		                reached[u] = true;
 		                stack.push_back(u);
+		              }
+		            }
+		          }
 		        } else {
 		          // Find the min. cost incomming arc for each demand node
 		          for (int i = 0; i != int(demand_nodes.size()); ++i) {
 		            Node v = demand_nodes[i];
 		            Cost c, min_cost = std::numeric_limits<Cost>::max();
 		            Arc min_arc = INVALID;
 		            for (InArcIt a(_graph, v); a != INVALID; ++a) {
 		              c = _cost[_arc_id[a]];
 		              if (c < min_cost) {
 		                min_cost = c;
 		                min_arc = a;
+		              }
+		            }
 		            if (min_arc != INVALID) {
 		              arc_vector.push_back(_arc_id[min_arc]);
+		            }
+		          }
+		        }
 		      } else {
 		        // Find the min. cost outgoing arc for each supply node
 		        for (int i = 0; i != int(supply_nodes.size()); ++i) {
 		          Node u = supply_nodes[i];
 		          Cost c, min_cost = std::numeric_limits<Cost>::max();
 		          Arc min_arc = INVALID;
 		          for (OutArcIt a(_graph, u); a != INVALID; ++a) {
 		            c = _cost[_arc_id[a]];
 		            if (c < min_cost) {
 		              min_cost = c;
 		              min_arc = a;
+		            }
+		          }
 		          if (min_arc != INVALID) {
 		            arc_vector.push_back(_arc_id[min_arc]);
+		          }
+		        }
+		      }
 		      // Perform heuristic initial pivots
 		      for (int i = 0; i != int(arc_vector.size()); ++i) {
 		        in_arc = arc_vector[i];
 		        if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -
 		            _pi[_target[in_arc]]) >= 0) continue;
 		        findJoinNode();
 		        bool change = findLeavingArc();
 		        if (delta >= MAX) return false;
 		        changeFlow(change);
 		        if (change) {
 		          updateTreeStructure();
 		          updatePotential();
+		        }
+		      }
 		      return true;
+		    }
 		    // Execute the algorithm
 		    ProblemType start(PivotRule pivot_rule) {
 		      // Select the pivot rule implementation
 		      switch (pivot_rule) {
 		        case FIRST_ELIGIBLE:
 		          return start<FirstEligiblePivotRule>();
 		        case BEST_ELIGIBLE:
 		          return start<BestEligiblePivotRule>();
 		        case BLOCK_SEARCH:
 		          return start<BlockSearchPivotRule>();
 		        case CANDIDATE_LIST:
 		          return start<CandidateListPivotRule>();
 		        case ALTERING_LIST:
 		          return start<AlteringListPivotRule>();
+		      }
 		      return INFEASIBLE; // avoid warning
+		    }
 		    template <typename PivotRuleImpl>
 		    ProblemType start() {
 		      PivotRuleImpl pivot(*this);
 		      // Perform heuristic initial pivots
 		      if (!initialPivots()) return UNBOUNDED;
 		      // Execute the Network Simplex algorithm
 		      while (pivot.findEnteringArc()) {
 		        findJoinNode();
 		        bool change = findLeavingArc();
 		        if (delta >= MAX) return UNBOUNDED;
 		        changeFlow(change);
 		        if (change) {
 		          updateTreeStructure();
 		          updatePotential();
+		        }
+		      }
 		      // Check feasibility
 		      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
 		        if (_flow[e] != 0) return INFEASIBLE;
+		      }
 		      // Transform the solution and the supply map to the original form
 		      if (_have_lower) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Value c = _lower[i];
 		          if (c != 0) {
 		            _flow[i] += c;
 		            _supply[_source[i]] += c;
 		            _supply[_target[i]] -= c;
+		          }
+		        }
+		      }
 		      // Shift potentials to meet the requirements of the GEQ/LEQ type
 		      // optimality conditions
 		      if (_sum_supply == 0) {
 		        if (_stype == GEQ) {
 		          Cost max_pot = std::numeric_limits<Cost>::min();
 		          for (int i = 0; i != _node_num; ++i) {
 		            if (_pi[i] > max_pot) max_pot = _pi[i];
+		          }
 		          if (max_pot > 0) {
 		            for (int i = 0; i != _node_num; ++i)
 		              _pi[i] -= max_pot;
+		          }
 		        } else {
 		          Cost min_pot = std::numeric_limits<Cost>::max();
 		          for (int i = 0; i != _node_num; ++i) {
 		            if (_pi[i] < min_pot) min_pot = _pi[i];
+		          }
 		          if (min_pot < 0) {
 		            for (int i = 0; i != _node_num; ++i)

0 comments (0 inline)

RhodeCode

Login to your account