LEMON/LEMON-official Changeset - r658:85cb3aa71cce

Repositories » LEMON » LEMON-official

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

Changeset - r658:85cb3aa71cce

« 657:dacc2c
« 647:0ba8df

666:ec817d »
660:b1811c »
659:0c8e5c »

r658:85cb3aa71cce

Tue, 21 Apr 2009 16:18:54

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge and fix

0 8 2

merge default

8 files changed with 2189 insertions and 157 deletions:

lemon/network_simplex.h

1582

test/min_cost_flow_test.cc

339

doc/groups.dox

lemon/Makefile.am

lemon/circulation.h

122

105

lemon/preflow.h

test/CMakeLists.txt

test/Makefile.am

test/circulation_test.cc

tools/dimacs-solver.cc

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_NETWORK_SIMPLEX_H
 		#define LEMON_NETWORK_SIMPLEX_H
 		/// \ingroup min_cost_flow
 		///
 		/// \file
 		/// \brief Network Simplex algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <algorithm>
 		#include <lemon/core.h>
 		#include <lemon/math.h>
 		#include <lemon/maps.h>
 		#include <lemon/circulation.h>
 		#include <lemon/adaptors.h>
 		namespace lemon {
 		  /// \addtogroup min_cost_flow
 		  /// @{
 		  /// \brief Implementation of the primal Network Simplex algorithm
 		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
 		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  /// This algorithm is a specialized version of the linear programming
 		  /// simplex method directly for the minimum cost flow problem.
 		  /// It is one of the most efficient solution methods.
 		  ///
 		  /// In general this class is the fastest implementation available
 		  /// in LEMON for the minimum cost flow problem.
 		  /// Moreover it supports both direction of the supply/demand inequality
 		  /// constraints. For more information see \ref ProblemType.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam F The value type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default it is \c int.
 		  /// \tparam C The value type used for costs and potentials in the
 		  /// algorithm. By default it is the same as \c F.
 		  ///
 		  /// \warning Both value types must be signed and all input data must
 		  /// be integer.
 		  ///
 		  /// \note %NetworkSimplex provides five different pivot rule
 		  /// implementations, from which the most efficient one is used
 		  /// by default. For more information see \ref PivotRule.
 		  template <typename GR, typename F = int, typename C = F>
 		  class NetworkSimplex
+		  {
 		  public:
 		    /// The flow type of the algorithm
 		    typedef F Flow;
 		    /// The cost type of the algorithm
 		    typedef C Cost;
 		#ifdef DOXYGEN
 		    /// The type of the flow map
 		    typedef GR::ArcMap<Flow> FlowMap;
 		    /// The type of the potential map
 		    typedef GR::NodeMap<Cost> PotentialMap;
 		#else
 		    /// The type of the flow map
 		    typedef typename GR::template ArcMap<Flow> FlowMap;
 		    /// The type of the potential map
 		    typedef typename GR::template NodeMap<Cost> PotentialMap;
 		#endif
 		  public:
 		    /// \brief Enum type for selecting the pivot rule.
 		    ///
 		    /// Enum type 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 according to our benchmark tests.
 		    /// However another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum PivotRule {
 		      /// The First Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
 		      /// The Best Eligible pivot rule.
 		      /// The best eligible arc is selected in every iteration.
 		      BEST_ELIGIBLE,
 		      /// The Block 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 Candidate 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 Altering Candidate 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
 		    };
 		    /// \brief Enum type for selecting the problem type.
 		    ///
 		    /// Enum type for selecting the problem type, i.e. the direction of
 		    /// the inequalities in the supply/demand constraints of the
 		    /// \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// The default problem type is \c GEQ, since this form is supported
 		    /// by other minimum cost flow algorithms and the \ref Circulation
 		    /// algorithm as well.
 		    /// The \c LEQ problem type can be selected using the \ref problemType()
 		    /// function.
 		    ///
 		    /// Note that the equality form is a special case of both problem type.
 		    enum ProblemType {
 		      /// This option means that there are "<em>greater or equal</em>"
 		      /// constraints in the defintion, i.e. the exact formulation of the
 		      /// problem is the following.
 		      /**
 		          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		          \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		              sup(u) \quad \forall u\in V \f]
 		          \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		      */
 		      /// It means that the total demand must be greater or equal to the
 		      /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		      /// negative) and all the supplies have to be carried out from
 		      /// the supply nodes, but there could be demands that are not
 		      /// satisfied.
 		      GEQ,
 		      /// It is just an alias for the \c GEQ option.
 		      CARRY_SUPPLIES = GEQ,
 		      /// This option means that there are "<em>less or equal</em>"
 		      /// constraints in the defintion, i.e. the exact formulation of the
 		      /// problem is the following.
 		      /**
 		          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		          \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		              sup(u) \quad \forall u\in V \f]
 		          \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		      */
 		      /// It means that the total demand must be less or equal to the
 		      /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		      /// positive) and all the demands have to be satisfied, but there
 		      /// could be supplies that are not carried out from the supply
 		      /// nodes.
 		      LEQ,
 		      /// It is just an alias for the \c LEQ option.
 		      SATISFY_DEMANDS = LEQ
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef typename GR::template ArcMap<Flow> FlowArcMap;
 		    typedef typename GR::template ArcMap<Cost> CostArcMap;
 		    typedef typename GR::template NodeMap<Flow> FlowNodeMap;
 		    typedef std::vector<Arc> ArcVector;
 		    typedef std::vector<Node> NodeVector;
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<bool> BoolVector;
 		    typedef std::vector<Flow> FlowVector;
 		    typedef std::vector<Cost> CostVector;
 		    // 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;
 		    // Parameters of the problem
 		    FlowArcMap *_plower;
 		    FlowArcMap *_pupper;
 		    CostArcMap *_pcost;
 		    FlowNodeMap *_psupply;
 		    bool _pstsup;
 		    Node _psource, _ptarget;
 		    Flow _pstflow;
 		    ProblemType _ptype;
 		    // Result maps
 		    FlowMap *_flow_map;
 		    PotentialMap *_potential_map;
 		    bool _local_flow;
 		    bool _local_potential;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    ArcVector _arc_ref;
 		    IntVector _source;
 		    IntVector _target;
 		    // Node and arc data
 		    FlowVector _cap;
 		    CostVector _cost;
 		    FlowVector _supply;
 		    FlowVector _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;
 		    BoolVector _forward;
 		    IntVector _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;
 		    Flow delta;
 		  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 IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _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), _arc_num(ns._arc_num), _next_arc(0)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c;
 		        for (int e = _next_arc; e < _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) {
 		          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 IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _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), _arc_num(ns._arc_num)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
 		        for (int e = 0; e < _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 IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _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), _arc_num(ns._arc_num), _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
 		        const double BLOCK_SIZE_FACTOR = 2.0;
 		        const int MIN_BLOCK_SIZE = 10;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
 		                                MIN_BLOCK_SIZE );
+		      }
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
 		        int cnt = _block_size;
 		        int e, min_arc = _next_arc;
 		        for (e = _next_arc; e < _arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            min_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (min < 0) break;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (min == 0 || cnt > 0) {
 		          for (e = 0; e < _next_arc; ++e) {
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
 		              min_arc = e;
+		            }
 		            if (--cnt == 0) {
 		              if (min < 0) break;
 		              cnt = _block_size;
+		            }
+		          }
+		        }
 		        if (min >= 0) return false;
 		        _in_arc = min_arc;
 		        _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 IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _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), _arc_num(ns._arc_num), _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
 		        const double LIST_LENGTH_FACTOR = 1.0;
 		        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 * sqrt(_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, min_arc = _next_arc;
 		        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;
 		              min_arc = e;
+		            }
 		            if (c >= 0) {
 		              _candidates[i--] = _candidates[--_curr_length];
+		            }
+		          }
 		          if (min < 0) {
 		            _in_arc = min_arc;
 		            return true;
+		          }
+		        }
 		        // Major iteration: build a new candidate list
 		        min = 0;
 		        _curr_length = 0;
 		        for (e = _next_arc; e < _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;
 		              min_arc = e;
+		            }
 		            if (_curr_length == _list_length) break;
+		          }
+		        }
 		        if (_curr_length < _list_length) {
 		          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;
 		                min_arc = e;
+		              }
 		              if (_curr_length == _list_length) break;
+		            }
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		        _minor_count = 1;
 		        _in_arc = min_arc;
 		        _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 IntVector  &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _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), _arc_num(ns._arc_num),
 		        _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
