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: /// - \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<int>,
kpeter@2556: typename CostMap = typename Graph::template EdgeMap<int> >
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<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@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