deba@2440: /* -*- C++ -*- deba@2440: * deba@2440: * This file is a part of LEMON, a generic C++ optimization library deba@2440: * deba@2440: * Copyright (C) 2003-2007 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 deba@2440: /// \brief An efficient algorithm for finding a minimum cost maximum deba@2440: /// 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: deba@2440: /// \brief An efficient algorithm for finding a minimum cost maximum deba@2440: /// flow. deba@2440: /// deba@2440: /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient deba@2440: /// algorithm for finding a maximum flow having minimal total cost deba@2440: /// from a given source node to a given target node in a directed deba@2440: /// graph. deba@2440: /// deba@2440: /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses deba@2440: /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum deba@2440: /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" deba@2440: /// algorithm for finding a minimum cost flow of that value. deba@2440: /// deba@2440: /// \param Graph The directed graph type the algorithm runs on. deba@2440: /// \param CapacityMap The type of the capacity (upper bound) map. deba@2440: /// \param CostMap The type of the cost (length) map. deba@2440: /// deba@2440: /// \warning deba@2440: /// - Edge capacities and costs should be nonnegative integers. deba@2440: /// However \c CostMap::Value should be signed type. deba@2440: /// deba@2440: /// \author Peter Kovacs deba@2440: deba@2440: template < typename Graph, deba@2440: typename CapacityMap = typename Graph::template EdgeMap, deba@2440: 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; deba@2440: typedef typename Graph::template NodeMap SupplyMap; deba@2440: typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, deba@2440: CostMap, SupplyMap > deba@2440: MinCostFlowImpl; deba@2440: deba@2440: public: deba@2440: deba@2440: /// \brief The type of the flow map. deba@2440: typedef typename Graph::template EdgeMap FlowMap; deba@2440: deba@2440: private: deba@2440: deba@2440: /// \brief The directed graph the algorithm runs on. deba@2440: const Graph &graph; deba@2440: /// \brief The modified capacity map. deba@2440: const CapacityMap &capacity; deba@2440: /// \brief The cost map. deba@2440: const CostMap &cost; deba@2440: /// \brief The source node. deba@2440: Node source; deba@2440: /// \brief The target node. deba@2440: Node target; deba@2440: /// \brief The edge map of the found flow. deba@2440: FlowMap flow; deba@2440: deba@2440: typedef Preflow PreflowImpl; deba@2440: /// \brief \ref lemon::Preflow "Preflow" class for finding the deba@2440: /// maximum flow value. deba@2440: PreflowImpl preflow; 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. deba@2440: MinCostMaxFlow( const Graph &_graph, deba@2440: const CapacityMap &_capacity, deba@2440: const CostMap &_cost, deba@2440: Node _s, Node _t ) : deba@2440: graph(_graph), capacity(_capacity), cost(_cost), deba@2440: source(_s), target(_t), flow(_graph), deba@2440: preflow(_graph, _s, _t, _capacity, flow) deba@2440: {} deba@2440: deba@2440: /// \brief Returns a const reference to the flow map. deba@2440: /// deba@2440: /// Returns a const reference to the flow map. deba@2440: /// deba@2440: /// \pre \ref run() must be called before using this function. deba@2440: const FlowMap& flowMap() const { deba@2440: return flow; 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; deba@2440: for (EdgeIt e(graph); e != INVALID; ++e) deba@2440: c += flow[e] * cost[e]; deba@2440: return c; deba@2440: } deba@2440: deba@2440: /// \brief Runs the algorithm. deba@2440: void run() { deba@2440: preflow.phase1(); deba@2440: MinCostFlowImpl mcf_impl( graph, capacity, cost, deba@2440: source, target, preflow.flowValue() ); deba@2440: mcf_impl.run(); deba@2440: flow = mcf_impl.flowMap(); 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