+		      {
 		        // The main parameters of the pivot rule
 		        const double BLOCK_SIZE_FACTOR = 1.5;
 		        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 * sqrt(_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) {
 		          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 last_arc = 0;
 		        int limit = _head_length;
 		        for (int e = _next_arc; e < _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;
 		            last_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) break;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (_curr_length <= limit) {
 		          for (int 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;
 		              last_arc = e;
+		            }
 		            if (--cnt == 0) {
 		              if (_curr_length > limit) break;
 		              limit = 0;
 		              cnt = _block_size;
+		            }
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		        _next_arc = last_arc + 1;
 		        // 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];
 		        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.
 		    NetworkSimplex(const GR& graph) :
 		      _graph(graph),
 		      _plower(NULL), _pupper(NULL), _pcost(NULL),
 		      _psupply(NULL), _pstsup(false), _ptype(GEQ),
 		      _flow_map(NULL), _potential_map(NULL),
 		      _local_flow(false), _local_potential(false),
 		      _node_id(graph)
+		    {
 		      LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
 		                   std::numeric_limits<Flow>::is_signed,
 		        "The flow type of NetworkSimplex must be signed integer");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
 		                   std::numeric_limits<Cost>::is_signed,
 		        "The cost type of NetworkSimplex must be signed integer");
+		    }
 		    /// Destructor.
 		    ~NetworkSimplex() {
 		      if (_local_flow) delete _flow_map;
 		      if (_local_potential) delete _potential_map;
+		    }
 		    /// \name Parameters
 		    /// The parameters of the algorithm can be specified using these
 		    /// functions.
 		    /// @{
 		    /// \brief Set the lower bounds on the arcs.
 		    ///
 		    /// This function sets the lower bounds on the arcs.
 		    /// If neither this function nor \ref boundMaps() is used before
 		    /// calling \ref run(), the lower bounds will be set to zero
 		    /// on all arcs.
 		    ///
 		    /// \param map An arc map storing the lower bounds.
 		    /// Its \c Value type must be convertible to the \c Flow type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template <typename LOWER>
 		    NetworkSimplex& lowerMap(const LOWER& map) {
 		      delete _plower;
 		      _plower = new FlowArcMap(_graph);
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        (*_plower)[a] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the upper bounds (capacities) on the arcs.
 		    ///
 		    /// This function sets the upper bounds (capacities) on the arcs.
 		    /// If none of the functions \ref upperMap(), \ref capacityMap()
 		    /// and \ref boundMaps() is used before calling \ref run(),
 		    /// the upper bounds (capacities) will be set to
 		    /// \c std::numeric_limits<Flow>::max() on all arcs.
 		    ///
 		    /// \param map An arc map storing the upper bounds.
 		    /// Its \c Value type must be convertible to the \c Flow type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename UPPER>
 		    NetworkSimplex& upperMap(const UPPER& map) {
 		      delete _pupper;
 		      _pupper = new FlowArcMap(_graph);
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        (*_pupper)[a] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the upper bounds (capacities) on the arcs.
 		    ///
 		    /// This function sets the upper bounds (capacities) on the arcs.
 		    /// It is just an alias for \ref upperMap().
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CAP>
 		    NetworkSimplex& capacityMap(const CAP& map) {
 		      return upperMap(map);
+		    }
 		    /// \brief Set the lower and upper bounds on the arcs.
 		    ///
 		    /// This function sets the lower and upper bounds on the arcs.
 		    /// If neither this function nor \ref lowerMap() is used before
 		    /// calling \ref run(), the lower bounds will be set to zero
 		    /// on all arcs.
 		    /// If none of the functions \ref upperMap(), \ref capacityMap()
 		    /// and \ref boundMaps() is used before calling \ref run(),
 		    /// the upper bounds (capacities) will be set to
 		    /// \c std::numeric_limits<Flow>::max() on all arcs.
 		    ///
 		    /// \param lower An arc map storing the lower bounds.
 		    /// \param upper An arc map storing the upper bounds.
 		    ///
 		    /// The \c Value type of the maps must be convertible to the
 		    /// \c Flow type of the algorithm.
 		    ///
 		    /// \note This function is just a shortcut of calling \ref lowerMap()
 		    /// and \ref upperMap() separately.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template <typename LOWER, typename UPPER>
 		    NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) {
 		      return lowerMap(lower).upperMap(upper);
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename COST>
 		    NetworkSimplex& costMap(const COST& map) {
 		      delete _pcost;
 		      _pcost = new CostArcMap(_graph);
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        (*_pcost)[a] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    /// (It makes sense only if non-zero lower bounds are given.)
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Flow type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SUP>
 		    NetworkSimplex& supplyMap(const SUP& map) {
 		      delete _psupply;
 		      _pstsup = false;
 		      _psupply = new FlowNodeMap(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_psupply)[n] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    /// (It makes sense only if non-zero lower bounds are given.)
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k 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).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
 		      delete _psupply;
 		      _psupply = NULL;
 		      _pstsup = true;
 		      _psource = s;
 		      _ptarget = t;
 		      _pstflow = k;
 		      return *this;
+		    }
 		    /// \brief Set the problem type.
 		    ///
 		    /// This function sets the problem type for the algorithm.
 		    /// If it is not used before calling \ref run(), the \ref GEQ problem
 		    /// type will be used.
 		    ///
 		    /// For more information see \ref ProblemType.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& problemType(ProblemType problem_type) {
 		      _ptype = problem_type;
 		      return *this;
+		    }
 		    /// \brief Set the flow map.
 		    ///
 		    /// This function sets the flow map.
 		    /// If it is not used before calling \ref run(), an instance will
 		    /// be allocated automatically. The destructor deallocates this
 		    /// automatically allocated map, of course.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow_map;
 		        _local_flow = false;
+		      }
 		      _flow_map = &map;
 		      return *this;
+		    }
 		    /// \brief Set the potential map.
 		    ///
 		    /// This function sets the potential map, which is used for storing
 		    /// the dual solution.
 		    /// If it is not used before calling \ref run(), an instance will
 		    /// be allocated automatically. The destructor deallocates this
 		    /// automatically allocated map, of course.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& potentialMap(PotentialMap& map) {
 		      if (_local_potential) {
 		        delete _potential_map;
 		        _local_potential = false;
+		      }
 		      _potential_map = &map;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution Control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply(),
 		    /// \ref problemType(), \ref flowMap() and \ref potentialMap().
 		    /// For example,
 		    /// \code
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///   ns.boundMaps(lower, upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the parameters
 		    /// that have been given are kept for the next call, unless
 		    /// \ref reset() is called, thus only the modified parameters
 		    /// have to be set again. See \ref reset() for examples.
 		    ///
 		    /// \param pivot_rule The pivot rule that will be used during the
 		    /// algorithm. For more information see \ref PivotRule.
 		    ///
 		    /// \return \c true if a feasible flow can be found.
 		    bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
 		      return init() && start(pivot_rule);
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref capacityMap(), \ref boundMaps(), \ref costMap(),
 		    /// \ref supplyMap(), \ref stSupply(), \ref problemType(),
 		    /// \ref flowMap() and \ref potentialMap().
 		    ///
 		    /// It is useful for multiple run() calls. If this function is not
 		    /// used, all the parameters given before are kept for the next
 		    /// \ref run() call.
 		    ///
 		    /// For example,
 		    /// \code
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///
 		    ///   // First run
 		    ///   ns.lowerMap(lower).capacityMap(cap).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
 		    ///   // Run again with modified cost map (reset() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   ns.costMap(cost).run();
 		    ///
 		    ///   // Run again from scratch using reset()
 		    ///   // (the lower bounds will be set to zero on all arcs)
 		    ///   ns.reset();
 		    ///   ns.capacityMap(cap).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& reset() {
 		      delete _plower;
 		      delete _pupper;
 		      delete _pcost;
 		      delete _psupply;
 		      _plower = NULL;
 		      _pupper = NULL;
 		      _pcost = NULL;
 		      _psupply = NULL;
 		      _pstsup = false;
 		      _ptype = GEQ;
 		      if (_local_flow) delete _flow_map;
 		      if (_local_potential) delete _potential_map;
 		      _flow_map = NULL;
 		      _potential_map = NULL;
 		      _local_flow = false;
 		      _local_potential = false;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// The complexity of the function is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   ns.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename Num>
 		    Num totalCost() const {
 		      Num c = 0;
 		      if (_pcost) {
 		        for (ArcIt e(_graph); e != INVALID; ++e)
 		          c += (*_flow_map)[e] * (*_pcost)[e];
 		      } else {
 		        for (ArcIt e(_graph); e != INVALID; ++e)
 		          c += (*_flow_map)[e];
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Flow flow(const Arc& a) const {
 		      return (*_flow_map)[a];
+		    }
 		    /// \brief Return a const reference to the flow map.
 		    ///
 		    /// This function returns a const reference to an arc map storing
 		    /// the found flow.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow_map;
+		    }
 		    /// \brief Return the potential (dual value) of the given node.
 		    ///
 		    /// This function returns the potential (dual value) of the
 		    /// given node.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Cost potential(const Node& n) const {
 		      return (*_potential_map)[n];
+		    }
 		    /// \brief Return a const reference to the potential map
 		    /// (the dual solution).
 		    ///
 		    /// This function returns a const reference to a node map storing
 		    /// the found potentials, which form the dual solution of the
 		    /// \ref min_cost_flow "minimum cost flow" problem.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    const PotentialMap& potentialMap() const {
 		      return *_potential_map;
+		    }
 		    /// @}
 		  private:
 		    // Initialize internal data structures
 		    bool init() {
 		      // Initialize result maps
 		      if (!_flow_map) {
 		        _flow_map = new FlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_potential_map) {
 		        _potential_map = new PotentialMap(_graph);
 		        _local_potential = true;
+		      }
 		      // Initialize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      int all_node_num = _node_num + 1;
 		      int all_arc_num = _arc_num + _node_num;
 		      if (_node_num == 0) return false;
 		      _arc_ref.resize(_arc_num);
 		      _source.resize(all_arc_num);
 		      _target.resize(all_arc_num);
 		      _cap.resize(all_arc_num);
 		      _cost.resize(all_arc_num);
 		      _supply.resize(all_node_num);
 		      _flow.resize(all_arc_num);
 		      _pi.resize(all_node_num);
 		      _parent.resize(all_node_num);
 		      _pred.resize(all_node_num);
 		      _forward.resize(all_node_num);
 		      _thread.resize(all_node_num);
 		      _rev_thread.resize(all_node_num);
 		      _succ_num.resize(all_node_num);
 		      _last_succ.resize(all_node_num);
 		      _state.resize(all_arc_num);
 		      // Initialize node related data
 		      bool valid_supply = true;
 		      Flow sum_supply = 0;
 		      if (!_pstsup && !_psupply) {
 		        _pstsup = true;
 		        _psource = _ptarget = NodeIt(_graph);
 		        _pstflow = 0;
+		      }
 		      if (_psupply) {
 		        int i = 0;
 		        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		          _node_id[n] = i;
 		          _supply[i] = (*_psupply)[n];
 		          sum_supply += _supply[i];
+		        }
 		        valid_supply = (_ptype == GEQ && sum_supply <= 0) ||
 		                       (_ptype == LEQ && sum_supply >= 0);
 		      } else {
 		        int i = 0;
 		        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		          _node_id[n] = i;
 		          _supply[i] = 0;
+		        }
 		        _supply[_node_id[_psource]] =  _pstflow;
 		        _supply[_node_id[_ptarget]] = -_pstflow;
+		      }
 		      if (!valid_supply) return false;
 		      // Infinite capacity value
 		      Flow inf_cap =
 		        std::numeric_limits<Flow>::has_infinity ?
 		        std::numeric_limits<Flow>::infinity() :
 		        std::numeric_limits<Flow>::max();
 		      // Initialize artifical cost
 		      Cost art_cost;
 		      if (std::numeric_limits<Cost>::is_exact) {
 		        art_cost = std::numeric_limits<Cost>::max() / 4 + 1;
 		      } else {
 		        art_cost = std::numeric_limits<Cost>::min();
 		        for (int i = 0; i != _arc_num; ++i) {
 		          if (_cost[i] > art_cost) art_cost = _cost[i];
+		        }
 		        art_cost = (art_cost + 1) * _node_num;
+		      }
 		      // Run Circulation to check if a feasible solution exists
 		      typedef ConstMap<Arc, Flow> ConstArcMap;
 		      FlowNodeMap *csup = NULL;
 		      bool local_csup = false;
 		      if (_psupply) {
 		        csup = _psupply;
 		      } else {
 		        csup = new FlowNodeMap(_graph, 0);
 		        (*csup)[_psource] =  _pstflow;
 		        (*csup)[_ptarget] = -_pstflow;
 		        local_csup = true;
+		      }
 		      bool circ_result = false;
 		      if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) {
 		        // GEQ problem type
 		        if (_plower) {
 		          if (_pupper) {
 		            Circulation<GR, FlowArcMap, FlowArcMap, FlowNodeMap>
 		              circ(_graph, *_plower, *_pupper, *csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
 		              circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);
 		            circ_result = circ.run();
+		          }
 		        } else {
 		          if (_pupper) {
 		            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
 		              circ(_graph, ConstArcMap(0), *_pupper, *csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
 		              circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);
 		            circ_result = circ.run();
+		          }
+		        }
 		      } else {
 		        // LEQ problem type
 		        typedef ReverseDigraph<const GR> RevGraph;
 		        typedef NegMap<FlowNodeMap> NegNodeMap;
 		        RevGraph rgraph(_graph);
 		        NegNodeMap neg_csup(*csup);
 		        if (_plower) {
 		          if (_pupper) {
 		            Circulation<RevGraph, FlowArcMap, FlowArcMap, NegNodeMap>
 		              circ(rgraph, *_plower, *_pupper, neg_csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
 		              circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);
 		            circ_result = circ.run();
+		          }
 		        } else {
 		          if (_pupper) {
 		            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
 		              circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
 		              circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);
 		            circ_result = circ.run();
+		          }
+		        }
+		      }
 		      if (local_csup) delete csup;
 		      if (!circ_result) return false;
 		      // Set data for the artificial root node
 		      _root = _node_num;
 		      _parent[_root] = -1;
 		      _pred[_root] = -1;
 		      _thread[_root] = 0;
 		      _rev_thread[0] = _root;
 		      _succ_num[_root] = all_node_num;
 		      _last_succ[_root] = _root - 1;
 		      _supply[_root] = -sum_supply;
 		      if (sum_supply < 0) {
 		        _pi[_root] = -art_cost;
 		      } else {
 		        _pi[_root] = art_cost;
+		      }
 		      // Store the arcs in a mixed order
 		      int k = std::max(int(sqrt(_arc_num)), 10);
 		      int i = 0;
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _arc_ref[i] = e;
 		        if ((i += k) >= _arc_num) i = (i % k) + 1;
