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

   ///

   /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum

   /// flow value and \ref NetworkSimplex for finding a minimum cost

   /// flow of that value.

   /// According to our benchmark tests \ref Preflow is generally the

   /// most efficient algorithm for the maximum flow problem and

   /// \ref NetworkSimplex is the most efficient for the minimum cost

   /// flow problem in LEMON.

   ///

   /// \tparam Graph The directed graph type the algorithm runs on.

   /// \tparam CapacityMap The type of the capacity (upper bound) map.

   /// \tparam CostMap The type of the cost (length) map.

   ///

   /// \warning

   /// - Edge capacities and costs should be \e non-negative \e integers.

   /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.

   /// - \c CostMap::Value must 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

   {

     GRAPH_TYPEDEFS(typename Graph);

     typedef typename CapacityMap::Value Capacity;

     typedef typename CostMap::Value Cost;

     typedef typename Graph::template NodeMap<Cost> SupplyMap;

     typedef Preflow<Graph, CapacityMap> MaxFlowImpl;

     typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,

                             CostMap, SupplyMap > MinCostFlowImpl;

   public:

     /// The type of the flow map.

     typedef typename Graph::template EdgeMap<Capacity> FlowMap;

     /// The type of the potential map.

     typedef typename Graph::template NodeMap<Cost> PotentialMap;

   private:

     // The directed graph the algorithm runs on

     const Graph &_graph;

     // The capacity map

     const CapacityMap &_capacity;

     // The cost map

     const CostMap &_cost;

     // Edge map of the found flow

     FlowMap *_flow;

     bool _local_flow;

     // Node map of the current potentials

     PotentialMap *_potential;

     bool _local_potential;

     // The source node

     Node _source;

     // The target node

     Node _target;

   public:

     /// \brief Constructor.

     ///

     /// Constructor.

     ///

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

       _local_flow(false), _potential(0), _local_potential(false),

       _source(s), _target(t) {}

     /// Destructor.

     ~MinCostMaxFlow() {

       if (_local_flow) delete _flow;

       if (_local_potential) delete _potential;

     }

     /// \brief Sets the flow map.

     ///

     /// Sets the flow map.

     ///

     /// \return \c (*this)

     MinCostMaxFlow& flowMap(FlowMap &map) {

       if (_local_flow) {

         delete _flow;

         _local_flow = false;

       }

       _flow = ↦

       return *this;

     }

     /// \brief Sets the potential map.

     ///

     /// Sets the potential map.

     ///

     /// \return \c (*this)

     MinCostMaxFlow& potentialMap(PotentialMap &map) {

       if (_local_potential) {

         delete _potential;

         _local_potential = false;

       }

       _potential = ↦

       return *this;

     }

     /// \name Execution control

     /// The only way to execute the algorithm is to call the run()

     /// function.

     /// @{

     /// \brief Runs the algorithm.

     ///

     /// Runs the algorithm.

     void run() {

       // Initializing maps

       if (!_flow) {

         _flow = new FlowMap(_graph);

         _local_flow = true;

       }

       if (!_potential) {

         _potential = new PotentialMap(_graph);

         _local_potential = true;

       }

       // Running Preflow

       MaxFlowImpl preflow(_graph, _capacity, _source, _target);

       preflow.flowMap(*_flow).runMinCut();

       // Running NetworkSimplex

       MinCostFlowImpl mcf( _graph, _capacity, _cost,

                            _source, _target, preflow.flowValue() );

       mcf.flowMap(*_flow).potentialMap(*_potential).run();

     }

     /// @}

     /// \name Query Functions

     /// The result of the algorithm can be obtained using these

     /// functions.

     /// \n run() must be called before using them.

     /// @{

     /// \brief Returns a const reference to the edge map storing the

     /// found flow.

     ///

     /// Returns a const reference to the edge map storing the found flow.

     ///

     /// \pre \ref run() must be called before using this function.

     const FlowMap& flowMap() const {

       return *_flow;

     }

     /// \brief Returns a const reference to the node map storing the

     /// found potentials (the dual solution).

     ///

     /// Returns a const reference to the node map storing the found

     /// potentials (the dual solution).

     ///

     /// \pre \ref run() must be called before using this function.

     const PotentialMap& potentialMap() const {

       return *_potential;

     }

     /// \brief Returns the flow on the given edge.

     ///

     /// Returns the flow on the given edge.

     ///

     /// \pre \ref run() must be called before using this function.

     Capacity flow(const Edge& edge) const {

       return (*_flow)[edge];

     }

     /// \brief Returns the potential of the given node.

     ///

     /// Returns the potential of the given node.

     ///

     /// \pre \ref run() must be called before using this function.

     Cost potential(const Node& node) const {

       return (*_potential)[node];

     }

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

     }

     /// @}

   }; //class MinCostMaxFlow

   ///@}

 } //namespace lemon

 #endif //LEMON_MIN_COST_MAX_FLOW_H