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