+		      }
 		      // Initialize arc maps
 		      if (_pupper && _pcost) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Arc e = _arc_ref[i];
 		          _source[i] = _node_id[_graph.source(e)];
 		          _target[i] = _node_id[_graph.target(e)];
 		          _cap[i] = (*_pupper)[e];
 		          _cost[i] = (*_pcost)[e];
 		          _flow[i] = 0;
 		          _state[i] = STATE_LOWER;
+		        }
 		      } else {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Arc e = _arc_ref[i];
 		          _source[i] = _node_id[_graph.source(e)];
 		          _target[i] = _node_id[_graph.target(e)];
 		          _flow[i] = 0;
 		          _state[i] = STATE_LOWER;
+		        }
 		        if (_pupper) {
 		          for (int i = 0; i != _arc_num; ++i)
 		            _cap[i] = (*_pupper)[_arc_ref[i]];
 		        } else {
 		          for (int i = 0; i != _arc_num; ++i)
 		            _cap[i] = inf_cap;
+		        }
 		        if (_pcost) {
 		          for (int i = 0; i != _arc_num; ++i)
 		            _cost[i] = (*_pcost)[_arc_ref[i]];
 		        } else {
 		          for (int i = 0; i != _arc_num; ++i)
 		            _cost[i] = 1;
+		        }
+		      }
 		      // Remove non-zero lower bounds
 		      if (_plower) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Flow c = (*_plower)[_arc_ref[i]];
 		          if (c != 0) {
 		            _cap[i] -= c;
 		            _supply[_source[i]] -= c;
 		            _supply[_target[i]] += c;
+		          }
+		        }
+		      }
 		      // Add artificial arcs and initialize the spanning tree data structure
 		      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
 		        _thread[u] = u + 1;
 		        _rev_thread[u + 1] = u;
 		        _succ_num[u] = 1;
 		        _last_succ[u] = u;
 		        _parent[u] = _root;
 		        _pred[u] = e;
 		        _cost[e] = art_cost;
 		        _cap[e] = inf_cap;
 		        _state[e] = STATE_TREE;
 		        if (_supply[u] > 0 || (_supply[u] == 0 && sum_supply <= 0)) {
 		          _flow[e] = _supply[u];
 		          _forward[u] = true;
 		          _pi[u] = -art_cost + _pi[_root];
 		        } else {
 		          _flow[e] = -_supply[u];
 		          _forward[u] = false;
 		          _pi[u] = art_cost + _pi[_root];
+		        }
+		      }
 		      return true;
+		    }
 		    // Find the join node
 		    void findJoinNode() {
 		      int u = _source[in_arc];
 		      int v = _target[in_arc];
 		      while (u != v) {
 		        if (_succ_num[u] < _succ_num[v]) {
 		          u = _parent[u];
 		        } else {
 		          v = _parent[v];
+		        }
+		      }
 		      join = u;
+		    }
 		    // Find the leaving arc of the cycle and returns true if the
 		    // leaving arc is not the same as the entering arc
 		    bool findLeavingArc() {
 		      // Initialize first and second nodes according to the direction
 		      // of the cycle
 		      if (_state[in_arc] == STATE_LOWER) {
 		        first  = _source[in_arc];
 		        second = _target[in_arc];
 		      } else {
 		        first  = _target[in_arc];
 		        second = _source[in_arc];
+		      }
 		      delta = _cap[in_arc];
 		      int result = 0;
 		      Flow d;
 		      int e;
 		      // Search the cycle along the path form the first node to the root
 		      for (int u = first; u != join; u = _parent[u]) {
 		        e = _pred[u];
 		        d = _forward[u] ? _flow[e] : _cap[e] - _flow[e];
 		        if (d < delta) {
 		          delta = d;
 		          u_out = u;
 		          result = 1;
+		        }
+		      }
 		      // Search the cycle along the path form the second node to the root
 		      for (int u = second; u != join; u = _parent[u]) {
 		        e = _pred[u];
 		        d = _forward[u] ? _cap[e] - _flow[e] : _flow[e];
 		        if (d <= delta) {
 		          delta = d;
 		          u_out = u;
 		          result = 2;
+		        }
+		      }
 		      if (result == 1) {
 		        u_in = first;
 		        v_in = second;
 		      } else {
 		        u_in = second;
 		        v_in = first;
+		      }
 		      return result != 0;
+		    }
 		    // Change _flow and _state vectors
 		    void changeFlow(bool change) {
 		      // Augment along the cycle
 		      if (delta > 0) {
 		        Flow val = _state[in_arc] * delta;
 		        _flow[in_arc] += val;
 		        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
 		          _flow[_pred[u]] += _forward[u] ? -val : val;
+		        }
 		        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
 		          _flow[_pred[u]] += _forward[u] ? val : -val;
+		        }
+		      }
 		      // Update the state of the entering and leaving arcs
 		      if (change) {
 		        _state[in_arc] = STATE_TREE;
 		        _state[_pred[u_out]] =
 		          (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER;
 		      } else {
 		        _state[in_arc] = -_state[in_arc];
+		      }
+		    }
 		    // Update the tree structure
 		    void updateTreeStructure() {
 		      int u, w;
 		      int old_rev_thread = _rev_thread[u_out];
 		      int old_succ_num = _succ_num[u_out];
 		      int old_last_succ = _last_succ[u_out];
 		      v_out = _parent[u_out];
 		      u = _last_succ[u_in];  // the last successor of u_in
 		      right = _thread[u];    // the node after it
 		      // Handle 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) {
 		        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) {
 		        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;
+		      }
+		    }
 		    // Execute the algorithm
 		    bool 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 false;
+		    }
 		    template <typename PivotRuleImpl>
 		    bool start() {
 		      PivotRuleImpl pivot(*this);
 		      // Execute the Network Simplex algorithm
 		      while (pivot.findEnteringArc()) {
 		        findJoinNode();
 		        bool change = findLeavingArc();
 		        changeFlow(change);
 		        if (change) {
 		          updateTreeStructure();
 		          updatePotential();
+		        }
+		      }
 		      // Copy flow values to _flow_map
 		      if (_plower) {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          Arc e = _arc_ref[i];
 		          _flow_map->set(e, (*_plower)[e] + _flow[i]);
+		        }
 		      } else {
 		        for (int i = 0; i != _arc_num; ++i) {
 		          _flow_map->set(_arc_ref[i], _flow[i]);
+		        }
+		      }
 		      // Copy potential values to _potential_map
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _potential_map->set(n, _pi[_node_id[n]]);
+		      }
 		      return true;
+		    }
 		  }; //class NetworkSimplex
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_NETWORK_SIMPLEX_H

test/min_cost_flow_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include <fstream>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/network_simplex.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concept_check.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label  sup1 sup2 sup3 sup4 sup5\n"
 		  "    1    20   27    0   20   30\n"
 		  "    2    -4    0    0   -8   -3\n"
 		  "    3     0    0    0    0    0\n"
 		  "    4     0    0    0    0    0\n"
 		  "    5     9    0    0    6   11\n"
 		  "    6    -6    0    0   -5   -6\n"
 		  "    7     0    0    0    0    0\n"
 		  "    8     0    0    0    0    3\n"
 		  "    9     3    0    0    0    0\n"
 		  "   10    -2    0    0   -7   -2\n"
 		  "   11     0    0    0  -10    0\n"
 		  "   12   -20  -27    0  -30  -20\n"
 		  "\n"
 		  "@arcs\n"
 		  "       cost  cap low1 low2\n"
 		  " 1  2    70   11    0    8\n"
 		  " 1  3   150    3    0    1\n"
 		  " 1  4    80   15    0    2\n"
 		  " 2  8    80   12    0    0\n"
 		  " 3  5   140    5    0    3\n"
 		  " 4  6    60   10    0    1\n"
 		  " 4  7    80    2    0    0\n"
 		  " 4  8   110    3    0    0\n"
 		  " 5  7    60   14    0    0\n"
 		  " 5 11   120   12    0    0\n"
 		  " 6  3     0    3    0    0\n"
 		  " 6  9   140    4    0    0\n"
 		  " 6 10    90    8    0    0\n"
 		  " 7  1    30    5    0    0\n"
 		  " 8 12    60   16    0    4\n"
 		  " 9 12    50    6    0    0\n"
 		  "10 12    70   13    0    5\n"
 		  "10  2   100    7    0    0\n"
 		  "10  7    60   10    0    0\n"
 		  "11 10    20   14    0    6\n"
 		  "12 11    30   10    0    0\n"
 		  "\n"
 		  "@attributes\n"
 		  "source 1\n"
 		  "target 12\n";
 		enum ProblemType {
 		  EQ,
 		  GEQ,
 		  LEQ
 		};
 		// Check the interface of an MCF algorithm
 		template <typename GR, typename Flow, typename Cost>
 		class McfClassConcept
