source: lemon-0.x/lemon/cycle_canceling.h @ 2526:b7727edd44f2

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * 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_CYCLE_CANCELING_H
#define LEMON_CYCLE_CANCELING_H

/// \ingroup min_cost_flow
///
/// \file
/// \brief A cycle-canceling algorithm for finding a minimum cost flow.

#include <vector>
#include <lemon/graph_adaptor.h>
#include <lemon/circulation.h>

/// \brief The used cycle-canceling method.
#define LIMITED_CYCLE_CANCELING
//#define MIN_MEAN_CYCLE_CANCELING

#ifdef LIMITED_CYCLE_CANCELING
  #include <lemon/bellman_ford.h>
  /// \brief The maximum number of iterations for the first execution
  /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
  /// It should be at least 2.
  #define STARTING_LIMIT        2
  /// \brief The iteration limit for the
  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
  #define ALPHA_MUL             3
  /// \brief The iteration limit for the
  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
  #define ALPHA_DIV             2

//#define _ONLY_ONE_CYCLE_
//#define _NO_BACK_STEP_
//#define _DEBUG_ITER_
#endif

#ifdef MIN_MEAN_CYCLE_CANCELING
  #include <lemon/min_mean_cycle.h>
  #include <lemon/path.h>
#endif

namespace lemon {

  /// \addtogroup min_cost_flow
  /// @{

  /// \brief Implementation of a cycle-canceling algorithm for finding
  /// a minimum cost flow.
  ///
  /// \ref lemon::CycleCanceling "CycleCanceling" implements a
  /// cycle-canceling algorithm for finding a minimum cost flow.
  ///
  /// \param Graph The directed graph type the algorithm runs on.
  /// \param LowerMap The type of the lower bound map.
  /// \param CapacityMap The type of the capacity (upper bound) map.
  /// \param CostMap The type of the cost (length) map.
  /// \param SupplyMap The type of the supply map.
  ///
  /// \warning
  /// - Edge capacities and costs should be nonnegative integers.
  ///   However \c CostMap::Value should be signed type.
  /// - Supply values should be signed integers.
  /// - \c LowerMap::Value must be convertible to
  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
  ///   convertible to \c SupplyMap::Value.
  ///
  /// \author Peter Kovacs

template < typename Graph,
           typename LowerMap = typename Graph::template EdgeMap<int>,
           typename CapacityMap = LowerMap,
           typename CostMap = typename Graph::template EdgeMap<int>,
           typename SupplyMap = typename Graph::template NodeMap
                                <typename CapacityMap::Value> >
  class CycleCanceling
  {
    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::InEdgeIt InEdgeIt;
    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename LowerMap::Value Lower;
    typedef typename CapacityMap::Value Capacity;
    typedef typename CostMap::Value Cost;
    typedef typename SupplyMap::Value Supply;
    typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
    typedef typename Graph::template NodeMap<Supply> SupplyRefMap;

    typedef ResGraphAdaptor< const Graph, Capacity,
                             CapacityRefMap, CapacityRefMap > ResGraph;
    typedef typename ResGraph::Node ResNode;
    typedef typename ResGraph::NodeIt ResNodeIt;
    typedef typename ResGraph::Edge ResEdge;
    typedef typename ResGraph::EdgeIt ResEdgeIt;

  public:

    /// \brief The type of the flow map.
    typedef CapacityRefMap FlowMap;

  protected:

    /// \brief Map adaptor class for handling residual edge costs.
    class ResCostMap : public MapBase<ResEdge, Cost>
    {
    private:

      const CostMap &cost_map;

    public:

      ResCostMap(const CostMap &_cost) : cost_map(_cost) {}

      Cost operator[](const ResEdge &e) const {
        return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
      }

    }; //class ResCostMap

  protected:

    /// \brief The directed graph the algorithm runs on.
    const Graph &graph;
    /// \brief The original lower bound map.
    const LowerMap *lower;
    /// \brief The modified capacity map.
    CapacityRefMap capacity;
    /// \brief The cost map.
    const CostMap &cost;
    /// \brief The modified supply map.
    SupplyRefMap supply;
    /// \brief The sum of supply values equals zero.
    bool valid_supply;

    /// \brief The current flow.
    FlowMap flow;
    /// \brief The residual graph.
    ResGraph res_graph;
    /// \brief The residual cost map.
    ResCostMap res_cost;

  public :

