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: { kpeter@2587: GRAPH_TYPEDEFS(typename Graph); 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@2587: // The 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@2587: FlowMap *_flow; kpeter@2587: bool _local_flow; kpeter@2587: // Node map of the current potentials kpeter@2587: PotentialMap *_potential; kpeter@2587: bool _local_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: kpeter@2587: /// \brief Constructor. deba@2440: /// kpeter@2587: /// Constructor. deba@2440: /// kpeter@2587: /// \param graph The directed graph the algorithm runs on. kpeter@2587: /// \param capacity The capacities (upper bounds) of the edges. kpeter@2587: /// \param cost The cost (length) values of the edges. kpeter@2587: /// \param s The source node. kpeter@2587: /// \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@2587: _graph(graph), _capacity(capacity), _cost(cost), _flow(0), kpeter@2587: _local_flow(false), _potential(0), _local_potential(false), kpeter@2587: _source(s), _target(t) {} kpeter@2587: kpeter@2587: /// Destructor. kpeter@2587: ~MinCostMaxFlow() { kpeter@2587: if (_local_flow) delete _flow; kpeter@2587: if (_local_potential) delete _potential; kpeter@2587: } kpeter@2587: kpeter@2587: /// \brief Sets the flow map. kpeter@2587: /// kpeter@2587: /// Sets the flow map. kpeter@2587: /// kpeter@2587: /// \return \c (*this) kpeter@2587: MinCostMaxFlow& flowMap(FlowMap &map) { kpeter@2587: if (_local_flow) { kpeter@2587: delete _flow; kpeter@2587: _local_flow = false; kpeter@2587: } kpeter@2587: _flow = ↦ kpeter@2587: return *this; kpeter@2587: } kpeter@2587: kpeter@2587: /// \brief Sets the potential map. kpeter@2587: /// kpeter@2587: /// Sets the potential map. kpeter@2587: /// kpeter@2587: /// \return \c (*this) kpeter@2587: MinCostMaxFlow& potentialMap(PotentialMap &map) { kpeter@2587: if (_local_potential) { kpeter@2587: delete _potential; kpeter@2587: _local_potential = false; kpeter@2587: } kpeter@2587: _potential = ↦ kpeter@2587: return *this; kpeter@2587: } kpeter@2587: kpeter@2587: /// \name Execution control kpeter@2587: /// The only way to execute the algorithm is to call the run() kpeter@2587: /// function. kpeter@2587: kpeter@2587: /// @{ deba@2440: kpeter@2576: /// \brief Runs the algorithm. deba@2440: /// kpeter@2576: /// Runs the algorithm. kpeter@2576: void run() { kpeter@2587: // Initializing maps kpeter@2587: if (!_flow) { kpeter@2587: _flow = new FlowMap(_graph); kpeter@2587: _local_flow = true; kpeter@2587: } kpeter@2587: if (!_potential) { kpeter@2587: _potential = new PotentialMap(_graph); kpeter@2587: _local_potential = true; kpeter@2587: } kpeter@2587: // Running Preflow kpeter@2576: MaxFlowImpl preflow(_graph, _capacity, _source, _target); kpeter@2587: preflow.flowMap(*_flow).runMinCut(); kpeter@2587: // Running NetworkSimplex kpeter@2576: MinCostFlowImpl mcf( _graph, _capacity, _cost, kpeter@2576: _source, _target, preflow.flowValue() ); kpeter@2587: mcf.flowMap(*_flow).potentialMap(*_potential).run(); kpeter@2576: } kpeter@2576: kpeter@2587: /// @} kpeter@2587: kpeter@2587: /// \name Query Functions kpeter@2587: /// The result of the algorithm can be obtained using these kpeter@2587: /// functions. kpeter@2587: /// \n run() must be called before using them. kpeter@2587: kpeter@2587: /// @{ kpeter@2587: 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@2587: 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@2587: return *_potential; kpeter@2587: } kpeter@2587: kpeter@2587: /// \brief Returns the flow on the given edge. kpeter@2587: /// kpeter@2587: /// Returns the flow on the given edge. kpeter@2587: /// kpeter@2587: /// \pre \ref run() must be called before using this function. kpeter@2587: Capacity flow(const Edge& edge) const { kpeter@2587: return (*_flow)[edge]; kpeter@2587: } kpeter@2587: kpeter@2587: /// \brief Returns the potential of the given node. kpeter@2587: /// kpeter@2587: /// Returns the potential of the given node. kpeter@2587: /// kpeter@2587: /// \pre \ref run() must be called before using this function. kpeter@2587: Cost potential(const Node& node) const { kpeter@2587: return (*_potential)[node]; 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@2587: for (EdgeIt e(_graph); e != INVALID; ++e) kpeter@2587: c += (*_flow)[e] * _cost[e]; deba@2440: return c; deba@2440: } deba@2440: kpeter@2587: /// @} kpeter@2587: 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