+		{
 		public:
 		  template <typename MCF>
 		  struct Constraints {
 		    void constraints() {
 		      checkConcept<concepts::Digraph, GR>();
 		      MCF mcf(g);
 		      b = mcf.reset()
 		             .lowerMap(lower)
 		             .upperMap(upper)
 		             .capacityMap(upper)
 		             .boundMaps(lower, upper)
 		             .costMap(cost)
 		             .supplyMap(sup)
 		             .stSupply(n, n, k)
 		             .flowMap(flow)
 		             .potentialMap(pot)
 		             .run();
 		      const MCF& const_mcf = mcf;
 		      const typename MCF::FlowMap &fm = const_mcf.flowMap();
 		      const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
 		      v = const_mcf.totalCost();
 		      double x = const_mcf.template totalCost<double>();
 		      v = const_mcf.flow(a);
 		      v = const_mcf.potential(n);
 		      ignore_unused_variable_warning(fm);
 		      ignore_unused_variable_warning(pm);
 		      ignore_unused_variable_warning(x);
+		    }
 		    typedef typename GR::Node Node;
 		    typedef typename GR::Arc Arc;
 		    typedef concepts::ReadMap<Node, Flow> NM;
 		    typedef concepts::ReadMap<Arc, Flow> FAM;
 		    typedef concepts::ReadMap<Arc, Cost> CAM;
 		    const GR &g;
 		    const FAM &lower;
 		    const FAM &upper;
 		    const CAM &cost;
 		    const NM &sup;
 		    const Node &n;
 		    const Arc &a;
 		    const Flow &k;
 		    Flow v;
 		    bool b;
 		    typename MCF::FlowMap &flow;
 		    typename MCF::PotentialMap &pot;
 		  };
 		};
 		// Check the feasibility of the given flow (primal soluiton)
 		template < typename GR, typename LM, typename UM,
 		           typename SM, typename FM >
 		bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
 		                const SM& supply, const FM& flow,
 		                ProblemType type = EQ )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  for (ArcIt e(gr); e != INVALID; ++e) {
 		    if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
+		  }
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
 		    bool b = (type ==  EQ && sum == supply[n]) ||
 		             (type == GEQ && sum >= supply[n]) ||
 		             (type == LEQ && sum <= supply[n]);
 		    if (!b) return false;
+		  }
 		  return true;
+		}
 		// Check the feasibility of the given potentials (dual soluiton)
 		// using the "Complementary Slackness" optimality condition
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename FM, typename PM >
 		bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
 		                     const CM& cost, const SM& supply, const FM& flow,
 		                     const PM& pi )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  bool opt = true;
 		  for (ArcIt e(gr); opt && e != INVALID; ++e) {
 		    typename CM::Value red_cost =
 		      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
 		    opt = red_cost == 0 ||
 		          (red_cost > 0 && flow[e] == lower[e]) ||
 		          (red_cost < 0 && flow[e] == upper[e]);
+		  }
 		  for (NodeIt n(gr); opt && n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
 		    opt = (sum == supply[n]) || (pi[n] == 0);
+		  }
 		  return opt;
+		}
 		// Run a minimum cost flow algorithm and check the results
 		template < typename MCF, typename GR,
 		           typename LM, typename UM,
 		           typename CM, typename SM >
 		void checkMcf( const MCF& mcf, bool mcf_result,
 		               const GR& gr, const LM& lower, const UM& upper,
 		               const CM& cost, const SM& supply,
 		               bool result, typename CM::Value total,
 		               const std::string &test_id = "",
 		               ProblemType type = EQ )
+		{
 		  check(mcf_result == result, "Wrong result " + test_id);
 		  if (result) {
 		    check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
 		          "The flow is not feasible " + test_id);
 		    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
 		    check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(),
 		                         mcf.potentialMap()),
 		          "Wrong potentials " + test_id);
+		  }
+		}
 		int main()
+		{
 		  // Check the interfaces
+		  {
 		    typedef int Flow;
 		    typedef int Cost;
 		    // TODO: This typedef should be enabled if the standard maps are
 		    // reference maps in the graph concepts (See #190).
 		/**/
 		    //typedef concepts::Digraph GR;
 		    typedef ListDigraph GR;
 		/**/
 		    checkConcept< McfClassConcept<GR, Flow, Cost>,
 		                  NetworkSimplex<GR, Flow, Cost> >();
+		  }
 		  // Run various MCF tests
 		  typedef ListDigraph Digraph;
 		  DIGRAPH_TYPEDEFS(ListDigraph);
 		  // Read the test digraph
 		  Digraph gr;
 		  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
 		  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
 		  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
 		  Node v, w;
 		  std::istringstream input(test_lgf);
 		  DigraphReader<Digraph>(gr, input)
 		    .arcMap("cost", c)
 		    .arcMap("cap", u)
 		    .arcMap("low1", l1)
 		    .arcMap("low2", l2)
 		    .nodeMap("sup1", s1)
 		    .nodeMap("sup2", s2)
 		    .nodeMap("sup3", s3)
 		    .nodeMap("sup4", s4)
 		    .nodeMap("sup5", s5)
 		    .node("source", v)
 		    .node("target", w)
 		    .run();
 		  // A. Test NetworkSimplex with the default pivot rule
+		  {
 		    NetworkSimplex<Digraph> mcf(gr);
 		    // Check the equality form
 		    mcf.upperMap(u).costMap(c);
 		    checkMcf(mcf, mcf.supplyMap(s1).run(),
 		             gr, l1, u, c, s1, true,  5240, "#A1");
 		    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
 		             gr, l1, u, c, s2, true,  7620, "#A2");
 		    mcf.lowerMap(l2);
 		    checkMcf(mcf, mcf.supplyMap(s1).run(),
 		             gr, l2, u, c, s1, true,  5970, "#A3");
 		    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
 		             gr, l2, u, c, s2, true,  8010, "#A4");
 		    mcf.reset();
 		    checkMcf(mcf, mcf.supplyMap(s1).run(),
 		             gr, l1, cu, cc, s1, true,  74, "#A5");
 		    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
 		             gr, l2, cu, cc, s2, true,  94, "#A6");
 		    mcf.reset();
 		    checkMcf(mcf, mcf.run(),
 		             gr, l1, cu, cc, s3, true,   0, "#A7");
 		    checkMcf(mcf, mcf.boundMaps(l2, u).run(),
 		             gr, l2, u, cc, s3, false,   0, "#A8");
 		    // Check the GEQ form
 		    mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l1, u, c, s4, true,  3530, "#A9", GEQ);
 		    mcf.problemType(mcf.GEQ);
 		    checkMcf(mcf, mcf.lowerMap(l2).run(),
 		             gr, l2, u, c, s4, true,  4540, "#A10", GEQ);
 		    mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l2, u, c, s5, false,    0, "#A11", GEQ);
 		    // Check the LEQ form
 		    mcf.reset().problemType(mcf.LEQ);
 		    mcf.upperMap(u).costMap(c).supplyMap(s5);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l1, u, c, s5, true,  5080, "#A12", LEQ);
 		    checkMcf(mcf, mcf.lowerMap(l2).run(),
 		             gr, l2, u, c, s5, true,  5930, "#A13", LEQ);
 		    mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
 		    checkMcf(mcf, mcf.run(),
 		             gr, l2, u, c, s4, false,    0, "#A14", LEQ);
+		  }
 		  // B. Test NetworkSimplex with each pivot rule
+		  {
 		    NetworkSimplex<Digraph> mcf(gr);
 		    mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
 		             gr, l2, u, c, s1, true,  5970, "#B1");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
 		             gr, l2, u, c, s1, true,  5970, "#B2");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
 		             gr, l2, u, c, s1, true,  5970, "#B3");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
 		             gr, l2, u, c, s1, true,  5970, "#B4");
 		    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
 		             gr, l2, u, c, s1, true,  5970, "#B5");
+		  }
 		  return 0;
+		}

doc/groups.dox

Show inline comments

