Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

min_cost_flow.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/min_cost_flow.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_MIN_COST_FLOW_H
00018 #define LEMON_MIN_COST_FLOW_H
00019 
00023 
00024 
00025 #include <lemon/dijkstra.h>
00026 #include <lemon/graph_wrapper.h>
00027 #include <lemon/maps.h>
00028 #include <vector>
00029 
00030 namespace lemon {
00031 
00034 
00059   template <typename Graph, typename LengthMap, typename CapacityMap>
00060   class MinCostFlow {
00061 
00062     typedef typename LengthMap::Value Length;
00063 
00064     //Warning: this should be integer type
00065     typedef typename CapacityMap::Value Capacity;
00066     
00067     typedef typename Graph::Node Node;
00068     typedef typename Graph::NodeIt NodeIt;
00069     typedef typename Graph::Edge Edge;
00070     typedef typename Graph::OutEdgeIt OutEdgeIt;
00071     typedef typename Graph::template EdgeMap<int> EdgeIntMap;
00072 
00073     typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
00074     typedef typename ResGW::Edge ResGraphEdge;
00075 
00076   protected:
00077 
00078     const Graph& g;
00079     const LengthMap& length;
00080     const CapacityMap& capacity;
00081 
00082     EdgeIntMap flow; 
00083     typedef typename Graph::template NodeMap<Length> PotentialMap;
00084     PotentialMap potential;
00085 
00086     Node s;
00087     Node t;
00088     
00089     Length total_length;
00090 
00091     class ModLengthMap {   
00092       typedef typename Graph::template NodeMap<Length> NodeMap;
00093       const ResGW& g;
00094       const LengthMap &length;
00095       const NodeMap &pot;
00096     public :
00097       typedef typename LengthMap::Key Key;
00098       typedef typename LengthMap::Value Value;
00099 
00100       ModLengthMap(const ResGW& _g, 
00101                    const LengthMap &_length, const NodeMap &_pot) : 
00102         g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { }
00103         
00104       Value operator[](typename ResGW::Edge e) const {     
00105         if (g.forward(e))
00106           return  length[e]-(pot[g.target(e)]-pot[g.source(e)]);   
00107         else
00108           return -length[e]-(pot[g.target(e)]-pot[g.source(e)]);   
00109       }     
00110         
00111     }; //ModLengthMap
00112 
00113     ResGW res_graph;
00114     ModLengthMap mod_length;
00115     Dijkstra<ResGW, ModLengthMap> dijkstra;
00116 
00117   public :
00118 
00127     MinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap, 
00128                 Node _s, Node _t) : 
00129       g(_g), length(_length), capacity(_cap), flow(_g), potential(_g), 
00130       s(_s), t(_t), 
00131       res_graph(g, capacity, flow), 
00132       mod_length(res_graph, length, potential),
00133       dijkstra(res_graph, mod_length) { 
00134       reset();
00135       }
00136 
00140     bool augment() {
00141       dijkstra.run(s);
00142       if (!dijkstra.reached(t)) {
00143 
00144         //Unsuccessful augmentation.
00145         return false;
00146       } else {
00147 
00148         //We have to change the potential
00149         for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
00150           potential.set(n, potential[n]+dijkstra.distMap()[n]);
00151         
00152         //Augmenting on the sortest path
00153         Node n=t;
00154         ResGraphEdge e;
00155         while (n!=s){
00156           e = dijkstra.pred(n);
00157           n = dijkstra.predNode(n);
00158           res_graph.augment(e,1);
00159           //Let's update the total length
00160           if (res_graph.forward(e))
00161             total_length += length[e];
00162           else 
00163             total_length -= length[e];      
00164         }
00165 
00166         return true;
00167       }
00168     }
00169     
00184     int run(int k) {
00185       if (flowValue()>k) reset();
00186       while (flowValue()<k && augment()) { }
00187       return flowValue();
00188     }
00189 
00193     void reset() {
00194       total_length=0;
00195       for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
00196       for (typename Graph::NodeIt n(g); n!=INVALID; ++n) potential.set(n, 0);  
00197     }
00198 
00201     int flowValue() const {
00202       int i=0;
00203       for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e];
00204       for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e];
00205       return i;
00206     }
00207 
00209 
00211     Length totalLength(){
00212       return total_length;
00213     }
00214 
00216 
00218     const EdgeIntMap &getFlow() const { return flow;}
00219 
00224     const PotentialMap &getPotential() const { return potential;}
00225 
00233     bool checkComplementarySlackness(){
00234       Length mod_pot;
00235       Length fl_e;
00236         for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
00237         //C^{\Pi}_{i,j}
00238         mod_pot = length[e]-potential[g.target(e)]+potential[g.source(e)];
00239         fl_e = flow[e];
00240         if (0<fl_e && fl_e<capacity[e]) {
00243           if (mod_pot != 0)
00244             return false;
00245         } 
00246         else {
00247           if (mod_pot > 0 && fl_e != 0)
00248             return false;
00249           if (mod_pot < 0 && fl_e != capacity[e])
00250             return false;
00251         }
00252       }
00253       return true;
00254     }
00255     
00256   }; //class MinCostFlow
00257 
00259 
00260 } //namespace lemon
00261 
00262 #endif //LEMON_MIN_COST_FLOW_H

Generated on Mon Feb 21 15:02:22 2005 for LEMON by  doxygen 1.4.1