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@2556: /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding kpeter@2556: /// the maximum flow value and \ref NetworkSimplex algorithm for kpeter@2556: /// 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 kpeter@2556: /// - Edge capacities and costs should be non-negative integers. kpeter@2556: /// However \c CostMap::Value should 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; deba@2440: typedef typename Graph::template NodeMap SupplyMap; deba@2440: typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, kpeter@2556: CostMap, SupplyMap > deba@2440: MinCostFlowImpl; deba@2440: deba@2440: public: deba@2440: kpeter@2556: /// The type of the flow map. deba@2440: typedef typename Graph::template EdgeMap FlowMap; deba@2440: deba@2440: private: deba@2440: kpeter@2556: /// The directed graph the algorithm runs on. deba@2440: const Graph &graph; kpeter@2556: /// The modified capacity map. deba@2440: const CapacityMap &capacity; kpeter@2556: /// The cost map. deba@2440: const CostMap &cost; kpeter@2556: /// The edge map of the found flow. kpeter@2556: FlowMap flow; kpeter@2556: /// The source node. deba@2440: Node source; kpeter@2556: /// The target node. deba@2440: Node target; deba@2440: kpeter@2556: typedef Preflow MaxFlowImpl; kpeter@2556: /// \brief \ref Preflow class for finding the maximum flow value. kpeter@2556: MaxFlowImpl 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, kpeter@2556: const CapacityMap &_capacity, kpeter@2556: const CostMap &_cost, kpeter@2556: Node _s, Node _t ) : deba@2440: graph(_graph), capacity(_capacity), cost(_cost), deba@2440: source(_s), target(_t), flow(_graph), deba@2515: preflow(_graph, _capacity, _s, _t) 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; kpeter@2507: for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) kpeter@2556: c += flow[e] * cost[e]; deba@2440: return c; deba@2440: } deba@2440: deba@2440: /// \brief Runs the algorithm. deba@2440: void run() { deba@2515: preflow.flowMap(flow); deba@2515: preflow.runMinCut(); deba@2440: MinCostFlowImpl mcf_impl( graph, capacity, cost, kpeter@2556: 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