    /// \brief General constructor of the class (with lower bounds).
    ///
    /// General constructor of the class (with lower bounds).
    ///
    /// \param _graph The directed graph the algorithm runs on.
    /// \param _lower The lower bounds of the edges.
    /// \param _capacity The capacities (upper bounds) of the edges.
    /// \param _cost The cost (length) values of the edges.
    /// \param _supply The supply values of the nodes (signed).
    CycleCanceling( const Graph &_graph,
                    const LowerMap &_lower,
                    const CapacityMap &_capacity,
                    const CostMap &_cost,
                    const SupplyMap &_supply ) :
      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
      supply(_graph), flow(_graph, 0),
      res_graph(_graph, capacity, flow), res_cost(cost)
    {
      // Removing nonzero lower bounds
      capacity = subMap(_capacity, _lower);
      Supply sum = 0;
      for (NodeIt n(graph); n != INVALID; ++n) {
        Supply s = _supply[n];
        for (InEdgeIt e(graph, n); e != INVALID; ++e)
          s += _lower[e];
        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
          s -= _lower[e];
        sum += (supply[n] = s);
      }
      valid_supply = sum == 0;
    }

    /// \brief General constructor of the class (without lower bounds).
    ///
    /// General constructor of the class (without lower bounds).
    ///
    /// \param _graph The directed graph the algorithm runs on.
    /// \param _capacity The capacities (upper bounds) of the edges.
    /// \param _cost The cost (length) values of the edges.
    /// \param _supply The supply values of the nodes (signed).
    CycleCanceling( const Graph &_graph,
                    const CapacityMap &_capacity,
                    const CostMap &_cost,
                    const SupplyMap &_supply ) :
      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
      supply(_supply), flow(_graph, 0),
      res_graph(_graph, capacity, flow), res_cost(cost)
    {
      // Checking the sum of supply values
      Supply sum = 0;
      for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
      valid_supply = sum == 0;
    }


    /// \brief Simple constructor of the class (with lower bounds).
    ///
    /// Simple constructor of the class (with lower bounds).
    ///
    /// \param _graph The directed graph the algorithm runs on.
    /// \param _lower The lower bounds of the edges.
    /// \param _capacity The capacities (upper bounds) of the edges.
    /// \param _cost The cost (length) values of the edges.
    /// \param _s The source node.
    /// \param _t The target node.
    /// \param _flow_value The required amount of flow from node \c _s
    /// to node \c _t (i.e. the supply of \c _s and the demand of
    /// \c _t).
    CycleCanceling( const Graph &_graph,
                    const LowerMap &_lower,
                    const CapacityMap &_capacity,
                    const CostMap &_cost,
                    Node _s, Node _t,
                    Supply _flow_value ) :
      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
      supply(_graph), flow(_graph, 0),
      res_graph(_graph, capacity, flow), res_cost(cost)
    {
      // Removing nonzero lower bounds
      capacity = subMap(_capacity, _lower);
      for (NodeIt n(graph); n != INVALID; ++n) {
        Supply s = 0;
        if (n == _s) s =  _flow_value;
        if (n == _t) s = -_flow_value;
        for (InEdgeIt e(graph, n); e != INVALID; ++e)
          s += _lower[e];
        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
          s -= _lower[e];
        supply[n] = s;
      }
      valid_supply = true;
    }

    /// \brief Simple constructor of the class (without lower bounds).
    ///
    /// Simple constructor of the class (without lower bounds).
    ///
    /// \param _graph The directed graph the algorithm runs on.
    /// \param _capacity The capacities (upper bounds) of the edges.
    /// \param _cost The cost (length) values of the edges.
    /// \param _s The source node.
    /// \param _t The target node.
    /// \param _flow_value The required amount of flow from node \c _s
    /// to node \c _t (i.e. the supply of \c _s and the demand of
    /// \c _t).
    CycleCanceling( const Graph &_graph,
                    const CapacityMap &_capacity,
                    const CostMap &_cost,
                    Node _s, Node _t,
                    Supply _flow_value ) :
      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
      supply(_graph, 0), flow(_graph, 0),
      res_graph(_graph, capacity, flow), res_cost(cost)
    {
      supply[_s] =  _flow_value;
      supply[_t] = -_flow_value;
      valid_supply = true;
    }

    /// \brief Returns a const reference to the flow map.
    ///
    /// Returns a const reference to the flow map.
    ///
    /// \pre \ref run() must be called before using this function.
    const FlowMap& flowMap() const {
      return flow;
    }

    /// \brief Returns the total cost of the found flow.
    ///
    /// Returns the total cost of the found flow. The complexity of the
    /// function is \f$ O(e) \f$.
    ///
    /// \pre \ref run() must be called before using this function.
    Cost totalCost() const {
      Cost c = 0;
      for (EdgeIt e(graph); e != INVALID; ++e)
        c += flow[e] * cost[e];
      return c;
    }

    /// \brief Runs the algorithm.
    ///
    /// Runs the algorithm.
    ///
    /// \return \c true if a feasible flow can be found.
    bool run() {
      return init() && start();
    }

  protected:

