/* -*- C++ -*-
*
* This file is a part of LEMON, a generic C++ optimization library
*
* Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#ifndef LEMON_MIN_COST_MAX_FLOW_H
#define LEMON_MIN_COST_MAX_FLOW_H
/// \ingroup min_cost_flow
///
/// \file
/// \brief An efficient algorithm for finding a minimum cost maximum flow.
#include
#include
#include
namespace lemon {
/// \addtogroup min_cost_flow
/// @{
/// \brief An efficient algorithm for finding a minimum cost
/// maximum flow.
///
/// \ref MinCostMaxFlow implements an efficient algorithm for
/// finding a maximum flow having minimal total cost from a given
/// source node to a given target node in a directed graph.
///
/// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
/// the maximum flow value and \ref NetworkSimplex algorithm for
/// finding a minimum cost flow of that value.
///
/// \param Graph The directed graph type the algorithm runs on.
/// \param CapacityMap The type of the capacity (upper bound) map.
/// \param CostMap The type of the cost (length) map.
///
/// \warning
/// - Edge capacities and costs should be non-negative integers.
/// However \c CostMap::Value should be signed type.
///
/// \author Peter Kovacs
template < typename Graph,
typename CapacityMap = typename Graph::template EdgeMap,
typename CostMap = typename Graph::template EdgeMap >
class MinCostMaxFlow
{
typedef typename Graph::Node Node;
typedef typename Graph::Edge Edge;
typedef typename CapacityMap::Value Capacity;
typedef typename CostMap::Value Cost;
typedef typename Graph::template NodeMap SupplyMap;
typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
CostMap, SupplyMap >
MinCostFlowImpl;
public:
/// The type of the flow map.
typedef typename Graph::template EdgeMap FlowMap;
private:
/// The directed graph the algorithm runs on.
const Graph &graph;
/// The modified capacity map.
const CapacityMap &capacity;
/// The cost map.
const CostMap &cost;
/// The edge map of the found flow.
FlowMap flow;
/// The source node.
Node source;
/// The target node.
Node target;
typedef Preflow MaxFlowImpl;
/// \brief \ref Preflow class for finding the maximum flow value.
MaxFlowImpl preflow;
public:
/// \brief The constructor of the class.
///
/// The constructor of the class.
///
/// \param _graph The directed graph the algorithm runs on.
/// \param _capacity The capacities (upper bounds) of the edges.
/// \param _cost The cost (length) values of the edges.
/// \param _s The source node.
/// \param _t The target node.
MinCostMaxFlow( const Graph &_graph,
const CapacityMap &_capacity,
const CostMap &_cost,
Node _s, Node _t ) :
graph(_graph), capacity(_capacity), cost(_cost),
source(_s), target(_t), flow(_graph),
preflow(_graph, _capacity, _s, _t)
{}
/// \brief Returns a const reference to the flow map.
///
/// Returns a const reference to the flow map.
///
/// \pre \ref run() must be called before using this function.
const FlowMap& flowMap() const {
return flow;
}
/// \brief Returns the total cost of the found flow.
///
/// Returns the total cost of the found flow. The complexity of the
/// function is \f$ O(e) \f$.
///
/// \pre \ref run() must be called before using this function.
Cost totalCost() const {
Cost c = 0;
for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
c += flow[e] * cost[e];
return c;
}
/// \brief Runs the algorithm.
void run() {
preflow.flowMap(flow);
preflow.runMinCut();
MinCostFlowImpl mcf_impl( graph, capacity, cost,
source, target, preflow.flowValue() );
mcf_impl.run();
flow = mcf_impl.flowMap();
}
}; //class MinCostMaxFlow
///@}
} //namespace lemon
#endif //LEMON_MIN_COST_MAX_FLOW_H