/* -*- C++ -*- * src/lemon/min_cost_flow.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Combinatorial Optimization Research Group, 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_FLOW_H #define LEMON_MIN_COST_FLOW_H ///\ingroup flowalgs ///\file ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost #include #include #include #include namespace lemon { /// \addtogroup flowalgs /// @{ ///\brief Implementation of an algorithm for finding a flow of value \c k ///(for small values of \c k) having minimal total cost between 2 nodes /// /// /// The class \ref lemon::MinCostFlow "MinCostFlow" implements /// an algorithm for finding a flow of value \c k /// having minimal total cost /// from a given source node to a given target node in an /// edge-weighted directed graph. To this end, /// the edge-capacities and edge-weitghs have to be nonnegative. /// The edge-capacities should be integers, but the edge-weights can be /// integers, reals or of other comparable numeric type. /// This algorithm is intended to use only for small values of \c k, /// since it is only polynomial in k, /// not in the length of k (which is log k). /// In order to find the minimum cost flow of value \c k it /// finds the minimum cost flow of value \c i for every /// \c i between 0 and \c k. /// ///\param Graph The directed graph type the algorithm runs on. ///\param LengthMap The type of the length map. ///\param CapacityMap The capacity map type. /// ///\author Attila Bernath template class MinCostFlow { typedef typename LengthMap::ValueType Length; //Warning: this should be integer type typedef typename CapacityMap::ValueType Capacity; typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt OutEdgeIt; typedef typename Graph::template EdgeMap EdgeIntMap; typedef ResGraphWrapper ResGW; typedef typename ResGW::Edge ResGraphEdge; class ModLengthMap { typedef typename Graph::template NodeMap NodeMap; const ResGW& G; const LengthMap &ol; const NodeMap &pot; public : typedef typename LengthMap::KeyType KeyType; typedef typename LengthMap::ValueType ValueType; ValueType operator[](typename ResGW::Edge e) const { if (G.forward(e)) return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); else return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); } ModLengthMap(const ResGW& _G, const LengthMap &o, const NodeMap &p) : G(_G), /*rev(_rev),*/ ol(o), pot(p){}; };//ModLengthMap protected: //Input const Graph& G; const LengthMap& length; const CapacityMap& capacity; //auxiliary variables //To store the flow EdgeIntMap flow; //To store the potential (dual variables) typedef typename Graph::template NodeMap PotentialMap; PotentialMap potential; Length total_length; public : /// The constructor of the class. ///\param _G The directed graph the algorithm runs on. ///\param _length The length (weight or cost) of the edges. ///\param _cap The capacity of the edges. MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), length(_length), capacity(_cap), flow(_G), potential(_G){ } ///Runs the algorithm. ///Runs the algorithm. ///Returns k if there is a flow of value at least k edge-disjoint ///from s to t. ///Otherwise it returns the maximum value of a flow from s to t. /// ///\param s The source node. ///\param t The target node. ///\param k The value of the flow we are looking for. /// ///\todo May be it does make sense to be able to start with a nonzero /// feasible primal-dual solution pair as well. int run(Node s, Node t, int k) { //Resetting variables from previous runs total_length = 0; for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0); //Initialize the potential to zero for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0); //We need a residual graph ResGW res_graph(G, capacity, flow); ModLengthMap mod_length(res_graph, length, potential); Dijkstra dijkstra(res_graph, mod_length); int i; for (i=0; i 0 && fl_e != 0) return false; if (mod_pot < 0 && fl_e != capacity[e]) return false; } } return true; } }; //class MinCostFlow ///@} } //namespace lemon #endif //LEMON_MIN_COST_FLOW_H