@@ -133,436 +133,504 @@
 		int algorithm1(const ListDigraph& g) {
 		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group contains some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.
 		On the other hand they are not light-weight structures as the adaptors.
 		*/
 		/**
 		@defgroup maps Maps
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group contains the map structures implemented in LEMON.
 		LEMON provides several special purpose maps and map adaptors that e.g. combine
 		new maps from existing ones.
 		<b>See also:</b> \ref map_concepts "Map Concepts".
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group contains maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group contains map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
 		usage of map adaptors with the \c graphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group contains the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
 		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group contains the algorithms for finding shortest paths in digraphs.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
 		 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
 		\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
 		    \qquad \forall v\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
 		- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
 		In most cases the \ref Preflow "Preflow" algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		provides functions to also query the minimum cut, which is the dual
 		problem of the maximum flow.
 		*/
 		/**
 		@defgroup min_cost_flow Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations.
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
-		in a network with capacity constraints and arc costs.
+		in a network with capacity constraints (lower and upper bounds)
 		and arc costs.
 		Formally, let \f$G=(V,A)\f$ be a digraph,
 		\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
 		upper bounds for the flow values on the arcs,
+		upper bounds for the flow values on the arcs, for which
 		\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
 		\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
 		on the arcs, and
 		\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
 		of the nodes.
 		A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
-		the following optimization problem.
+		on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{a\in A} f(a) cost(a) \f]
 		\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
 		    supply(v) \qquad \forall v\in V \f]
 		\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving minimum cost flow problems:
 		 - \ref CycleCanceling Cycle-canceling algorithms.
-		 - \ref CapacityScaling Successive shortest path algorithm with optional
+		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		If you need the opposite inequalities in the supply/demand constraints
 		(i.e. the total demand is less than the total supply and all the demands
 		have to be satisfied while there could be supplies that are not used),
 		then you could easily transform the problem to the above form by reversing
 		the direction of the arcs and taking the negative of the supply values
 		(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		A feasible solution for this problem can be found using \ref Circulation.
 		Note that the above formulation is actually more general than the usual
 		definition of the minimum cost flow problem, in which strict equalities
 		are required in the supply/demand contraints, i.e.
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V. \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent. So if you need the equality form, you have to ensure this
 		additional contraint for the algorithms.
 		The dual solution of the minimum cost flow problem is represented by node
 		potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
 		An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
 		node potentials the following \e complementary \e slackness optimality
 		conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$:
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials) as well
 		if an optimal flow is found.
 		LEMON contains several algorithms for solving minimum cost flow problems.
 		 - \ref NetworkSimplex Primal Network Simplex algorithm with various
 		   pivot strategies.
 		 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
 		   cost scaling.
 		 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
 		   capacity scaling.
 		 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
 		   cost scaling.
 		 - \ref NetworkSimplex Primal network simplex algorithm with various
 		   pivot strategies.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm.
 		 - \ref CycleCanceling Cycle-Canceling algorithms.
 		Most of these implementations support the general inequality form of the
 		minimum cost flow problem, but CancelAndTighten and CycleCanceling
 		only support the equality form due to the primal method they use.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
 		For example, if the total supply and/or capacities are rather small,
 		CapacityScaling is usually the fastest algorithm (without effective scaling).
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the edges for which each node has at most one incident
 		edge.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding a minimum cost spanning tree in a graph.
 		This group contains the algorithms for finding a minimum cost spanning
 		tree in a graph.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group contains Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		*/
 		/**
 		@defgroup lp_utils Tools for Lp and Mip Solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group contains some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group contains several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/

lemon/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			lemon/lemon.pc.in \
 			lemon/CMakeLists.txt
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 			lemon/arg_parser.cc \
 			lemon/base.cc \
 			lemon/color.cc \
 			lemon/lp_base.cc \
 			lemon/lp_skeleton.cc \
 			lemon/random.cc \
 			lemon/bits/windows.cc
 		lemon_libemon_la_CXXFLAGS = \
 			$(AM_CXXFLAGS) \
 			$(GLPK_CFLAGS) \
 			$(CPLEX_CFLAGS) \
 			$(SOPLEX_CXXFLAGS) \
 			$(CLP_CXXFLAGS) \
 			$(CBC_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = \
 			$(GLPK_LIBS) \
 			$(CPLEX_LIBS) \
 			$(SOPLEX_LIBS) \
 			$(CLP_LIBS) \
 			$(CBC_LIBS)
 		if HAVE_GLPK
 		lemon_libemon_la_SOURCES += lemon/glpk.cc
 		endif
 		if HAVE_CPLEX
 		lemon_libemon_la_SOURCES += lemon/cplex.cc
 		endif
 		if HAVE_SOPLEX
 		lemon_libemon_la_SOURCES += lemon/soplex.cc
 		endif
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		if HAVE_CBC
 		lemon_libemon_la_SOURCES += lemon/cbc.cc
 		endif
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 			lemon/arg_parser.h \
 			lemon/assert.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			lemon/min_cost_arborescence.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/path.h \
 			lemon/preflow.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/soplex.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
 			lemon/bits/windows.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/graph_components.h \
 			lemon/concepts/heap.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h

lemon/circulation.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CIRCULATION_H
 		#define LEMON_CIRCULATION_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		///\ingroup max_flow
 		///\file
 		///\brief Push-relabel algorithm for finding a feasible circulation.
 		///
 		namespace lemon {
 		  /// \brief Default traits class of Circulation class.
 		  ///
 		  /// Default traits class of Circulation class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam LM Lower bound capacity map type.
 		  /// \tparam UM Upper bound capacity map type.
 		  /// \tparam DM Delta map type.
 		  ///
 		  /// \tparam GR Type of the digraph the algorithm runs on.
 		  /// \tparam LM The type of the lower bound map.
 		  /// \tparam UM The type of the upper bound (capacity) map.
 		  /// \tparam SM The type of the supply map.
 		  template <typename GR, typename LM,
-		            typename UM, typename DM>
+		            typename UM, typename SM>
 		  struct CirculationDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the circulation lower
 		    /// bound.
 		    /// \brief The type of the lower bound map.
 		    ///
 		    /// The type of the map that stores the circulation lower bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-		    typedef LM LCapMap;
+		    /// The type of the map that stores the lower bounds on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LowerMap;
 		    /// \brief The type of the map that stores the circulation upper
 		    /// bound.
 		    /// \brief The type of the upper bound (capacity) map.
 		    ///
 		    /// The type of the map that stores the circulation upper bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-		    typedef UM UCapMap;
+		    /// The type of the map that stores the upper bounds (capacities)
 		    /// on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UpperMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    /// \brief The type of supply map.
 		    ///
 		    /// The type of the map that stores the lower bound for the supply
 		    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
 		    /// concept.
 		    typedef DM DeltaMap;
 		    /// The type of the map that stores the signed supply values of the
 		    /// nodes.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef SM SupplyMap;
 		    /// \brief The type of the flow values.
-		    typedef typename DeltaMap::Value Value;
+		    typedef typename SupplyMap::Value Flow;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		    /// concept.
 		    typedef typename Digraph::template ArcMap<Flow> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
-		    /// \param digraph The digraph, to which we would like to define
+		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// The elevator type used by the algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
-		    /// \param digraph The digraph, to which we would like to define
+		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
-		    typedef lemon::Tolerance<Value> Tolerance;
+		    typedef lemon::Tolerance<Flow> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the network
 		     circulation problem.
 		     This class implements a push-relabel algorithm for the \e network
 		     \e circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds
 		     are given for the supply values of the nodes.
 		     are given for the flow values on the arcs and lower bounds are
 		     given for the difference between the outgoing and incoming flow
 		     at the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph,
 		     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
 		     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
 		     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
 		     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
 		     \geq delta(v) \quad \forall v\in V, \f]
 		     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
 		     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
 		     \f$v\f$. It can be either positive or negative, however note that
 		     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
 		     have a feasible solution.
 		     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
 		     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
 		     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
 		     denotes the signed supply values of the nodes.
 		     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		     \f$-sup(u)\f$ demand.
 		     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
 		     solution of the following problem.
 		     \note A special case of this problem is when
 		     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
 		     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
 		     Thus a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow" problem can be calculated
 		     in this way.
 		     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
 		     \geq sup(u) \quad \forall u\in V, \f]
 		     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
 		     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		     zero or negative in order to have a feasible solution (since the sum
 		     of the expressions on the left-hand side of the inequalities is zero).
 		     It means that the total demand must be greater or equal to the total
 		     supply and all the supplies have to be carried out from the supply nodes,
 		     but there could be demands that are not satisfied.
 		     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		     constraints have to be satisfied with equality, i.e. all demands
 		     have to be satisfied and all supplies have to be used.
 		     If you need the opposite inequalities in the supply/demand constraints
 		     (i.e. the total demand is less than the total supply and all the demands
 		     have to be satisfied while there could be supplies that are not used),
 		     then you could easily transform the problem to the above form by reversing
 		     the direction of the arcs and taking the negative of the supply values
 		     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		     Note that this algorithm also provides a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow problem".
 		     \tparam GR The type of the digraph the algorithm runs on.
-		     \tparam LM The type of the lower bound capacity map. The default
 		     \tparam LM The type of the lower bound map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound capacity map. The default
 		     map type is \c LM.
 		     \tparam DM The type of the map that stores the lower bound
 		     for the supply of the nodes. The default map type is
 		     \tparam UM The type of the upper bound (capacity) map.
 		     The default map type is \c LM.
 		     \tparam SM The type of the supply map. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
-		          typename DM,
+		          typename SM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename DM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
 		          typename SM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the flow values.
-		    typedef typename Traits::Value Value;
+		    typedef typename Traits::Flow Flow;
 		    /// The type of the lower bound capacity map.
 		    typedef typename Traits::LCapMap LCapMap;
 		    /// The type of the upper bound capacity map.
 		    typedef typename Traits::UCapMap UCapMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
-		    typedef typename Traits::DeltaMap DeltaMap;
+		    ///The type of the lower bound map.
 		    typedef typename Traits::LowerMap LowerMap;
 		    ///The type of the upper bound (capacity) map.
 		    typedef typename Traits::UpperMap UpperMap;
 		    ///The type of the supply map.
 		    typedef typename Traits::SupplyMap SupplyMap;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LCapMap *_lo;
 		    const UCapMap *_up;
-		    const DeltaMap *_delta;
+		    const LowerMap *_lo;
 		    const UpperMap *_up;
 		    const SupplyMap *_supply;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
-		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+		    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
-		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetFlowMapTraits<T> > {
-		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
-		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetElevatorTraits<T> > {
-		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
-		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                       SetStandardElevatorTraits<T> > {
-		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
-		    /// The constructor of the class.
+		    /// Constructor.
 		    /// The constructor of the class.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param lo The lower bound capacity of the arcs.
 		    /// \param up The upper bound capacity of the arcs.
 		    /// \param delta The lower bound for the supply of the nodes.
 		    Circulation(const Digraph &g,const LCapMap &lo,
 		                const UCapMap &up,const DeltaMap &delta)
 		      : _g(g), _node_num(),
 		        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
-		        _level(0), _local_level(false), _excess(0), _el() {}
+		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param lower The lower bounds for the flow values on the arcs.
 		    /// \param upper The upper bounds (capacities) for the flow values
 		    /// on the arcs.
 		    /// \param supply The signed supply values of the nodes.
 		    Circulation(const Digraph &graph, const LowerMap &lower,
 		                const UpperMap &upper, const SupplyMap &supply)
 		      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
 		        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
 		        _excess(NULL) {}
 		    /// Destructor.
 		    ~Circulation() {
 		      destroyStructures();
+		    }
 		  private:
 		    void createStructures() {
 		      _node_num = _el = countNodes(_g);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_g);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_g, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_g);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
-		    /// Sets the lower bound capacity map.
 		    /// Sets the lower bound map.
-		    /// Sets the lower bound capacity map.
 		    /// Sets the lower bound map.
 		    /// \return <tt>(*this)</tt>
-		    Circulation& lowerCapMap(const LCapMap& map) {
+		    Circulation& lowerMap(const LowerMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound capacity map.
+		    /// Sets the upper bound (capacity) map.
 		    /// Sets the upper bound capacity map.
+		    /// Sets the upper bound (capacity) map.
 		    /// \return <tt>(*this)</tt>
-		    Circulation& upperCapMap(const LCapMap& map) {
+		    Circulation& upperMap(const LowerMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
-		    /// Sets the lower bound map for the supply of the nodes.
+		    /// Sets the supply map.
-		    /// Sets the lower bound map for the supply of the nodes.
+		    /// Sets the supply map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& deltaMap(const DeltaMap& map) {
 		      _delta = &map;
 		    Circulation& supplyMap(const SupplyMap& map) {
 		      _supply = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by algorithm.
 		    ///
 		    /// Sets the tolerance used by algorithm.
 		    Circulation& tolerance(const Tolerance& tolerance) const {
 		      _tol = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance.
 		    const Tolerance& tolerance() const {
 		      return tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call \ref run().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// the \ref start() function.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
-		        (*_excess)[n] = (*_delta)[n];
+		        (*_excess)[n] = (*_supply)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        _flow->set(e, (*_lo)[e]);
 		        (*_excess)[_g.target(e)] += (*_flow)[e];
 		        (*_excess)[_g.source(e)] -= (*_flow)[e];
+		      }
 		      // global relabeling tested, but in general case it provides
 		      // worse performance for random digraphs
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    /// Initializes the internal data structures using a greedy approach.
 		    /// Initializes the internal data structures using a greedy approach
 		    /// to construct the initial solution.
 		    void greedyInit()
+		    {
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
-		        (*_excess)[n] = (*_delta)[n];
+		        (*_excess)[n] = (*_supply)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
 		          _flow->set(e, (*_up)[e]);
 		          (*_excess)[_g.target(e)] += (*_up)[e];
 		          (*_excess)[_g.source(e)] -= (*_up)[e];
 		        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
 		          _flow->set(e, (*_lo)[e]);
 		          (*_excess)[_g.target(e)] += (*_lo)[e];
 		          (*_excess)[_g.source(e)] -= (*_lo)[e];
 		        } else {
-		          Value fc = -(*_excess)[_g.target(e)];
+		          Flow fc = -(*_excess)[_g.target(e)];
 		          _flow->set(e, fc);
 		          (*_excess)[_g.target(e)] = 0;
 		          (*_excess)[_g.source(e)] -= fc;
+		        }
+		      }
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    ///Executes the algorithm
 		    ///This function executes the algorithm.
 		    ///
 		    ///\return \c true if a feasible circulation is found.
 		    ///
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool start()
+		    {
 		      Node act;
 		      Node bact=INVALID;
 		      Node last_activated=INVALID;
 		      while((act=_level->highestActive())!=INVALID) {
 		        int actlevel=(*_level)[act];
 		        int mlevel=_node_num;
-		        Value exc=(*_excess)[act];
+		        Flow exc=(*_excess)[act];
 		        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.target(e);
-		          Value fc=(*_up)[e]-(*_flow)[e];
+		          Flow fc=(*_up)[e]-(*_flow)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->set(e, (*_flow)[e] + exc);
 		              (*_excess)[v] += exc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              (*_excess)[act] = 0;
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_up)[e]);
 		              (*_excess)[v] += fc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              exc-=fc;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
 		        for(InArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.source(e);
-		          Value fc=(*_flow)[e]-(*_lo)[e];
+		          Flow fc=(*_flow)[e]-(*_lo)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->set(e, (*_flow)[e] - exc);
 		              (*_excess)[v] += exc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              (*_excess)[act] = 0;
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_lo)[e]);
 		              (*_excess)[v] += fc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              exc-=fc;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
 		        (*_excess)[act] = exc;
 		        if(!_tol.positive(exc)) _level->deactivate(act);
 		        else if(mlevel==_node_num) {
 		          _level->liftHighestActiveToTop();
 		          _el = _node_num;
 		          return false;
+		        }
 		        else {
 		          _level->liftHighestActive(mlevel+1);
 		          if(_level->onLevel(actlevel)==0) {
 		            _el = actlevel;
 		            return false;
+		          }
+		        }
 		      next_l:
+		        ;
+		      }
 		      return true;
+		    }
 		    /// Runs the algorithm.
 		    /// This function runs the algorithm.
 		    ///
 		    /// \return \c true if a feasible circulation is found.
 		    ///
 		    /// \note Apart from the return value, c.run() is just a shortcut of
 		    /// the following code.
 		    /// \code
 		    ///   c.greedyInit();
 		    ///   c.start();
 		    /// \endcode
 		    bool run() {
 		      greedyInit();
 		      return start();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the circulation algorithm can be obtained using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    /// \brief Returns the flow on the given arc.
 		    ///
 		    /// Returns the flow on the given arc.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
-		    Value flow(const Arc& arc) const {
+		    Flow flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Returns a const reference to the flow map.
 		    ///
 		    /// Returns a const reference to the arc map storing the found flow.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /**
 		       \brief Returns \c true if the given node is in a barrier.
 		       Barrier is a set \e B of nodes for which
 		       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
 		           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
 		       \f[ \sum_{uv\in A: u\in B} upper(uv) -
 		           \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
 		       holds. The existence of a set with this property prooves that a
 		       feasible circualtion cannot exist.
 		       This function returns \c true if the given node is in the found
 		       barrier. If a feasible circulation is found, the function
 		       gives back \c false for every node.
 		       \pre Either \ref run() or \ref init() must be called before
 		       using this function.
 		       \sa barrierMap()
 		       \sa checkBarrier()
 		    */
 		    bool barrier(const Node& node) const
+		    {
 		      return (*_level)[node] >= _el;
+		    }
 		    /// \brief Gives back a barrier.
 		    ///
 		    /// This function sets \c bar to the characteristic vector of the
 		    /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// If a feasible circulation is found, the function gives back an
 		    /// empty set, so \c bar[v] will be \c false for all nodes \c v.
 		    ///
 		    /// \note This function calls \ref barrier() for each node,
 		    /// so it runs in O(n) time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    ///
 		    /// \sa barrier()
 		    /// \sa checkBarrier()
 		    template<class BarrierMap>
 		    void barrierMap(BarrierMap &bar) const
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        bar.set(n, (*_level)[n] >= _el);
+		    }
 		    /// @}
 		    /// \name Checker Functions
 		    /// The feasibility of the results can be checked using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    ///Check if the found flow is a feasible circulation
 		    ///Check if the found flow is a feasible circulation,
 		    ///
 		    bool checkFlow() const {
 		      for(ArcIt e(_g);e!=INVALID;++e)
 		        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
 		      for(NodeIt n(_g);n!=INVALID;++n)
+		        {
-		          Value dif=-(*_delta)[n];
+		          Flow dif=-(*_supply)[n];
 		          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
 		          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
 		          if(_tol.negative(dif)) return false;
+		        }
 		      return true;
+		    }
 		    ///Check whether or not the last execution provides a barrier
 		    ///Check whether or not the last execution provides a barrier.
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool checkBarrier() const
+		    {
-		      Value delta=0;
+		      Flow delta=0;
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(barrier(n))
-		          delta-=(*_delta)[n];
+		          delta-=(*_supply)[n];
 		      for(ArcIt e(_g);e!=INVALID;++e)
+		        {
 		          Node s=_g.source(e);
 		          Node t=_g.target(e);
 		          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
 		          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
+		        }
 		      return _tol.negative(delta);
+		    }
 		    /// @}
 		  };