    /// \brief Initializes the algorithm.
    bool init() {
      // Checking the sum of supply values
      Supply sum = 0;
      for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
      if (sum != 0) return false;

      // Finding a feasible flow
      Circulation< Graph, Capacity, ConstMap<Edge, Capacity>,
        CapacityRefMap, SupplyMap >::DefFlowMap<FlowMap>::Create
        circulation( graph, constMap<Edge>((Capacity)0),
                     capacity, supply);
      circulation.flowMap(flowMap);
      return circulation.run();
    }

#ifdef LIMITED_CYCLE_CANCELING
    /// \brief Executes a cycle-canceling algorithm using
    /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
    /// iteration count.
    bool start() {
      typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
      typename ResGraph::template NodeMap<int> visited(res_graph);
      std::vector<ResEdge> cycle;
      int node_num = countNodes(graph);

#ifdef _DEBUG_ITER_
      int cycle_num = 0;
#endif
      int length_bound = STARTING_LIMIT;
      bool optimal = false;
      while (!optimal) {
        BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
        bf.predMap(pred);
        bf.init(0);
        int iter_num = 0;
        bool cycle_found = false;
        while (!cycle_found) {
#ifdef _NO_BACK_STEP_
          int curr_iter_num = length_bound <= node_num ?
                              length_bound - iter_num : node_num - iter_num;
#else
          int curr_iter_num = iter_num + length_bound <= node_num ?
                              length_bound : node_num - iter_num;
#endif
          iter_num += curr_iter_num;
          int real_iter_num = curr_iter_num;
          for (int i = 0; i < curr_iter_num; ++i) {
            if (bf.processNextWeakRound()) {
              real_iter_num = i;
              break;
            }
          }
          if (real_iter_num < curr_iter_num) {
            optimal = true;
            break;
          } else {
            // Searching for node disjoint negative cycles
            for (ResNodeIt n(res_graph); n != INVALID; ++n)
              visited[n] = 0;
            int id = 0;
            for (ResNodeIt n(res_graph); n != INVALID; ++n) {
              if (visited[n] > 0) continue;
              visited[n] = ++id;
              ResNode u = pred[n] == INVALID ?
                          INVALID : res_graph.source(pred[n]);
              while (u != INVALID && visited[u] == 0) {
                visited[u] = id;
                u = pred[u] == INVALID ?
                    INVALID : res_graph.source(pred[u]);
              }
              if (u != INVALID && visited[u] == id) {
                // Finding the negative cycle
                cycle_found = true;
                cycle.clear();
                ResEdge e = pred[u];
                cycle.push_back(e);
                Capacity d = res_graph.rescap(e);
                while (res_graph.source(e) != u) {
                  cycle.push_back(e = pred[res_graph.source(e)]);
                  if (res_graph.rescap(e) < d)
                    d = res_graph.rescap(e);
                }
#ifdef _DEBUG_ITER_
                ++cycle_num;
#endif
                // Augmenting along the cycle
                for (int i = 0; i < cycle.size(); ++i)
                  res_graph.augment(cycle[i], d);
#ifdef _ONLY_ONE_CYCLE_
                break;
#endif
              }
            }
          }

          if (!cycle_found)
            length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
        }
      }

#ifdef _DEBUG_ITER_
      std::cout << "Limited cycle-canceling algorithm finished. "
                << "Found " << cycle_num << " negative cycles."
                << std::endl;
#endif

      // Handling nonzero lower bounds
      if (lower) {
        for (EdgeIt e(graph); e != INVALID; ++e)
          flow[e] += (*lower)[e];
      }
      return true;
    }
#endif

#ifdef MIN_MEAN_CYCLE_CANCELING
    /// \brief Executes the minimum mean cycle-canceling algorithm
    /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
    bool start() {
      typedef Path<ResGraph> ResPath;
      MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
      ResPath cycle;

#ifdef _DEBUG_ITER_
      int cycle_num = 0;
#endif
      mmc.cyclePath(cycle).init();
      if (mmc.findMinMean()) {
        while (mmc.cycleLength() < 0) {
#ifdef _DEBUG_ITER_
          ++iter;
#endif
          // Finding the cycle
          mmc.findCycle();

          // Finding the largest flow amount that can be augmented
          // along the cycle
          Capacity delta = 0;
          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
            if (delta == 0 || res_graph.rescap(e) < delta)
              delta = res_graph.rescap(e);
          }

          // Augmenting along the cycle
          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
            res_graph.augment(e, delta);

          // Finding the minimum cycle mean for the modified residual
          // graph
          mmc.reset();
          if (!mmc.findMinMean()) break;
        }
      }

#ifdef _DEBUG_ITER_
      std::cout << "Minimum mean cycle-canceling algorithm finished. "
                << "Found " << cycle_num << " negative cycles."
                << std::endl;
#endif

      // Handling nonzero lower bounds
      if (lower) {
        for (EdgeIt e(graph); e != INVALID; ++e)
          flow[e] += (*lower)[e];
      }
      return true;
    }
#endif

  }; //class CycleCanceling

  ///@}

} //namespace lemon

#endif //LEMON_CYCLE_CANCELING_H