|
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@174
|
250 |
template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
|
|
marci@174
|
251 |
class MaxFlow {
|
|
marci@174
|
252 |
public:
|
|
marci@174
|
253 |
typedef typename Graph::Node Node;
|
|
marci@174
|
254 |
typedef typename Graph::Edge Edge;
|
|
marci@174
|
255 |
typedef typename Graph::EdgeIt EdgeIt;
|
|
marci@174
|
256 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
marci@174
|
257 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
|
marci@174
|
258 |
|
|
marci@174
|
259 |
private:
|
|
marci@174
|
260 |
const Graph* G;
|
|
marci@174
|
261 |
Node s;
|
|
marci@174
|
262 |
Node t;
|
|
marci@174
|
263 |
FlowMap* flow;
|
|
marci@174
|
264 |
const CapacityMap* capacity;
|
|
marci@174
|
265 |
typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
|
|
marci@174
|
266 |
typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
|
|
marci@174
|
267 |
typedef typename AugGraph::Edge AugEdge;
|
|
marci@174
|
268 |
|
|
marci@174
|
269 |
public:
|
|
marci@174
|
270 |
MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
|
|
marci@191
|
271 |
G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
|
|
marci@174
|
272 |
bool augmentOnShortestPath() {
|
|
marci@174
|
273 |
AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@174
|
274 |
bool _augment=false;
|
|
marci@174
|
275 |
|
|
marci@174
|
276 |
typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@174
|
277 |
BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
|
|
marci@174
|
278 |
res_bfs.pushAndSetReached(s);
|
|
marci@174
|
279 |
|
|
marci@174
|
280 |
typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@174
|
281 |
pred.set(s, AugEdge(INVALID));
|
|
marci@174
|
282 |
|
|
marci@174
|
283 |
typename AugGraph::NodeMap<Number> free(res_graph);
|
|
marci@174
|
284 |
|
|
marci@174
|
285 |
//searching for augmenting path
|
|
marci@174
|
286 |
while ( !res_bfs.finished() ) {
|
|
marci@191
|
287 |
AugOutEdgeIt e=res_bfs;
|
|
marci@174
|
288 |
if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
|
|
marci@174
|
289 |
Node v=res_graph.tail(e);
|
|
marci@174
|
290 |
Node w=res_graph.head(e);
|
|
marci@174
|
291 |
pred.set(w, e);
|
|
marci@174
|
292 |
if (res_graph.valid(pred.get(v))) {
|
|
marci@174
|
293 |
free.set(w, std::min(free.get(v), res_graph.free(e)));
|
|
marci@174
|
294 |
} else {
|
|
marci@174
|
295 |
free.set(w, res_graph.free(e));
|
|
marci@174
|
296 |
}
|
|
marci@174
|
297 |
if (res_graph.head(e)==t) { _augment=true; break; }
|
|
marci@174
|
298 |
}
|
|
marci@174
|
299 |
|
|
marci@174
|
300 |
++res_bfs;
|
|
marci@174
|
301 |
} //end of searching augmenting path
|
|
marci@174
|
302 |
|
|
marci@174
|
303 |
if (_augment) {
|
|
marci@174
|
304 |
Node n=t;
|
|
marci@174
|
305 |
Number augment_value=free.get(t);
|
|
marci@174
|
306 |
while (res_graph.valid(pred.get(n))) {
|
|
marci@174
|
307 |
AugEdge e=pred.get(n);
|
|
marci@174
|
308 |
res_graph.augment(e, augment_value);
|
|
marci@174
|
309 |
n=res_graph.tail(e);
|
|
marci@174
|
310 |
}
|
|
marci@174
|
311 |
}
|
|
marci@174
|
312 |
|
|
marci@174
|
313 |
return _augment;
|
|
marci@174
|
314 |
}
|
|
marci@174
|
315 |
|
|
marci@263
|
316 |
// template<typename MutableGraph> bool augmentOnBlockingFlow() {
|
|
marci@263
|
317 |
// bool _augment=false;
|
|
marci@263
|
318 |
|
|
marci@263
|
319 |
// AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@263
|
320 |
|
|
marci@263
|
321 |
// typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@263
|
322 |
// BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
|
|
marci@263
|
323 |
|
|
marci@263
|
324 |
// bfs.pushAndSetReached(s);
|
|
marci@263
|
325 |
// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@263
|
326 |
// while ( !bfs.finished() ) {
|
|
marci@263
|
327 |
// AugOutEdgeIt e=bfs;
|
|
marci@263
|
328 |
// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@263
|
329 |
// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@263
|
330 |
// }
|
|
marci@263
|
331 |
|
|
marci@263
|
332 |
// ++bfs;
|
|
marci@263
|
333 |
// } //computing distances from s in the residual graph
|
|
marci@263
|
334 |
|
|
marci@263
|
335 |
// MutableGraph F;
|
|
marci@263
|
336 |
// typename AugGraph::NodeMap<typename MutableGraph::Node>
|
|
marci@263
|
337 |
// res_graph_to_F(res_graph);
|
|
marci@263
|
338 |
// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@263
|
339 |
// res_graph_to_F.set(n, F.addNode());
|
|
marci@263
|
340 |
// }
|
|
marci@263
|
341 |
|
|
marci@263
|
342 |
// typename MutableGraph::Node sF=res_graph_to_F.get(s);
|
|
marci@263
|
343 |
// typename MutableGraph::Node tF=res_graph_to_F.get(t);
|
|
marci@263
|
344 |
|
|
marci@263
|
345 |
// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
|
|
marci@263
|
346 |
// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
|
|
marci@263
|
347 |
|
|
marci@263
|
348 |
// //Making F to the graph containing the edges of the residual graph
|
|
marci@263
|
349 |
// //which are in some shortest paths
|
|
marci@263
|
350 |
// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
|
|
marci@263
|
351 |
// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
|
|
marci@263
|
352 |
// 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@263
|
353 |
// original_edge.update();
|
|
marci@263
|
354 |
// original_edge.set(f, e);
|
|
marci@263
|
355 |
// residual_capacity.update();
|
|
marci@263
|
356 |
// residual_capacity.set(f, res_graph.free(e));
|
|
marci@263
|
357 |
// }
|
|
marci@263
|
358 |
// }
|
|
marci@263
|
359 |
|
|
marci@263
|
360 |
// bool __augment=true;
|
|
marci@263
|
361 |
|
|
marci@263
|
362 |
// while (__augment) {
|
|
marci@263
|
363 |
// __augment=false;
|
|
marci@263
|
364 |
// //computing blocking flow with dfs
|
|
marci@263
|
365 |
// typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
|
|
marci@263
|
366 |
// DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
|
|
marci@263
|
367 |
// typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
|
|
marci@263
|
368 |
// pred.set(sF, typename MutableGraph::Edge(INVALID));
|
|
marci@263
|
369 |
// //invalid iterators for sources
|
|
marci@263
|
370 |
|
|
marci@263
|
371 |
// typename MutableGraph::NodeMap<Number> free(F);
|
|
marci@263
|
372 |
|
|
marci@263
|
373 |
// dfs.pushAndSetReached(sF);
|
|
marci@263
|
374 |
// while (!dfs.finished()) {
|
|
marci@263
|
375 |
// ++dfs;
|
|
marci@263
|
376 |
// if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
|
|
marci@263
|
377 |
// if (dfs.isBNodeNewlyReached()) {
|
|
marci@263
|
378 |
// typename MutableGraph::Node v=F.aNode(dfs);
|
|
marci@263
|
379 |
// typename MutableGraph::Node w=F.bNode(dfs);
|
|
marci@263
|
380 |
// pred.set(w, dfs);
|
|
marci@263
|
381 |
// if (F.valid(pred.get(v))) {
|
|
marci@263
|
382 |
// free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
|
|
marci@263
|
383 |
// } else {
|
|
marci@263
|
384 |
// free.set(w, residual_capacity.get(dfs));
|
|
marci@263
|
385 |
// }
|
|
marci@263
|
386 |
// if (w==tF) {
|
|
marci@263
|
387 |
// __augment=true;
|
|
marci@263
|
388 |
// _augment=true;
|
|
marci@263
|
389 |
// break;
|
|
marci@263
|
390 |
// }
|
|
marci@263
|
391 |
|
|
marci@263
|
392 |
// } else {
|
|
marci@263
|
393 |
// F.erase(typename MutableGraph::OutEdgeIt(dfs));
|
|
marci@263
|
394 |
// }
|
|
marci@263
|
395 |
// }
|
|
marci@263
|
396 |
// }
|
|
marci@263
|
397 |
|
|
marci@263
|
398 |
// if (__augment) {
|
|
marci@263
|
399 |
// typename MutableGraph::Node n=tF;
|
|
marci@263
|
400 |
// Number augment_value=free.get(tF);
|
|
marci@263
|
401 |
// while (F.valid(pred.get(n))) {
|
|
marci@263
|
402 |
// typename MutableGraph::Edge e=pred.get(n);
|
|
marci@263
|
403 |
// res_graph.augment(original_edge.get(e), augment_value);
|
|
marci@263
|
404 |
// n=F.tail(e);
|
|
marci@263
|
405 |
// if (residual_capacity.get(e)==augment_value)
|
|
marci@263
|
406 |
// F.erase(e);
|
|
marci@263
|
407 |
// else
|
|
marci@263
|
408 |
// residual_capacity.set(e, residual_capacity.get(e)-augment_value);
|
|
marci@263
|
409 |
// }
|
|
marci@263
|
410 |
// }
|
|
marci@263
|
411 |
|
|
marci@263
|
412 |
// }
|
|
marci@263
|
413 |
|
|
marci@263
|
414 |
// return _augment;
|
|
marci@263
|
415 |
// }
|
|
marci@263
|
416 |
|
|
marci@263
|
417 |
template<typename GraphWrapper>
|
|
marci@263
|
418 |
class DistanceMap {
|
|
marci@263
|
419 |
protected:
|
|
marci@263
|
420 |
GraphWrapper gw;
|
|
marci@263
|
421 |
typename GraphWrapper::NodeMap<int> dist;
|
|
marci@263
|
422 |
public:
|
|
marci@263
|
423 |
DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
|
|
marci@263
|
424 |
//NodeMap(const ListGraph& _G, T a) :
|
|
marci@263
|
425 |
//G(_G), container(G.node_id, a) { }
|
|
marci@263
|
426 |
void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
|
|
marci@263
|
427 |
int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
|
|
marci@263
|
428 |
bool get(const typename GraphWrapper::Edge& e) const {
|
|
marci@263
|
429 |
return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
|
|
marci@263
|
430 |
}
|
|
marci@263
|
431 |
//typename std::vector<T>::reference operator[](Node n) {
|
|
marci@263
|
432 |
//return container[/*G.id(n)*/n.node->id]; }
|
|
marci@263
|
433 |
//typename std::vector<T>::const_reference operator[](Node n) const {
|
|
marci@263
|
434 |
//return container[/*G.id(n)*/n.node->id];
|
|
marci@263
|
435 |
};
|
|
marci@263
|
436 |
|
|
marci@191
|
437 |
template<typename MutableGraph> bool augmentOnBlockingFlow() {
|
|
marci@174
|
438 |
bool _augment=false;
|
|
marci@174
|
439 |
|
|
marci@174
|
440 |
AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@174
|
441 |
|
|
marci@174
|
442 |
typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@263
|
443 |
BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
|
|
marci@174
|
444 |
|
|
marci@174
|
445 |
bfs.pushAndSetReached(s);
|
|
marci@263
|
446 |
//typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@263
|
447 |
DistanceMap<AugGraph> dist(res_graph);
|
|
marci@174
|
448 |
while ( !bfs.finished() ) {
|
|
marci@191
|
449 |
AugOutEdgeIt e=bfs;
|
|
marci@174
|
450 |
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@174
|
451 |
dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@174
|
452 |
}
|
|
marci@174
|
453 |
++bfs;
|
|
marci@174
|
454 |
} //computing distances from s in the residual graph
|
|
marci@174
|
455 |
|
|
marci@263
|
456 |
// MutableGraph F;
|
|
marci@263
|
457 |
// typename AugGraph::NodeMap<typename MutableGraph::Node>
|
|
marci@263
|
458 |
// res_graph_to_F(res_graph);
|
|
marci@263
|
459 |
// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@263
|
460 |
// res_graph_to_F.set(n, F.addNode());
|
|
marci@263
|
461 |
// }
|
|
marci@263
|
462 |
|
|
marci@263
|
463 |
// typename MutableGraph::Node sF=res_graph_to_F.get(s);
|
|
marci@263
|
464 |
// typename MutableGraph::Node tF=res_graph_to_F.get(t);
|
|
marci@263
|
465 |
|
|
marci@263
|
466 |
// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
|
|
marci@263
|
467 |
// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
|
|
marci@263
|
468 |
|
|
marci@263
|
469 |
// //Making F to the graph containing the edges of the residual graph
|
|
marci@263
|
470 |
// //which are in some shortest paths
|
|
marci@263
|
471 |
// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
|
|
marci@263
|
472 |
// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
|
|
marci@263
|
473 |
// 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@263
|
474 |
// original_edge.update();
|
|
marci@263
|
475 |
// original_edge.set(f, e);
|
|
marci@263
|
476 |
// residual_capacity.update();
|
|
marci@263
|
477 |
// residual_capacity.set(f, res_graph.free(e));
|
|
marci@263
|
478 |
// }
|
|
marci@263
|
479 |
// }
|
|
marci@263
|
480 |
|
|
marci@174
|
481 |
MutableGraph F;
|
|
marci@263
|
482 |
typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
|
|
marci@263
|
483 |
FilterResGraph filter_res_graph(res_graph, dist);
|
|
marci@174
|
484 |
typename AugGraph::NodeMap<typename MutableGraph::Node>
|
|
marci@174
|
485 |
res_graph_to_F(res_graph);
|
|
marci@174
|
486 |
for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@174
|
487 |
res_graph_to_F.set(n, F.addNode());
|
|
marci@174
|
488 |
}
|
|
marci@174
|
489 |
|
|
marci@174
|
490 |
typename MutableGraph::Node sF=res_graph_to_F.get(s);
|
|
marci@174
|
491 |
typename MutableGraph::Node tF=res_graph_to_F.get(t);
|
|
marci@174
|
492 |
|
|
marci@174
|
493 |
typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
|
|
marci@174
|
494 |
typename MutableGraph::EdgeMap<Number> residual_capacity(F);
|
|
marci@174
|
495 |
|
|
marci@174
|
496 |
//Making F to the graph containing the edges of the residual graph
|
|
marci@174
|
497 |
//which are in some shortest paths
|
|
marci@174
|
498 |
for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
|
|
marci@174
|
499 |
if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
|
|
marci@174
|
500 |
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@174
|
501 |
original_edge.update();
|
|
marci@174
|
502 |
original_edge.set(f, e);
|
|
marci@174
|
503 |
residual_capacity.update();
|
|
marci@174
|
504 |
residual_capacity.set(f, res_graph.free(e));
|
|
marci@174
|
505 |
}
|
|
marci@174
|
506 |
}
|
|
marci@174
|
507 |
|
|
marci@174
|
508 |
bool __augment=true;
|
|
marci@174
|
509 |
|
|
marci@174
|
510 |
while (__augment) {
|
|
marci@174
|
511 |
__augment=false;
|
|
marci@174
|
512 |
//computing blocking flow with dfs
|
|
marci@243
|
513 |
typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
|
|
marci@263
|
514 |
DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
|
|
marci@174
|
515 |
typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
|
|
marci@174
|
516 |
pred.set(sF, typename MutableGraph::Edge(INVALID));
|
|
marci@174
|
517 |
//invalid iterators for sources
|
|
marci@174
|
518 |
|
|
marci@174
|
519 |
typename MutableGraph::NodeMap<Number> free(F);
|
|
marci@174
|
520 |
|
|
marci@174
|
521 |
dfs.pushAndSetReached(sF);
|
|
marci@174
|
522 |
while (!dfs.finished()) {
|
|
marci@174
|
523 |
++dfs;
|
|
marci@174
|
524 |
if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
|
|
marci@174
|
525 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@174
|
526 |
typename MutableGraph::Node v=F.aNode(dfs);
|
|
marci@174
|
527 |
typename MutableGraph::Node w=F.bNode(dfs);
|
|
marci@174
|
528 |
pred.set(w, dfs);
|
|
marci@174
|
529 |
if (F.valid(pred.get(v))) {
|
|
marci@174
|
530 |
free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
|
|
marci@174
|
531 |
} else {
|
|
marci@174
|
532 |
free.set(w, residual_capacity.get(dfs));
|
|
marci@174
|
533 |
}
|
|
marci@174
|
534 |
if (w==tF) {
|
|
marci@174
|
535 |
__augment=true;
|
|
marci@174
|
536 |
_augment=true;
|
|
marci@174
|
537 |
break;
|
|
marci@174
|
538 |
}
|
|
marci@174
|
539 |
|
|
marci@174
|
540 |
} else {
|
|
marci@174
|
541 |
F.erase(typename MutableGraph::OutEdgeIt(dfs));
|
|
marci@174
|
542 |
}
|
|
marci@174
|
543 |
}
|
|
marci@174
|
544 |
}
|
|
marci@174
|
545 |
|
|
marci@174
|
546 |
if (__augment) {
|
|
marci@174
|
547 |
typename MutableGraph::Node n=tF;
|
|
marci@174
|
548 |
Number augment_value=free.get(tF);
|
|
marci@174
|
549 |
while (F.valid(pred.get(n))) {
|
|
marci@174
|
550 |
typename MutableGraph::Edge e=pred.get(n);
|
|
marci@174
|
551 |
res_graph.augment(original_edge.get(e), augment_value);
|
|
marci@174
|
552 |
n=F.tail(e);
|
|
marci@174
|
553 |
if (residual_capacity.get(e)==augment_value)
|
|
marci@174
|
554 |
F.erase(e);
|
|
marci@174
|
555 |
else
|
|
marci@174
|
556 |
residual_capacity.set(e, residual_capacity.get(e)-augment_value);
|
|
marci@174
|
557 |
}
|
|
marci@174
|
558 |
}
|
|
marci@174
|
559 |
|
|
marci@174
|
560 |
}
|
|
marci@174
|
561 |
|
|
marci@174
|
562 |
return _augment;
|
|
marci@174
|
563 |
}
|
|
marci@263
|
564 |
|
|
marci@206
|
565 |
template<typename MutableGraph> bool augmentOnBlockingFlow1() {
|
|
marci@206
|
566 |
bool _augment=false;
|
|
marci@206
|
567 |
|
|
marci@206
|
568 |
AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@206
|
569 |
|
|
marci@206
|
570 |
//bfs for distances on the residual graph
|
|
marci@206
|
571 |
typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@263
|
572 |
BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
|
|
marci@206
|
573 |
bfs.pushAndSetReached(s);
|
|
marci@206
|
574 |
typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@206
|
575 |
|
|
marci@206
|
576 |
//F will contain the physical copy of the residual graph
|
|
marci@206
|
577 |
//with the set of edges which areon shortest paths
|
|
marci@206
|
578 |
MutableGraph F;
|
|
marci@206
|
579 |
typename AugGraph::NodeMap<typename MutableGraph::Node>
|
|
marci@206
|
580 |
res_graph_to_F(res_graph);
|
|
marci@206
|
581 |
for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@206
|
582 |
res_graph_to_F.set(n, F.addNode());
|
|
marci@206
|
583 |
}
|
|
marci@206
|
584 |
typename MutableGraph::Node sF=res_graph_to_F.get(s);
|
|
marci@206
|
585 |
typename MutableGraph::Node tF=res_graph_to_F.get(t);
|
|
marci@206
|
586 |
typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
|
|
marci@206
|
587 |
typename MutableGraph::EdgeMap<Number> residual_capacity(F);
|
|
marci@206
|
588 |
|
|
marci@206
|
589 |
while ( !bfs.finished() ) {
|
|
marci@206
|
590 |
AugOutEdgeIt e=bfs;
|
|
marci@206
|
591 |
if (res_graph.valid(e)) {
|
|
marci@206
|
592 |
if (bfs.isBNodeNewlyReached()) {
|
|
marci@206
|
593 |
dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@206
|
594 |
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@206
|
595 |
original_edge.update();
|
|
marci@206
|
596 |
original_edge.set(f, e);
|
|
marci@206
|
597 |
residual_capacity.update();
|
|
marci@206
|
598 |
residual_capacity.set(f, res_graph.free(e));
|
|
marci@206
|
599 |
} else {
|
|
marci@206
|
600 |
if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
|
|
marci@206
|
601 |
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@206
|
602 |
original_edge.update();
|
|
marci@206
|
603 |
original_edge.set(f, e);
|
|
marci@206
|
604 |
residual_capacity.update();
|
|
marci@206
|
605 |
residual_capacity.set(f, res_graph.free(e));
|
|
marci@206
|
606 |
}
|
|
marci@206
|
607 |
}
|
|
marci@206
|
608 |
}
|
|
marci@206
|
609 |
++bfs;
|
|
marci@206
|
610 |
} //computing distances from s in the residual graph
|
|
marci@206
|
611 |
|
|
marci@206
|
612 |
bool __augment=true;
|
|
marci@206
|
613 |
|
|
marci@206
|
614 |
while (__augment) {
|
|
marci@206
|
615 |
__augment=false;
|
|
marci@206
|
616 |
//computing blocking flow with dfs
|
|
marci@243
|
617 |
typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
|
|
marci@243
|
618 |
DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
|
|
marci@206
|
619 |
typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
|
|
marci@206
|
620 |
pred.set(sF, typename MutableGraph::Edge(INVALID));
|
|
marci@206
|
621 |
//invalid iterators for sources
|
|
marci@206
|
622 |
|
|
marci@206
|
623 |
typename MutableGraph::NodeMap<Number> free(F);
|
|
marci@206
|
624 |
|
|
marci@206
|
625 |
dfs.pushAndSetReached(sF);
|
|
marci@206
|
626 |
while (!dfs.finished()) {
|
|
marci@206
|
627 |
++dfs;
|
|
marci@206
|
628 |
if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
|
|
marci@206
|
629 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@206
|
630 |
typename MutableGraph::Node v=F.aNode(dfs);
|
|
marci@206
|
631 |
typename MutableGraph::Node w=F.bNode(dfs);
|
|
marci@206
|
632 |
pred.set(w, dfs);
|
|
marci@206
|
633 |
if (F.valid(pred.get(v))) {
|
|
marci@206
|
634 |
free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
|
|
marci@206
|
635 |
} else {
|
|
marci@206
|
636 |
free.set(w, residual_capacity.get(dfs));
|
|
marci@206
|
637 |
}
|
|
marci@206
|
638 |
if (w==tF) {
|
|
marci@206
|
639 |
__augment=true;
|
|
marci@206
|
640 |
_augment=true;
|
|
marci@206
|
641 |
break;
|
|
marci@206
|
642 |
}
|
|
marci@206
|
643 |
|
|
marci@206
|
644 |
} else {
|
|
marci@206
|
645 |
F.erase(typename MutableGraph::OutEdgeIt(dfs));
|
|
marci@206
|
646 |
}
|
|
marci@206
|
647 |
}
|
|
marci@206
|
648 |
}
|
|
marci@206
|
649 |
|
|
marci@206
|
650 |
if (__augment) {
|
|
marci@206
|
651 |
typename MutableGraph::Node n=tF;
|
|
marci@206
|
652 |
Number augment_value=free.get(tF);
|
|
marci@206
|
653 |
while (F.valid(pred.get(n))) {
|
|
marci@206
|
654 |
typename MutableGraph::Edge e=pred.get(n);
|
|
marci@206
|
655 |
res_graph.augment(original_edge.get(e), augment_value);
|
|
marci@206
|
656 |
n=F.tail(e);
|
|
marci@206
|
657 |
if (residual_capacity.get(e)==augment_value)
|
|
marci@206
|
658 |
F.erase(e);
|
|
marci@206
|
659 |
else
|
|
marci@206
|
660 |
residual_capacity.set(e, residual_capacity.get(e)-augment_value);
|
|
marci@206
|
661 |
}
|
|
marci@206
|
662 |
}
|
|
marci@206
|
663 |
|
|
marci@206
|
664 |
}
|
|
marci@206
|
665 |
|
|
marci@206
|
666 |
return _augment;
|
|
marci@206
|
667 |
}
|
|
marci@174
|
668 |
bool augmentOnBlockingFlow2() {
|
|
marci@174
|
669 |
bool _augment=false;
|
|
marci@174
|
670 |
|
|
marci@174
|
671 |
//typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
|
|
marci@174
|
672 |
typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
|
|
marci@174
|
673 |
typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
|
|
marci@174
|
674 |
typedef typename EAugGraph::Edge EAugEdge;
|
|
marci@174
|
675 |
|
|
marci@174
|
676 |
EAugGraph res_graph(*G, *flow, *capacity);
|
|
marci@174
|
677 |
|
|
marci@174
|
678 |
//typedef typename EAugGraph::NodeMap<bool> ReachedMap;
|
|
marci@243
|
679 |
BfsIterator5<
|
|
marci@174
|
680 |
ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
|
|
marci@243
|
681 |
/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
|
|
marci@174
|
682 |
ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
|
|
marci@174
|
683 |
|
|
marci@191
|
684 |
bfs.pushAndSetReached(s);
|
|
marci@174
|
685 |
|
|
marci@174
|
686 |
typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
|
|
marci@174
|
687 |
NodeMap<int>& dist=res_graph.dist;
|
|
marci@174
|
688 |
|
|
marci@174
|
689 |
while ( !bfs.finished() ) {
|
|
marci@175
|
690 |
typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
|
|
marci@174
|
691 |
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@174
|
692 |
dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@174
|
693 |
}
|
|
marci@174
|
694 |
++bfs;
|
|
marci@174
|
695 |
} //computing distances from s in the residual graph
|
|
marci@174
|
696 |
|
|
marci@174
|
697 |
bool __augment=true;
|
|
marci@174
|
698 |
|
|
marci@174
|
699 |
while (__augment) {
|
|
marci@174
|
700 |
|
|
marci@174
|
701 |
__augment=false;
|
|
marci@174
|
702 |
//computing blocking flow with dfs
|
|
marci@174
|
703 |
typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
|
|
marci@243
|
704 |
DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
|
|
marci@174
|
705 |
dfs(res_graph);
|
|
marci@174
|
706 |
typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
|
|
marci@174
|
707 |
pred.set(s, EAugEdge(INVALID));
|
|
marci@174
|
708 |
//invalid iterators for sources
|
|
marci@174
|
709 |
|
|
marci@174
|
710 |
typename EAugGraph::NodeMap<Number> free(res_graph);
|
|
marci@174
|
711 |
|
|
marci@174
|
712 |
dfs.pushAndSetReached(s);
|
|
marci@174
|
713 |
while (!dfs.finished()) {
|
|
marci@174
|
714 |
++dfs;
|
|
marci@174
|
715 |
if (res_graph.valid(EAugOutEdgeIt(dfs))) {
|
|
marci@174
|
716 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@174
|
717 |
|
|
marci@174
|
718 |
typename EAugGraph::Node v=res_graph.aNode(dfs);
|
|
marci@174
|
719 |
typename EAugGraph::Node w=res_graph.bNode(dfs);
|
|
marci@174
|
720 |
|
|
marci@174
|
721 |
pred.set(w, EAugOutEdgeIt(dfs));
|
|
marci@174
|
722 |
if (res_graph.valid(pred.get(v))) {
|
|
marci@191
|
723 |
free.set(w, std::min(free.get(v), res_graph.free(dfs)));
|
|
marci@174
|
724 |
} else {
|
|
marci@191
|
725 |
free.set(w, res_graph.free(dfs));
|
|
marci@174
|
726 |
}
|
|
marci@174
|
727 |
|
|
marci@174
|
728 |
if (w==t) {
|
|
marci@174
|
729 |
__augment=true;
|
|
marci@174
|
730 |
_augment=true;
|
|
marci@174
|
731 |
break;
|
|
marci@174
|
732 |
}
|
|
marci@174
|
733 |
} else {
|
|
marci@174
|
734 |
res_graph.erase(dfs);
|
|
marci@174
|
735 |
}
|
|
marci@174
|
736 |
}
|
|
marci@174
|
737 |
|
|
marci@174
|
738 |
}
|
|
marci@174
|
739 |
|
|
marci@174
|
740 |
if (__augment) {
|
|
marci@174
|
741 |
typename EAugGraph::Node n=t;
|
|
marci@174
|
742 |
Number augment_value=free.get(t);
|
|
marci@174
|
743 |
while (res_graph.valid(pred.get(n))) {
|
|
marci@174
|
744 |
EAugEdge e=pred.get(n);
|
|
marci@174
|
745 |
res_graph.augment(e, augment_value);
|
|
marci@174
|
746 |
n=res_graph.tail(e);
|
|
marci@174
|
747 |
if (res_graph.free(e)==0)
|
|
marci@174
|
748 |
res_graph.erase(e);
|
|
marci@174
|
749 |
}
|
|
marci@174
|
750 |
}
|
|
marci@174
|
751 |
|
|
marci@174
|
752 |
}
|
|
marci@174
|
753 |
|
|
marci@174
|
754 |
return _augment;
|
|
marci@174
|
755 |
}
|
|
marci@174
|
756 |
void run() {
|
|
marci@174
|
757 |
//int num_of_augmentations=0;
|
|
marci@174
|
758 |
while (augmentOnShortestPath()) {
|
|
marci@174
|
759 |
//while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@174
|
760 |
//std::cout << ++num_of_augmentations << " ";
|
|
marci@174
|
761 |
//std::cout<<std::endl;
|
|
marci@174
|
762 |
}
|
|
marci@174
|
763 |
}
|
|
marci@174
|
764 |
template<typename MutableGraph> void run() {
|
|
marci@174
|
765 |
//int num_of_augmentations=0;
|
|
marci@174
|
766 |
//while (augmentOnShortestPath()) {
|
|
marci@174
|
767 |
while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@174
|
768 |
//std::cout << ++num_of_augmentations << " ";
|
|
marci@174
|
769 |
//std::cout<<std::endl;
|
|
marci@174
|
770 |
}
|
|
marci@174
|
771 |
}
|
|
marci@174
|
772 |
Number flowValue() {
|
|
marci@174
|
773 |
Number a=0;
|
|
marci@174
|
774 |
OutEdgeIt e;
|
|
marci@174
|
775 |
for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
|
|
marci@174
|
776 |
a+=flow->get(e);
|
|
marci@174
|
777 |
}
|
|
marci@174
|
778 |
return a;
|
|
marci@174
|
779 |
}
|
|
marci@174
|
780 |
};
|
|
marci@174
|
781 |
|
|
marci@193
|
782 |
|
|
marci@193
|
783 |
template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
|
|
marci@193
|
784 |
class MaxMatching {
|
|
marci@193
|
785 |
public:
|
|
marci@193
|
786 |
typedef typename Graph::Node Node;
|
|
marci@194
|
787 |
typedef typename Graph::NodeIt NodeIt;
|
|
marci@193
|
788 |
typedef typename Graph::Edge Edge;
|
|
marci@193
|
789 |
typedef typename Graph::EdgeIt EdgeIt;
|
|
marci@193
|
790 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
marci@193
|
791 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
|
marci@193
|
792 |
|
|
marci@193
|
793 |
typedef typename Graph::NodeMap<bool> SMap;
|
|
marci@193
|
794 |
typedef typename Graph::NodeMap<bool> TMap;
|
|
marci@193
|
795 |
private:
|
|
marci@193
|
796 |
const Graph* G;
|
|
marci@193
|
797 |
SMap* S;
|
|
marci@193
|
798 |
TMap* T;
|
|
marci@193
|
799 |
//Node s;
|
|
marci@193
|
800 |
//Node t;
|
|
marci@193
|
801 |
FlowMap* flow;
|
|
marci@193
|
802 |
const CapacityMap* capacity;
|
|
marci@193
|
803 |
typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
|
|
marci@193
|
804 |
typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
|
|
marci@193
|
805 |
typedef typename AugGraph::Edge AugEdge;
|
|
marci@198
|
806 |
typename Graph::NodeMap<int> used; //0
|
|
marci@193
|
807 |
|
|
marci@193
|
808 |
public:
|
|
marci@193
|
809 |
MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
|
|
marci@198
|
810 |
G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
|
|
marci@193
|
811 |
bool augmentOnShortestPath() {
|
|
marci@193
|
812 |
AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@193
|
813 |
bool _augment=false;
|
|
marci@193
|
814 |
|
|
marci@193
|
815 |
typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@193
|
816 |
BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
|
|
marci@193
|
817 |
typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@193
|
818 |
for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@198
|
819 |
if ((S->get(s)) && (used.get(s)<1) ) {
|
|
marci@198
|
820 |
//Number u=0;
|
|
marci@198
|
821 |
//for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@198
|
822 |
//u+=flow->get(e);
|
|
marci@198
|
823 |
//if (u<1) {
|
|
marci@196
|
824 |
res_bfs.pushAndSetReached(s);
|
|
marci@196
|
825 |
pred.set(s, AugEdge(INVALID));
|
|
marci@198
|
826 |
//}
|
|
marci@193
|
827 |
}
|
|
marci@193
|
828 |
}
|
|
marci@193
|
829 |
|
|
marci@193
|
830 |
typename AugGraph::NodeMap<Number> free(res_graph);
|
|
marci@193
|
831 |
|
|
marci@193
|
832 |
Node n;
|
|
marci@193
|
833 |
//searching for augmenting path
|
|
marci@193
|
834 |
while ( !res_bfs.finished() ) {
|
|
marci@193
|
835 |
AugOutEdgeIt e=res_bfs;
|
|
marci@193
|
836 |
if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
|
|
marci@193
|
837 |
Node v=res_graph.tail(e);
|
|
marci@193
|
838 |
Node w=res_graph.head(e);
|
|
marci@193
|
839 |
pred.set(w, e);
|
|
marci@193
|
840 |
if (res_graph.valid(pred.get(v))) {
|
|
marci@193
|
841 |
free.set(w, std::min(free.get(v), res_graph.free(e)));
|
|
marci@193
|
842 |
} else {
|
|
marci@193
|
843 |
free.set(w, res_graph.free(e));
|
|
marci@193
|
844 |
}
|
|
marci@197
|
845 |
n=res_graph.head(e);
|
|
marci@198
|
846 |
if (T->get(n) && (used.get(n)<1) ) {
|
|
marci@198
|
847 |
//Number u=0;
|
|
marci@198
|
848 |
//for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
|
|
marci@198
|
849 |
//u+=flow->get(f);
|
|
marci@198
|
850 |
//if (u<1) {
|
|
marci@197
|
851 |
_augment=true;
|
|
marci@197
|
852 |
break;
|
|
marci@198
|
853 |
//}
|
|
marci@193
|
854 |
}
|
|
marci@193
|
855 |
}
|
|
marci@193
|
856 |
|
|
marci@193
|
857 |
++res_bfs;
|
|
marci@193
|
858 |
} //end of searching augmenting path
|
|
marci@193
|
859 |
|
|
marci@193
|
860 |
if (_augment) {
|
|
marci@193
|
861 |
//Node n=t;
|
|
marci@198
|
862 |
used.set(n, 1); //mind2 vegen jav
|
|
marci@194
|
863 |
Number augment_value=free.get(n);
|
|
marci@193
|
864 |
while (res_graph.valid(pred.get(n))) {
|
|
marci@193
|
865 |
AugEdge e=pred.get(n);
|
|
marci@193
|
866 |
res_graph.augment(e, augment_value);
|
|
marci@193
|
867 |
n=res_graph.tail(e);
|
|
marci@193
|
868 |
}
|
|
marci@198
|
869 |
used.set(n, 1); //mind2 vegen jav
|
|
marci@193
|
870 |
}
|
|
marci@193
|
871 |
|
|
marci@193
|
872 |
return _augment;
|
|
marci@193
|
873 |
}
|
|
marci@193
|
874 |
|
|
marci@193
|
875 |
// template<typename MutableGraph> bool augmentOnBlockingFlow() {
|
|
marci@193
|
876 |
// bool _augment=false;
|
|
marci@193
|
877 |
|
|
marci@193
|
878 |
// AugGraph res_graph(*G, *flow, *capacity);
|
|
marci@193
|
879 |
|
|
marci@193
|
880 |
// typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@193
|
881 |
// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
|
|
marci@193
|
882 |
|
|
marci@197
|
883 |
|
|
marci@197
|
884 |
|
|
marci@197
|
885 |
|
|
marci@197
|
886 |
|
|
marci@197
|
887 |
// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@197
|
888 |
// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@197
|
889 |
// if (S->get(s)) {
|
|
marci@197
|
890 |
// Number u=0;
|
|
marci@197
|
891 |
// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@197
|
892 |
// u+=flow->get(e);
|
|
marci@197
|
893 |
// if (u<1) {
|
|
marci@197
|
894 |
// res_bfs.pushAndSetReached(s);
|
|
marci@197
|
895 |
// //pred.set(s, AugEdge(INVALID));
|
|
marci@197
|
896 |
// }
|
|
marci@197
|
897 |
// }
|
|
marci@197
|
898 |
// }
|
|
marci@197
|
899 |
|
|
marci@197
|
900 |
|
|
marci@197
|
901 |
|
|
marci@197
|
902 |
|
|
marci@197
|
903 |
// //bfs.pushAndSetReached(s);
|
|
marci@193
|
904 |
// typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
|
|
marci@193
|
905 |
// while ( !bfs.finished() ) {
|
|
marci@193
|
906 |
// AugOutEdgeIt e=bfs;
|
|
marci@193
|
907 |
// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@193
|
908 |
// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@193
|
909 |
// }
|
|
marci@193
|
910 |
|
|
marci@193
|
911 |
// ++bfs;
|
|
marci@193
|
912 |
// } //computing distances from s in the residual graph
|
|
marci@193
|
913 |
|
|
marci@193
|
914 |
// MutableGraph F;
|
|
marci@193
|
915 |
// typename AugGraph::NodeMap<typename MutableGraph::Node>
|
|
marci@193
|
916 |
// res_graph_to_F(res_graph);
|
|
marci@193
|
917 |
// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
|
|
marci@193
|
918 |
// res_graph_to_F.set(n, F.addNode());
|
|
marci@193
|
919 |
// }
|
|
marci@193
|
920 |
|
|
marci@193
|
921 |
// typename MutableGraph::Node sF=res_graph_to_F.get(s);
|
|
marci@193
|
922 |
// typename MutableGraph::Node tF=res_graph_to_F.get(t);
|
|
marci@193
|
923 |
|
|
marci@193
|
924 |
// typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
|
|
marci@193
|
925 |
// typename MutableGraph::EdgeMap<Number> residual_capacity(F);
|
|
marci@193
|
926 |
|
|
marci@193
|
927 |
// //Making F to the graph containing the edges of the residual graph
|
|
marci@193
|
928 |
// //which are in some shortest paths
|
|
marci@193
|
929 |
// for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
|
|
marci@193
|
930 |
// if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
|
|
marci@193
|
931 |
// 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@193
|
932 |
// original_edge.update();
|
|
marci@193
|
933 |
// original_edge.set(f, e);
|
|
marci@193
|
934 |
// residual_capacity.update();
|
|
marci@193
|
935 |
// residual_capacity.set(f, res_graph.free(e));
|
|
marci@193
|
936 |
// }
|
|
marci@193
|
937 |
// }
|
|
marci@193
|
938 |
|
|
marci@193
|
939 |
// bool __augment=true;
|
|
marci@193
|
940 |
|
|
marci@193
|
941 |
// while (__augment) {
|
|
marci@193
|
942 |
// __augment=false;
|
|
marci@193
|
943 |
// //computing blocking flow with dfs
|
|
marci@193
|
944 |
// typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
|
|
marci@193
|
945 |
// DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
|
|
marci@193
|
946 |
// typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
|
|
marci@193
|
947 |
// pred.set(sF, typename MutableGraph::Edge(INVALID));
|
|
marci@193
|
948 |
// //invalid iterators for sources
|
|
marci@193
|
949 |
|
|
marci@193
|
950 |
// typename MutableGraph::NodeMap<Number> free(F);
|
|
marci@193
|
951 |
|
|
marci@193
|
952 |
// dfs.pushAndSetReached(sF);
|
|
marci@193
|
953 |
// while (!dfs.finished()) {
|
|
marci@193
|
954 |
// ++dfs;
|
|
marci@193
|
955 |
// if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
|
|
marci@193
|
956 |
// if (dfs.isBNodeNewlyReached()) {
|
|
marci@193
|
957 |
// typename MutableGraph::Node v=F.aNode(dfs);
|
|
marci@193
|
958 |
// typename MutableGraph::Node w=F.bNode(dfs);
|
|
marci@193
|
959 |
// pred.set(w, dfs);
|
|
marci@193
|
960 |
// if (F.valid(pred.get(v))) {
|
|
marci@193
|
961 |
// free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
|
|
marci@193
|
962 |
// } else {
|
|
marci@193
|
963 |
// free.set(w, residual_capacity.get(dfs));
|
|
marci@193
|
964 |
// }
|
|
marci@193
|
965 |
// if (w==tF) {
|
|
marci@193
|
966 |
// __augment=true;
|
|
marci@193
|
967 |
// _augment=true;
|
|
marci@193
|
968 |
// break;
|
|
marci@193
|
969 |
// }
|
|
marci@193
|
970 |
|
|
marci@193
|
971 |
// } else {
|
|
marci@193
|
972 |
// F.erase(typename MutableGraph::OutEdgeIt(dfs));
|
|
marci@193
|
973 |
// }
|
|
marci@193
|
974 |
// }
|
|
marci@193
|
975 |
// }
|
|
marci@193
|
976 |
|
|
marci@193
|
977 |
// if (__augment) {
|
|
marci@193
|
978 |
// typename MutableGraph::Node n=tF;
|
|
marci@193
|
979 |
// Number augment_value=free.get(tF);
|
|
marci@193
|
980 |
// while (F.valid(pred.get(n))) {
|
|
marci@193
|
981 |
// typename MutableGraph::Edge e=pred.get(n);
|
|
marci@193
|
982 |
// res_graph.augment(original_edge.get(e), augment_value);
|
|
marci@193
|
983 |
// n=F.tail(e);
|
|
marci@193
|
984 |
// if (residual_capacity.get(e)==augment_value)
|
|
marci@193
|
985 |
// F.erase(e);
|
|
marci@193
|
986 |
// else
|
|
marci@193
|
987 |
// residual_capacity.set(e, residual_capacity.get(e)-augment_value);
|
|
marci@193
|
988 |
// }
|
|
marci@193
|
989 |
// }
|
|
marci@193
|
990 |
|
|
marci@193
|
991 |
// }
|
|
marci@193
|
992 |
|
|
marci@193
|
993 |
// return _augment;
|
|
marci@193
|
994 |
// }
|
|
marci@197
|
995 |
bool augmentOnBlockingFlow2() {
|
|
marci@197
|
996 |
bool _augment=false;
|
|
marci@193
|
997 |
|
|
marci@197
|
998 |
//typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
|
|
marci@197
|
999 |
typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
|
|
marci@197
|
1000 |
typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
|
|
marci@197
|
1001 |
typedef typename EAugGraph::Edge EAugEdge;
|
|
marci@193
|
1002 |
|
|
marci@197
|
1003 |
EAugGraph res_graph(*G, *flow, *capacity);
|
|
marci@193
|
1004 |
|
|
marci@197
|
1005 |
//typedef typename EAugGraph::NodeMap<bool> ReachedMap;
|
|
marci@243
|
1006 |
BfsIterator5<
|
|
marci@197
|
1007 |
ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
|
|
marci@243
|
1008 |
/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
|
|
marci@197
|
1009 |
ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
|
|
marci@197
|
1010 |
|
|
marci@197
|
1011 |
|
|
marci@197
|
1012 |
//typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@197
|
1013 |
for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@197
|
1014 |
if (S->get(s)) {
|
|
marci@197
|
1015 |
Number u=0;
|
|
marci@197
|
1016 |
for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@197
|
1017 |
u+=flow->get(e);
|
|
marci@197
|
1018 |
if (u<1) {
|
|
marci@197
|
1019 |
bfs.pushAndSetReached(s);
|
|
marci@197
|
1020 |
//pred.set(s, AugEdge(INVALID));
|
|
marci@197
|
1021 |
}
|
|
marci@197
|
1022 |
}
|
|
marci@197
|
1023 |
}
|
|
marci@197
|
1024 |
|
|
marci@193
|
1025 |
|
|
marci@197
|
1026 |
//bfs.pushAndSetReached(s);
|
|
marci@193
|
1027 |
|
|
marci@197
|
1028 |
typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
|
|
marci@197
|
1029 |
NodeMap<int>& dist=res_graph.dist;
|
|
marci@193
|
1030 |
|
|
marci@197
|
1031 |
while ( !bfs.finished() ) {
|
|
marci@197
|
1032 |
typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
|
|
marci@197
|
1033 |
if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
|
|
marci@197
|
1034 |
dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
|
|
marci@197
|
1035 |
}
|
|
marci@197
|
1036 |
++bfs;
|
|
marci@197
|
1037 |
} //computing distances from s in the residual graph
|
|
marci@193
|
1038 |
|
|
marci@197
|
1039 |
bool __augment=true;
|
|
marci@193
|
1040 |
|
|
marci@197
|
1041 |
while (__augment) {
|
|
marci@193
|
1042 |
|
|
marci@197
|
1043 |
__augment=false;
|
|
marci@197
|
1044 |
//computing blocking flow with dfs
|
|
marci@197
|
1045 |
typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
|
|
marci@243
|
1046 |
DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
|
|
marci@197
|
1047 |
dfs(res_graph);
|
|
marci@197
|
1048 |
typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
|
|
marci@197
|
1049 |
//pred.set(s, EAugEdge(INVALID));
|
|
marci@197
|
1050 |
//invalid iterators for sources
|
|
marci@193
|
1051 |
|
|
marci@197
|
1052 |
typename EAugGraph::NodeMap<Number> free(res_graph);
|
|
marci@193
|
1053 |
|
|
marci@197
|
1054 |
|
|
marci@197
|
1055 |
//typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@197
|
1056 |
for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
|
|
marci@197
|
1057 |
if (S->get(s)) {
|
|
marci@197
|
1058 |
Number u=0;
|
|
marci@197
|
1059 |
for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
|
|
marci@197
|
1060 |
u+=flow->get(e);
|
|
marci@197
|
1061 |
if (u<1) {
|
|
marci@197
|
1062 |
dfs.pushAndSetReached(s);
|
|
marci@197
|
1063 |
//pred.set(s, AugEdge(INVALID));
|
|
marci@197
|
1064 |
}
|
|
marci@197
|
1065 |
}
|
|
marci@197
|
1066 |
}
|
|
marci@197
|
1067 |
|
|
marci@197
|
1068 |
|
|
marci@197
|
1069 |
|
|
marci@197
|
1070 |
//dfs.pushAndSetReached(s);
|
|
marci@197
|
1071 |
typename EAugGraph::Node n;
|
|
marci@197
|
1072 |
while (!dfs.finished()) {
|
|
marci@197
|
1073 |
++dfs;
|
|
marci@197
|
1074 |
if (res_graph.valid(EAugOutEdgeIt(dfs))) {
|
|
marci@197
|
1075 |
if (dfs.isBNodeNewlyReached()) {
|
|
marci@193
|
1076 |
|
|
marci@197
|
1077 |
typename EAugGraph::Node v=res_graph.aNode(dfs);
|
|
marci@197
|
1078 |
typename EAugGraph::Node w=res_graph.bNode(dfs);
|
|
marci@193
|
1079 |
|
|
marci@197
|
1080 |
pred.set(w, EAugOutEdgeIt(dfs));
|
|
marci@197
|
1081 |
if (res_graph.valid(pred.get(v))) {
|
|
marci@197
|
1082 |
free.set(w, std::min(free.get(v), res_graph.free(dfs)));
|
|
marci@197
|
1083 |
} else {
|
|
marci@197
|
1084 |
free.set(w, res_graph.free(dfs));
|
|
marci@197
|
1085 |
}
|
|
marci@197
|
1086 |
|
|
marci@197
|
1087 |
n=w;
|
|
marci@197
|
1088 |
if (T->get(w)) {
|
|
marci@197
|
1089 |
Number u=0;
|
|
marci@197
|
1090 |
for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
|
|
marci@197
|
1091 |
u+=flow->get(f);
|
|
marci@197
|
1092 |
if (u<1) {
|
|
marci@197
|
1093 |
__augment=true;
|
|
marci@197
|
1094 |
_augment=true;
|
|
marci@197
|
1095 |
break;
|
|
marci@197
|
1096 |
}
|
|
marci@197
|
1097 |
}
|
|
marci@197
|
1098 |
} else {
|
|
marci@197
|
1099 |
res_graph.erase(dfs);
|
|
marci@197
|
1100 |
}
|
|
marci@197
|
1101 |
}
|
|
marci@193
|
1102 |
|
|
marci@197
|
1103 |
}
|
|
marci@193
|
1104 |
|
|
marci@197
|
1105 |
if (__augment) {
|
|
marci@197
|
1106 |
// typename EAugGraph::Node n=t;
|
|
marci@197
|
1107 |
Number augment_value=free.get(n);
|
|
marci@197
|
1108 |
while (res_graph.valid(pred.get(n))) {
|
|
marci@197
|
1109 |
EAugEdge e=pred.get(n);
|
|
marci@197
|
1110 |
res_graph.augment(e, augment_value);
|
|
marci@197
|
1111 |
n=res_graph.tail(e);
|
|
marci@197
|
1112 |
if (res_graph.free(e)==0)
|
|
marci@197
|
1113 |
res_graph.erase(e);
|
|
marci@197
|
1114 |
}
|
|
marci@197
|
1115 |
}
|
|
marci@193
|
1116 |
|
|
marci@197
|
1117 |
}
|
|
marci@193
|
1118 |
|
|
marci@197
|
1119 |
return _augment;
|
|
marci@197
|
1120 |
}
|
|
marci@193
|
1121 |
void run() {
|
|
marci@193
|
1122 |
//int num_of_augmentations=0;
|
|
marci@193
|
1123 |
while (augmentOnShortestPath()) {
|
|
marci@193
|
1124 |
//while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@193
|
1125 |
//std::cout << ++num_of_augmentations << " ";
|
|
marci@193
|
1126 |
//std::cout<<std::endl;
|
|
marci@193
|
1127 |
}
|
|
marci@193
|
1128 |
}
|
|
marci@194
|
1129 |
// template<typename MutableGraph> void run() {
|
|
marci@194
|
1130 |
// //int num_of_augmentations=0;
|
|
marci@194
|
1131 |
// //while (augmentOnShortestPath()) {
|
|
marci@194
|
1132 |
// while (augmentOnBlockingFlow<MutableGraph>()) {
|
|
marci@194
|
1133 |
// //std::cout << ++num_of_augmentations << " ";
|
|
marci@194
|
1134 |
// //std::cout<<std::endl;
|
|
marci@194
|
1135 |
// }
|
|
marci@194
|
1136 |
// }
|
|
marci@193
|
1137 |
Number flowValue() {
|
|
marci@193
|
1138 |
Number a=0;
|
|
marci@194
|
1139 |
EdgeIt e;
|
|
marci@194
|
1140 |
for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
|
|
marci@193
|
1141 |
a+=flow->get(e);
|
|
marci@193
|
1142 |
}
|
|
marci@193
|
1143 |
return a;
|
|
marci@193
|
1144 |
}
|
|
marci@193
|
1145 |
};
|
|
marci@193
|
1146 |
|
|
marci@193
|
1147 |
|
|
marci@193
|
1148 |
|
|
marci@193
|
1149 |
|
|
marci@193
|
1150 |
|
|
marci@174
|
1151 |
|
|
marci@174
|
1152 |
// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
|
|
marci@174
|
1153 |
// class MaxFlow2 {
|
|
marci@174
|
1154 |
// public:
|
|
marci@174
|
1155 |
// typedef typename Graph::Node Node;
|
|
marci@174
|
1156 |
// typedef typename Graph::Edge Edge;
|
|
marci@174
|
1157 |
// typedef typename Graph::EdgeIt EdgeIt;
|
|
marci@174
|
1158 |
// typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
marci@174
|
1159 |
// typedef typename Graph::InEdgeIt InEdgeIt;
|
|
marci@174
|
1160 |
// private:
|
|
marci@174
|
1161 |
// const Graph& G;
|
|
marci@174
|
1162 |
// std::list<Node>& S;
|
|
marci@174
|
1163 |
// std::list<Node>& T;
|
|
marci@174
|
1164 |
// FlowMap& flow;
|
|
marci@174
|
1165 |
// const CapacityMap& capacity;
|
|
marci@174
|
1166 |
// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
|
|
marci@174
|
1167 |
// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
|
|
marci@174
|
1168 |
// typedef typename AugGraph::Edge AugEdge;
|
|
marci@174
|
1169 |
// typename Graph::NodeMap<bool> SMap;
|
|
marci@174
|
1170 |
// typename Graph::NodeMap<bool> TMap;
|
|
marci@174
|
1171 |
// public:
|
|
marci@174
|
1172 |
// 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@174
|
1173 |
// for(typename std::list<Node>::const_iterator i=S.begin();
|
|
marci@174
|
1174 |
// i!=S.end(); ++i) {
|
|
marci@174
|
1175 |
// SMap.set(*i, true);
|
|
marci@174
|
1176 |
// }
|
|
marci@174
|
1177 |
// for (typename std::list<Node>::const_iterator i=T.begin();
|
|
marci@174
|
1178 |
// i!=T.end(); ++i) {
|
|
marci@174
|
1179 |
// TMap.set(*i, true);
|
|
marci@174
|
1180 |
// }
|
|
marci@174
|
1181 |
// }
|
|
marci@174
|
1182 |
// bool augment() {
|
|
marci@174
|
1183 |
// AugGraph res_graph(G, flow, capacity);
|
|
marci@174
|
1184 |
// bool _augment=false;
|
|
marci@174
|
1185 |
// Node reached_t_node;
|
|
marci@174
|
1186 |
|
|
marci@174
|
1187 |
// typedef typename AugGraph::NodeMap<bool> ReachedMap;
|
|
marci@174
|
1188 |
// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
|
|
marci@174
|
1189 |
// for(typename std::list<Node>::const_iterator i=S.begin();
|
|
marci@174
|
1190 |
// i!=S.end(); ++i) {
|
|
marci@174
|
1191 |
// res_bfs.pushAndSetReached(*i);
|
|
marci@174
|
1192 |
// }
|
|
marci@174
|
1193 |
// //res_bfs.pushAndSetReached(s);
|
|
marci@174
|
1194 |
|
|
marci@174
|
1195 |
// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
|
|
marci@174
|
1196 |
// //filled up with invalid iterators
|
|
marci@174
|
1197 |
|
|
marci@174
|
1198 |
// typename AugGraph::NodeMap<Number> free(res_graph);
|
|
marci@174
|
1199 |
|
|
marci@174
|
1200 |
// //searching for augmenting path
|
|
marci@174
|
1201 |
// while ( !res_bfs.finished() ) {
|
|
marci@174
|
1202 |
// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
|
|
marci@174
|
1203 |
// if (e.valid() && res_bfs.isBNodeNewlyReached()) {
|
|
marci@174
|
1204 |
// Node v=res_graph.tail(e);
|
|
marci@174
|
1205 |
// Node w=res_graph.head(e);
|
|
marci@174
|
1206 |
// pred.set(w, e);
|
|
marci@174
|
1207 |
// if (pred.get(v).valid()) {
|
|
marci@174
|
1208 |
// free.set(w, std::min(free.get(v), e.free()));
|
|
marci@174
|
1209 |
// } else {
|
|
marci@174
|
1210 |
// free.set(w, e.free());
|
|
marci@174
|
1211 |
// }
|
|
marci@174
|
1212 |
// if (TMap.get(res_graph.head(e))) {
|
|
marci@174
|
1213 |
// _augment=true;
|
|
marci@174
|
1214 |
// reached_t_node=res_graph.head(e);
|
|
marci@174
|
1215 |
// break;
|
|
marci@174
|
1216 |
// }
|
|
marci@174
|
1217 |
// }
|
|
marci@174
|
1218 |
|
|
marci@174
|
1219 |
// ++res_bfs;
|
|
marci@174
|
1220 |
// } //end of searching augmenting path
|
|
marci@174
|
1221 |
|
|
marci@174
|
1222 |
// if (_augment) {
|
|
marci@174
|
1223 |
// Node n=reached_t_node;
|
|
marci@174
|
1224 |
// Number augment_value=free.get(reached_t_node);
|
|
marci@174
|
1225 |
// while (pred.get(n).valid()) {
|
|
marci@174
|
1226 |
// AugEdge e=pred.get(n);
|
|
marci@174
|
1227 |
// e.augment(augment_value);
|
|
marci@174
|
1228 |
// n=res_graph.tail(e);
|
|
marci@174
|
1229 |
// }
|
|
marci@174
|
1230 |
// }
|
|
marci@174
|
1231 |
|
|
marci@174
|
1232 |
// return _augment;
|
|
marci@174
|
1233 |
// }
|
|
marci@174
|
1234 |
// void run() {
|
|
marci@174
|
1235 |
// while (augment()) { }
|
|
marci@174
|
1236 |
// }
|
|
marci@174
|
1237 |
// Number flowValue() {
|
|
marci@174
|
1238 |
// Number a=0;
|
|
marci@174
|
1239 |
// for(typename std::list<Node>::const_iterator i=S.begin();
|
|
marci@174
|
1240 |
// i!=S.end(); ++i) {
|
|
marci@174
|
1241 |
// for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
|
|
marci@174
|
1242 |
// a+=flow.get(e);
|
|
marci@174
|
1243 |
// }
|
|
marci@174
|
1244 |
// for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
|
|
marci@174
|
1245 |
// a-=flow.get(e);
|
|
marci@174
|
1246 |
// }
|
|
marci@174
|
1247 |
// }
|
|
marci@174
|
1248 |
// return a;
|
|
marci@174
|
1249 |
// }
|
|
marci@174
|
1250 |
// };
|
|
marci@174
|
1251 |
|
|
marci@174
|
1252 |
|
|
marci@174
|
1253 |
|
|
marci@174
|
1254 |
} // namespace hugo
|
|
marci@174
|
1255 |
|
|
marci@259
|
1256 |
#endif //HUGO_EDMONDS_KARP_H
|