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_CAPACITY_SCALING_H
deba@2440: #define LEMON_CAPACITY_SCALING_H
deba@2440: 
deba@2440: /// \ingroup min_cost_flow
deba@2440: ///
deba@2440: /// \file
deba@2440: /// \brief The capacity scaling algorithm for finding a minimum cost
deba@2440: /// flow.
deba@2440: 
deba@2440: #include <vector>
kpeter@2509: #include <lemon/graph_adaptor.h>
deba@2440: #include <lemon/dijkstra.h>
deba@2440: 
deba@2440: #define WITH_SCALING
deba@2440: 
kpeter@2471: #ifdef WITH_SCALING
kpeter@2471: #define SCALING_FACTOR	  2
kpeter@2471: #endif
kpeter@2471: 
deba@2457: //#define _DEBUG_ITER_
deba@2457: 
deba@2440: namespace lemon {
deba@2440: 
deba@2440:   /// \addtogroup min_cost_flow
deba@2440:   /// @{
deba@2440: 
deba@2440:   /// \brief Implementation of the capacity scaling version of the
kpeter@2509:   /// successive shortest path algorithm for finding a minimum cost
kpeter@2509:   /// flow.
deba@2440:   ///
kpeter@2509:   /// \ref lemon::CapacityScaling "CapacityScaling" implements the
kpeter@2509:   /// capacity scaling version of the successive shortest path
kpeter@2509:   /// algorithm for finding a minimum cost flow.
deba@2440:   ///
deba@2440:   /// \param Graph The directed graph type the algorithm runs on.
deba@2440:   /// \param LowerMap The type of the lower bound map.
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:   /// \param SupplyMap The type of the supply 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.
kpeter@2509:   /// - Supply values should be signed integers.
deba@2440:   /// - \c LowerMap::Value must be convertible to
deba@2440:   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
deba@2440:   ///	convertible to \c SupplyMap::Value.
deba@2440:   ///
deba@2440:   /// \author Peter Kovacs
deba@2440: 
deba@2440: template < typename Graph,
deba@2440: 	   typename LowerMap = typename Graph::template EdgeMap<int>,
deba@2440: 	   typename CapacityMap = LowerMap,
deba@2440: 	   typename CostMap = typename Graph::template EdgeMap<int>,
deba@2440: 	   typename SupplyMap = typename Graph::template NodeMap
deba@2440: 				<typename CapacityMap::Value> >
deba@2440:   class CapacityScaling
deba@2440:   {
deba@2440:     typedef typename Graph::Node Node;
deba@2440:     typedef typename Graph::NodeIt NodeIt;
deba@2440:     typedef typename Graph::Edge Edge;
deba@2440:     typedef typename Graph::EdgeIt EdgeIt;
deba@2440:     typedef typename Graph::InEdgeIt InEdgeIt;
deba@2440:     typedef typename Graph::OutEdgeIt OutEdgeIt;
deba@2440: 
deba@2440:     typedef typename LowerMap::Value Lower;
deba@2440:     typedef typename CapacityMap::Value Capacity;
deba@2440:     typedef typename CostMap::Value Cost;
deba@2440:     typedef typename SupplyMap::Value Supply;
deba@2440:     typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
deba@2440:     typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
deba@2440: 
deba@2440:     typedef ResGraphAdaptor< const Graph, Capacity,
deba@2440: 			     CapacityRefMap, CapacityRefMap > ResGraph;
deba@2440:     typedef typename ResGraph::Node ResNode;
deba@2440:     typedef typename ResGraph::NodeIt ResNodeIt;
deba@2440:     typedef typename ResGraph::Edge ResEdge;
deba@2440:     typedef typename ResGraph::EdgeIt ResEdgeIt;
deba@2440: 
deba@2440:   public:
deba@2440: 
deba@2440:     /// \brief The type of the flow map.
deba@2440:     typedef CapacityRefMap FlowMap;
deba@2440:     /// \brief The type of the potential map.
deba@2440:     typedef typename Graph::template NodeMap<Cost> PotentialMap;
deba@2440: 
deba@2440:   protected:
deba@2440: 
deba@2440:     /// \brief Map adaptor class for handling reduced edge costs.
deba@2440:     class ReducedCostMap : public MapBase<ResEdge, Cost>
deba@2440:     {
deba@2440:     private:
deba@2440: 
deba@2440:       const ResGraph &gr;
deba@2440:       const CostMap &cost_map;
deba@2440:       const PotentialMap &pot_map;
deba@2440: 
deba@2440:     public:
deba@2440: 
deba@2440:       ReducedCostMap( const ResGraph &_gr,
deba@2440: 		      const CostMap &_cost,
deba@2440: 		      const PotentialMap &_pot ) :
deba@2440: 	gr(_gr), cost_map(_cost), pot_map(_pot) {}
deba@2440: 
kpeter@2509:       Cost operator[](const ResEdge &e) const {
deba@2440: 	return ResGraph::forward(e) ?
deba@2440: 	   cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
deba@2440: 	  -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
deba@2440:       }
deba@2440: 
deba@2440:     }; //class ReducedCostMap
deba@2440: 
kpeter@2509:     /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"
kpeter@2509:     /// algorithm to update node potentials.
deba@2440:     class PotentialUpdateMap : public MapBase<ResNode, Cost>
deba@2440:     {
deba@2440:     private:
deba@2440: 
deba@2440:       PotentialMap *pot;
deba@2440:       typedef std::pair<ResNode, Cost> Pair;
deba@2440:       std::vector<Pair> data;
deba@2440: 
deba@2440:     public:
deba@2440: 
deba@2440:       void potentialMap(PotentialMap &_pot) {
deba@2440: 	pot = &_pot;
deba@2440:       }
deba@2440: 
deba@2440:       void init() {
deba@2440: 	data.clear();
deba@2440:       }
deba@2440: 
kpeter@2509:       void set(const ResNode &n, const Cost &v) {
deba@2440: 	data.push_back(Pair(n, v));
deba@2440:       }
deba@2440: 
deba@2440:       void update() {
deba@2440: 	Cost val = data[data.size()-1].second;
deba@2440: 	for (int i = 0; i < data.size()-1; ++i)
deba@2440: 	  (*pot)[data[i].first] += val - data[i].second;
deba@2440:       }
deba@2440: 
deba@2440:     }; //class PotentialUpdateMap
deba@2440: 
deba@2440: #ifdef WITH_SCALING
deba@2440:     /// \brief Map adaptor class for identifing deficit nodes.
deba@2440:     class DeficitBoolMap : public MapBase<ResNode, bool>
deba@2440:     {
deba@2440:     private:
deba@2440: 
deba@2440:       const SupplyRefMap &imb;
deba@2440:       const Capacity &delta;
deba@2440: 
deba@2440:     public:
deba@2440: 
deba@2440:       DeficitBoolMap(const SupplyRefMap &_imb, const Capacity &_delta) :
deba@2440: 	imb(_imb), delta(_delta) {}
deba@2440: 
deba@2440:       bool operator[](const ResNode &n) const {
deba@2440: 	return imb[n] <= -delta;
deba@2440:       }
deba@2440: 
deba@2440:     }; //class DeficitBoolMap
deba@2440: 
deba@2440:     /// \brief Map adaptor class for filtering edges with at least
kpeter@2509:     /// \c delta residual capacity.
deba@2440:     class DeltaFilterMap : public MapBase<ResEdge, bool>
deba@2440:     {
deba@2440:     private:
deba@2440: 
deba@2440:       const ResGraph &gr;
deba@2440:       const Capacity &delta;
deba@2440: 
deba@2440:     public:
deba@2440: 
deba@2440:       DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
deba@2440: 	gr(_gr), delta(_delta) {}
deba@2440: 
kpeter@2509:       bool operator[](const ResEdge &e) const {
deba@2440: 	return gr.rescap(e) >= delta;
deba@2440:       }
deba@2440: 
deba@2440:     }; //class DeltaFilterMap
deba@2440: 
deba@2440:     typedef EdgeSubGraphAdaptor<const ResGraph, const DeltaFilterMap>
deba@2440:       DeltaResGraph;
deba@2440: 
deba@2440:     /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.
deba@2440:     class ResDijkstraTraits :
deba@2440:       public DijkstraDefaultTraits<DeltaResGraph, ReducedCostMap>
deba@2440:     {
deba@2440:     public:
deba@2440: 
deba@2440:       typedef PotentialUpdateMap DistMap;
deba@2440: 
deba@2440:       static DistMap *createDistMap(const DeltaResGraph&) {
deba@2440: 	return new DistMap();
deba@2440:       }
deba@2440: 
deba@2440:     }; //class ResDijkstraTraits
deba@2440: 
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:     /// \brief Map adaptor class for identifing deficit nodes.
deba@2440:     class DeficitBoolMap : public MapBase<ResNode, bool>
deba@2440:     {
deba@2440:     private:
deba@2440: 
deba@2440:       const SupplyRefMap &imb;
deba@2440: 
deba@2440:     public:
deba@2440: 
deba@2440:       DeficitBoolMap(const SupplyRefMap &_imb) : imb(_imb) {}
deba@2440: 
deba@2440:       bool operator[](const ResNode &n) const {
deba@2440: 	return imb[n] < 0;
deba@2440:       }
deba@2440: 
deba@2440:     }; //class DeficitBoolMap
deba@2440: 
deba@2440:     /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.
deba@2440:     class ResDijkstraTraits :
deba@2440:       public DijkstraDefaultTraits<ResGraph, ReducedCostMap>
deba@2440:     {
deba@2440:     public:
deba@2440: 
deba@2440:       typedef PotentialUpdateMap DistMap;
deba@2440: 
deba@2440:       static DistMap *createDistMap(const ResGraph&) {
deba@2440: 	return new DistMap();
deba@2440:       }
deba@2440: 
deba@2440:     }; //class ResDijkstraTraits
deba@2440: #endif
deba@2440: 
deba@2440:   protected:
deba@2440: 
deba@2440:     /// \brief The directed graph the algorithm runs on.
deba@2440:     const Graph &graph;
deba@2440:     /// \brief The original lower bound map.
deba@2440:     const LowerMap *lower;
deba@2440:     /// \brief The modified capacity map.
deba@2440:     CapacityRefMap capacity;
deba@2440:     /// \brief The cost map.
deba@2440:     const CostMap &cost;
deba@2440:     /// \brief The modified supply map.
deba@2440:     SupplyRefMap supply;
deba@2440:     /// \brief The sum of supply values equals zero.
deba@2440:     bool valid_supply;
deba@2440: 
deba@2440:     /// \brief The edge map of the current flow.
deba@2440:     FlowMap flow;
deba@2440:     /// \brief The potential node map.
deba@2440:     PotentialMap potential;
deba@2440:     /// \brief The residual graph.
deba@2440:     ResGraph res_graph;
deba@2440:     /// \brief The reduced cost map.
deba@2440:     ReducedCostMap red_cost;
deba@2440: 
deba@2440:     /// \brief The imbalance map.
deba@2440:     SupplyRefMap imbalance;
deba@2440:     /// \brief The excess nodes.
deba@2440:     std::vector<ResNode> excess_nodes;
deba@2440:     /// \brief The index of the next excess node.
deba@2440:     int next_node;
deba@2440: 
deba@2440: #ifdef WITH_SCALING
deba@2440:     typedef Dijkstra<DeltaResGraph, ReducedCostMap, ResDijkstraTraits>
deba@2440:       ResDijkstra;
deba@2440:     /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding
deba@2440:     /// shortest paths in the residual graph with respect to the
deba@2440:     /// reduced edge costs.
deba@2440:     ResDijkstra dijkstra;
deba@2440: 
deba@2440:     /// \brief The delta parameter used for capacity scaling.
deba@2440:     Capacity delta;
kpeter@2509:     /// \brief Edge filter map for filtering edges with at least
kpeter@2509:     /// \c delta residual capacity.
deba@2440:     DeltaFilterMap delta_filter;
kpeter@2509:     /// \brief The delta residual graph (i.e. the subgraph of the
kpeter@2509:     /// residual graph consisting of edges with at least \c delta
kpeter@2509:     /// residual capacity).
deba@2440:     DeltaResGraph dres_graph;
deba@2440:     /// \brief Map for identifing deficit nodes.
deba@2440:     DeficitBoolMap delta_deficit;
deba@2440: 
deba@2457:     /// \brief The deficit nodes.
deba@2457:     std::vector<ResNode> deficit_nodes;
deba@2457: 
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:     typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>
deba@2440:       ResDijkstra;
deba@2440:     /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding
deba@2440:     /// shortest paths in the residual graph with respect to the
deba@2440:     /// reduced edge costs.
deba@2440:     ResDijkstra dijkstra;
deba@2440:     /// \brief Map for identifing deficit nodes.
deba@2440:     DeficitBoolMap has_deficit;
deba@2440: #endif
deba@2440: 
deba@2440:     /// \brief Pred map for the \ref lemon::Dijkstra "Dijkstra" class.
deba@2440:     typename ResDijkstra::PredMap pred;
deba@2440:     /// \brief Dist map for the \ref lemon::Dijkstra "Dijkstra" class to
deba@2440:     /// update node potentials.
deba@2440:     PotentialUpdateMap updater;
deba@2440: 
deba@2440:   public :
deba@2440: 
deba@2440:     /// \brief General constructor of the class (with lower bounds).
deba@2440:     ///
deba@2440:     /// General constructor of the class (with lower bounds).
deba@2440:     ///
deba@2440:     /// \param _graph The directed graph the algorithm runs on.
deba@2440:     /// \param _lower The lower bounds of the edges.
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 _supply The supply values of the nodes (signed).
deba@2440:     CapacityScaling( const Graph &_graph,
deba@2440: 		     const LowerMap &_lower,
deba@2440: 		     const CapacityMap &_capacity,
deba@2440: 		     const CostMap &_cost,
deba@2440: 		     const SupplyMap &_supply ) :
deba@2440:       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
deba@2440:       supply(_graph), flow(_graph, 0), potential(_graph, 0),
deba@2440:       res_graph(_graph, capacity, flow),
deba@2440:       red_cost(res_graph, cost, potential), imbalance(_graph),
deba@2440: #ifdef WITH_SCALING
deba@2440:       delta(0), delta_filter(res_graph, delta),
deba@2440:       dres_graph(res_graph, delta_filter),
deba@2440:       dijkstra(dres_graph, red_cost), pred(dres_graph),
deba@2440:       delta_deficit(imbalance, delta)
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:       dijkstra(res_graph, red_cost), pred(res_graph),
deba@2440:       has_deficit(imbalance)
deba@2440: #endif
deba@2440:     {
deba@2440:       // Removing nonzero lower bounds
deba@2440:       capacity = subMap(_capacity, _lower);
deba@2440:       Supply sum = 0;
deba@2440:       for (NodeIt n(graph); n != INVALID; ++n) {
deba@2440: 	Supply s = _supply[n];
deba@2440: 	for (InEdgeIt e(graph, n); e != INVALID; ++e)
deba@2440: 	  s += _lower[e];
deba@2440: 	for (OutEdgeIt e(graph, n); e != INVALID; ++e)
deba@2440: 	  s -= _lower[e];
kpeter@2507: 	supply[n] = s;
deba@2440: 	sum += s;
deba@2440:       }
deba@2440:       valid_supply = sum == 0;
deba@2440:     }
deba@2440: 
deba@2440:     /// \brief General constructor of the class (without lower bounds).
deba@2440:     ///
deba@2440:     /// General constructor of the class (without lower bounds).
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 _supply The supply values of the nodes (signed).
deba@2440:     CapacityScaling( const Graph &_graph,
deba@2440: 		     const CapacityMap &_capacity,
deba@2440: 		     const CostMap &_cost,
deba@2440: 		     const SupplyMap &_supply ) :
deba@2440:       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
deba@2440:       supply(_supply), flow(_graph, 0), potential(_graph, 0),
deba@2440:       res_graph(_graph, capacity, flow),
deba@2440:       red_cost(res_graph, cost, potential), imbalance(_graph),
deba@2440: #ifdef WITH_SCALING
deba@2440:       delta(0), delta_filter(res_graph, delta),
deba@2440:       dres_graph(res_graph, delta_filter),
deba@2440:       dijkstra(dres_graph, red_cost), pred(dres_graph),
deba@2440:       delta_deficit(imbalance, delta)
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:       dijkstra(res_graph, red_cost), pred(res_graph),
deba@2440:       has_deficit(imbalance)
deba@2440: #endif
deba@2440:     {
deba@2440:       // Checking the sum of supply values
deba@2440:       Supply sum = 0;
deba@2440:       for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
deba@2440:       valid_supply = sum == 0;
deba@2440:     }
deba@2440: 
deba@2440:     /// \brief Simple constructor of the class (with lower bounds).
deba@2440:     ///
deba@2440:     /// Simple constructor of the class (with lower bounds).
deba@2440:     ///
deba@2440:     /// \param _graph The directed graph the algorithm runs on.
deba@2440:     /// \param _lower The lower bounds of the edges.
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:     /// \param _flow_value The required amount of flow from node \c _s
deba@2440:     /// to node \c _t (i.e. the supply of \c _s and the demand of
deba@2440:     /// \c _t).
deba@2440:     CapacityScaling( const Graph &_graph,
deba@2440: 		     const LowerMap &_lower,
deba@2440: 		     const CapacityMap &_capacity,
deba@2440: 		     const CostMap &_cost,
deba@2440: 		     Node _s, Node _t,
deba@2440: 		     Supply _flow_value ) :
deba@2440:       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
deba@2440:       supply(_graph), flow(_graph, 0), potential(_graph, 0),
deba@2440:       res_graph(_graph, capacity, flow),
deba@2440:       red_cost(res_graph, cost, potential), imbalance(_graph),
deba@2440: #ifdef WITH_SCALING
deba@2440:       delta(0), delta_filter(res_graph, delta),
deba@2440:       dres_graph(res_graph, delta_filter),
deba@2440:       dijkstra(dres_graph, red_cost), pred(dres_graph),
deba@2440:       delta_deficit(imbalance, delta)
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:       dijkstra(res_graph, red_cost), pred(res_graph),
deba@2440:       has_deficit(imbalance)
deba@2440: #endif
deba@2440:     {
deba@2440:       // Removing nonzero lower bounds
deba@2440:       capacity = subMap(_capacity, _lower);
deba@2440:       for (NodeIt n(graph); n != INVALID; ++n) {
deba@2440: 	Supply s = 0;
deba@2440: 	if (n == _s) s =  _flow_value;
deba@2440: 	if (n == _t) s = -_flow_value;
deba@2440: 	for (InEdgeIt e(graph, n); e != INVALID; ++e)
deba@2440: 	  s += _lower[e];
deba@2440: 	for (OutEdgeIt e(graph, n); e != INVALID; ++e)
deba@2440: 	  s -= _lower[e];
kpeter@2507: 	supply[n] = s;
deba@2440:       }
deba@2440:       valid_supply = true;
deba@2440:     }
deba@2440: 
deba@2440:     /// \brief Simple constructor of the class (without lower bounds).
deba@2440:     ///
deba@2440:     /// Simple constructor of the class (without lower bounds).
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:     /// \param _flow_value The required amount of flow from node \c _s
deba@2440:     /// to node \c _t (i.e. the supply of \c _s and the demand of
deba@2440:     /// \c _t).
deba@2440:     CapacityScaling( const Graph &_graph,
deba@2440: 		     const CapacityMap &_capacity,
deba@2440: 		     const CostMap &_cost,
deba@2440: 		     Node _s, Node _t,
deba@2440: 		     Supply _flow_value ) :
deba@2440:       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
deba@2440:       supply(_graph, 0), flow(_graph, 0), potential(_graph, 0),
deba@2440:       res_graph(_graph, capacity, flow),
deba@2440:       red_cost(res_graph, cost, potential), imbalance(_graph),
deba@2440: #ifdef WITH_SCALING
deba@2440:       delta(0), delta_filter(res_graph, delta),
deba@2440:       dres_graph(res_graph, delta_filter),
deba@2440:       dijkstra(dres_graph, red_cost), pred(dres_graph),
deba@2440:       delta_deficit(imbalance, delta)
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:       dijkstra(res_graph, red_cost), pred(res_graph),
deba@2440:       has_deficit(imbalance)
deba@2440: #endif
deba@2440:     {
deba@2440:       supply[_s] =  _flow_value;
deba@2440:       supply[_t] = -_flow_value;
deba@2440:       valid_supply = true;
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 a const reference to the potential map (the dual
deba@2440:     /// solution).
deba@2440:     ///
deba@2440:     /// Returns a const reference to the potential map (the dual
deba@2440:     /// solution).
deba@2440:     ///
deba@2440:     /// \pre \ref run() must be called before using this function.
deba@2440:     const PotentialMap& potentialMap() const {
deba@2440:       return potential;
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@2457:     /// \brief Runs the algorithm.
deba@2440:     ///
deba@2457:     /// Runs the algorithm.
deba@2440:     ///
deba@2440:     /// \return \c true if a feasible flow can be found.
deba@2440:     bool run() {
deba@2440:       return init() && start();
deba@2440:     }
deba@2440: 
deba@2440:   protected:
deba@2440: 
deba@2440:     /// \brief Initializes the algorithm.
deba@2440:     bool init() {
deba@2440:       if (!valid_supply) return false;
kpeter@2507:       imbalance = supply;
deba@2440: 
deba@2440:       // Initalizing Dijkstra class
deba@2440:       updater.potentialMap(potential);
deba@2440:       dijkstra.distMap(updater).predMap(pred);
deba@2440: 
deba@2440: #ifdef WITH_SCALING
deba@2440:       // Initilaizing delta value
deba@2457:       Supply max_sup = 0, max_dem = 0;
deba@2457:       for (NodeIt n(graph); n != INVALID; ++n) {
deba@2457: 	if (supply[n] >  max_sup) max_sup =  supply[n];
deba@2457: 	if (supply[n] < -max_dem) max_dem = -supply[n];
deba@2440:       }
deba@2457:       if (max_dem < max_sup) max_sup = max_dem;
kpeter@2471:       for ( delta = 1; SCALING_FACTOR * delta < max_sup;
kpeter@2471: 	    delta *= SCALING_FACTOR ) ;
deba@2440: #endif
deba@2440:       return true;
deba@2440:     }
deba@2440: 
deba@2440: #ifdef WITH_SCALING
deba@2440:     /// \brief Executes the capacity scaling version of the successive
deba@2440:     /// shortest path algorithm.
deba@2440:     bool start() {
deba@2440:       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
deba@2440:       typedef typename DeltaResGraph::Edge DeltaResEdge;
deba@2457: #ifdef _DEBUG_ITER_
deba@2457:       int dijk_num = 0;
deba@2457: #endif
deba@2440: 
deba@2440:       // Processing capacity scaling phases
deba@2440:       ResNode s, t;
kpeter@2471:       for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ?
kpeter@2471: 				  1 : delta / SCALING_FACTOR )
deba@2440:       {
deba@2440: 	// Saturating edges not satisfying the optimality condition
deba@2440: 	Capacity r;
deba@2440: 	for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {
deba@2440: 	  if (red_cost[e] < 0) {
deba@2440: 	    res_graph.augment(e, r = res_graph.rescap(e));
kpeter@2509: 	    imbalance[dres_graph.source(e)] -= r;
deba@2440: 	    imbalance[dres_graph.target(e)] += r;
deba@2440: 	  }
deba@2440: 	}
deba@2440: 
deba@2440: 	// Finding excess nodes
deba@2440: 	excess_nodes.clear();
deba@2457: 	deficit_nodes.clear();
deba@2440: 	for (ResNodeIt n(res_graph); n != INVALID; ++n) {
deba@2457: 	  if (imbalance[n] >=  delta) excess_nodes.push_back(n);
deba@2457: 	  if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
deba@2440: 	}
deba@2440: 	next_node = 0;
deba@2440: 
deba@2457: 	// Finding shortest paths
deba@2440: 	while (next_node < excess_nodes.size()) {
deba@2457: 	  // Checking deficit nodes
deba@2457: 	  if (delta > 1) {
deba@2457: 	    bool delta_def = false;
deba@2457: 	    for (int i = 0; i < deficit_nodes.size(); ++i) {
deba@2457: 	      if (imbalance[deficit_nodes[i]] <= -delta) {
deba@2457: 		delta_def = true;
deba@2457: 		break;
deba@2457: 	      }
deba@2457: 	    }
deba@2457: 	    if (!delta_def) break;
deba@2457: 	  }
deba@2457: 
deba@2440: 	  // Running Dijkstra
deba@2440: 	  s = excess_nodes[next_node];
deba@2440: 	  updater.init();
deba@2440: 	  dijkstra.init();
deba@2440: 	  dijkstra.addSource(s);
deba@2457: #ifdef _DEBUG_ITER_
deba@2457: 	  ++dijk_num;
deba@2457: #endif
deba@2440: 	  if ((t = dijkstra.start(delta_deficit)) == INVALID) {
deba@2440: 	    if (delta > 1) {
deba@2440: 	      ++next_node;
deba@2440: 	      continue;
deba@2440: 	    }
deba@2440: 	    return false;
deba@2440: 	  }
deba@2440: 
deba@2440: 	  // Updating node potentials
deba@2440: 	  updater.update();
deba@2440: 
deba@2440: 	  // Augment along a shortest path from s to t
deba@2440: 	  Capacity d = imbalance[s] < -imbalance[t] ?
deba@2440: 	    imbalance[s] : -imbalance[t];
deba@2440: 	  ResNode u = t;
deba@2440: 	  ResEdge e;
deba@2440: 	  if (d > delta) {
deba@2440: 	    while ((e = pred[u]) != INVALID) {
deba@2440: 	      if (res_graph.rescap(e) < d) d = res_graph.rescap(e);
deba@2440: 	      u = dres_graph.source(e);
deba@2440: 	    }
deba@2440: 	  }
deba@2440: 	  u = t;
deba@2440: 	  while ((e = pred[u]) != INVALID) {
deba@2440: 	    res_graph.augment(e, d);
deba@2440: 	    u = dres_graph.source(e);
deba@2440: 	  }
deba@2440: 	  imbalance[s] -= d;
deba@2440: 	  imbalance[t] += d;
deba@2440: 	  if (imbalance[s] < delta) ++next_node;
deba@2440: 	}
deba@2440:       }
deba@2457: #ifdef _DEBUG_ITER_
deba@2457:       std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
deba@2457: 	<< dijk_num << " times." << std::endl;
deba@2457: #endif
deba@2440: 
deba@2440:       // Handling nonzero lower bounds
deba@2440:       if (lower) {
deba@2440: 	for (EdgeIt e(graph); e != INVALID; ++e)
deba@2440: 	  flow[e] += (*lower)[e];
deba@2440:       }
deba@2440:       return true;
deba@2440:     }
deba@2440: 
deba@2440: #else //WITHOUT_CAPACITY_SCALING
deba@2440:     /// \brief Executes the successive shortest path algorithm without
deba@2440:     /// capacity scaling.
deba@2440:     bool start() {
deba@2440:       // Finding excess nodes
deba@2440:       for (ResNodeIt n(res_graph); n != INVALID; ++n) {
deba@2440: 	if (imbalance[n] > 0) excess_nodes.push_back(n);
deba@2440:       }
deba@2440:       if (excess_nodes.size() == 0) return true;
deba@2440:       next_node = 0;
deba@2440: 
deba@2457:       // Finding shortest paths
deba@2440:       ResNode s, t;
deba@2440:       while ( imbalance[excess_nodes[next_node]] > 0 ||
deba@2440: 	      ++next_node < excess_nodes.size() )
deba@2440:       {
deba@2440: 	// Running Dijkstra
deba@2440: 	s = excess_nodes[next_node];
deba@2440: 	updater.init();
deba@2440: 	dijkstra.init();
deba@2440: 	dijkstra.addSource(s);
deba@2440: 	if ((t = dijkstra.start(has_deficit)) == INVALID)
deba@2440: 	  return false;
deba@2440: 
deba@2440: 	// Updating node potentials
deba@2440: 	updater.update();
deba@2440: 
deba@2440: 	// Augmenting along a shortest path from s to t
deba@2440: 	Capacity delta = imbalance[s] < -imbalance[t] ?
deba@2440: 	  imbalance[s] : -imbalance[t];
deba@2440: 	ResNode u = t;
deba@2440: 	ResEdge e;
deba@2440: 	while ((e = pred[u]) != INVALID) {
deba@2440: 	  if (res_graph.rescap(e) < delta) delta = res_graph.rescap(e);
deba@2440: 	  u = res_graph.source(e);
deba@2440: 	}
deba@2440: 	u = t;
deba@2440: 	while ((e = pred[u]) != INVALID) {
deba@2440: 	  res_graph.augment(e, delta);
deba@2440: 	  u = res_graph.source(e);
deba@2440: 	}
deba@2440: 	imbalance[s] -= delta;
deba@2440: 	imbalance[t] += delta;
deba@2440:       }
deba@2440: 
deba@2440:       // Handling nonzero lower bounds
deba@2440:       if (lower) {
deba@2440: 	for (EdgeIt e(graph); e != INVALID; ++e)
deba@2440: 	  flow[e] += (*lower)[e];
deba@2440:       }
deba@2440:       return true;
deba@2440:     }
deba@2440: #endif
deba@2440: 
deba@2440:   }; //class CapacityScaling
deba@2440: 
deba@2440:   ///@}
deba@2440: 
deba@2440: } //namespace lemon
deba@2440: 
deba@2440: #endif //LEMON_CAPACITY_SCALING_H