69 typedef typename Graph::Edge Edge; |
69 typedef typename Graph::Edge Edge; |
70 typedef typename Graph::OutEdgeIt OutEdgeIt; |
70 typedef typename Graph::OutEdgeIt OutEdgeIt; |
71 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
71 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
72 |
72 |
73 |
73 |
74 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType; |
74 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW; |
75 typedef typename ResGraphType::Edge ResGraphEdge; |
75 typedef typename ResGW::Edge ResGraphEdge; |
76 |
76 |
77 class ModLengthMap { |
77 class ModLengthMap { |
78 typedef typename Graph::template NodeMap<Length> NodeMap; |
78 typedef typename Graph::template NodeMap<Length> NodeMap; |
79 const ResGraphType& G; |
79 const ResGW& G; |
80 const LengthMap &ol; |
80 const LengthMap &ol; |
81 const NodeMap &pot; |
81 const NodeMap &pot; |
82 public : |
82 public : |
83 typedef typename LengthMap::KeyType KeyType; |
83 typedef typename LengthMap::KeyType KeyType; |
84 typedef typename LengthMap::ValueType ValueType; |
84 typedef typename LengthMap::ValueType ValueType; |
85 |
85 |
86 ValueType operator[](typename ResGraphType::Edge e) const { |
86 ValueType operator[](typename ResGW::Edge e) const { |
87 if (G.forward(e)) |
87 if (G.forward(e)) |
88 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
88 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
89 else |
89 else |
90 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
90 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
91 } |
91 } |
92 |
92 |
93 ModLengthMap(const ResGraphType& _G, |
93 ModLengthMap(const ResGW& _G, |
94 const LengthMap &o, const NodeMap &p) : |
94 const LengthMap &o, const NodeMap &p) : |
95 G(_G), /*rev(_rev),*/ ol(o), pot(p){}; |
95 G(_G), /*rev(_rev),*/ ol(o), pot(p){}; |
96 };//ModLengthMap |
96 };//ModLengthMap |
97 |
97 |
98 |
98 |
150 //Initialize the potential to zero |
150 //Initialize the potential to zero |
151 for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0); |
151 for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0); |
152 |
152 |
153 |
153 |
154 //We need a residual graph |
154 //We need a residual graph |
155 ResGraphType res_graph(G, capacity, flow); |
155 ResGW res_graph(G, capacity, flow); |
156 |
156 |
157 |
157 |
158 ModLengthMap mod_length(res_graph, length, potential); |
158 ModLengthMap mod_length(res_graph, length, potential); |
159 |
159 |
160 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
160 Dijkstra<ResGW, ModLengthMap> dijkstra(res_graph, mod_length); |
161 |
161 |
162 int i; |
162 int i; |
163 for (i=0; i<k; ++i){ |
163 for (i=0; i<k; ++i){ |
164 dijkstra.run(s); |
164 dijkstra.run(s); |
165 if (!dijkstra.reached(t)){ |
165 if (!dijkstra.reached(t)){ |
166 //There are no flow of value k from s to t |
166 //There are no flow of value k from s to t |
167 break; |
167 break; |
168 }; |
168 }; |
169 |
169 |
170 //We have to change the potential |
170 //We have to change the potential |
171 for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n) |
171 for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n) |
172 potential[n] += dijkstra.distMap()[n]; |
172 potential[n] += dijkstra.distMap()[n]; |
173 |
173 |
174 |
174 |
175 //Augmenting on the sortest path |
175 //Augmenting on the sortest path |
176 Node n=t; |
176 Node n=t; |