source: lemon-0.x/lemon/min_cost_max_flow.h @ 2573:a9758ea1f01c

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

/// \ingroup min_cost_flow
///
/// \file
/// \brief An efficient algorithm for finding a minimum cost maximum flow.

#include <lemon/preflow.h>
#include <lemon/network_simplex.h>
#include <lemon/maps.h>

namespace lemon {

  /// \addtogroup min_cost_flow
  /// @{

  /// \brief An efficient algorithm for finding a minimum cost
  /// maximum flow.
  ///
  /// \ref MinCostMaxFlow implements an efficient algorithm for
  /// finding a maximum flow having minimal total cost from a given
  /// source node to a given target node in a directed graph.
  ///
  /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
  /// the maximum flow value and \ref NetworkSimplex algorithm for
  /// finding a minimum cost flow of that value.
  ///
  /// \param Graph The directed graph type the algorithm runs on.
  /// \param CapacityMap The type of the capacity (upper bound) map.
  /// \param CostMap The type of the cost (length) map.
  ///
  /// \warning
  /// - Edge capacities and costs should be non-negative integers.
  ///   However \c CostMap::Value should be signed type.
  ///
  /// \author Peter Kovacs

  template < typename Graph,
             typename CapacityMap = typename Graph::template EdgeMap<int>,
             typename CostMap = typename Graph::template EdgeMap<int> >
  class MinCostMaxFlow
  {
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;

    typedef typename CapacityMap::Value Capacity;
    typedef typename CostMap::Value Cost;
    typedef typename Graph::template NodeMap<Capacity> SupplyMap;
    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
                            CostMap, SupplyMap >
      MinCostFlowImpl;

  public:

    /// The type of the flow map.
    typedef typename Graph::template EdgeMap<Capacity> FlowMap;

  private:

    /// The directed graph the algorithm runs on.
    const Graph &graph;
    /// The modified capacity map.
    const CapacityMap &capacity;
    /// The cost map.
    const CostMap &cost;
    /// The edge map of the found flow.
    FlowMap flow;
    /// The source node.
    Node source;
    /// The target node.
    Node target;

    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
    /// \brief \ref Preflow class for finding the maximum flow value.
    MaxFlowImpl preflow;

  public:

    /// \brief The constructor of the class.
    ///
    /// The constructor of the class.
    ///
    /// \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.
    MinCostMaxFlow( const Graph &_graph,
                    const CapacityMap &_capacity,
                    const CostMap &_cost,
                    Node _s, Node _t ) :
      graph(_graph), capacity(_capacity), cost(_cost),
      source(_s), target(_t), flow(_graph),
      preflow(_graph, _capacity, _s, _t)
    {}

    /// \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 (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
        c += flow[e] * cost[e];
      return c;
    }

    /// \brief Runs the algorithm.
    void run() {
      preflow.flowMap(flow);
      preflow.runMinCut();
      MinCostFlowImpl mcf_impl( graph, capacity, cost,
                                source, target, preflow.flowValue() );
      mcf_impl.run();
      flow = mcf_impl.flowMap();
    }

  }; //class MinCostMaxFlow

  ///@}

} //namespace lemon

#endif //LEMON_MIN_COST_MAX_FLOW_H