+		}
 		#endif

lemon/preflow.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_PREFLOW_H
 		#define LEMON_PREFLOW_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		/// \file
 		/// \ingroup max_flow
 		/// \brief Implementation of the preflow algorithm.
 		namespace lemon {
 		  /// \brief Default traits class of Preflow class.
 		  ///
 		  /// Default traits class of Preflow class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam CAP Capacity map type.
 		  template <typename GR, typename CAP>
 		  struct PreflowDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc capacities.
 		    ///
 		    /// The type of the map that stores the arc capacities.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CAP CapacityMap;
 		    /// \brief The type of the flow values.
-		    typedef typename CapacityMap::Value Value;
+		    typedef typename CapacityMap::Value Flow;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
-		    typedef typename Digraph::template ArcMap<Value> FlowMap;
+		    typedef typename Digraph::template ArcMap<Flow> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
-		    /// \param digraph The digraph, to which we would like to define
+		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by Preflow algorithm.
 		    ///
 		    /// The elevator type used by Preflow algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
-		    /// \param digraph The digraph, to which we would like to define
+		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
-		    typedef lemon::Tolerance<Value> Tolerance;
+		    typedef lemon::Tolerance<Flow> Tolerance;
 		  };
 		  /// \ingroup max_flow
 		  ///
 		  /// \brief %Preflow algorithm class.
 		  ///
 		  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
 		  /// \e push-relabel algorithm producing a \ref max_flow
 		  /// "flow of maximum value" in a digraph.
 		  /// The preflow algorithms are the fastest known maximum
 		  /// flow algorithms. The current implementation use a mixture of the
 		  /// \e "highest label" and the \e "bound decrease" heuristics.
 		  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
 		  ///
 		  /// The algorithm consists of two phases. After the first phase
 		  /// the maximum flow value and the minimum cut is obtained. The
 		  /// second phase constructs a feasible maximum flow on each arc.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CAP The type of the capacity map. The default map
 		  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TR>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TR = PreflowDefaultTraits<GR, CAP> >
 		#endif
 		  class Preflow {
 		  public:
 		    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the capacity map.
 		    typedef typename Traits::CapacityMap CapacityMap;
 		    ///The type of the flow values.
-		    typedef typename Traits::Value Value;
+		    typedef typename Traits::Flow Flow;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph& _graph;
 		    const CapacityMap* _capacity;
 		    int _node_num;
 		    Node _source, _target;
 		    FlowMap* _flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
-		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+		    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tolerance;
 		    bool _phase;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_graph, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    typedef Preflow Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Preflow<Digraph, CapacityMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Preflow() {}
 		  public:
 		    /// \brief The constructor of the class.
 		    ///
 		    /// The constructor of the class.
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param capacity The capacity of the arcs.
 		    /// \param source The source node.
 		    /// \param target The target node.
 		    Preflow(const Digraph& digraph, const CapacityMap& capacity,
 		            Node source, Node target)
 		      : _graph(digraph), _capacity(&capacity),
 		        _node_num(0), _source(source), _target(target),
 		        _flow(0), _local_flow(false),
 		        _level(0), _local_level(false),
 		        _excess(0), _tolerance(), _phase() {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor.
 		    ~Preflow() {
 		      destroyStructures();
+		    }
 		    /// \brief Sets the capacity map.
 		    ///
 		    /// Sets the capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& capacityMap(const CapacityMap& map) {
 		      _capacity = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the source node.
 		    ///
 		    /// Sets the source node.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& source(const Node& node) {
 		      _source = node;
 		      return *this;
+		    }
 		    /// \brief Sets the target node.
 		    ///
 		    /// Sets the target node.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& target(const Node& node) {
 		      _target = node;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by algorithm.
 		    ///
 		    /// Sets the tolerance used by algorithm.
 		    Preflow& tolerance(const Tolerance& tolerance) const {
 		      _tolerance = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance.
 		    const Tolerance& tolerance() const {
 		      return tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the preflow algorithm is to use
 		    /// \ref run() or \ref runMinCut().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to zero on each arc.
 		    void init() {
 		      createStructures();
 		      _phase = true;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_excess)[n] = 0;
+		      }
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _flow->set(e, 0);
+		      }
 		      typename Digraph::template NodeMap<bool> reached(_graph, false);
 		      _level->initStart();
 		      _level->initAddItem(_target);
 		      std::vector<Node> queue;
 		      reached[_source] = true;
 		      queue.push_back(_target);
 		      reached[_target] = true;
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
 		              reached[u] = true;
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
 		        if (_tolerance.positive((*_capacity)[e])) {
 		          Node u = _graph.target(e);
 		          if ((*_level)[u] == _level->maxLevel()) continue;
 		          _flow->set(e, (*_capacity)[e]);
 		          (*_excess)[u] += (*_capacity)[e];
 		          if (u != _target && !_level->active(u)) {
 		            _level->activate(u);
+		          }
+		        }
+		      }
+		    }
 		    /// \brief Initializes the internal data structures using the
 		    /// given flow map.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to the given \c flowMap. The \c flowMap should contain a
 		    /// flow or at least a preflow, i.e. at each node excluding the
 		    /// source node the incoming flow should greater or equal to the
 		    /// outgoing flow.
 		    /// \return \c false if the given \c flowMap is not a preflow.
 		    template <typename FlowMap>
 		    bool init(const FlowMap& flowMap) {
 		      createStructures();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _flow->set(e, flowMap[e]);
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
-		        Value excess = 0;
+		        Flow excess = 0;
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          excess += (*_flow)[e];
+		        }
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          excess -= (*_flow)[e];
+		        }
 		        if (excess < 0 && n != _source) return false;
 		        (*_excess)[n] = excess;
+		      }
 		      typename Digraph::template NodeMap<bool> reached(_graph, false);
 		      _level->initStart();
 		      _level->initAddItem(_target);
 		      std::vector<Node> queue;
 		      reached[_source] = true;
 		      queue.push_back(_target);
 		      reached[_target] = true;
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] &&
 		                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
 		              reached[u] = true;
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node v = _graph.target(e);
 		            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
 		              reached[v] = true;
 		              _level->initAddItem(v);
 		              nqueue.push_back(v);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
-		        Value rem = (*_capacity)[e] - (*_flow)[e];
+		        Flow rem = (*_capacity)[e] - (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node u = _graph.target(e);
 		          if ((*_level)[u] == _level->maxLevel()) continue;
 		          _flow->set(e, (*_capacity)[e]);
 		          (*_excess)[u] += rem;
 		          if (u != _target && !_level->active(u)) {
 		            _level->activate(u);
+		          }
+		        }
+		      }
 		      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
