RhodeCode

following optimization problem.

\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 (lower and upper bounds)

and arc costs.

upper bounds for the flow values on the arcs, for which

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.

of the following optimization problem.

\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]

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$.

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$.

   - 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[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

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 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

/* -*- 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>

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.

  ///

  /// \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:

    ///

    /// 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

    };

  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;

    // 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) {

              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),

      _flow_map(NULL), _potential_map(NULL),

      _local_flow(false), _local_potential(false),

    {

    }

    /// 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.

    ///

    /// \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>

      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.

    ///

    /// \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>

      delete _pupper;

      _pupper = new FlowArcMap(_graph);

      for (ArcIt a(_graph); a != INVALID; ++a) {

        (*_pupper)[a] = map[a];

      }

      return *this;

    }

    /// \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>

      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>

      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;

    }

    ///

    /// type will be used.

    ///

    ///

    /// \return <tt>(*this)</tt>

      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 = ↦

      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 = ↦

      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(),

    /// For example,

    /// \code

    ///   NetworkSimplex<ListDigraph> ns(graph);

    ///     .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.

    ///

    }

    /// \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 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

    ///     .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();

    ///     .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;

      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.

    ///

    /// \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.

      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

    ///

    /// \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;

      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];

        }

      } 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;