1.1 --- a/src/work/edmonds_karp.hh Thu Mar 04 15:13:43 2004 +0000
1.2 +++ b/src/work/edmonds_karp.hh Thu Mar 04 19:38:07 2004 +0000
1.3 @@ -245,303 +245,6 @@
1.4 };
1.5 };
1.6
1.7 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.8 - class ResGraphWrapper {
1.9 - public:
1.10 - typedef typename Graph::NodeIt NodeIt;
1.11 - typedef typename Graph::EachNodeIt EachNodeIt;
1.12 - private:
1.13 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.14 - typedef typename Graph::InEdgeIt OldInEdgeIt;
1.15 - const Graph* G;
1.16 - FlowMap* flow;
1.17 - const CapacityMap* capacity;
1.18 - public:
1.19 - ResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.20 - const CapacityMap& _capacity) :
1.21 - G(&_G), flow(&_flow), capacity(&_capacity) { }
1.22 -// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
1.23 -// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
1.24 - class EdgeIt;
1.25 - class OutEdgeIt;
1.26 - friend class EdgeIt;
1.27 - friend class OutEdgeIt;
1.28 -
1.29 - class EdgeIt {
1.30 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.31 - protected:
1.32 - //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
1.33 - const Graph* G;
1.34 - FlowMap* flow;
1.35 - const CapacityMap* capacity;
1.36 - //OldSymEdgeIt sym;
1.37 - OldOutEdgeIt out;
1.38 - OldInEdgeIt in;
1.39 - bool out_or_in; //true, iff out
1.40 - public:
1.41 - EdgeIt() : out_or_in(true) { }
1.42 - EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
1.43 - G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
1.44 - //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
1.45 - Number free() const {
1.46 - if (out_or_in) {
1.47 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.48 - } else {
1.49 - return (/*resG->*/flow->get(in));
1.50 - }
1.51 - }
1.52 - bool valid() const {
1.53 - return out_or_in && out.valid() || in.valid(); }
1.54 - void augment(Number a) const {
1.55 - if (out_or_in) {
1.56 - /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
1.57 - } else {
1.58 - /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
1.59 - }
1.60 - }
1.61 - void print() {
1.62 - if (out_or_in) {
1.63 - std::cout << "out ";
1.64 - if (out.valid())
1.65 - std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
1.66 - else
1.67 - std::cout << "invalid";
1.68 - }
1.69 - else {
1.70 - std::cout << "in ";
1.71 - if (in.valid())
1.72 - std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
1.73 - else
1.74 - std::cout << "invalid";
1.75 - }
1.76 - std::cout << std::endl;
1.77 - }
1.78 - };
1.79 -
1.80 - Number free(OldOutEdgeIt out) const {
1.81 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.82 - }
1.83 - Number free(OldInEdgeIt in) const {
1.84 - return (/*resG->*/flow->get(in));
1.85 - }
1.86 -
1.87 - class OutEdgeIt : public EdgeIt {
1.88 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.89 - public:
1.90 - OutEdgeIt() { }
1.91 - private:
1.92 - OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.93 - //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
1.94 - G->getFirst(out, v);
1.95 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.96 - if (!out.valid()) {
1.97 - out_or_in=0;
1.98 - //in=/*resG->*/G->template first<OldInEdgeIt>(v);
1.99 - G->getFirst(in, v);
1.100 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.101 - }
1.102 - }
1.103 - public:
1.104 - OutEdgeIt& operator++() {
1.105 - if (out_or_in) {
1.106 - NodeIt v=/*resG->*/G->aNode(out);
1.107 - ++out;
1.108 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.109 - if (!out.valid()) {
1.110 - out_or_in=0;
1.111 - G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.112 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.113 - }
1.114 - } else {
1.115 - ++in;
1.116 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.117 - }
1.118 - return *this;
1.119 - }
1.120 - };
1.121 -
1.122 - class EachEdgeIt : public EdgeIt {
1.123 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.124 - typename Graph::EachNodeIt v;
1.125 - public:
1.126 - EachEdgeIt() { }
1.127 - //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
1.128 - EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.129 - out_or_in=true;
1.130 - G->getFirst(v);
1.131 - if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
1.132 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.133 - while (v.valid() && !out.valid()) {
1.134 - ++v;
1.135 - if (v.valid()) G->getFirst(out, v);
1.136 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.137 - }
1.138 - if (!out.valid()) {
1.139 - out_or_in=0;
1.140 - G->getFirst(v);
1.141 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.142 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.143 - while (v.valid() && !in.valid()) {
1.144 - ++v;
1.145 - if (v.valid()) G->getFirst(in, v);
1.146 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.147 - }
1.148 - }
1.149 - }
1.150 - EachEdgeIt& operator++() {
1.151 - if (out_or_in) {
1.152 - ++out;
1.153 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.154 - while (v.valid() && !out.valid()) {
1.155 - ++v;
1.156 - if (v.valid()) G->getFirst(out, v);
1.157 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.158 - }
1.159 - if (!out.valid()) {
1.160 - out_or_in=0;
1.161 - G->getFirst(v);
1.162 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.163 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.164 - while (v.valid() && !in.valid()) {
1.165 - ++v;
1.166 - if (v.valid()) G->getFirst(in, v);
1.167 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.168 - }
1.169 - }
1.170 - } else {
1.171 - ++in;
1.172 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.173 - while (v.valid() && !in.valid()) {
1.174 - ++v;
1.175 - if (v.valid()) G->getFirst(in, v);
1.176 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.177 - }
1.178 - }
1.179 - return *this;
1.180 - }
1.181 - };
1.182 -
1.183 - void getFirst(EachNodeIt& v) const { G->getFirst(v); }
1.184 - void getFirst(OutEdgeIt& e, NodeIt v) const {
1.185 - e=OutEdgeIt(*G, v, *flow, *capacity);
1.186 - }
1.187 - void getFirst(EachEdgeIt& e) const {
1.188 - e=EachEdgeIt(*G, *flow, *capacity);
1.189 - }
1.190 -
1.191 - EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
1.192 -
1.193 - OutEdgeIt& next(OutEdgeIt& e) const {
1.194 - if (e.out_or_in) {
1.195 - NodeIt v=G->aNode(e.out);
1.196 - ++(e.out);
1.197 - while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.198 - if (!G->valid(e.out)) {
1.199 - e.out_or_in=0;
1.200 - G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.201 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.202 - }
1.203 - } else {
1.204 - ++(e.in);
1.205 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.206 - }
1.207 - return e;
1.208 - }
1.209 -
1.210 - EachEdgeIt& next(EachEdgeIt& e) const {
1.211 - if (e.out_or_in) {
1.212 - ++(e.out);
1.213 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.214 - while (G->valid(e.v) && !G->valid(e.out)) {
1.215 - ++(e.v);
1.216 - if (G->valid(e.v)) G->getFirst(e.out, e.v);
1.217 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.218 - }
1.219 - if (!G->valid(e.out)) {
1.220 - e.out_or_in=0;
1.221 - G->getFirst(e.v);
1.222 - if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
1.223 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.224 - while (G->valid(e.v) && !G->valid(e.in)) {
1.225 - ++(e.v);
1.226 - if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.227 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.228 - }
1.229 - }
1.230 - } else {
1.231 - ++(e.in);
1.232 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.233 - while (G->valid(e.v) && !G->valid(e.in)) {
1.234 - ++(e.v);
1.235 - if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.236 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.237 - }
1.238 - }
1.239 - return e;
1.240 - }
1.241 -
1.242 -
1.243 - template< typename It >
1.244 - It first() const {
1.245 - It e;
1.246 - getFirst(e);
1.247 - return e;
1.248 - }
1.249 -
1.250 - template< typename It >
1.251 - It first(NodeIt v) const {
1.252 - It e;
1.253 - getFirst(e, v);
1.254 - return e;
1.255 - }
1.256 -
1.257 - NodeIt tail(EdgeIt e) const {
1.258 - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
1.259 - NodeIt head(EdgeIt e) const {
1.260 - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
1.261 -
1.262 - NodeIt aNode(OutEdgeIt e) const {
1.263 - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
1.264 - NodeIt bNode(OutEdgeIt e) const {
1.265 - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
1.266 -
1.267 - int id(NodeIt v) const { return G->id(v); }
1.268 -
1.269 - bool valid(NodeIt n) const { return G->valid(n); }
1.270 - bool valid(EdgeIt e) const {
1.271 - return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
1.272 -
1.273 - template <typename T>
1.274 - class NodeMap {
1.275 - typename Graph::NodeMap<T> node_map;
1.276 - public:
1.277 - NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
1.278 - NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
1.279 - void set(NodeIt nit, T a) { node_map.set(nit, a); }
1.280 - T get(NodeIt nit) const { return node_map.get(nit); }
1.281 - };
1.282 -
1.283 - template <typename T>
1.284 - class EdgeMap {
1.285 - typename Graph::EdgeMap<T> forward_map, backward_map;
1.286 - public:
1.287 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
1.288 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
1.289 - void set(EdgeIt e, T a) {
1.290 - if (e.out_or_in)
1.291 - forward_map.set(e.out, a);
1.292 - else
1.293 - backward_map.set(e.in, a);
1.294 - }
1.295 - T get(EdgeIt e) {
1.296 - if (e.out_or_in)
1.297 - return forward_map.get(e.out);
1.298 - else
1.299 - return backward_map.get(e.in);
1.300 - }
1.301 - };
1.302 -
1.303 - };
1.304
1.305 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.306 class MaxFlow {
1.307 @@ -758,105 +461,105 @@
1.308 };
1.309
1.310
1.311 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.312 - class MaxFlow2 {
1.313 - public:
1.314 - typedef typename Graph::NodeIt NodeIt;
1.315 - typedef typename Graph::EdgeIt EdgeIt;
1.316 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.317 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.318 - typedef typename Graph::InEdgeIt InEdgeIt;
1.319 - private:
1.320 - const Graph& G;
1.321 - std::list<NodeIt>& S;
1.322 - std::list<NodeIt>& T;
1.323 - FlowMap& flow;
1.324 - const CapacityMap& capacity;
1.325 - typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.326 - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.327 - typedef typename AugGraph::EdgeIt AugEdgeIt;
1.328 - typename Graph::NodeMap<bool> SMap;
1.329 - typename Graph::NodeMap<bool> TMap;
1.330 - public:
1.331 - MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.332 - for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.333 - i!=S.end(); ++i) {
1.334 - SMap.set(*i, true);
1.335 - }
1.336 - for (typename std::list<NodeIt>::const_iterator i=T.begin();
1.337 - i!=T.end(); ++i) {
1.338 - TMap.set(*i, true);
1.339 - }
1.340 - }
1.341 - bool augment() {
1.342 - AugGraph res_graph(G, flow, capacity);
1.343 - bool _augment=false;
1.344 - NodeIt reached_t_node;
1.345 +// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.346 +// class MaxFlow2 {
1.347 +// public:
1.348 +// typedef typename Graph::NodeIt NodeIt;
1.349 +// typedef typename Graph::EdgeIt EdgeIt;
1.350 +// typedef typename Graph::EachEdgeIt EachEdgeIt;
1.351 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.352 +// typedef typename Graph::InEdgeIt InEdgeIt;
1.353 +// private:
1.354 +// const Graph& G;
1.355 +// std::list<NodeIt>& S;
1.356 +// std::list<NodeIt>& T;
1.357 +// FlowMap& flow;
1.358 +// const CapacityMap& capacity;
1.359 +// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.360 +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.361 +// typedef typename AugGraph::EdgeIt AugEdgeIt;
1.362 +// typename Graph::NodeMap<bool> SMap;
1.363 +// typename Graph::NodeMap<bool> TMap;
1.364 +// public:
1.365 +// MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.366 +// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.367 +// i!=S.end(); ++i) {
1.368 +// SMap.set(*i, true);
1.369 +// }
1.370 +// for (typename std::list<NodeIt>::const_iterator i=T.begin();
1.371 +// i!=T.end(); ++i) {
1.372 +// TMap.set(*i, true);
1.373 +// }
1.374 +// }
1.375 +// bool augment() {
1.376 +// AugGraph res_graph(G, flow, capacity);
1.377 +// bool _augment=false;
1.378 +// NodeIt reached_t_node;
1.379
1.380 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.381 - BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.382 - for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.383 - i!=S.end(); ++i) {
1.384 - res_bfs.pushAndSetReached(*i);
1.385 - }
1.386 - //res_bfs.pushAndSetReached(s);
1.387 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.388 +// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.389 +// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.390 +// i!=S.end(); ++i) {
1.391 +// res_bfs.pushAndSetReached(*i);
1.392 +// }
1.393 +// //res_bfs.pushAndSetReached(s);
1.394
1.395 - typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.396 - //filled up with invalid iterators
1.397 +// typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.398 +// //filled up with invalid iterators
1.399
1.400 - typename AugGraph::NodeMap<Number> free(res_graph);
1.401 +// typename AugGraph::NodeMap<Number> free(res_graph);
1.402
1.403 - //searching for augmenting path
1.404 - while ( !res_bfs.finished() ) {
1.405 - AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.406 - if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.407 - NodeIt v=res_graph.tail(e);
1.408 - NodeIt w=res_graph.head(e);
1.409 - pred.set(w, e);
1.410 - if (pred.get(v).valid()) {
1.411 - free.set(w, std::min(free.get(v), e.free()));
1.412 - } else {
1.413 - free.set(w, e.free());
1.414 - }
1.415 - if (TMap.get(res_graph.head(e))) {
1.416 - _augment=true;
1.417 - reached_t_node=res_graph.head(e);
1.418 - break;
1.419 - }
1.420 - }
1.421 +// //searching for augmenting path
1.422 +// while ( !res_bfs.finished() ) {
1.423 +// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.424 +// if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.425 +// NodeIt v=res_graph.tail(e);
1.426 +// NodeIt w=res_graph.head(e);
1.427 +// pred.set(w, e);
1.428 +// if (pred.get(v).valid()) {
1.429 +// free.set(w, std::min(free.get(v), e.free()));
1.430 +// } else {
1.431 +// free.set(w, e.free());
1.432 +// }
1.433 +// if (TMap.get(res_graph.head(e))) {
1.434 +// _augment=true;
1.435 +// reached_t_node=res_graph.head(e);
1.436 +// break;
1.437 +// }
1.438 +// }
1.439
1.440 - ++res_bfs;
1.441 - } //end of searching augmenting path
1.442 +// ++res_bfs;
1.443 +// } //end of searching augmenting path
1.444
1.445 - if (_augment) {
1.446 - NodeIt n=reached_t_node;
1.447 - Number augment_value=free.get(reached_t_node);
1.448 - while (pred.get(n).valid()) {
1.449 - AugEdgeIt e=pred.get(n);
1.450 - e.augment(augment_value);
1.451 - n=res_graph.tail(e);
1.452 - }
1.453 - }
1.454 +// if (_augment) {
1.455 +// NodeIt n=reached_t_node;
1.456 +// Number augment_value=free.get(reached_t_node);
1.457 +// while (pred.get(n).valid()) {
1.458 +// AugEdgeIt e=pred.get(n);
1.459 +// e.augment(augment_value);
1.460 +// n=res_graph.tail(e);
1.461 +// }
1.462 +// }
1.463
1.464 - return _augment;
1.465 - }
1.466 - void run() {
1.467 - while (augment()) { }
1.468 - }
1.469 - Number flowValue() {
1.470 - Number a=0;
1.471 - for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.472 - i!=S.end(); ++i) {
1.473 - for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.474 - a+=flow.get(e);
1.475 - }
1.476 - for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.477 - a-=flow.get(e);
1.478 - }
1.479 - }
1.480 - return a;
1.481 - }
1.482 - };
1.483 +// return _augment;
1.484 +// }
1.485 +// void run() {
1.486 +// while (augment()) { }
1.487 +// }
1.488 +// Number flowValue() {
1.489 +// Number a=0;
1.490 +// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.491 +// i!=S.end(); ++i) {
1.492 +// for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.493 +// a+=flow.get(e);
1.494 +// }
1.495 +// for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.496 +// a-=flow.get(e);
1.497 +// }
1.498 +// }
1.499 +// return a;
1.500 +// }
1.501 +// };
1.502
1.503
1.504