|
marci@301
|
1 |
// -*- c++ -*-
|
|
marci@301
|
2 |
#ifndef HUGO_EDMONDS_KARP_H
|
|
marci@301
|
3 |
#define HUGO_EDMONDS_KARP_H
|
|
marci@301
|
4 |
|
|
marci@301
|
5 |
#include <algorithm>
|
|
marci@301
|
6 |
#include <list>
|
|
marci@301
|
7 |
#include <iterator>
|
|
marci@301
|
8 |
|
|
marci@301
|
9 |
#include <bfs_iterator.h>
|
|
marci@301
|
10 |
#include <invalid.h>
|
|
marci@303
|
11 |
#include <graph_wrapper.h>
|
|
marci@311
|
12 |
#include <maps.h>
|
|
marci@301
|
13 |
|
|
marci@301
|
14 |
namespace hugo {
|
|
marci@301
|
15 |
|
|
marci@330
|
16 |
// template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
|
|
marci@330
|
17 |
// class ResGraph {
|
|
marci@330
|
18 |
// public:
|
|
marci@330
|
19 |
// typedef typename Graph::Node Node;
|
|
marci@330
|
20 |
// typedef typename Graph::NodeIt NodeIt;
|
|
marci@330
|
21 |
// private:
|
|
marci@330
|
22 |
// typedef typename Graph::SymEdgeIt OldSymEdgeIt;
|
|
marci@330
|
23 |
// const Graph& G;
|
|
marci@330
|
24 |
// const CapacityMap& capacity;
|
|
marci@330
|
25 |
// FlowMap& flow;
|
|
marci@330
|
26 |
// public:
|
|
marci@330
|
27 |
// ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :
|
|
marci@330
|
28 |
// G(_G), capacity(_capacity), flow(_flow) { }
|
|
marci@301
|
29 |
|
|
marci@330
|
30 |
// class Edge;
|
|
marci@330
|
31 |
// class OutEdgeIt;
|
|
marci@330
|
32 |
// friend class Edge;
|
|
marci@330
|
33 |
// friend class OutEdgeIt;
|
|
marci@301
|
34 |
|
|
marci@330
|
35 |
// class Edge {
|
|
marci@330
|
36 |
// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
|
|
marci@330
|
37 |
// protected:
|
|
marci@330
|
38 |
// const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
|
|
marci@330
|
39 |
// OldSymEdgeIt sym;
|
|
marci@330
|
40 |
// public:
|
|
marci@330
|
41 |
// Edge() { }
|
|
marci@330
|
42 |
// //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
|
|
marci@330
|
43 |
// Number free() const {
|
|
marci@330
|
44 |
// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
|
|
marci@330
|
45 |
// return (resG->capacity.get(sym)-resG->flow.get(sym));
|
|
marci@330
|
46 |
// } else {
|
|
marci@330
|
47 |
// return (resG->flow.get(sym));
|
|
marci@330
|
48 |
// }
|
|
marci@330
|
49 |
// }
|
|
marci@330
|
50 |
// bool valid() const { return sym.valid(); }
|
|
marci@330
|
51 |
// void augment(Number a) const {
|
|
marci@330
|
52 |
// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
|
|
marci@330
|
53 |
// resG->flow.set(sym, resG->flow.get(sym)+a);
|
|
marci@330
|
54 |
// //resG->flow[sym]+=a;
|
|
marci@330
|
55 |
// } else {
|
|
marci@330
|
56 |
// resG->flow.set(sym, resG->flow.get(sym)-a);
|
|
marci@330
|
57 |
// //resG->flow[sym]-=a;
|
|
marci@330
|
58 |
// }
|
|
marci@330
|
59 |
// }
|
|
marci@330
|
60 |
// };
|
|
marci@301
|
61 |
|
|
marci@330
|
62 |
// class OutEdgeIt : public Edge {
|
|
marci@330
|
63 |
// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
|
|
marci@330
|
64 |
// public:
|
|
marci@330
|
65 |
// OutEdgeIt() { }
|
|
marci@330
|
66 |
// //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
|
|
marci@330
|
67 |
// private:
|
|
marci@330
|
68 |
// OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
|
|
marci@330
|
69 |
// resG=&_resG;
|
|
marci@330
|
70 |
// sym=resG->G.template first<OldSymEdgeIt>(v);
|
|
marci@330
|
71 |
// while( sym.valid() && !(free()>0) ) { ++sym; }
|
|
marci@330
|
72 |
// }
|
|
marci@330
|
73 |
// public:
|
|
marci@330
|
74 |
// OutEdgeIt& operator++() {
|
|
marci@330
|
75 |
// ++sym;
|
|
marci@330
|
76 |
// while( sym.valid() && !(free()>0) ) { ++sym; }
|
|
marci@330
|
77 |
// return *this;
|
|
marci@330
|
78 |
// }
|
|
marci@330
|
79 |
// };
|
|
marci@301
|
80 |
|
|
marci@330
|
81 |
// void /*getF*/first(OutEdgeIt& e, Node v) const {
|
|
marci@330
|
82 |
// e=OutEdgeIt(*this, v);
|
|
marci@330
|
83 |
// }
|
|
marci@330
|
84 |
// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
|
|
marci@301
|
85 |
|
|
marci@330
|
86 |
// template< typename It >
|
|
marci@330
|
87 |
// It first() const {
|
|
marci@330
|
88 |
// It e;
|
|
marci@330
|
89 |
// /*getF*/first(e);
|
|
marci@330
|
90 |
// return e;
|
|
marci@330
|
91 |
// }
|
|
marci@301
|
92 |
|
|
marci@330
|
93 |
// template< typename It >
|
|
marci@330
|
94 |
// It first(Node v) const {
|
|
marci@330
|
95 |
// It e;
|
|
marci@330
|
96 |
// /*getF*/first(e, v);
|
|
marci@330
|
97 |
// return e;
|
|
marci@330
|
98 |
// }
|
|
marci@301
|
99 |
|
|
marci@330
|
100 |
// Node tail(Edge e) const { return G.aNode(e.sym); }
|
|
marci@330
|
101 |
// Node head(Edge e) const { return G.bNode(e.sym); }
|
|
marci@301
|
102 |
|
|
marci@330
|
103 |
// Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
|
|
marci@330
|
104 |
// Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
|
|
marci@301
|
105 |
|
|
marci@330
|
106 |
// int id(Node v) const { return G.id(v); }
|
|
marci@301
|
107 |
|
|
marci@330
|
108 |
// template <typename S>
|
|
marci@330
|
109 |
// class NodeMap {
|
|
marci@330
|
110 |
// typename Graph::NodeMap<S> node_map;
|
|
marci@330
|
111 |
// public:
|
|
marci@330
|
112 |
// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
|
|
marci@330
|
113 |
// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
|
|
marci@330
|
114 |
// void set(Node nit, S a) { node_map.set(nit, a); }
|
|
marci@330
|
115 |
// S get(Node nit) const { return node_map.get(nit); }
|
|
marci@330
|
116 |
// S& operator[](Node nit) { return node_map[nit]; }
|
|
marci@330
|
117 |
// const S& operator[](Node nit) const { return node_map[nit]; }
|
|
marci@330
|
118 |
// };
|
|
marci@301
|
119 |
|
|
marci@330
|
120 |
// };
|
|
marci@301
|
121 |
|
|
marci@301
|
122 |
|
|
marci@330
|
123 |
// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
|
|
marci@330
|
124 |
// class ResGraph2 {
|
|
marci@330
|
125 |
// public:
|
|
marci@330
|
126 |
// typedef typename Graph::Node Node;
|
|
marci@330
|
127 |
// typedef typename Graph::NodeIt NodeIt;
|
|
marci@330
|
128 |
// private:
|
|
marci@330
|
129 |
// //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
|
|
marci@330
|
130 |
// typedef typename Graph::OutEdgeIt OldOutEdgeIt;
|
|
marci@330
|
131 |
// typedef typename Graph::InEdgeIt OldInEdgeIt;
|
|
marci@301
|
132 |
|
|
marci@330
|
133 |
// const Graph& G;
|
|
marci@330
|
134 |
// FlowMap& flow;
|
|
marci@330
|
135 |
// const CapacityMap& capacity;
|
|
marci@330
|
136 |
// public:
|
|
marci@330
|
137 |
// ResGraph2(const Graph& _G, FlowMap& _flow,
|
|
marci@330
|
138 |
// const CapacityMap& _capacity) :
|
|
marci@330
|
139 |
// G(_G), flow(_flow), capacity(_capacity) { }
|
|
marci@301
|
140 |
|
|
marci@330
|
141 |
// class Edge;
|
|
marci@330
|
142 |
// class OutEdgeIt;
|
|
marci@330
|
143 |
// friend class Edge;
|
|
marci@330
|
144 |
// friend class OutEdgeIt;
|
|
marci@301
|
145 |
|
|
marci@330
|
146 |
// class Edge {
|
|
marci@330
|
147 |
// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
|
|
marci@330
|
148 |
// protected:
|
|
marci@330
|
149 |
// const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
|
|
marci@330
|
150 |
// //OldSymEdgeIt sym;
|
|
marci@330
|
151 |
// OldOutEdgeIt out;
|
|
marci@330
|
152 |
// OldInEdgeIt in;
|
|
marci@330
|
153 |
// bool out_or_in; //true, iff out
|
|
marci@330
|
154 |
// public:
|
|
marci@330
|
155 |
// Edge() : out_or_in(true) { }
|
|
marci@330
|
156 |
// Number free() const {
|
|
marci@330
|
157 |
// if (out_or_in) {
|
|
marci@330
|
158 |
// return (resG->capacity.get(out)-resG->flow.get(out));
|
|
marci@330
|
159 |
// } else {
|
|
marci@330
|
160 |
// return (resG->flow.get(in));
|
|
marci@330
|
161 |
// }
|
|
marci@330
|
162 |
// }
|
|
marci@330
|
163 |
// bool valid() const {
|
|
marci@330
|
164 |
// return out_or_in && out.valid() || in.valid(); }
|
|
marci@330
|
165 |
// void augment(Number a) const {
|
|
marci@330
|
166 |
// if (out_or_in) {
|
|
marci@330
|
167 |
// resG->flow.set(out, resG->flow.get(out)+a);
|
|
marci@330
|
168 |
// } else {
|
|
marci@330
|
169 |
// resG->flow.set(in, resG->flow.get(in)-a);
|
|
marci@330
|
170 |
// }
|
|
marci@330
|
171 |
// }
|
|
marci@330
|
172 |
// };
|
|
marci@301
|
173 |
|
|
marci@330
|
174 |
// class OutEdgeIt : public Edge {
|
|
marci@330
|
175 |
// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
|
|
marci@330
|
176 |
// public:
|
|
marci@330
|
177 |
// OutEdgeIt() { }
|
|
marci@330
|
178 |
// private:
|
|
marci@330
|
179 |
// OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
|
|
marci@330
|
180 |
// resG=&_resG;
|
|
marci@330
|
181 |
// out=resG->G.template first<OldOutEdgeIt>(v);
|
|
marci@330
|
182 |
// while( out.valid() && !(free()>0) ) { ++out; }
|
|
marci@330
|
183 |
// if (!out.valid()) {
|
|
marci@330
|
184 |
// out_or_in=0;
|
|
marci@330
|
185 |
// in=resG->G.template first<OldInEdgeIt>(v);
|
|
marci@330
|
186 |
// while( in.valid() && !(free()>0) ) { ++in; }
|
|
marci@330
|
187 |
// }
|
|
marci@330
|
188 |
// }
|
|
marci@330
|
189 |
// public:
|
|
marci@330
|
190 |
// OutEdgeIt& operator++() {
|
|
marci@330
|
191 |
// if (out_or_in) {
|
|
marci@330
|
192 |
// Node v=resG->G.aNode(out);
|
|
marci@330
|
193 |
// ++out;
|
|
marci@330
|
194 |
// while( out.valid() && !(free()>0) ) { ++out; }
|
|
marci@330
|
195 |
// if (!out.valid()) {
|
|
marci@330
|
196 |
// out_or_in=0;
|
|
marci@330
|
197 |
// in=resG->G.template first<OldInEdgeIt>(v);
|
|
marci@330
|
198 |
// while( in.valid() && !(free()>0) ) { ++in; }
|
|
marci@330
|
199 |
// }
|
|
marci@330
|
200 |
// } else {
|
|
marci@330
|
201 |
// ++in;
|
|
marci@330
|
202 |
// while( in.valid() && !(free()>0) ) { ++in; }
|
|
marci@330
|
203 |
// }
|
|
marci@330
|
204 |
// return *this;
|
|
marci@330
|
205 |
// }
|
|
marci@330
|
206 |
// };
|
|
marci@301
|
207 |
|
|
marci@330
|
208 |
// void /*getF*/first(OutEdgeIt& e, Node v) const {
|
|
marci@330
|
209 |
// e=OutEdgeIt(*this, v);
|
|
marci@330
|
210 |
// }
|
|
marci@330
|
211 |
// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
|
|
marci@301
|
212 |
|
|
marci@330
|
213 |
// template< typename It >
|
|
marci@330
|
214 |
// It first() const {
|
|
marci@330
|
215 |
// It e;
|
|
marci@330
|
216 |
// /*getF*/first(e);
|
|
marci@330
|
217 |
// return e;
|
|
marci@330
|
218 |
// }
|
|
marci@301
|
219 |
|
|
marci@330
|
220 |
// template< typename It >
|
|
marci@330
|
221 |
// It first(Node v) const {
|
|
marci@330
|
222 |
// It e;
|
|
marci@330
|
223 |
// /*getF*/first(e, v);
|
|
marci@330
|
224 |
// return e;
|
|
marci@330
|
225 |
// }
|
|
marci@301
|
226 |
|
|
marci@330
|
227 |
// Node tail(Edge e) const {
|
|
marci@330
|
228 |
// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
|
|
marci@330
|
229 |
// Node head(Edge e) const {
|
|
marci@330
|
230 |
// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
|
|
marci@301
|
231 |
|
|
marci@330
|
232 |
// Node aNode(OutEdgeIt e) const {
|
|
marci@330
|
233 |
// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
|
|
marci@330
|
234 |
// Node bNode(OutEdgeIt e) const {
|
|
marci@330
|
235 |
// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
|
|
marci@301
|
236 |
|
|
marci@330
|
237 |
// int id(Node v) const { return G.id(v); }
|
|
marci@301
|
238 |
|
|
marci@330
|
239 |
// template <typename S>
|
|
marci@330
|
240 |
// class NodeMap {
|
|
marci@330
|
241 |
// typename Graph::NodeMap<S> node_map;
|
|
marci@330
|
242 |
// public:
|
|
marci@330
|
243 |
// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
|
|
marci@330
|
244 |
// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
|
|
marci@330
|
245 |
// void set(Node nit, S a) { node_map.set(nit, a); }
|
|
marci@330
|
246 |
// S get(Node nit) const { return node_map.get(nit); }
|
|
marci@330
|
247 |
// };
|
|
marci@330
|
248 |
// };
|
|
marci@301
|
249 |
|
|
marci@301
|
250 |
|
|
marci@330
|
251 |
template <typename Graph, typename Number,
|
|
marci@330
|
252 |
typename CapacityMap, typename FlowMap>
|
|
marci@301
|
253 |
class MaxFlow {
|
|
marci@301
|
254 |
protected:
|
|
marci@303
|
255 |
typedef typename Graph::Node Node;
|
|
marci@303
|
256 |
typedef typename Graph::Edge Edge;
|
|
marci@303
|
257 |
typedef typename Graph::EdgeIt EdgeIt;
|
|
marci@303
|
258 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
marci@303
|
259 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
|
marci@303
|
260 |
const Graph* g;
|
|
marci@301
|
261 |
Node s;
|
|
marci@301
|
262 |
Node t;
|
|
marci@330
|
263 |
const CapacityMap* capacity;
|
|
marci@301
|
264 |
FlowMap* flow;
|
|
marci@330
|
265 |
typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
|
|
marci@301
|
266 |
typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
|
|
marci@301
|
267 |
typedef typename ResGW::Edge ResGWEdge;
|
|
marci@301
|
268 |
public:
|
|
marci@301
|
269 |
|
|
marci@330
|
270 |
MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
|
|
marci@330
|
271 |
FlowMap& _flow) :
|
|
marci@330
|
272 |
g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
|
|
marci@301
|
273 |
|
|
marci@301
|
274 |
bool augmentOnShortestPath() {
|
|
marci@330
|
275 |
ResGW res_graph(*g, *capacity, *flow);
|
|
marci@301
|
276 |
bool _augment=false;
|
|
marci@301
|
277 |
|
|
marci@360
|
278 |
BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
|
|
marci@301
|
279 |
bfs.pushAndSetReached(s);
|
|
marci@301
|
280 |
|
|
marci@301
|
281 |
typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
|
|
marci@301
|
282 |
pred.set(s, INVALID);
|
|
marci@301
|
283 |
|
|
marci@301
|
284 |
typename ResGW::NodeMap<Number> free(res_graph);
|
|
marci@301
|
285 |
|
|
marci@301
|
286 |
//searching for augmenting path
|
|
marci@301
|
287 |
while ( !bfs.finished() ) {
|
|
marci@301
|
288 |
ResGWOutEdgeIt e=bfs;
|
|
marci@301
|
289 |
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@301
|
290 |
Node v=res_graph.tail(e);
|
|
marci@301
|
291 |
Node w=res_graph.head(e);
|
|
marci@301
|
292 |
pred.set(w, e);
|
|
marci@303
|
293 |
if (res_graph.valid(pred[v])) {
|
|
marci@303
|
294 |
free.set(w, std::min(free[v], res_graph.resCap(e)));
|
|
marci@301
|
295 |
} else {
|
|
marci@301
|
296 |
free.set(w, res_graph.resCap(e));
|
|
marci@301
|
297 |
}
|
|
marci@301
|
298 |
if (res_graph.head(e)==t) { _augment=true; break; }
|
|
marci@301
|
299 |
}
|
|
marci@301
|
300 |
|
|
marci@301
|
301 |
++bfs;
|
|
marci@301
|
302 |
} //end of searching augmenting path
|
|
marci@301
|
303 |
|
|
marci@301
|
304 |
if (_augment) {
|
|
marci@301
|
305 |
Node n=t;
|
|
marci@303
|
306 |
Number augment_value=free[t];
|
|
marci@303
|
307 |
while (res_graph.valid(pred[n])) {
|
|
marci@303
|
308 |
ResGWEdge e=pred[n];
|
|
marci@301
|
309 |
res_graph.augment(e, augment_value);
|
|
marci@301
|
310 |
n=res_graph.tail(e);
|
|
marci@301
|
311 |
}
|
|
marci@301
|
312 |
}
|
|
marci@301
|
313 |
|
|
marci@301
|
314 |
return _augment;
|
|
marci@301
|
315 |
}
|
|
marci@301
|
316 |
|
|
marci@301
|
317 |
template<typename MapGraphWrapper>
|
|
marci@301
|
318 |
class DistanceMap {
|
|
marci@301
|
319 |
protected:
|
|
marci@303
|
320 |
const MapGraphWrapper* g;
|
|
marci@301
|
321 |
typename MapGraphWrapper::NodeMap<int> dist;
|
|
marci@301
|
322 |
public:
|
|
marci@303
|
323 |
DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
|
|
marci@301
|
324 |
void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
|
|
marci@303
|
325 |
int operator[](const typename MapGraphWrapper::Node& n)
|
|
marci@303
|
326 |
{ return dist[n]; }
|
|
marci@303
|
327 |
// int get(const typename MapGraphWrapper::Node& n) const {
|
|
marci@303
|
328 |
// return dist[n]; }
|
|
marci@303
|
329 |
// bool get(const typename MapGraphWrapper::Edge& e) const {
|
|
marci@303
|
330 |
// return (dist.get(g->tail(e))<dist.get(g->head(e))); }
|
|
marci@303
|
331 |
bool operator[](const typename MapGraphWrapper::Edge& e) const {
|
|
marci@303
|
332 |
return (dist[g->tail(e)]<dist[g->head(e)]);
|
|
marci@301
|
333 |
}
|
|
marci@301
|
334 |
};
|
|
marci@301
|
335 |
|
|
marci@301
|
336 |
template<typename MutableGraph> bool augmentOnBlockingFlow() {
|
|
marci@301
|
337 |
typedef MutableGraph MG;
|
|
marci@301
|
338 |
bool _augment=false;
|
|
marci@301
|
339 |
|
|
marci@330
|
340 |
ResGW res_graph(*g, *capacity, *flow);
|
|
marci@301
|
341 |
|
|
marci@360
|
342 |
BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
|
|
marci@301
|
343 |
|
|
marci@301
|
344 |
bfs.pushAndSetReached(s);
|
|
marci@301
|
345 |
//typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@301
|
346 |
DistanceMap<ResGW> dist(res_graph);
|
|
marci@301
|
347 |
while ( !bfs.finished() ) {
|
|
marci@301
|
348 |
ResGWOutEdgeIt e=bfs;
|
|
marci@301
|
349 |
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@303
|
350 |
dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
|
|
marci@301
|
351 |
}
|
|
marci@301
|
352 |
++bfs;
|
|
marci@301
|
353 |
} //computing distances from s in the residual graph
|
|
marci@301
|
354 |
|
|
marci@301
|
355 |
MG F;
|
|
marci@311
|
356 |
ConstMap<typename ResGW::Node, bool> true_map(true);
|
|
marci@311
|
357 |
typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
|
|
marci@311
|
358 |
DistanceMap<ResGW> > FilterResGW;
|
|
marci@311
|
359 |
FilterResGW filter_res_graph(res_graph, true_map, dist);
|
|
marci@301
|
360 |
typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
|
|
marci@301
|
361 |
{
|
|
marci@301
|
362 |
typename ResGW::NodeIt n;
|
|
marci@301
|
363 |
for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@301
|
364 |
res_graph_to_F.set(n, F.addNode());
|
|
marci@301
|
365 |
}
|
|
marci@301
|
366 |
}
|
|
marci@301
|
367 |
|
|
marci@303
|
368 |
typename MG::Node sF=res_graph_to_F[s];
|
|
marci@303
|
369 |
typename MG::Node tF=res_graph_to_F[t];
|
|
marci@301
|
370 |
typename MG::EdgeMap<ResGWEdge> original_edge(F);
|
|
marci@301
|
371 |
typename MG::EdgeMap<Number> residual_capacity(F);
|
|
marci@301
|
372 |
|
|
marci@301
|
373 |
//Making F to the graph containing the edges of the residual graph
|
|
marci@301
|
374 |
//which are in some shortest paths
|
|
marci@301
|
375 |
{
|
|
marci@301
|
376 |
typename FilterResGW::EdgeIt e;
|
|
marci@301
|
377 |
for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
|
|
marci@301
|
378 |
//if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
|
|
marci@303
|
379 |
typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
|
|
marci@301
|
380 |
original_edge.update();
|
|
marci@301
|
381 |
original_edge.set(f, e);
|
|
marci@301
|
382 |
residual_capacity.update();
|
|
marci@301
|
383 |
residual_capacity.set(f, res_graph.resCap(e));
|
|
marci@301
|
384 |
//}
|
|
marci@301
|
385 |
}
|
|
marci@301
|
386 |
}
|
|
marci@301
|
387 |
|
|
marci@301
|
388 |
bool __augment=true;
|
|
marci@301
|
389 |
|
|
marci@301
|
390 |
while (__augment) {
|
|
marci@301
|
391 |
__augment=false;
|
|
marci@301
|
392 |
//computing blocking flow with dfs
|
|
marci@312
|
393 |
|
|
marci@360
|
394 |
DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
|
|
marci@301
|
395 |
typename MG::NodeMap<typename MG::Edge> pred(F);
|
|
marci@301
|
396 |
pred.set(sF, INVALID);
|
|
marci@301
|
397 |
//invalid iterators for sources
|
|
marci@301
|
398 |
|
|
marci@301
|
399 |
typename MG::NodeMap<Number> free(F);
|
|
marci@301
|
400 |
|
|
marci@301
|
401 |
dfs.pushAndSetReached(sF);
|
|
marci@301
|
402 |
while (!dfs.finished()) {
|
|
marci@301
|
403 |
++dfs;
|
|
marci@301
|
404 |
if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
|
|
marci@301
|
405 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@301
|
406 |
typename MG::Node v=F.aNode(dfs);
|
|
marci@301
|
407 |
typename MG::Node w=F.bNode(dfs);
|
|
marci@301
|
408 |
pred.set(w, dfs);
|
|
marci@303
|
409 |
if (F.valid(pred[v])) {
|
|
marci@303
|
410 |
free.set(w, std::min(free[v], residual_capacity[dfs]));
|
|
marci@301
|
411 |
} else {
|
|
marci@303
|
412 |
free.set(w, residual_capacity[dfs]);
|
|
marci@301
|
413 |
}
|
|
marci@301
|
414 |
if (w==tF) {
|
|
marci@301
|
415 |
__augment=true;
|
|
marci@301
|
416 |
_augment=true;
|
|
marci@301
|
417 |
break;
|
|
marci@301
|
418 |
}
|
|
marci@301
|
419 |
|
|
marci@301
|
420 |
} else {
|
|
marci@301
|
421 |
F.erase(/*typename MG::OutEdgeIt*/(dfs));
|
|
marci@301
|
422 |
}
|
|
marci@301
|
423 |
}
|
|
marci@301
|
424 |
}
|
|
marci@301
|
425 |
|
|
marci@301
|
426 |
if (__augment) {
|
|
marci@301
|
427 |
typename MG::Node n=tF;
|
|
marci@303
|
428 |
Number augment_value=free[tF];
|
|
marci@303
|
429 |
while (F.valid(pred[n])) {
|
|
marci@303
|
430 |
typename MG::Edge e=pred[n];
|
|
marci@303
|
431 |
res_graph.augment(original_edge[e], augment_value);
|
|
marci@301
|
432 |
n=F.tail(e);
|
|
marci@303
|
433 |
if (residual_capacity[e]==augment_value)
|
|
marci@301
|
434 |
F.erase(e);
|
|
marci@301
|
435 |
else
|
|
marci@303
|
436 |
residual_capacity.set(e, residual_capacity[e]-augment_value);
|
|
marci@301
|
437 |
}
|
|
marci@301
|
438 |
}
|
|
marci@301
|
439 |
|
|
marci@301
|
440 |
}
|
|
marci@301
|
441 |
|
|
marci@301
|
442 |
return _augment;
|
|
marci@301
|
443 |
}
|
|
marci@301
|
444 |
|
|
marci@301
|
445 |
template<typename MutableGraph> bool augmentOnBlockingFlow1() {
|
|
marci@301
|
446 |
typedef MutableGraph MG;
|
|
marci@301
|
447 |
bool _augment=false;
|
|
marci@301
|
448 |
|
|
marci@330
|
449 |
ResGW res_graph(*g, *capacity, *flow);
|
|
marci@301
|
450 |
|
|
marci@301
|
451 |
//bfs for distances on the residual graph
|
|
marci@360
|
452 |
BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
|
|
marci@301
|
453 |
bfs.pushAndSetReached(s);
|
|
marci@301
|
454 |
typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@301
|
455 |
|
|
marci@301
|
456 |
//F will contain the physical copy of the residual graph
|
|
marci@301
|
457 |
//with the set of edges which are on shortest paths
|
|
marci@301
|
458 |
MG F;
|
|
marci@301
|
459 |
typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
|
|
marci@301
|
460 |
{
|
|
marci@301
|
461 |
typename ResGW::NodeIt n;
|
|
marci@301
|
462 |
for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@301
|
463 |
res_graph_to_F.set(n, F.addNode());
|
|
marci@301
|
464 |
}
|
|
marci@301
|
465 |
}
|
|
marci@301
|
466 |
|
|
marci@303
|
467 |
typename MG::Node sF=res_graph_to_F[s];
|
|
marci@303
|
468 |
typename MG::Node tF=res_graph_to_F[t];
|
|
marci@301
|
469 |
typename MG::EdgeMap<ResGWEdge> original_edge(F);
|
|
marci@301
|
470 |
typename MG::EdgeMap<Number> residual_capacity(F);
|
|
marci@301
|
471 |
|
|
marci@301
|
472 |
while ( !bfs.finished() ) {
|
|
marci@301
|
473 |
ResGWOutEdgeIt e=bfs;
|
|
marci@301
|
474 |
if (res_graph.valid(e)) {
|
|
marci@301
|
475 |
if (bfs.isBNodeNewlyReached()) {
|
|
marci@303
|
476 |
dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
|
|
marci@303
|
477 |
typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
|
|
marci@301
|
478 |
original_edge.update();
|
|
marci@301
|
479 |
original_edge.set(f, e);
|
|
marci@301
|
480 |
residual_capacity.update();
|
|
marci@301
|
481 |
residual_capacity.set(f, res_graph.resCap(e));
|
|
marci@301
|
482 |
} else {
|
|
marci@303
|
483 |
if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
|
|
marci@303
|
484 |
typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
|
|
marci@301
|
485 |
original_edge.update();
|
|
marci@301
|
486 |
original_edge.set(f, e);
|
|
marci@301
|
487 |
residual_capacity.update();
|
|
marci@301
|
488 |
residual_capacity.set(f, res_graph.resCap(e));
|
|
marci@301
|
489 |
}
|
|
marci@301
|
490 |
}
|
|
marci@301
|
491 |
}
|
|
marci@301
|
492 |
++bfs;
|
|
marci@301
|
493 |
} //computing distances from s in the residual graph
|
|
marci@301
|
494 |
|
|
marci@301
|
495 |
bool __augment=true;
|
|
marci@301
|
496 |
|
|
marci@301
|
497 |
while (__augment) {
|
|
marci@301
|
498 |
__augment=false;
|
|
marci@301
|
499 |
//computing blocking flow with dfs
|
|
marci@360
|
500 |
DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
|
|
marci@301
|
501 |
typename MG::NodeMap<typename MG::Edge> pred(F);
|
|
marci@301
|
502 |
pred.set(sF, INVALID);
|
|
marci@301
|
503 |
//invalid iterators for sources
|
|
marci@301
|
504 |
|
|
marci@301
|
505 |
typename MG::NodeMap<Number> free(F);
|
|
marci@301
|
506 |
|
|
marci@301
|
507 |
dfs.pushAndSetReached(sF);
|
|
marci@301
|
508 |
while (!dfs.finished()) {
|
|
marci@301
|
509 |
++dfs;
|
|
marci@301
|
510 |
if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
|
|
marci@301
|
511 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@301
|
512 |
typename MG::Node v=F.aNode(dfs);
|
|
marci@301
|
513 |
typename MG::Node w=F.bNode(dfs);
|
|
marci@301
|
514 |
pred.set(w, dfs);
|
|
marci@303
|
515 |
if (F.valid(pred[v])) {
|
|
marci@303
|
516 |
free.set(w, std::min(free[v], residual_capacity[dfs]));
|
|
marci@301
|
517 |
} else {
|
|
marci@303
|
518 |
free.set(w, residual_capacity[dfs]);
|
|
marci@301
|
519 |
}
|
|
marci@301
|
520 |
if (w==tF) {
|
|
marci@301
|
521 |
__augment=true;
|
|
marci@301
|
522 |
_augment=true;
|
|
marci@301
|
523 |
break;
|
|
marci@301
|
524 |
}
|
|
marci@301
|
525 |
|
|
marci@301
|
526 |
} else {
|
|
marci@301
|
527 |
F.erase(/*typename MG::OutEdgeIt*/(dfs));
|
|
marci@301
|
528 |
}
|
|
marci@301
|
529 |
}
|
|
marci@301
|
530 |
}
|
|
marci@301
|
531 |
|
|
marci@301
|
532 |
if (__augment) {
|
|
marci@301
|
533 |
typename MG::Node n=tF;
|
|
marci@303
|
534 |
Number augment_value=free[tF];
|
|
marci@303
|
535 |
while (F.valid(pred[n])) {
|
|
marci@303
|
536 |
typename MG::Edge e=pred[n];
|
|
marci@303
|
537 |
res_graph.augment(original_edge[e], augment_value);
|
|
marci@301
|
538 |
n=F.tail(e);
|
|
marci@303
|
539 |
if (residual_capacity[e]==augment_value)
|
|
marci@301
|
540 |
F.erase(e);
|
|
marci@301
|
541 |
else
|
|
marci@303
|
542 |
residual_capacity.set(e, residual_capacity[e]-augment_value);
|
|
marci@301
|
543 |
}
|
|
marci@301
|
544 |
}
|
|
marci@301
|
545 |
|
|
marci@301
|
546 |
}
|
|
marci@301
|
547 |
|
|
marci@301
|
548 |
return _augment;
|
|
marci@301
|
549 |
}
|
|
marci@301
|
550 |
|
|
marci@301
|
551 |
bool augmentOnBlockingFlow2() {
|
|
marci@301
|
552 |
bool _augment=false;
|
|
marci@301
|
553 |
|
|
marci@330
|
554 |
ResGW res_graph(*g, *capacity, *flow);
|
|
marci@301
|
555 |
|
|
marci@360
|
556 |
BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
|
|
marci@301
|
557 |
|
|
marci@301
|
558 |
bfs.pushAndSetReached(s);
|
|
marci@301
|
559 |
DistanceMap<ResGW> dist(res_graph);
|
|
marci@301
|
560 |
while ( !bfs.finished() ) {
|
|
marci@301
|
561 |
ResGWOutEdgeIt e=bfs;
|
|
marci@301
|
562 |
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@303
|
563 |
dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
|
|
marci@301
|
564 |
}
|
|
marci@301
|
565 |
++bfs;
|
|
marci@301
|
566 |
} //computing distances from s in the residual graph
|
|
marci@301
|
567 |
|
|
marci@301
|
568 |
//Subgraph containing the edges on some shortest paths
|
|
marci@311
|
569 |
ConstMap<typename ResGW::Node, bool> true_map(true);
|
|
marci@311
|
570 |
typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
|
|
marci@311
|
571 |
DistanceMap<ResGW> > FilterResGW;
|
|
marci@311
|
572 |
FilterResGW filter_res_graph(res_graph, true_map, dist);
|
|
marci@301
|
573 |
|
|
marci@301
|
574 |
//Subgraph, which is able to delete edges which are already
|
|
marci@301
|
575 |
//met by the dfs
|
|
marci@301
|
576 |
typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
|
|
marci@301
|
577 |
first_out_edges(filter_res_graph);
|
|
marci@301
|
578 |
typename FilterResGW::NodeIt v;
|
|
marci@301
|
579 |
for(filter_res_graph.first(v); filter_res_graph.valid(v);
|
|
marci@301
|
580 |
filter_res_graph.next(v))
|
|
marci@301
|
581 |
{
|
|
marci@301
|
582 |
typename FilterResGW::OutEdgeIt e;
|
|
marci@301
|
583 |
filter_res_graph.first(e, v);
|
|
marci@301
|
584 |
first_out_edges.set(v, e);
|
|
marci@301
|
585 |
}
|
|
marci@301
|
586 |
typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
|
|
marci@301
|
587 |
NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
|
|
marci@301
|
588 |
ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
|
|
marci@301
|
589 |
|
|
marci@301
|
590 |
bool __augment=true;
|
|
marci@301
|
591 |
|
|
marci@301
|
592 |
while (__augment) {
|
|
marci@301
|
593 |
|
|
marci@301
|
594 |
__augment=false;
|
|
marci@311
|
595 |
//computing blocking flow with dfs
|
|
marci@360
|
596 |
DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap<bool> >
|
|
marci@311
|
597 |
dfs(erasing_res_graph);
|
|
marci@301
|
598 |
typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
|
|
marci@301
|
599 |
pred(erasing_res_graph);
|
|
marci@301
|
600 |
pred.set(s, INVALID);
|
|
marci@311
|
601 |
//invalid iterators for sources
|
|
marci@301
|
602 |
|
|
marci@317
|
603 |
typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph);
|
|
marci@301
|
604 |
|
|
marci@317
|
605 |
dfs.pushAndSetReached(
|
|
marci@317
|
606 |
typename ErasingResGW::Node(
|
|
marci@317
|
607 |
typename FilterResGW::Node(
|
|
marci@317
|
608 |
typename ResGW::Node(s)
|
|
marci@317
|
609 |
)
|
|
marci@317
|
610 |
)
|
|
marci@317
|
611 |
);
|
|
marci@301
|
612 |
while (!dfs.finished()) {
|
|
marci@301
|
613 |
++dfs;
|
|
marci@301
|
614 |
if (erasing_res_graph.valid(
|
|
marci@317
|
615 |
typename ErasingResGW::OutEdgeIt(dfs)))
|
|
marci@301
|
616 |
{
|
|
marci@311
|
617 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@301
|
618 |
|
|
marci@301
|
619 |
typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
|
|
marci@301
|
620 |
typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
|
|
marci@301
|
621 |
|
|
marci@301
|
622 |
pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
|
|
marci@303
|
623 |
if (erasing_res_graph.valid(pred[v])) {
|
|
marci@317
|
624 |
free1.set(w, std::min(free1[v], res_graph.resCap(
|
|
marci@317
|
625 |
typename ErasingResGW::OutEdgeIt(dfs))));
|
|
marci@301
|
626 |
} else {
|
|
marci@317
|
627 |
free1.set(w, res_graph.resCap(
|
|
marci@317
|
628 |
typename ErasingResGW::OutEdgeIt(dfs)));
|
|
marci@301
|
629 |
}
|
|
marci@301
|
630 |
|
|
marci@301
|
631 |
if (w==t) {
|
|
marci@301
|
632 |
__augment=true;
|
|
marci@301
|
633 |
_augment=true;
|
|
marci@301
|
634 |
break;
|
|
marci@301
|
635 |
}
|
|
marci@311
|
636 |
} else {
|
|
marci@311
|
637 |
erasing_res_graph.erase(dfs);
|
|
marci@301
|
638 |
}
|
|
marci@301
|
639 |
}
|
|
marci@301
|
640 |
}
|
|
marci@301
|
641 |
|
|
marci@311
|
642 |
if (__augment) {
|
|
marci@317
|
643 |
typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
|
|
marci@317
|
644 |
// typename ResGW::NodeMap<Number> a(res_graph);
|
|
marci@317
|
645 |
// typename ResGW::Node b;
|
|
marci@317
|
646 |
// Number j=a[b];
|
|
marci@317
|
647 |
// typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
|
|
marci@317
|
648 |
// typename FilterResGW::Node b1;
|
|
marci@317
|
649 |
// Number j1=a1[b1];
|
|
marci@317
|
650 |
// typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
|
|
marci@317
|
651 |
// typename ErasingResGW::Node b2;
|
|
marci@317
|
652 |
// Number j2=a2[b2];
|
|
marci@317
|
653 |
Number augment_value=free1[n];
|
|
marci@303
|
654 |
while (erasing_res_graph.valid(pred[n])) {
|
|
marci@303
|
655 |
typename ErasingResGW::OutEdgeIt e=pred[n];
|
|
marci@301
|
656 |
res_graph.augment(e, augment_value);
|
|
marci@301
|
657 |
n=erasing_res_graph.tail(e);
|
|
marci@301
|
658 |
if (res_graph.resCap(e)==0)
|
|
marci@301
|
659 |
erasing_res_graph.erase(e);
|
|
marci@311
|
660 |
}
|
|
marci@311
|
661 |
}
|
|
marci@301
|
662 |
|
|
marci@301
|
663 |
} //while (__augment)
|
|
marci@301
|
664 |
|
|
marci@301
|
665 |
return _augment;
|
|
marci@301
|
666 |
}
|
|
marci@301
|
667 |
|
|
marci@301
|
668 |
void run() {
|
|
marci@301
|
669 |
//int num_of_augmentations=0;
|
|
marci@301
|
670 |
while (augmentOnShortestPath()) {
|
|
marci@301
|
671 |
//while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@301
|
672 |
//std::cout << ++num_of_augmentations << " ";
|
|
marci@301
|
673 |
//std::cout<<std::endl;
|
|
marci@301
|
674 |
}
|
|
marci@301
|
675 |
}
|
|
marci@301
|
676 |
|
|
marci@301
|
677 |
template<typename MutableGraph> void run() {
|
|
marci@301
|
678 |
//int num_of_augmentations=0;
|
|
marci@301
|
679 |
//while (augmentOnShortestPath()) {
|
|
marci@301
|
680 |
while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@301
|
681 |
//std::cout << ++num_of_augmentations << " ";
|
|
marci@301
|
682 |
//std::cout<<std::endl;
|
|
marci@301
|
683 |
}
|
|
marci@301
|
684 |
}
|
|
marci@301
|
685 |
|
|
marci@301
|
686 |
Number flowValue() {
|
|
marci@301
|
687 |
Number a=0;
|
|
marci@301
|
688 |
OutEdgeIt e;
|
|
marci@303
|
689 |
for(g->first(e, s); g->valid(e); g->next(e)) {
|
|
marci@303
|
690 |
a+=(*flow)[e];
|
|
marci@301
|
691 |
}
|
|
marci@301
|
692 |
return a;
|
|
marci@301
|
693 |
}
|
|
marci@301
|
694 |
|
|
marci@301
|
695 |
};
|
|
marci@301
|
696 |
|
|
marci@301
|
697 |
|
|
marci@301
|
698 |
// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
|
|
marci@301
|
699 |
// class MaxMatching {
|
|
marci@301
|
700 |
// public:
|
|
marci@301
|
701 |
// typedef typename Graph::Node Node;
|
|
marci@301
|
702 |
// typedef typename Graph::NodeIt NodeIt;
|
|
marci@301
|
703 |
// typedef typename Graph::Edge Edge;
|
|
marci@301
|
704 |
// typedef typename Graph::EdgeIt EdgeIt;
|
|
marci@301
|
705 |
// typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
marci@301
|
706 |
// typedef typename Graph::InEdgeIt InEdgeIt;
|
|
marci@301
|
707 |
|
|
marci@301
|
708 |
// typedef typename Graph::NodeMap<bool> SMap;
|
|
marci@301
|
709 |
// typedef typename Graph::NodeMap<bool> TMap;
|
|
marci@301
|
710 |
// private:
|
|
marci@301
|
711 |
// const Graph* G;
|
|
marci@301
|
712 |
// SMap* S;
|
|
marci@301
|
713 |
// TMap* T;
|
|
marci@301
|
714 |
// //Node s;
|
|
marci@301
|
715 |
// //Node t;
|
|
marci@301
|
716 |
// FlowMap* flow;
|
|
marci@301
|
717 |
// const CapacityMap* capacity;
|
|
marci@301
|
718 |
// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
|
|
marci@301
|
719 |
// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
|
|
marci@301
|
720 |
// typedef typename AugGraph::Edge AugEdge;
|
|
marci@301
|
721 |
// typename Graph::NodeMap<int> used; //0
|
|
marci@301
|
722 |
|
|
marci@301
|
723 |
// public:
|
|
marci@301
|
724 |
// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
|
|
marci@301
|
725 |
// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
|
|
marci@301
|
726 |
// bool augmentOnShortestPath() {
|
|
marci@301
|
727 |
// AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@301
|
728 |
// bool _augment=false;
|
|
marci@301
|
729 |
|
|
marci@301
|
730 |
// typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@360
|
731 |
// BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
|
|
marci@301
|
732 |
// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@301
|
733 |
// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@301
|
734 |
// if ((S->get(s)) && (used.get(s)<1) ) {
|
|
marci@301
|
735 |
// //Number u=0;
|
|
marci@301
|
736 |
// //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@301
|
737 |
// //u+=flow->get(e);
|
|
marci@301
|
738 |
// //if (u<1) {
|
|
marci@301
|
739 |
// bfs.pushAndSetReached(s);
|
|
marci@301
|
740 |
// pred.set(s, AugEdge(INVALID));
|
|
marci@301
|
741 |
// //}
|
|
marci@301
|
742 |
// }
|
|
marci@301
|
743 |
// }
|
|
marci@301
|
744 |
|
|
marci@301
|
745 |
// typename AugGraph::NodeMap<Number> free(res_graph);
|
|
marci@301
|
746 |
|
|
marci@301
|
747 |
// Node n;
|
|
marci@301
|
748 |
// //searching for augmenting path
|
|
marci@301
|
749 |
// while ( !bfs.finished() ) {
|
|
marci@301
|
750 |
// AugOutEdgeIt e=bfs;
|
|
marci@301
|
751 |
// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@301
|
752 |
// Node v=res_graph.tail(e);
|
|
marci@301
|
753 |
// Node w=res_graph.head(e);
|
|
marci@301
|
754 |
// pred.set(w, e);
|
|
marci@301
|
755 |
// if (res_graph.valid(pred.get(v))) {
|
|
marci@301
|
756 |
// free.set(w, std::min(free.get(v), res_graph.free(e)));
|
|
marci@301
|
757 |
// } else {
|
|
marci@301
|
758 |
// free.set(w, res_graph.free(e));
|
|
marci@301
|
759 |
// }
|
|
marci@301
|
760 |
// n=res_graph.head(e);
|
|
marci@301
|
761 |
// if (T->get(n) && (used.get(n)<1) ) {
|
|
marci@301
|
762 |
// //Number u=0;
|
|
marci@301
|
763 |
// //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
|
|
marci@301
|
764 |
// //u+=flow->get(f);
|
|
marci@301
|
765 |
// //if (u<1) {
|
|
marci@301
|
766 |
// _augment=true;
|
|
marci@301
|
767 |
// break;
|
|
marci@301
|
768 |
// //}
|
|
marci@301
|
769 |
// }
|
|
marci@301
|
770 |
// }
|
|
marci@301
|
771 |
|
|
marci@301
|
772 |
// ++bfs;
|
|
marci@301
|
773 |
// } //end of searching augmenting path
|
|
marci@301
|
774 |
|
|
marci@301
|
775 |
// if (_augment) {
|
|
marci@301
|
776 |
// //Node n=t;
|
|
marci@301
|
777 |
// used.set(n, 1); //mind2 vegen jav
|
|
marci@301
|
778 |
// Number augment_value=free.get(n);
|
|
marci@301
|
779 |
// while (res_graph.valid(pred.get(n))) {
|
|
marci@301
|
780 |
// AugEdge e=pred.get(n);
|
|
marci@301
|
781 |
// res_graph.augment(e, augment_value);
|
|
marci@301
|
782 |
// n=res_graph.tail(e);
|
|
marci@301
|
783 |
// }
|
|
marci@301
|
784 |
// used.set(n, 1); //mind2 vegen jav
|
|
marci@301
|
785 |
// }
|
|
marci@301
|
786 |
|
|
marci@301
|
787 |
// return _augment;
|
|
marci@301
|
788 |
// }
|
|
marci@301
|
789 |
|
|
marci@301
|
790 |
// // template<typename MutableGraph> bool augmentOnBlockingFlow() {
|
|
marci@301
|
791 |
// // bool _augment=false;
|
|
marci@301
|
792 |
|
|
marci@301
|
793 |
// // AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@301
|
794 |
|
|
marci@301
|
795 |
// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@301
|
796 |
// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
|
|
marci@301
|
797 |
|
|
marci@301
|
798 |
|
|
marci@301
|
799 |
|
|
marci@301
|
800 |
|
|
marci@301
|
801 |
|
|
marci@301
|
802 |
// // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@301
|
803 |
// // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@301
|
804 |
// // if (S->get(s)) {
|
|
marci@301
|
805 |
// // Number u=0;
|
|
marci@301
|
806 |
// // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@301
|
807 |
// // u+=flow->get(e);
|
|
marci@301
|
808 |
// // if (u<1) {
|
|
marci@301
|
809 |
// // bfs.pushAndSetReached(s);
|
|
marci@301
|
810 |
// // //pred.set(s, AugEdge(INVALID));
|
|
marci@301
|
811 |
// // }
|
|
marci@301
|
812 |
// // }
|
|
marci@301
|
813 |
// // }
|
|
marci@301
|
814 |
|
|
marci@301
|
815 |
|
|
marci@301
|
816 |
|
|
marci@301
|
817 |
|
|
marci@301
|
818 |
// // //bfs.pushAndSetReached(s);
|
|
marci@301
|
819 |
// // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@301
|
820 |
// // while ( !bfs.finished() ) {
|
|
marci@301
|
821 |
// // AugOutEdgeIt e=bfs;
|
|
marci@301
|
822 |
// // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@301
|
823 |
// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@301
|
824 |
// // }
|
|
marci@301
|
825 |
|
|
marci@301
|
826 |
// // ++bfs;
|
|
marci@301
|
827 |
// // } //computing distances from s in the residual graph
|
|
marci@301
|
828 |
|
|
marci@301
|
829 |
// // MutableGraph F;
|
|
marci@301
|
830 |
// // typename AugGraph::NodeMap<typename MutableGraph::Node>
|
|
marci@301
|
831 |
// // res_graph_to_F(res_graph);
|
|
marci@301
|
832 |
// // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@301
|
833 |
// // res_graph_to_F.set(n, F.addNode());
|
|
marci@301
|
834 |
// // }
|
|
marci@301
|
835 |
|
|
marci@301
|
836 |
// // typename MutableGraph::Node sF=res_graph_to_F.get(s);
|
|
marci@301
|
837 |
// // typename MutableGraph::Node tF=res_graph_to_F.get(t);
|
|
marci@301
|
838 |
|
|
marci@301
|
839 |
// // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
|
|
marci@301
|
840 |
// // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
|
|
marci@301
|
841 |
|
|
marci@301
|
842 |
// // //Making F to the graph containing the edges of the residual graph
|
|
marci@301
|
843 |
// // //which are in some shortest paths
|
|
marci@301
|
844 |
// // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
|
|
marci@301
|
845 |
// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
|
|
marci@301
|
846 |
// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
|
|
marci@301
|
847 |
// // original_edge.update();
|
|
marci@301
|
848 |
// // original_edge.set(f, e);
|
|
marci@301
|
849 |
// // residual_capacity.update();
|
|
marci@301
|
850 |
// // residual_capacity.set(f, res_graph.free(e));
|
|
marci@301
|
851 |
// // }
|
|
marci@301
|
852 |
// // }
|
|
marci@301
|
853 |
|
|
marci@301
|
854 |
// // bool __augment=true;
|
|
marci@301
|
855 |
|
|
marci@301
|
856 |
// // while (__augment) {
|
|
marci@301
|
857 |
// // __augment=false;
|
|
marci@301
|
858 |
// // //computing blocking flow with dfs
|
|
marci@301
|
859 |
// // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
|
|
marci@301
|
860 |
// // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
|
|
marci@301
|
861 |
// // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
|
|
marci@301
|
862 |
// // pred.set(sF, typename MutableGraph::Edge(INVALID));
|
|
marci@301
|
863 |
// // //invalid iterators for sources
|
|
marci@301
|
864 |
|
|
marci@301
|
865 |
// // typename MutableGraph::NodeMap<Number> free(F);
|
|
marci@301
|
866 |
|
|
marci@301
|
867 |
// // dfs.pushAndSetReached(sF);
|
|
marci@301
|
868 |
// // while (!dfs.finished()) {
|
|
marci@301
|
869 |
// // ++dfs;
|
|
marci@301
|
870 |
// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
|
|
marci@301
|
871 |
// // if (dfs.isBNodeNewlyReached()) {
|
|
marci@301
|
872 |
// // typename MutableGraph::Node v=F.aNode(dfs);
|
|
marci@301
|
873 |
// // typename MutableGraph::Node w=F.bNode(dfs);
|
|
marci@301
|
874 |
// // pred.set(w, dfs);
|
|
marci@301
|
875 |
// // if (F.valid(pred.get(v))) {
|
|
marci@301
|
876 |
// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
|
|
marci@301
|
877 |
// // } else {
|
|
marci@301
|
878 |
// // free.set(w, residual_capacity.get(dfs));
|
|
marci@301
|
879 |
// // }
|
|
marci@301
|
880 |
// // if (w==tF) {
|
|
marci@301
|
881 |
// // __augment=true;
|
|
marci@301
|
882 |
// // _augment=true;
|
|
marci@301
|
883 |
// // break;
|
|
marci@301
|
884 |
// // }
|
|
marci@301
|
885 |
|
|
marci@301
|
886 |
// // } else {
|
|
marci@301
|
887 |
// // F.erase(typename MutableGraph::OutEdgeIt(dfs));
|
|
marci@301
|
888 |
// // }
|
|
marci@301
|
889 |
// // }
|
|
marci@301
|
890 |
// // }
|
|
marci@301
|
891 |
|
|
marci@301
|
892 |
// // if (__augment) {
|
|
marci@301
|
893 |
// // typename MutableGraph::Node n=tF;
|
|
marci@301
|
894 |
// // Number augment_value=free.get(tF);
|
|
marci@301
|
895 |
// // while (F.valid(pred.get(n))) {
|
|
marci@301
|
896 |
// // typename MutableGraph::Edge e=pred.get(n);
|
|
marci@301
|
897 |
// // res_graph.augment(original_edge.get(e), augment_value);
|
|
marci@301
|
898 |
// // n=F.tail(e);
|
|
marci@301
|
899 |
// // if (residual_capacity.get(e)==augment_value)
|
|
marci@301
|
900 |
// // F.erase(e);
|
|
marci@301
|
901 |
// // else
|
|
marci@301
|
902 |
// // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
|
|
marci@301
|
903 |
// // }
|
|
marci@301
|
904 |
// // }
|
|
marci@301
|
905 |
|
|
marci@301
|
906 |
// // }
|
|
marci@301
|
907 |
|
|
marci@301
|
908 |
// // return _augment;
|
|
marci@301
|
909 |
// // }
|
|
marci@301
|
910 |
// bool augmentOnBlockingFlow2() {
|
|
marci@301
|
911 |
// bool _augment=false;
|
|
marci@301
|
912 |
|
|
marci@301
|
913 |
// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
|
|
marci@301
|
914 |
// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
|
|
marci@301
|
915 |
// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
|
|
marci@301
|
916 |
// typedef typename EAugGraph::Edge EAugEdge;
|
|
marci@301
|
917 |
|
|
marci@301
|
918 |
// EAugGraph res_graph(*G, *flow, *capacity);
|
|
marci@301
|
919 |
|
|
marci@301
|
920 |
// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
|
|
marci@360
|
921 |
// BfsIterator<
|
|
marci@301
|
922 |
// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
|
|
marci@301
|
923 |
// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
|
|
marci@301
|
924 |
// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
|
|
marci@301
|
925 |
|
|
marci@301
|
926 |
|
|
marci@301
|
927 |
// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@301
|
928 |
// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@301
|
929 |
// if (S->get(s)) {
|
|
marci@301
|
930 |
// Number u=0;
|
|
marci@301
|
931 |
// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@301
|
932 |
// u+=flow->get(e);
|
|
marci@301
|
933 |
// if (u<1) {
|
|
marci@301
|
934 |
// bfs.pushAndSetReached(s);
|
|
marci@301
|
935 |
// //pred.set(s, AugEdge(INVALID));
|
|
marci@301
|
936 |
// }
|
|
marci@301
|
937 |
// }
|
|
marci@301
|
938 |
// }
|
|
marci@301
|
939 |
|
|
marci@301
|
940 |
|
|
marci@301
|
941 |
// //bfs.pushAndSetReached(s);
|
|
marci@301
|
942 |
|
|
marci@301
|
943 |
// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
|
|
marci@301
|
944 |
// NodeMap<int>& dist=res_graph.dist;
|
|
marci@301
|
945 |
|
|
marci@301
|
946 |
// while ( !bfs.finished() ) {
|
|
marci@301
|
947 |
// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
|
|
marci@301
|
948 |
// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@301
|
949 |
// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@301
|
950 |
// }
|
|
marci@301
|
951 |
// ++bfs;
|
|
marci@301
|
952 |
// } //computing distances from s in the residual graph
|
|
marci@301
|
953 |
|
|
marci@301
|
954 |
// bool __augment=true;
|
|
marci@301
|
955 |
|
|
marci@301
|
956 |
// while (__augment) {
|
|
marci@301
|
957 |
|
|
marci@301
|
958 |
// __augment=false;
|
|
marci@301
|
959 |
// //computing blocking flow with dfs
|
|
marci@301
|
960 |
// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
|
|
marci@360
|
961 |
// DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
|
|
marci@301
|
962 |
// dfs(res_graph);
|
|
marci@301
|
963 |
// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
|
|
marci@301
|
964 |
// //pred.set(s, EAugEdge(INVALID));
|
|
marci@301
|
965 |
// //invalid iterators for sources
|
|
marci@301
|
966 |
|
|
marci@301
|
967 |
// typename EAugGraph::NodeMap<Number> free(res_graph);
|
|
marci@301
|
968 |
|
|
marci@301
|
969 |
|
|
marci@301
|
970 |
// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@301
|
971 |
// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@301
|
972 |
// if (S->get(s)) {
|
|
marci@301
|
973 |
// Number u=0;
|
|
marci@301
|
974 |
// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@301
|
975 |
// u+=flow->get(e);
|
|
marci@301
|
976 |
// if (u<1) {
|
|
marci@301
|
977 |
// dfs.pushAndSetReached(s);
|
|
marci@301
|
978 |
// //pred.set(s, AugEdge(INVALID));
|
|
marci@301
|
979 |
// }
|
|
marci@301
|
980 |
// }
|
|
marci@301
|
981 |
// }
|
|
marci@301
|
982 |
|
|
marci@301
|
983 |
|
|
marci@301
|
984 |
|
|
marci@301
|
985 |
// //dfs.pushAndSetReached(s);
|
|
marci@301
|
986 |
// typename EAugGraph::Node n;
|
|
marci@301
|
987 |
// while (!dfs.finished()) {
|
|
marci@301
|
988 |
// ++dfs;
|
|
marci@301
|
989 |
// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
|
|
marci@301
|
990 |
// if (dfs.isBNodeNewlyReached()) {
|
|
marci@301
|
991 |
|
|
marci@301
|
992 |
// typename EAugGraph::Node v=res_graph.aNode(dfs);
|
|
marci@301
|
993 |
// typename EAugGraph::Node w=res_graph.bNode(dfs);
|
|
marci@301
|
994 |
|
|
marci@301
|
995 |
// pred.set(w, EAugOutEdgeIt(dfs));
|
|
marci@301
|
996 |
// if (res_graph.valid(pred.get(v))) {
|
|
marci@301
|
997 |
// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
|
|
marci@301
|
998 |
// } else {
|
|
marci@301
|
999 |
// free.set(w, res_graph.free(dfs));
|
|
marci@301
|
1000 |
// }
|
|
marci@301
|
1001 |
|
|
marci@301
|
1002 |
// n=w;
|
|
marci@301
|
1003 |
// if (T->get(w)) {
|
|
marci@301
|
1004 |
// Number u=0;
|
|
marci@301
|
1005 |
// for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
|
|
marci@301
|
1006 |
// u+=flow->get(f);
|
|
marci@301
|
1007 |
// if (u<1) {
|
|
marci@301
|
1008 |
// __augment=true;
|
|
marci@301
|
1009 |
// _augment=true;
|
|
marci@301
|
1010 |
// break;
|
|
marci@301
|
1011 |
// }
|
|
marci@301
|
1012 |
// }
|
|
marci@301
|
1013 |
// } else {
|
|
marci@301
|
1014 |
// res_graph.erase(dfs);
|
|
marci@301
|
1015 |
// }
|
|
marci@301
|
1016 |
// }
|
|
marci@301
|
1017 |
|
|
marci@301
|
1018 |
// }
|
|
marci@301
|
1019 |
|
|
marci@301
|
1020 |
// if (__augment) {
|
|
marci@301
|
1021 |
// // typename EAugGraph::Node n=t;
|
|
marci@301
|
1022 |
// Number augment_value=free.get(n);
|
|
marci@301
|
1023 |
// while (res_graph.valid(pred.get(n))) {
|
|
marci@301
|
1024 |
// EAugEdge e=pred.get(n);
|
|
marci@301
|
1025 |
// res_graph.augment(e, augment_value);
|
|
marci@301
|
1026 |
// n=res_graph.tail(e);
|
|
marci@301
|
1027 |
// if (res_graph.free(e)==0)
|
|
marci@301
|
1028 |
// res_graph.erase(e);
|
|
marci@301
|
1029 |
// }
|
|
marci@301
|
1030 |
// }
|
|
marci@301
|
1031 |
|
|
marci@301
|
1032 |
// }
|
|
marci@301
|
1033 |
|
|
marci@301
|
1034 |
// return _augment;
|
|
marci@301
|
1035 |
// }
|
|
marci@301
|
1036 |
// void run() {
|
|
marci@301
|
1037 |
// //int num_of_augmentations=0;
|
|
marci@301
|
1038 |
// while (augmentOnShortestPath()) {
|
|
marci@301
|
1039 |
// //while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@301
|
1040 |
// //std::cout << ++num_of_augmentations << " ";
|
|
marci@301
|
1041 |
// //std::cout<<std::endl;
|
|
marci@301
|
1042 |
// }
|
|
marci@301
|
1043 |
// }
|
|
marci@301
|
1044 |
// // template<typename MutableGraph> void run() {
|
|
marci@301
|
1045 |
// // //int num_of_augmentations=0;
|
|
marci@301
|
1046 |
// // //while (augmentOnShortestPath()) {
|
|
marci@301
|
1047 |
// // while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@301
|
1048 |
// // //std::cout << ++num_of_augmentations << " ";
|
|
marci@301
|
1049 |
// // //std::cout<<std::endl;
|
|
marci@301
|
1050 |
// // }
|
|
marci@301
|
1051 |
// // }
|
|
marci@301
|
1052 |
// Number flowValue() {
|
|
marci@301
|
1053 |
// Number a=0;
|
|
marci@301
|
1054 |
// EdgeIt e;
|
|
marci@301
|
1055 |
// for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
|
|
marci@301
|
1056 |
// a+=flow->get(e);
|
|
marci@301
|
1057 |
// }
|
|
marci@301
|
1058 |
// return a;
|
|
marci@301
|
1059 |
// }
|
|
marci@301
|
1060 |
// };
|
|
marci@301
|
1061 |
|
|
marci@301
|
1062 |
|
|
marci@301
|
1063 |
|
|
marci@301
|
1064 |
|
|
marci@301
|
1065 |
|
|
marci@301
|
1066 |
|
|
marci@301
|
1067 |
// // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
|
|
marci@301
|
1068 |
// // class MaxFlow2 {
|
|
marci@301
|
1069 |
// // public:
|
|
marci@301
|
1070 |
// // typedef typename Graph::Node Node;
|
|
marci@301
|
1071 |
// // typedef typename Graph::Edge Edge;
|
|
marci@301
|
1072 |
// // typedef typename Graph::EdgeIt EdgeIt;
|
|
marci@301
|
1073 |
// // typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
marci@301
|
1074 |
// // typedef typename Graph::InEdgeIt InEdgeIt;
|
|
marci@301
|
1075 |
// // private:
|
|
marci@301
|
1076 |
// // const Graph& G;
|
|
marci@301
|
1077 |
// // std::list<Node>& S;
|
|
marci@301
|
1078 |
// // std::list<Node>& T;
|
|
marci@301
|
1079 |
// // FlowMap& flow;
|
|
marci@301
|
1080 |
// // const CapacityMap& capacity;
|
|
marci@301
|
1081 |
// // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
|
|
marci@301
|
1082 |
// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
|
|
marci@301
|
1083 |
// // typedef typename AugGraph::Edge AugEdge;
|
|
marci@301
|
1084 |
// // typename Graph::NodeMap<bool> SMap;
|
|
marci@301
|
1085 |
// // typename Graph::NodeMap<bool> TMap;
|
|
marci@301
|
1086 |
// // public:
|
|
marci@301
|
1087 |
// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
|
|
marci@301
|
1088 |
// // for(typename std::list<Node>::const_iterator i=S.begin();
|
|
marci@301
|
1089 |
// // i!=S.end(); ++i) {
|
|
marci@301
|
1090 |
// // SMap.set(*i, true);
|
|
marci@301
|
1091 |
// // }
|
|
marci@301
|
1092 |
// // for (typename std::list<Node>::const_iterator i=T.begin();
|
|
marci@301
|
1093 |
// // i!=T.end(); ++i) {
|
|
marci@301
|
1094 |
// // TMap.set(*i, true);
|
|
marci@301
|
1095 |
// // }
|
|
marci@301
|
1096 |
// // }
|
|
marci@301
|
1097 |
// // bool augment() {
|
|
marci@301
|
1098 |
// // AugGraph res_graph(G, flow, capacity);
|
|
marci@301
|
1099 |
// // bool _augment=false;
|
|
marci@301
|
1100 |
// // Node reached_t_node;
|
|
marci@301
|
1101 |
|
|
marci@301
|
1102 |
// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@301
|
1103 |
// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
|
|
marci@301
|
1104 |
// // for(typename std::list<Node>::const_iterator i=S.begin();
|
|
marci@301
|
1105 |
// // i!=S.end(); ++i) {
|
|
marci@301
|
1106 |
// // bfs.pushAndSetReached(*i);
|
|
marci@301
|
1107 |
// // }
|
|
marci@301
|
1108 |
// // //bfs.pushAndSetReached(s);
|
|
marci@301
|
1109 |
|
|
marci@301
|
1110 |
// // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@301
|
1111 |
// // //filled up with invalid iterators
|
|
marci@301
|
1112 |
|
|
marci@301
|
1113 |
// // typename AugGraph::NodeMap<Number> free(res_graph);
|
|
marci@301
|
1114 |
|
|
marci@301
|
1115 |
// // //searching for augmenting path
|
|
marci@301
|
1116 |
// // while ( !bfs.finished() ) {
|
|
marci@301
|
1117 |
// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
|
|
marci@301
|
1118 |
// // if (e.valid() && bfs.isBNodeNewlyReached()) {
|
|
marci@301
|
1119 |
// // Node v=res_graph.tail(e);
|
|
marci@301
|
1120 |
// // Node w=res_graph.head(e);
|
|
marci@301
|
1121 |
// // pred.set(w, e);
|
|
marci@301
|
1122 |
// // if (pred.get(v).valid()) {
|
|
marci@301
|
1123 |
// // free.set(w, std::min(free.get(v), e.free()));
|
|
marci@301
|
1124 |
// // } else {
|
|
marci@301
|
1125 |
// // free.set(w, e.free());
|
|
marci@301
|
1126 |
// // }
|
|
marci@301
|
1127 |
// // if (TMap.get(res_graph.head(e))) {
|
|
marci@301
|
1128 |
// // _augment=true;
|
|
marci@301
|
1129 |
// // reached_t_node=res_graph.head(e);
|
|
marci@301
|
1130 |
// // break;
|
|
marci@301
|
1131 |
// // }
|
|
marci@301
|
1132 |
// // }
|
|
marci@301
|
1133 |
|
|
marci@301
|
1134 |
// // ++bfs;
|
|
marci@301
|
1135 |
// // } //end of searching augmenting path
|
|
marci@301
|
1136 |
|
|
marci@301
|
1137 |
// // if (_augment) {
|
|
marci@301
|
1138 |
// // Node n=reached_t_node;
|
|
marci@301
|
1139 |
// // Number augment_value=free.get(reached_t_node);
|
|
marci@301
|
1140 |
// // while (pred.get(n).valid()) {
|
|
marci@301
|
1141 |
// // AugEdge e=pred.get(n);
|
|
marci@301
|
1142 |
// // e.augment(augment_value);
|
|
marci@301
|
1143 |
// // n=res_graph.tail(e);
|
|
marci@301
|
1144 |
// // }
|
|
marci@301
|
1145 |
// // }
|
|
marci@301
|
1146 |
|
|
marci@301
|
1147 |
// // return _augment;
|
|
marci@301
|
1148 |
// // }
|
|
marci@301
|
1149 |
// // void run() {
|
|
marci@301
|
1150 |
// // while (augment()) { }
|
|
marci@301
|
1151 |
// // }
|
|
marci@301
|
1152 |
// // Number flowValue() {
|
|
marci@301
|
1153 |
// // Number a=0;
|
|
marci@301
|
1154 |
// // for(typename std::list<Node>::const_iterator i=S.begin();
|
|
marci@301
|
1155 |
// // i!=S.end(); ++i) {
|
|
marci@301
|
1156 |
// // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
|
|
marci@301
|
1157 |
// // a+=flow.get(e);
|
|
marci@301
|
1158 |
// // }
|
|
marci@301
|
1159 |
// // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
|
|
marci@301
|
1160 |
// // a-=flow.get(e);
|
|
marci@301
|
1161 |
// // }
|
|
marci@301
|
1162 |
// // }
|
|
marci@301
|
1163 |
// // return a;
|
|
marci@301
|
1164 |
// // }
|
|
marci@301
|
1165 |
// // };
|
|
marci@301
|
1166 |
|
|
marci@301
|
1167 |
|
|
marci@301
|
1168 |
} // namespace hugo
|
|
marci@301
|
1169 |
|
|
marci@301
|
1170 |
#endif //HUGO_EDMONDS_KARP_H
|