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 deba@2440: #include deba@2440: #include 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: /// - \c CapacityMap::Value must be convertible to \c CostMap::Value. kpeter@2582: /// - \c CostMap::Value must be signed type. deba@2440: /// deba@2440: /// \author Peter Kovacs deba@2440: kpeter@2533: template < typename Graph, kpeter@2556: typename CapacityMap = typename Graph::template EdgeMap, kpeter@2556: typename CostMap = typename Graph::template EdgeMap > 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 SupplyMap; kpeter@2576: kpeter@2576: typedef Preflow 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 FlowMap; kpeter@2576: /// The type of the potential map. kpeter@2576: typedef typename Graph::template NodeMap 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@2582: mcf.flowMap(_flow).potentialMap(_potential).run(); 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