00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_MIN_COST_FLOW_H
00020 #define LEMON_MIN_COST_FLOW_H
00021
00025
00026
00027 #include <lemon/dijkstra.h>
00028 #include <lemon/graph_adaptor.h>
00029 #include <lemon/maps.h>
00030 #include <vector>
00031
00032 namespace lemon {
00033
00036
00059 template <typename Graph, typename LengthMap, typename CapacityMap>
00060 class MinCostFlow {
00061
00062 typedef typename LengthMap::Value Length;
00063
00064
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 ResGraphAdaptor<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), 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 };
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
00145 return false;
00146 } else {
00147
00148
00149 for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
00150 potential.set(n, potential[n]+dijkstra.distMap()[n]);
00151
00152
00153 Node n=t;
00154 ResGraphEdge e;
00155 while (n!=s){
00156 e = dijkstra.predEdge(n);
00157 n = dijkstra.predNode(n);
00158 res_graph.augment(e,1);
00159
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
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 };
00257
00259
00260 }
00261
00262 #endif //LEMON_MIN_COST_FLOW_H