deba@2276: /* -*- C++ -*- deba@2276: * deba@2276: * This file is a part of LEMON, a generic C++ optimization library deba@2276: * deba@2276: * Copyright (C) 2003-2006 deba@2276: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2276: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2276: * deba@2276: * Permission to use, modify and distribute this software is granted deba@2276: * provided that this copyright notice appears in all copies. For deba@2276: * precise terms see the accompanying LICENSE file. deba@2276: * deba@2276: * This software is provided "AS IS" with no warranty of any kind, deba@2276: * express or implied, and with no claim as to its suitability for any deba@2276: * purpose. deba@2276: * deba@2276: */ deba@2276: deba@2276: #ifndef LEMON_MIN_COST_FLOW_H deba@2276: #define LEMON_MIN_COST_FLOW_H deba@2276: deba@2276: ///\ingroup flowalgs deba@2276: /// deba@2276: ///\file \brief An algorithm for finding a flow of value \c k (for deba@2276: ///small values of \c k) having minimal total cost deba@2276: deba@2276: deba@2276: #include deba@2276: #include deba@2276: #include deba@2276: #include deba@2276: deba@2276: namespace lemon { deba@2276: deba@2276: /// \addtogroup flowalgs deba@2276: /// @{ deba@2276: deba@2276: /// \brief Implementation of an algorithm for finding a flow of deba@2276: /// value \c k (for small values of \c k) having minimal total cost deba@2276: /// between two nodes deba@2276: /// deba@2276: /// deba@2276: /// The \ref lemon::SspMinCostFlow "Successive Shortest Path Minimum deba@2276: /// Cost Flow" implements an algorithm for finding a flow of value deba@2276: /// \c k having minimal total cost from a given source node to a deba@2276: /// given target node in a directed graph with a cost function on deba@2276: /// the edges. To this end, the edge-capacities and edge-costs have deba@2276: /// to be nonnegative. The edge-capacities should be integers, but deba@2276: /// the edge-costs can be integers, reals or of other comparable deba@2276: /// numeric type. This algorithm is intended to be used only for deba@2276: /// small values of \c k, since it is only polynomial in k, not in deba@2276: /// the length of k (which is log k): in order to find the minimum deba@2276: /// cost flow of value \c k it finds the minimum cost flow of value deba@2276: /// \c i for every \c i between 0 and \c k. deba@2276: /// deba@2276: ///\param Graph The directed graph type the algorithm runs on. deba@2276: ///\param LengthMap The type of the length map. deba@2276: ///\param CapacityMap The capacity map type. deba@2276: /// deba@2276: ///\author Attila Bernath deba@2276: template deba@2276: class SspMinCostFlow { deba@2276: deba@2276: typedef typename LengthMap::Value Length; deba@2276: deba@2276: //Warning: this should be integer type deba@2276: typedef typename CapacityMap::Value Capacity; deba@2276: deba@2276: typedef typename Graph::Node Node; deba@2276: typedef typename Graph::NodeIt NodeIt; deba@2276: typedef typename Graph::Edge Edge; deba@2276: typedef typename Graph::OutEdgeIt OutEdgeIt; deba@2276: typedef typename Graph::template EdgeMap EdgeIntMap; deba@2276: deba@2276: typedef ResGraphAdaptor ResGW; deba@2276: typedef typename ResGW::Edge ResGraphEdge; deba@2276: deba@2276: protected: deba@2276: deba@2276: const Graph& g; deba@2276: const LengthMap& length; deba@2276: const CapacityMap& capacity; deba@2276: deba@2276: EdgeIntMap flow; deba@2276: typedef typename Graph::template NodeMap PotentialMap; deba@2276: PotentialMap potential; deba@2276: deba@2276: Node s; deba@2276: Node t; deba@2276: deba@2276: Length total_length; deba@2276: deba@2276: class ModLengthMap { deba@2276: typedef typename Graph::template NodeMap NodeMap; deba@2276: const ResGW& g; deba@2276: const LengthMap &length; deba@2276: const NodeMap &pot; deba@2276: public : deba@2276: typedef typename LengthMap::Key Key; deba@2276: typedef typename LengthMap::Value Value; deba@2276: deba@2276: ModLengthMap(const ResGW& _g, deba@2276: const LengthMap &_length, const NodeMap &_pot) : deba@2276: g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { } deba@2276: deba@2276: Value operator[](typename ResGW::Edge e) const { deba@2276: if (g.forward(e)) deba@2276: return length[e]-(pot[g.target(e)]-pot[g.source(e)]); deba@2276: else deba@2276: return -length[e]-(pot[g.target(e)]-pot[g.source(e)]); deba@2276: } deba@2276: deba@2276: }; //ModLengthMap deba@2276: deba@2276: ResGW res_graph; deba@2276: ModLengthMap mod_length; deba@2276: Dijkstra dijkstra; deba@2276: deba@2276: public : deba@2276: deba@2276: /// \brief The constructor of the class. deba@2276: /// deba@2276: /// \param _g The directed graph the algorithm runs on. deba@2276: /// \param _length The length (cost) of the edges. deba@2276: /// \param _cap The capacity of the edges. deba@2276: /// \param _s Source node. deba@2276: /// \param _t Target node. deba@2276: SspMinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap, deba@2276: Node _s, Node _t) : deba@2276: g(_g), length(_length), capacity(_cap), flow(_g), potential(_g), deba@2276: s(_s), t(_t), deba@2276: res_graph(g, capacity, flow), deba@2276: mod_length(res_graph, length, potential), deba@2276: dijkstra(res_graph, mod_length) { deba@2276: reset(); deba@2276: } deba@2276: deba@2276: /// \brief Tries to augment the flow between s and t by 1. The deba@2276: /// return value shows if the augmentation is successful. deba@2276: bool augment() { deba@2276: dijkstra.run(s); deba@2276: if (!dijkstra.reached(t)) { deba@2276: deba@2276: //Unsuccessful augmentation. deba@2276: return false; deba@2276: } else { deba@2276: deba@2276: //We have to change the potential deba@2276: for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n) deba@2276: potential.set(n, potential[n]+dijkstra.distMap()[n]); deba@2276: deba@2276: //Augmenting on the shortest path deba@2276: Node n=t; deba@2276: ResGraphEdge e; deba@2276: while (n!=s){ deba@2276: e = dijkstra.predEdge(n); deba@2276: n = dijkstra.predNode(n); deba@2276: res_graph.augment(e,1); deba@2276: //Let's update the total length deba@2276: if (res_graph.forward(e)) deba@2276: total_length += length[e]; deba@2276: else deba@2276: total_length -= length[e]; deba@2276: } deba@2276: deba@2276: return true; deba@2276: } deba@2276: } deba@2276: deba@2276: /// \brief Runs the algorithm. deba@2276: /// deba@2276: /// Runs the algorithm. deba@2276: /// Returns k if there is a flow of value at least k from s to t. deba@2276: /// Otherwise it returns the maximum value of a flow from s to t. deba@2276: /// deba@2276: /// \param k The value of the flow we are looking for. deba@2276: /// deba@2276: /// \todo May be it does make sense to be able to start with a deba@2276: /// nonzero feasible primal-dual solution pair as well. deba@2276: /// deba@2276: /// \todo If the actual flow value is bigger than k, then deba@2276: /// everything is cleared and the algorithm starts from zero deba@2276: /// flow. Is it a good approach? deba@2276: int run(int k) { deba@2276: if (flowValue()>k) reset(); deba@2276: while (flowValue() 0 && fl_e != 0) deba@2276: return false; deba@2276: if (mod_pot < 0 && fl_e != capacity[e]) deba@2276: return false; deba@2276: } deba@2276: } deba@2276: return true; deba@2276: } deba@2276: deba@2276: }; //class SspMinCostFlow deba@2276: deba@2276: ///@} deba@2276: deba@2276: } //namespace lemon deba@2276: deba@2276: #endif //LEMON_MIN_COST_FLOW_H