RhodeCode

\brief Algorithms for finding maximum flows.

This group describes 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.

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.

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

Formally, let \f$G=(V,A)\f$ be a digraph,

\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and

\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow

   capacity scaling.

*/

/**

@defgroup min_cut Minimum Cut Algorithms

@ingroup algs

\brief Algorithms for finding minimum cut in graphs.

This group describes 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

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

  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;

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

  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

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

    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;

        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.

    ///

    ///

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

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

    }

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

    ///

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

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

    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),

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

    ///

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

    ///

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

    NetworkSimplex& reset() {

      delete _plower;

      delete _pupper;

      delete _pcost;

      delete _psupply;

      _plower = NULL;

      _pupper = NULL;

      _pcost = NULL;

      _psupply = NULL;

      _pstsup = 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.

    /// @{

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

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

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

          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;

          _flow[e] = _supply[u];

          _forward[u] = true;

        } else {

          _flow[e] = -_supply[u];

          _forward[u] = false;

        }

      }

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

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

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

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

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

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

             .run();

      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;

    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,

{

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

  }

  return true;

}

// Check the feasibility of the given potentials (dual soluiton)

// using the "Complementary Slackness" optimality condition

template < typename GR, typename LM, typename UM,

bool checkPotential( const GR& gr, const LM& lower, const UM& upper,

{

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

  }

  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,

{

  check(mcf_result == result, "Wrong result " + test_id);

  if (result) {

          "The flow is not feasible " + test_id);

    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);

                         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

/**/

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

  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)

    .node("source", v)

    .node("target", w)

    .run();

  // A. Test NetworkSimplex with the default pivot rule

  {

    NetworkSimplex<Digraph> mcf(gr);

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