-		        Value rem = (*_flow)[e];
+		        Flow rem = (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] == _level->maxLevel()) continue;
 		          _flow->set(e, 0);
 		          (*_excess)[v] += rem;
 		          if (v != _target && !_level->active(v)) {
 		            _level->activate(v);
+		          }
+		        }
+		      }
 		      return true;
+		    }
 		    /// \brief Starts the first phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the first phase. After the first phase the maximum flow value
 		    /// and a minimum value cut can already be computed, although a
 		    /// maximum flow is not yet obtained. So after calling this method
 		    /// \ref flowValue() returns the value of a maximum flow and \ref
 		    /// minCut() returns a minimum cut.
 		    /// \pre One of the \ref init() functions must be called before
 		    /// using this function.
 		    void startFirstPhase() {
 		      _phase = true;
 		      Node n = _level->highestActive();
 		      int level = _level->highestActiveLevel();
 		      while (n != INVALID) {
 		        int num = _node_num;
 		        while (num > 0 && n != INVALID) {
-		          Value excess = (*_excess)[n];
+		          Flow excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_capacity)[e] - (*_flow)[e];
+		            Flow rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] + excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_1;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, (*_capacity)[e]);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_flow)[e];
+		            Flow rem = (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] - excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_1;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, 0);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		        no_more_push_1:
 		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if (new_level + 1 < _level->maxLevel()) {
 		              _level->liftHighestActive(new_level + 1);
 		            } else {
 		              _level->liftHighestActiveToTop();
+		            }
 		            if (_level->emptyLevel(level)) {
 		              _level->liftToTop(level);
+		            }
 		          } else {
 		            _level->deactivate(n);
+		          }
 		          n = _level->highestActive();
 		          level = _level->highestActiveLevel();
 		          --num;
+		        }
 		        num = _node_num * 20;
 		        while (num > 0 && n != INVALID) {
-		          Value excess = (*_excess)[n];
+		          Flow excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_capacity)[e] - (*_flow)[e];
+		            Flow rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] + excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_2;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, (*_capacity)[e]);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_flow)[e];
+		            Flow rem = (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] - excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_2;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, 0);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		        no_more_push_2:
 		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if (new_level + 1 < _level->maxLevel()) {
 		              _level->liftActiveOn(level, new_level + 1);
 		            } else {
 		              _level->liftActiveToTop(level);
+		            }
 		            if (_level->emptyLevel(level)) {
 		              _level->liftToTop(level);
+		            }
 		          } else {
 		            _level->deactivate(n);
+		          }
 		          while (level >= 0 && _level->activeFree(level)) {
 		            --level;
+		          }
 		          if (level == -1) {
 		            n = _level->highestActive();
 		            level = _level->highestActiveLevel();
 		          } else {
 		            n = _level->activeOn(level);
+		          }
 		          --num;
+		        }
+		      }
+		    }
 		    /// \brief Starts the second phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the second phase. After calling one of the \ref init() functions
 		    /// and \ref startFirstPhase() and then \ref startSecondPhase(),
 		    /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
 		    /// value of a maximum flow, \ref minCut() returns a minimum cut
 		    /// \pre One of the \ref init() functions and \ref startFirstPhase()
 		    /// must be called before using this function.
 		    void startSecondPhase() {
 		      _phase = false;
 		      typename Digraph::template NodeMap<bool> reached(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        reached[n] = (*_level)[n] < _level->maxLevel();
+		      }
 		      _level->initStart();
 		      _level->initAddItem(_source);
 		      std::vector<Node> queue;
 		      queue.push_back(_source);
 		      reached[_source] = true;
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node v = _graph.target(e);
 		            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
 		              reached[v] = true;
 		              _level->initAddItem(v);
 		              nqueue.push_back(v);
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] &&
 		                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
 		              reached[u] = true;
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if (!reached[n]) {
 		          _level->dirtyTopButOne(n);
 		        } else if ((*_excess)[n] > 0 && _target != n) {
 		          _level->activate(n);
+		        }
+		      }
 		      Node n;
 		      while ((n = _level->highestActive()) != INVALID) {
-		        Value excess = (*_excess)[n];
+		        Flow excess = (*_excess)[n];
 		        int level = _level->highestActiveLevel();
 		        int new_level = _level->maxLevel();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-		          Value rem = (*_capacity)[e] - (*_flow)[e];
+		          Flow rem = (*_capacity)[e] - (*_flow)[e];
 		          if (!_tolerance.positive(rem)) continue;
 		          Node v = _graph.target(e);
 		          if ((*_level)[v] < level) {
 		            if (!_level->active(v) && v != _source) {
 		              _level->activate(v);
+		            }
 		            if (!_tolerance.less(rem, excess)) {
 		              _flow->set(e, (*_flow)[e] + excess);
 		              (*_excess)[v] += excess;
 		              excess = 0;
 		              goto no_more_push;
 		            } else {
 		              excess -= rem;
 		              (*_excess)[v] += rem;
 		              _flow->set(e, (*_capacity)[e]);
+		            }
 		          } else if (new_level > (*_level)[v]) {
 		            new_level = (*_level)[v];
+		          }
+		        }
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
-		          Value rem = (*_flow)[e];
+		          Flow rem = (*_flow)[e];
 		          if (!_tolerance.positive(rem)) continue;
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] < level) {
 		            if (!_level->active(v) && v != _source) {
 		              _level->activate(v);
+		            }
 		            if (!_tolerance.less(rem, excess)) {
 		              _flow->set(e, (*_flow)[e] - excess);
 		              (*_excess)[v] += excess;
 		              excess = 0;
 		              goto no_more_push;
 		            } else {
 		              excess -= rem;
 		              (*_excess)[v] += rem;
 		              _flow->set(e, 0);
+		            }
 		          } else if (new_level > (*_level)[v]) {
 		            new_level = (*_level)[v];
+		          }
+		        }
 		      no_more_push:
 		        (*_excess)[n] = excess;
 		        if (excess != 0) {
 		          if (new_level + 1 < _level->maxLevel()) {
 		            _level->liftHighestActive(new_level + 1);
 		          } else {
 		            // Calculation error
 		            _level->liftHighestActiveToTop();
+		          }
 		          if (_level->emptyLevel(level)) {
 		            // Calculation error
 		            _level->liftToTop(level);
+		          }
 		        } else {
 		          _level->deactivate(n);
+		        }
+		      }
+		    }
 		    /// \brief Runs the preflow algorithm.
 		    ///
 		    /// Runs the preflow algorithm.
 		    /// \note pf.run() is just a shortcut of the following code.
 		    /// \code
 		    ///   pf.init();
 		    ///   pf.startFirstPhase();
 		    ///   pf.startSecondPhase();
 		    /// \endcode
 		    void run() {
 		      init();
 		      startFirstPhase();
 		      startSecondPhase();
+		    }
 		    /// \brief Runs the preflow algorithm to compute the minimum cut.
 		    ///
 		    /// Runs the preflow algorithm to compute the minimum cut.
 		    /// \note pf.runMinCut() is just a shortcut of the following code.
 		    /// \code
 		    ///   pf.init();
 		    ///   pf.startFirstPhase();
 		    /// \endcode
 		    void runMinCut() {
 		      init();
 		      startFirstPhase();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the preflow algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either one of the \ref run() "run*()" functions or one of the
 		    /// \ref startFirstPhase() "start*()" functions should be called
 		    /// before using them.
 		    ///@{
 		    /// \brief Returns the value of the maximum flow.
 		    ///
 		    /// Returns the value of the maximum flow by returning the excess
 		    /// of the target node. This value equals to the value of
 		    /// the maximum flow already after the first phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
-		    Value flowValue() const {
+		    Flow flowValue() const {
 		      return (*_excess)[_target];
+		    }
 		    /// \brief Returns the flow on the given arc.
 		    ///
 		    /// Returns the flow on the given arc. This method can
 		    /// be called after the second phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
-		    Value flow(const Arc& arc) const {
+		    Flow flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Returns a const reference to the flow map.
 		    ///
 		    /// Returns a const reference to the arc map storing the found flow.
 		    /// This method can be called after the second phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /// \brief Returns \c true when the node is on the source side of the
 		    /// minimum cut.
 		    ///
 		    /// Returns true when the node is on the source side of the found
 		    /// minimum cut. This method can be called both after running \ref
 		    /// startFirstPhase() and \ref startSecondPhase().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    bool minCut(const Node& node) const {
 		      return ((*_level)[node] == _level->maxLevel()) == _phase;
+		    }
 		    /// \brief Gives back a minimum value cut.
 		    ///
 		    /// Sets \c cutMap to the characteristic vector of a minimum value
 		    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// This method can be called both after running \ref startFirstPhase()
 		    /// and \ref startSecondPhase(). The result after the second phase
 		    /// could be slightly different if inexact computation is used.
 		    ///
 		    /// \note This function calls \ref minCut() for each node, so it runs in
 		    /// O(n) time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    template <typename CutMap>
 		    void minCutMap(CutMap& cutMap) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        cutMap.set(n, minCut(n));
+		      }
+		    }
 		    /// @}
 		  };
+		}
 		#endif

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		IF(HAVE_GLPK)
 		  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
 		ENDIF(HAVE_GLPK)
 		LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
 		SET(TESTS
 		  adaptors_test
 		  bfs_test
 		  circulation_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  gomory_hu_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  maps_test
 		  matching_test
 		  min_cost_arborescence_test
 		  min_cost_flow_test
 		  path_test
 		  preflow_test
 		  radix_sort_test
 		  random_test
 		  suurballe_test
 		  time_measure_test
 		  unionfind_test)
 		IF(HAVE_LP)
 		  ADD_EXECUTABLE(lp_test lp_test.cc)
 		  IF(HAVE_GLPK)
 		    TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
 		  ENDIF(HAVE_GLPK)
 		  ADD_TEST(lp_test lp_test)
 		  IF(WIN32 AND HAVE_GLPK)
 		    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+		    )
 		  ENDIF(WIN32 AND HAVE_GLPK)
 		ENDIF(HAVE_LP)
 		IF(HAVE_MIP)
 		  ADD_EXECUTABLE(mip_test mip_test.cc)
 		  IF(HAVE_GLPK)
 		    TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
 		  ENDIF(HAVE_GLPK)
 		  ADD_TEST(mip_test mip_test)
 		  IF(WIN32 AND HAVE_GLPK)
 		    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
 		      COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+		    )
 		  ENDIF(WIN32 AND HAVE_GLPK)
 		ENDIF(HAVE_MIP)
 		FOREACH(TEST_NAME ${TESTS})
 		  ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
 		  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
 		  ADD_TEST(${TEST_NAME} ${TEST_NAME})
 		ENDFOREACH(TEST_NAME)

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/euler_test \
 			test/gomory_hu_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/hao_orlin_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/maps_test \
 			test/matching_test \
 			test/min_cost_arborescence_test \
 			test/min_cost_flow_test \
 			test/path_test \
 			test/preflow_test \
 			test/radix_sort_test \
 			test/random_test \
 			test/suurballe_test \
 			test/test_tools_fail \
 			test/test_tools_pass \
 			test/time_measure_test \
 			test/unionfind_test
 		test_test_tools_pass_DEPENDENCIES = demo
 		if HAVE_LP
 		check_PROGRAMS += test/lp_test
 		endif HAVE_LP
 		if HAVE_MIP
 		check_PROGRAMS += test/mip_test
 		endif HAVE_MIP
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_euler_test_SOURCES = test/euler_test.cc
 		test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 		test_lp_test_SOURCES = test/lp_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_mip_test_SOURCES = test/mip_test.cc
 		test_matching_test_SOURCES = test/matching_test.cc
 		test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 		test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
 		test_path_test_SOURCES = test/path_test.cc
 		test_preflow_test_SOURCES = test/preflow_test.cc
 		test_radix_sort_test_SOURCES = test/radix_sort_test.cc
 		test_suurballe_test_SOURCES = test/suurballe_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_time_measure_test_SOURCES = test/time_measure_test.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

