deba@2440: /* -*- C++ -*-
deba@2440:  *
deba@2440:  * This file is a part of LEMON, a generic C++ optimization library
deba@2440:  *
alpar@2553:  * Copyright (C) 2003-2008
deba@2440:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2440:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2440:  *
deba@2440:  * Permission to use, modify and distribute this software is granted
deba@2440:  * provided that this copyright notice appears in all copies. For
deba@2440:  * precise terms see the accompanying LICENSE file.
deba@2440:  *
deba@2440:  * This software is provided "AS IS" with no warranty of any kind,
deba@2440:  * express or implied, and with no claim as to its suitability for any
deba@2440:  * purpose.
deba@2440:  *
deba@2440:  */
deba@2440: 
deba@2440: #ifndef LEMON_MIN_COST_MAX_FLOW_H
deba@2440: #define LEMON_MIN_COST_MAX_FLOW_H
deba@2440: 
deba@2440: /// \ingroup min_cost_flow
deba@2440: ///
deba@2440: /// \file
kpeter@2556: /// \brief An efficient algorithm for finding a minimum cost maximum flow.
deba@2440: 
deba@2440: #include <lemon/preflow.h>
deba@2440: #include <lemon/network_simplex.h>
deba@2440: #include <lemon/maps.h>
deba@2440: 
deba@2440: namespace lemon {
deba@2440: 
deba@2440:   /// \addtogroup min_cost_flow
deba@2440:   /// @{
deba@2440: 
kpeter@2556:   /// \brief An efficient algorithm for finding a minimum cost
kpeter@2556:   /// maximum flow.
deba@2440:   ///
kpeter@2556:   /// \ref MinCostMaxFlow implements an efficient algorithm for
kpeter@2556:   /// finding a maximum flow having minimal total cost from a given
kpeter@2556:   /// source node to a given target node in a directed graph.
deba@2440:   ///
kpeter@2576:   /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum
kpeter@2576:   /// flow value and \ref NetworkSimplex for finding a minimum cost
kpeter@2576:   /// flow of that value.
kpeter@2576:   /// According to our benchmark tests \ref Preflow is generally the
kpeter@2576:   /// most efficient algorithm for the maximum flow problem and
kpeter@2576:   /// \ref NetworkSimplex is the most efficient for the minimum cost
kpeter@2576:   /// flow problem in LEMON.
deba@2440:   ///
kpeter@2576:   /// \tparam Graph The directed graph type the algorithm runs on.
kpeter@2576:   /// \tparam CapacityMap The type of the capacity (upper bound) map.
kpeter@2576:   /// \tparam CostMap The type of the cost (length) map.
deba@2440:   ///
deba@2440:   /// \warning
kpeter@2576:   /// - Edge capacities and costs should be \e non-negative \e integers.
kpeter@2576:   ///   However \c CostMap::Value must be signed type.
kpeter@2576:   /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
deba@2440:   ///
deba@2440:   /// \author Peter Kovacs
deba@2440: 
kpeter@2533:   template < typename Graph,
kpeter@2556:              typename CapacityMap = typename Graph::template EdgeMap<int>,
kpeter@2556:              typename CostMap = typename Graph::template EdgeMap<int> >
deba@2440:   class MinCostMaxFlow
deba@2440:   {
deba@2440:     typedef typename Graph::Node Node;
deba@2440:     typedef typename Graph::Edge Edge;
deba@2440: 
deba@2440:     typedef typename CapacityMap::Value Capacity;
kpeter@2556:     typedef typename CostMap::Value Cost;
kpeter@2576:     typedef typename Graph::template NodeMap<Cost> SupplyMap;
kpeter@2576: 
kpeter@2576:     typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
deba@2440:     typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
kpeter@2576:                             CostMap, SupplyMap > MinCostFlowImpl;
deba@2440: 
deba@2440:   public:
deba@2440: 
kpeter@2556:     /// The type of the flow map.
deba@2440:     typedef typename Graph::template EdgeMap<Capacity> FlowMap;
kpeter@2576:     /// The type of the potential map.
kpeter@2576:     typedef typename Graph::template NodeMap<Cost> PotentialMap;
deba@2440: 
deba@2440:   private:
deba@2440: 
kpeter@2576:     // The directed graph the algorithm runs on
kpeter@2576:     const Graph &_graph;
kpeter@2576:     // The modified capacity map
kpeter@2576:     const CapacityMap &_capacity;
kpeter@2576:     // The cost map
kpeter@2576:     const CostMap &_cost;
deba@2440: 
kpeter@2576:     // Edge map of the found flow
kpeter@2576:     FlowMap _flow;
kpeter@2576:     // Node map of the found potentials
kpeter@2576:     PotentialMap _potential;
kpeter@2576: 
kpeter@2576:     // The source node
kpeter@2576:     Node _source;
kpeter@2576:     // The target node
kpeter@2576:     Node _target;
deba@2440: 
deba@2440:   public:
deba@2440: 
deba@2440:     /// \brief The constructor of the class.
deba@2440:     ///
deba@2440:     /// The constructor of the class.
deba@2440:     ///
deba@2440:     /// \param _graph The directed graph the algorithm runs on.
deba@2440:     /// \param _capacity The capacities (upper bounds) of the edges.
deba@2440:     /// \param _cost The cost (length) values of the edges.
deba@2440:     /// \param _s The source node.
deba@2440:     /// \param _t The target node.
kpeter@2576:     MinCostMaxFlow( const Graph &graph,
kpeter@2576:                     const CapacityMap &capacity,
kpeter@2576:                     const CostMap &cost,
kpeter@2576:                     Node s, Node t ) :
kpeter@2576:       _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
kpeter@2576:       _potential(graph), _source(s), _target(t)
deba@2440:     {}
deba@2440: 
kpeter@2576:     /// \brief Runs the algorithm.
deba@2440:     ///
kpeter@2576:     /// Runs the algorithm.
kpeter@2576:     void run() {
kpeter@2576:       MaxFlowImpl preflow(_graph, _capacity, _source, _target);
kpeter@2576:       preflow.flowMap(_flow).runMinCut();
kpeter@2576:       MinCostFlowImpl mcf( _graph, _capacity, _cost,
kpeter@2576:                            _source, _target, preflow.flowValue() );
kpeter@2576:       mcf.run();
kpeter@2576:       _flow = mcf.flowMap();
kpeter@2576:       _potential = mcf.potentialMap();
kpeter@2576:     }
kpeter@2576: 
kpeter@2576:     /// \brief Returns a const reference to the edge map storing the
kpeter@2576:     /// found flow.
kpeter@2576:     ///
kpeter@2576:     /// Returns a const reference to the edge map storing the found flow.
deba@2440:     ///
deba@2440:     /// \pre \ref run() must be called before using this function.
deba@2440:     const FlowMap& flowMap() const {
kpeter@2579:       return _flow;
kpeter@2576:     }
kpeter@2576: 
kpeter@2576:     /// \brief Returns a const reference to the node map storing the
kpeter@2576:     /// found potentials (the dual solution).
kpeter@2576:     ///
kpeter@2576:     /// Returns a const reference to the node map storing the found
kpeter@2576:     /// potentials (the dual solution).
kpeter@2576:     ///
kpeter@2576:     /// \pre \ref run() must be called before using this function.
kpeter@2576:     const PotentialMap& potentialMap() const {
kpeter@2579:       return _potential;
deba@2440:     }
deba@2440: 
deba@2440:     /// \brief Returns the total cost of the found flow.
deba@2440:     ///
deba@2440:     /// Returns the total cost of the found flow. The complexity of the
deba@2440:     /// function is \f$ O(e) \f$.
deba@2440:     ///
deba@2440:     /// \pre \ref run() must be called before using this function.
deba@2440:     Cost totalCost() const {
deba@2440:       Cost c = 0;
kpeter@2579:       for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e)
kpeter@2576:         c += _flow[e] * _cost[e];
deba@2440:       return c;
deba@2440:     }
deba@2440: 
deba@2440:   }; //class MinCostMaxFlow
deba@2440: 
deba@2440:   ///@}
deba@2440: 
deba@2440: } //namespace lemon
deba@2440: 
deba@2440: #endif //LEMON_MIN_COST_MAX_FLOW_H