Changeset 155:8c6292ec54c6 in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 03/04/04 20:38:07 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@217
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r148 r155 246 246 }; 247 247 248 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>249 class ResGraphWrapper {250 public:251 typedef typename Graph::NodeIt NodeIt;252 typedef typename Graph::EachNodeIt EachNodeIt;253 private:254 typedef typename Graph::OutEdgeIt OldOutEdgeIt;255 typedef typename Graph::InEdgeIt OldInEdgeIt;256 const Graph* G;257 FlowMap* flow;258 const CapacityMap* capacity;259 public:260 ResGraphWrapper(const Graph& _G, FlowMap& _flow,261 const CapacityMap& _capacity) :262 G(&_G), flow(&_flow), capacity(&_capacity) { }263 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :264 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }265 class EdgeIt;266 class OutEdgeIt;267 friend class EdgeIt;268 friend class OutEdgeIt;269 270 class EdgeIt {271 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;272 protected:273 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;274 const Graph* G;275 FlowMap* flow;276 const CapacityMap* capacity;277 //OldSymEdgeIt sym;278 OldOutEdgeIt out;279 OldInEdgeIt in;280 bool out_or_in; //true, iff out281 public:282 EdgeIt() : out_or_in(true) { }283 EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :284 G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }285 //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) { }286 Number free() const {287 if (out_or_in) {288 return (/*resG>*/capacity>get(out)/*resG>*/flow>get(out));289 } else {290 return (/*resG>*/flow>get(in));291 }292 }293 bool valid() const {294 return out_or_in && out.valid()  in.valid(); }295 void augment(Number a) const {296 if (out_or_in) {297 /*resG>*/flow>set(out, /*resG>*/flow>get(out)+a);298 } else {299 /*resG>*/flow>set(in, /*resG>*/flow>get(in)a);300 }301 }302 void print() {303 if (out_or_in) {304 std::cout << "out ";305 if (out.valid())306 std::cout << G>id(G>tail(out)) << ""<< G>id(out) <<">"<< G>id(G>head(out));307 else308 std::cout << "invalid";309 }310 else {311 std::cout << "in ";312 if (in.valid())313 std::cout << G>id(G>head(in)) << "<"<< G>id(in) <<""<< G>id(G>tail(in));314 else315 std::cout << "invalid";316 }317 std::cout << std::endl;318 }319 };320 321 Number free(OldOutEdgeIt out) const {322 return (/*resG>*/capacity>get(out)/*resG>*/flow>get(out));323 }324 Number free(OldInEdgeIt in) const {325 return (/*resG>*/flow>get(in));326 }327 328 class OutEdgeIt : public EdgeIt {329 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;330 public:331 OutEdgeIt() { }332 private:333 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {334 //out=/*resG>*/G>template first<OldOutEdgeIt>(v);335 G>getFirst(out, v);336 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }337 if (!out.valid()) {338 out_or_in=0;339 //in=/*resG>*/G>template first<OldInEdgeIt>(v);340 G>getFirst(in, v);341 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }342 }343 }344 public:345 OutEdgeIt& operator++() {346 if (out_or_in) {347 NodeIt v=/*resG>*/G>aNode(out);348 ++out;349 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }350 if (!out.valid()) {351 out_or_in=0;352 G>getFirst(in, v); //=/*resG>*/G>template first<OldInEdgeIt>(v);353 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }354 }355 } else {356 ++in;357 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }358 }359 return *this;360 }361 };362 363 class EachEdgeIt : public EdgeIt {364 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;365 typename Graph::EachNodeIt v;366 public:367 EachEdgeIt() { }368 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }369 EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {370 out_or_in=true;371 G>getFirst(v);372 if (v.valid()) G>getFirst(out, v); else out=OldOutEdgeIt();373 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }374 while (v.valid() && !out.valid()) {375 ++v;376 if (v.valid()) G>getFirst(out, v);377 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }378 }379 if (!out.valid()) {380 out_or_in=0;381 G>getFirst(v);382 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt();383 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }384 while (v.valid() && !in.valid()) {385 ++v;386 if (v.valid()) G>getFirst(in, v);387 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }388 }389 }390 }391 EachEdgeIt& operator++() {392 if (out_or_in) {393 ++out;394 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }395 while (v.valid() && !out.valid()) {396 ++v;397 if (v.valid()) G>getFirst(out, v);398 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }399 }400 if (!out.valid()) {401 out_or_in=0;402 G>getFirst(v);403 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt();404 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }405 while (v.valid() && !in.valid()) {406 ++v;407 if (v.valid()) G>getFirst(in, v);408 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }409 }410 }411 } else {412 ++in;413 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }414 while (v.valid() && !in.valid()) {415 ++v;416 if (v.valid()) G>getFirst(in, v);417 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }418 }419 }420 return *this;421 }422 };423 424 void getFirst(EachNodeIt& v) const { G>getFirst(v); }425 void getFirst(OutEdgeIt& e, NodeIt v) const {426 e=OutEdgeIt(*G, v, *flow, *capacity);427 }428 void getFirst(EachEdgeIt& e) const {429 e=EachEdgeIt(*G, *flow, *capacity);430 }431 432 EachNodeIt& next(EachNodeIt& n) const { return G>next(n); }433 434 OutEdgeIt& next(OutEdgeIt& e) const {435 if (e.out_or_in) {436 NodeIt v=G>aNode(e.out);437 ++(e.out);438 while( G>valid(e.out) && !(e.free()>0) ) { ++(e.out); }439 if (!G>valid(e.out)) {440 e.out_or_in=0;441 G>getFirst(e.in, v); //=/*resG>*/G>template first<OldInEdgeIt>(v);442 while( G>valid(e.in) && !(e.free()>0) ) { ++(e.in); }443 }444 } else {445 ++(e.in);446 while( G>valid(e.in) && !(e.free()>0) ) { ++(e.in); }447 }448 return e;449 }450 451 EachEdgeIt& next(EachEdgeIt& e) const {452 if (e.out_or_in) {453 ++(e.out);454 while (G>valid(e.out) && !(e.free()>0) ) { ++(e.out); }455 while (G>valid(e.v) && !G>valid(e.out)) {456 ++(e.v);457 if (G>valid(e.v)) G>getFirst(e.out, e.v);458 while (G>valid(e.out) && !(e.free()>0) ) { ++(e.out); }459 }460 if (!G>valid(e.out)) {461 e.out_or_in=0;462 G>getFirst(e.v);463 if (G>valid(e.v)) G>getFirst(e.in, e.v); else e.in=OldInEdgeIt();464 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); }465 while (G>valid(e.v) && !G>valid(e.in)) {466 ++(e.v);467 if (G>valid(e.v)) G>getFirst(e.in, e.v);468 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); }469 }470 }471 } else {472 ++(e.in);473 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); }474 while (G>valid(e.v) && !G>valid(e.in)) {475 ++(e.v);476 if (G>valid(e.v)) G>getFirst(e.in, e.v);477 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); }478 }479 }480 return e;481 }482 483 484 template< typename It >485 It first() const {486 It e;487 getFirst(e);488 return e;489 }490 491 template< typename It >492 It first(NodeIt v) const {493 It e;494 getFirst(e, v);495 return e;496 }497 498 NodeIt tail(EdgeIt e) const {499 return ((e.out_or_in) ? G>aNode(e.out) : G>aNode(e.in)); }500 NodeIt head(EdgeIt e) const {501 return ((e.out_or_in) ? G>bNode(e.out) : G>bNode(e.in)); }502 503 NodeIt aNode(OutEdgeIt e) const {504 return ((e.out_or_in) ? G>aNode(e.out) : G>aNode(e.in)); }505 NodeIt bNode(OutEdgeIt e) const {506 return ((e.out_or_in) ? G>bNode(e.out) : G>bNode(e.in)); }507 508 int id(NodeIt v) const { return G>id(v); }509 510 bool valid(NodeIt n) const { return G>valid(n); }511 bool valid(EdgeIt e) const {512 return e.out_or_in ? G>valid(e.out) : G>valid(e.in); }513 514 template <typename T>515 class NodeMap {516 typename Graph::NodeMap<T> node_map;517 public:518 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }519 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }520 void set(NodeIt nit, T a) { node_map.set(nit, a); }521 T get(NodeIt nit) const { return node_map.get(nit); }522 };523 524 template <typename T>525 class EdgeMap {526 typename Graph::EdgeMap<T> forward_map, backward_map;527 public:528 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }529 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }530 void set(EdgeIt e, T a) {531 if (e.out_or_in)532 forward_map.set(e.out, a);533 else534 backward_map.set(e.in, a);535 }536 T get(EdgeIt e) {537 if (e.out_or_in)538 return forward_map.get(e.out);539 else540 return backward_map.get(e.in);541 }542 };543 544 };545 248 546 249 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> … … 759 462 760 463 761 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>762 class MaxFlow2 {763 public:764 typedef typename Graph::NodeIt NodeIt;765 typedef typename Graph::EdgeIt EdgeIt;766 typedef typename Graph::EachEdgeIt EachEdgeIt;767 typedef typename Graph::OutEdgeIt OutEdgeIt;768 typedef typename Graph::InEdgeIt InEdgeIt;769 private:770 const Graph& G;771 std::list<NodeIt>& S;772 std::list<NodeIt>& T;773 FlowMap& flow;774 const CapacityMap& capacity;775 typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;776 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;777 typedef typename AugGraph::EdgeIt AugEdgeIt;778 typename Graph::NodeMap<bool> SMap;779 typename Graph::NodeMap<bool> TMap;780 public:781 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) {782 for(typename std::list<NodeIt>::const_iterator i=S.begin();783 i!=S.end(); ++i) {784 SMap.set(*i, true);785 }786 for (typename std::list<NodeIt>::const_iterator i=T.begin();787 i!=T.end(); ++i) {788 TMap.set(*i, true);789 }790 }791 bool augment() {792 AugGraph res_graph(G, flow, capacity);793 bool _augment=false;794 NodeIt reached_t_node;464 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 465 // class MaxFlow2 { 466 // public: 467 // typedef typename Graph::NodeIt NodeIt; 468 // typedef typename Graph::EdgeIt EdgeIt; 469 // typedef typename Graph::EachEdgeIt EachEdgeIt; 470 // typedef typename Graph::OutEdgeIt OutEdgeIt; 471 // typedef typename Graph::InEdgeIt InEdgeIt; 472 // private: 473 // const Graph& G; 474 // std::list<NodeIt>& S; 475 // std::list<NodeIt>& T; 476 // FlowMap& flow; 477 // const CapacityMap& capacity; 478 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 479 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 480 // typedef typename AugGraph::EdgeIt AugEdgeIt; 481 // typename Graph::NodeMap<bool> SMap; 482 // typename Graph::NodeMap<bool> TMap; 483 // public: 484 // 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) { 485 // for(typename std::list<NodeIt>::const_iterator i=S.begin(); 486 // i!=S.end(); ++i) { 487 // SMap.set(*i, true); 488 // } 489 // for (typename std::list<NodeIt>::const_iterator i=T.begin(); 490 // i!=T.end(); ++i) { 491 // TMap.set(*i, true); 492 // } 493 // } 494 // bool augment() { 495 // AugGraph res_graph(G, flow, capacity); 496 // bool _augment=false; 497 // NodeIt reached_t_node; 795 498 796 typedef typename AugGraph::NodeMap<bool> ReachedMap;797 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);798 for(typename std::list<NodeIt>::const_iterator i=S.begin();799 i!=S.end(); ++i) {800 res_bfs.pushAndSetReached(*i);801 }802 //res_bfs.pushAndSetReached(s);803 804 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);805 //filled up with invalid iterators499 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 500 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); 501 // for(typename std::list<NodeIt>::const_iterator i=S.begin(); 502 // i!=S.end(); ++i) { 503 // res_bfs.pushAndSetReached(*i); 504 // } 505 // //res_bfs.pushAndSetReached(s); 506 507 // typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 508 // //filled up with invalid iterators 806 509 807 typename AugGraph::NodeMap<Number> free(res_graph);808 809 //searching for augmenting path810 while ( !res_bfs.finished() ) {811 AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);812 if (e.valid() && res_bfs.isBNodeNewlyReached()) {813 NodeIt v=res_graph.tail(e);814 NodeIt w=res_graph.head(e);815 pred.set(w, e);816 if (pred.get(v).valid()) {817 free.set(w, std::min(free.get(v), e.free()));818 } else {819 free.set(w, e.free());820 }821 if (TMap.get(res_graph.head(e))) {822 _augment=true;823 reached_t_node=res_graph.head(e);824 break;825 }826 }827 828 ++res_bfs;829 } //end of searching augmenting path830 831 if (_augment) {832 NodeIt n=reached_t_node;833 Number augment_value=free.get(reached_t_node);834 while (pred.get(n).valid()) {835 AugEdgeIt e=pred.get(n);836 e.augment(augment_value);837 n=res_graph.tail(e);838 }839 }840 841 return _augment;842 }843 void run() {844 while (augment()) { }845 }846 Number flowValue() {847 Number a=0;848 for(typename std::list<NodeIt>::const_iterator i=S.begin();849 i!=S.end(); ++i) {850 for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {851 a+=flow.get(e);852 }853 for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {854 a=flow.get(e);855 }856 }857 return a;858 }859 };510 // typename AugGraph::NodeMap<Number> free(res_graph); 511 512 // //searching for augmenting path 513 // while ( !res_bfs.finished() ) { 514 // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); 515 // if (e.valid() && res_bfs.isBNodeNewlyReached()) { 516 // NodeIt v=res_graph.tail(e); 517 // NodeIt w=res_graph.head(e); 518 // pred.set(w, e); 519 // if (pred.get(v).valid()) { 520 // free.set(w, std::min(free.get(v), e.free())); 521 // } else { 522 // free.set(w, e.free()); 523 // } 524 // if (TMap.get(res_graph.head(e))) { 525 // _augment=true; 526 // reached_t_node=res_graph.head(e); 527 // break; 528 // } 529 // } 530 531 // ++res_bfs; 532 // } //end of searching augmenting path 533 534 // if (_augment) { 535 // NodeIt n=reached_t_node; 536 // Number augment_value=free.get(reached_t_node); 537 // while (pred.get(n).valid()) { 538 // AugEdgeIt e=pred.get(n); 539 // e.augment(augment_value); 540 // n=res_graph.tail(e); 541 // } 542 // } 543 544 // return _augment; 545 // } 546 // void run() { 547 // while (augment()) { } 548 // } 549 // Number flowValue() { 550 // Number a=0; 551 // for(typename std::list<NodeIt>::const_iterator i=S.begin(); 552 // i!=S.end(); ++i) { 553 // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { 554 // a+=flow.get(e); 555 // } 556 // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { 557 // a=flow.get(e); 558 // } 559 // } 560 // return a; 561 // } 562 // }; 860 563 861 564
Note: See TracChangeset
for help on using the changeset viewer.