test/circulation_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include "test_tools.h"
 		#include <lemon/list_graph.h>
 		#include <lemon/circulation.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/maps.h>
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@arcs\n"
 		  "     lcap  ucap\n"
 		  "0 1  2  10\n"
 		  "0 2  2  6\n"
 		  "1 3  4  7\n"
 		  "1 4  0  5\n"
 		  "2 4  1  3\n"
 		  "3 5  3  8\n"
 		  "4 5  3  7\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "sink   5\n";
 		void checkCirculationCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  typedef concepts::ReadMap<Arc,VType> CapMap;
-		  typedef concepts::ReadMap<Node,VType> DeltaMap;
+		  typedef concepts::ReadMap<Node,VType> SupplyMap;
 		  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
 		  typedef concepts::WriteMap<Node,bool> BarrierMap;
 		  typedef Elevator<Digraph, Digraph::Node> Elev;
 		  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
 		  Digraph g;
 		  Node n;
 		  Arc a;
 		  CapMap lcap, ucap;
-		  DeltaMap delta;
+		  SupplyMap supply;
 		  FlowMap flow;
 		  BarrierMap bar;
 		  VType v;
 		  bool b;
-		  typedef Circulation<Digraph, CapMap, CapMap, DeltaMap>
+		  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
 		            ::SetFlowMap<FlowMap>
 		            ::SetElevator<Elev>
 		            ::SetStandardElevator<LinkedElev>
 		            ::Create CirculationType;
-		  CirculationType circ_test(g, lcap, ucap, delta);
+		  CirculationType circ_test(g, lcap, ucap, supply);
 		  const CirculationType& const_circ_test = circ_test;
 		  circ_test
 		    .lowerCapMap(lcap)
 		    .upperCapMap(ucap)
-		    .deltaMap(delta)
+		    .lowerMap(lcap)
 		    .upperMap(ucap)
 		    .supplyMap(supply)
 		    .flowMap(flow);
 		  circ_test.init();
 		  circ_test.greedyInit();
 		  circ_test.start();
 		  circ_test.run();
 		  v = const_circ_test.flow(a);
 		  const FlowMap& fm = const_circ_test.flowMap();
 		  b = const_circ_test.barrier(n);
 		  const_circ_test.barrierMap(bar);
 		  ignore_unused_variable_warning(fm);
+		}
 		template <class G, class LM, class UM, class DM>
 		void checkCirculation(const G& g, const LM& lm, const UM& um,
 		                      const DM& dm, bool find)
+		{
 		  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
 		  bool ret = circ.run();
 		  if (find) {
 		    check(ret, "A feasible solution should have been found.");
 		    check(circ.checkFlow(), "The found flow is corrupt.");
 		    check(!circ.checkBarrier(), "A barrier should not have been found.");
 		  } else {
 		    check(!ret, "A feasible solution should not have been found.");
 		    check(circ.checkBarrier(), "The found barrier is corrupt.");
+		  }
+		}
 		int main (int, char*[])
+		{
 		  typedef ListDigraph Digraph;
 		  DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph g;
 		  IntArcMap lo(g), up(g);
 		  IntNodeMap delta(g, 0);
 		  Node s, t;
 		  std::istringstream input(test_lgf);
 		  DigraphReader<Digraph>(g,input).
 		    arcMap("lcap", lo).
 		    arcMap("ucap", up).
 		    node("source",s).
 		    node("sink",t).
 		    run();
 		  delta[s] = 7; delta[t] = -7;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 13; delta[t] = -13;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 6; delta[t] = -6;
 		  checkCirculation(g, lo, up, delta, false);
 		  delta[s] = 14; delta[t] = -14;
 		  checkCirculation(g, lo, up, delta, false);
 		  delta[s] = 7; delta[t] = -13;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 5; delta[t] = -15;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 10; delta[t] = -11;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 11; delta[t] = -10;
 		  checkCirculation(g, lo, up, delta, false);
 		  return 0;
+		}

tools/dimacs-solver.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup tools
 		///\file
 		///\brief DIMACS problem solver.
 		///
 		/// This program solves various problems given in DIMACS format.
 		///
 		/// See
 		/// \code
 		///   dimacs-solver --help
 		/// \endcode
 		/// for more info on usage.
 		#include <iostream>
 		#include <fstream>
 		#include <cstring>
 		#include <lemon/smart_graph.h>
 		#include <lemon/dimacs.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/time_measure.h>
 		#include <lemon/arg_parser.h>
 		#include <lemon/error.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/preflow.h>
 		#include <lemon/matching.h>
 		#include <lemon/network_simplex.h>
 		using namespace lemon;
 		typedef SmartDigraph Digraph;
 		DIGRAPH_TYPEDEFS(Digraph);
 		typedef SmartGraph Graph;
 		template<class Value>
 		void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
 		              DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
 		  Node s;
 		  Digraph::ArcMap<Value> len(g);
 		  Timer t;
 		  t.restart();
 		  readDimacsSp(is, g, len, s, desc);
 		  if(report) std::cerr << "Read the file: " << t << '\n';
 		  t.restart();
 		  Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
 		  if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
 		  t.restart();
 		  dij.run(s);
 		  if(report) std::cerr << "Run Dijkstra: " << t << '\n';
+		}
 		template<class Value>
 		void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
 		               Value infty, DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
 		  Node s,t;
 		  Digraph::ArcMap<Value> cap(g);
 		  Timer ti;
 		  ti.restart();
 		  readDimacsMax(is, g, cap, s, t, infty, desc);
 		  if(report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
 		  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
 		  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
 		  ti.restart();
 		  pre.run();
 		  if(report) std::cerr << "Run Preflow: " << ti << '\n';
 		  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
+		}
 		template<class Value>
 		void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
 		               DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
 		  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
 		  Digraph::NodeMap<Value> sup(g);
 		  Timer ti;
 		  ti.restart();
 		  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
 		  if (report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
 		  NetworkSimplex<Digraph, Value> ns(g);
 		  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
 		  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
 		  ti.restart();
 		  ns.run();
 		  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
 		  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
+		}
 		void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
 		              DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Graph g;
 		  Timer ti;
 		  ti.restart();
 		  readDimacsMat(is, g, desc);
 		  if(report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
 		  MaxMatching<Graph> mat(g);
 		  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
 		  ti.restart();
 		  mat.run();
 		  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
 		  if(report) std::cerr << "\nCardinality of max matching: "
 		                       << mat.matchingSize() << '\n';
+		}
 		template<class Value>
 		void solve(ArgParser &ap, std::istream &is, std::ostream &os,
 		           DimacsDescriptor &desc)
+		{
 		  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
 		  Value infty;
 		  iss >> infty;
 		  if(iss.fail())
+		    {
 		      std::cerr << "Cannot interpret '"
 		                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
 		                << std::endl;
 		      exit(1);
+		    }
 		  switch(desc.type)
+		    {
 		    case DimacsDescriptor::MIN:
 		      std::cerr <<
 		        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
 		      solve_min<Value>(ap,is,os,desc);
 		      break;
 		    case DimacsDescriptor::MAX:
 		      solve_max<Value>(ap,is,os,infty,desc);
 		      break;
 		    case DimacsDescriptor::SP:
 		      solve_sp<Value>(ap,is,os,desc);
 		      break;
 		    case DimacsDescriptor::MAT:
 		      solve_mat(ap,is,os,desc);
 		      break;
 		    default:
 		      break;
+		    }
+		}
 		int main(int argc, const char *argv[]) {
 		  typedef SmartDigraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  std::string inputName;
 		  std::string outputName;
 		  ArgParser ap(argc, argv);
 		  ap.other("[INFILE [OUTFILE]]",
 		           "If either the INFILE or OUTFILE file is missing the standard\n"
 		           "     input/output will be used instead.")
 		    .boolOption("q", "Do not print any report")
 		    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
 		    .optionGroup("datatype","int")
 		#ifdef HAVE_LONG_LONG
 		    .boolOption("long","Use 'long long' for capacities, costs etc.")
 		    .optionGroup("datatype","long")
 		#endif
 		    .boolOption("double","Use 'double' for capacities, costs etc.")
 		    .optionGroup("datatype","double")
 		    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
 		    .optionGroup("datatype","ldouble")
 		    .onlyOneGroup("datatype")
 		    .stringOption("infcap","Value used for 'very high' capacities","0")
 		    .run();
 		  std::ifstream input;
 		  std::ofstream output;
 		  switch(ap.files().size())
+		    {
 		    case 2:
 		      output.open(ap.files()[1].c_str());
 		      if (!output) {
 		        throw IoError("Cannot open the file for writing", ap.files()[1]);
+		      }
 		    case 1:
 		      input.open(ap.files()[0].c_str());
 		      if (!input) {
 		        throw IoError("File cannot be found", ap.files()[0]);
+		      }
 		    case 0:
 		      break;
 		    default:
 		      std::cerr << ap.commandName() << ": too many arguments\n";
 		      return 1;
+		    }
 		  std::istream& is = (ap.files().size()<1 ? std::cin : input);
 		  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
 		  DimacsDescriptor desc = dimacsType(is);
 		  if(!ap.given("q"))
+		    {
 		      std::cout << "Problem type: ";
 		      switch(desc.type)
+		        {
 		        case DimacsDescriptor::MIN:
 		          std::cout << "min";
 		          break;
 		        case DimacsDescriptor::MAX:
 		          std::cout << "max";
 		          break;
 		        case DimacsDescriptor::SP:
 		          std::cout << "sp";
 		        case DimacsDescriptor::MAT:
 		          std::cout << "mat";
 		          break;
 		        default:
 		          exit(1);
 		          break;
+		        }
 		      std::cout << "\nNum of nodes: " << desc.nodeNum;
 		      std::cout << "\nNum of arcs:  " << desc.edgeNum;
 		      std::cout << "\n\n";
+		    }
 		  if(ap.given("double"))
 		    solve<double>(ap,is,os,desc);
 		  else if(ap.given("ldouble"))
 		    solve<long double>(ap,is,os,desc);
 		#ifdef HAVE_LONG_LONG
 		  else if(ap.given("long"))
 		    solve<long long>(ap,is,os,desc);
 		#endif
 		  else solve<int>(ap,is,os,desc);
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account