Changeset 148:004fdf703abb in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 03/03/04 15:30:38 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@208
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r141 r148 149 149 OldOutEdgeIt out; 150 150 OldInEdgeIt in; 151 bool out_or_in; // 1, iff out152 public: 153 EdgeIt() : out_or_in( 1) { }151 bool out_or_in; //true, iff out 152 public: 153 EdgeIt() : out_or_in(true) { } 154 154 Number free() const { 155 155 if (out_or_in) { … … 247 247 248 248 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 249 class ResGraph 3{249 class ResGraphWrapper { 250 250 public: 251 251 typedef typename Graph::NodeIt NodeIt; 252 252 typedef typename Graph::EachNodeIt EachNodeIt; 253 254 253 private: 255 //typedef typename Graph::SymEdgeIt OldSymEdgeIt;256 254 typedef typename Graph::OutEdgeIt OldOutEdgeIt; 257 255 typedef typename Graph::InEdgeIt OldInEdgeIt; 258 const Graph &G;259 FlowMap &flow;260 const CapacityMap &capacity;261 public: 262 ResGraph 3(const Graph& _G, FlowMap& _flow,256 const Graph* G; 257 FlowMap* flow; 258 const CapacityMap* capacity; 259 public: 260 ResGraphWrapper(const Graph& _G, FlowMap& _flow, 263 261 const CapacityMap& _capacity) : 264 G(_G), flow(_flow), capacity(_capacity) { } 265 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) { } 266 265 class EdgeIt; 267 266 class OutEdgeIt; … … 270 269 271 270 class EdgeIt { 272 friend class ResGraph 3<Graph, Number, FlowMap, CapacityMap>;271 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 273 272 protected: 274 273 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG; … … 279 278 OldOutEdgeIt out; 280 279 OldInEdgeIt in; 281 bool out_or_in; //1, iff out 282 public: 283 EdgeIt() : out_or_in(1) { } 280 bool out_or_in; //true, iff out 281 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) { } 284 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) { } 285 286 Number free() const { … … 318 319 }; 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 320 328 class OutEdgeIt : public EdgeIt { 321 friend class ResGraph 3<Graph, Number, FlowMap, CapacityMap>;329 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 322 330 public: 323 331 OutEdgeIt() { } 324 332 private: 325 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 326 G=&_G; 327 flow=&_flow; 328 capacity=&_capacity; 333 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 329 334 //out=/*resG>*/G>template first<OldOutEdgeIt>(v); 330 335 G>getFirst(out, v); 331 while( out.valid() && !( free()>0) ) { ++out; }336 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 332 337 if (!out.valid()) { 333 338 out_or_in=0; 334 339 //in=/*resG>*/G>template first<OldInEdgeIt>(v); 335 340 G>getFirst(in, v); 336 while( in.valid() && !( free()>0) ) { ++in; }341 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 337 342 } 338 343 } … … 342 347 NodeIt v=/*resG>*/G>aNode(out); 343 348 ++out; 344 while( out.valid() && !( free()>0) ) { ++out; }349 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 345 350 if (!out.valid()) { 346 351 out_or_in=0; 347 352 G>getFirst(in, v); //=/*resG>*/G>template first<OldInEdgeIt>(v); 348 while( in.valid() && !( free()>0) ) { ++in; }353 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 349 354 } 350 355 } else { 351 356 ++in; 352 while( in.valid() && !( free()>0) ) { ++in; }357 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 353 358 } 354 359 return *this; … … 357 362 358 363 class EachEdgeIt : public EdgeIt { 364 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 359 365 typename Graph::EachNodeIt v; 360 366 public: 361 367 EachEdgeIt() { } 362 368 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } 363 EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) { 364 G=&_G; 365 flow=&_flow; 366 capacity=&_capacity; 367 out_or_in=1; 369 EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 370 out_or_in=true; 368 371 G>getFirst(v); 369 372 if (v.valid()) G>getFirst(out, v); else out=OldOutEdgeIt(); 370 while (out.valid() && !( free()>0) ) { ++out; }373 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 371 374 while (v.valid() && !out.valid()) { 372 375 ++v; 373 376 if (v.valid()) G>getFirst(out, v); 374 while (out.valid() && !( free()>0) ) { ++out; }377 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 375 378 } 376 379 if (!out.valid()) { … … 378 381 G>getFirst(v); 379 382 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt(); 380 while (in.valid() && !( free()>0) ) { ++in; }383 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 381 384 while (v.valid() && !in.valid()) { 382 385 ++v; 383 386 if (v.valid()) G>getFirst(in, v); 384 while (in.valid() && !( free()>0) ) { ++in; }387 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 385 388 } 386 389 } … … 389 392 if (out_or_in) { 390 393 ++out; 391 while (out.valid() && !( free()>0) ) { ++out; }394 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 392 395 while (v.valid() && !out.valid()) { 393 396 ++v; 394 397 if (v.valid()) G>getFirst(out, v); 395 while (out.valid() && !( free()>0) ) { ++out; }398 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 396 399 } 397 400 if (!out.valid()) { … … 399 402 G>getFirst(v); 400 403 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt(); 401 while (in.valid() && !( free()>0) ) { ++in; }404 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 402 405 while (v.valid() && !in.valid()) { 403 406 ++v; 404 407 if (v.valid()) G>getFirst(in, v); 405 while (in.valid() && !( free()>0) ) { ++in; }408 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 406 409 } 407 410 } 408 411 } else { 409 412 ++in; 410 while (in.valid() && !( free()>0) ) { ++in; }413 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 411 414 while (v.valid() && !in.valid()) { 412 415 ++v; 413 416 if (v.valid()) G>getFirst(in, v); 414 while (in.valid() && !( free()>0) ) { ++in; }417 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 415 418 } 416 419 } … … 419 422 }; 420 423 424 void getFirst(EachNodeIt& v) const { G>getFirst(v); } 421 425 void getFirst(OutEdgeIt& e, NodeIt v) const { 422 e=OutEdgeIt( G, v, flow,capacity);426 e=OutEdgeIt(*G, v, *flow, *capacity); 423 427 } 424 428 void getFirst(EachEdgeIt& e) const { 425 e=EachEdgeIt(G, flow, capacity); 426 } 427 void getFirst(EachNodeIt& v) const { G.getFirst(v); } 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 } 428 482 483 429 484 template< typename It > 430 485 It first() const { … … 442 497 443 498 NodeIt tail(EdgeIt e) const { 444 return ((e.out_or_in) ? G .aNode(e.out) : G.aNode(e.in)); }499 return ((e.out_or_in) ? G>aNode(e.out) : G>aNode(e.in)); } 445 500 NodeIt head(EdgeIt e) const { 446 return ((e.out_or_in) ? G .bNode(e.out) : G.bNode(e.in)); }501 return ((e.out_or_in) ? G>bNode(e.out) : G>bNode(e.in)); } 447 502 448 503 NodeIt aNode(OutEdgeIt e) const { 449 return ((e.out_or_in) ? G .aNode(e.out) : G.aNode(e.in)); }504 return ((e.out_or_in) ? G>aNode(e.out) : G>aNode(e.in)); } 450 505 NodeIt bNode(OutEdgeIt e) const { 451 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 452 453 int id(NodeIt v) const { return G.id(v); } 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); } 454 513 455 514 template <typename T> … … 457 516 typename Graph::NodeMap<T> node_map; 458 517 public: 459 NodeMap(const ResGraph 3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }460 NodeMap(const ResGraph 3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(_G.G, a) { }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) { } 461 520 void set(NodeIt nit, T a) { node_map.set(nit, a); } 462 521 T get(NodeIt nit) const { return node_map.get(nit); } … … 467 526 typename Graph::EdgeMap<T> forward_map, backward_map; 468 527 public: 469 EdgeMap(const ResGraph 3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }470 EdgeMap(const ResGraph 3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.G, a), backward_map(_G.G, a) { }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) { } 471 530 void set(EdgeIt e, T a) { 472 531 if (e.out_or_in) … … 495 554 496 555 private: 497 const Graph &G;556 const Graph* G; 498 557 NodeIt s; 499 558 NodeIt t; 500 FlowMap &flow;501 const CapacityMap &capacity;502 typedef ResGraph 3<Graph, Number, FlowMap, CapacityMap > AugGraph;559 FlowMap* flow; 560 const CapacityMap* capacity; 561 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; 503 562 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 504 563 typedef typename AugGraph::EdgeIt AugEdgeIt; … … 510 569 public: 511 570 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 512 G( _G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,571 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 513 572 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 514 573 { } 515 574 bool augmentOnShortestPath() { 516 AugGraph res_graph( G, flow,capacity);575 AugGraph res_graph(*G, *flow, *capacity); 517 576 bool _augment=false; 518 577 519 578 typedef typename AugGraph::NodeMap<bool> ReachedMap; 520 BfsIterator 4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);579 BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); 521 580 res_bfs.pushAndSetReached(s); 522 581 … … 530 589 while ( !res_bfs.finished() ) { 531 590 AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); 532 if ( e.valid() && res_bfs.isBNodeNewlyReached()) {591 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { 533 592 NodeIt v=res_graph.tail(e); 534 593 NodeIt w=res_graph.head(e); 535 594 pred.set(w, e); 536 if ( pred.get(v).valid()) {595 if (res_graph.valid(pred.get(v))) { 537 596 free.set(w, std::min(free.get(v), e.free())); 538 597 } else { … … 548 607 NodeIt n=t; 549 608 Number augment_value=free.get(t); 550 while ( pred.get(n).valid()) {609 while (res_graph.valid(pred.get(n))) { 551 610 AugEdgeIt e=pred.get(n); 552 611 e.augment(augment_value); … … 561 620 bool _augment=false; 562 621 563 AugGraph res_graph( G, flow,capacity);622 AugGraph res_graph(*G, *flow, *capacity); 564 623 565 624 typedef typename AugGraph::NodeMap<bool> ReachedMap; … … 570 629 while ( !bfs.finished() ) { 571 630 AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 572 if ( e.valid() && bfs.isBNodeNewlyReached()) {631 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 573 632 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 574 633 } … … 579 638 MutableGraph F; 580 639 typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph); 581 for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {640 for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { 582 641 res_graph_to_F.set(n, F.addNode()); 583 642 } … … 587 646 588 647 typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F); 589 typename MutableGraph::EdgeMap<Number> free_on_edge(F);648 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 590 649 591 650 //Making F to the graph containing the edges of the residual graph 592 651 //which are in some shortest paths 593 for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {652 for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 594 653 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 595 654 typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 596 655 original_edge.update(); 597 656 original_edge.set(f, e); 598 free_on_edge.update();599 free_on_edge.set(f, e.free());657 residual_capacity.update(); 658 residual_capacity.set(f, e.free()); 600 659 } 601 660 } … … 614 673 while (!dfs.finished()) { 615 674 ++dfs; 616 if ( typename MutableGraph::OutEdgeIt(dfs).valid()) {675 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 617 676 //std::cout << "OutEdgeIt: " << dfs; 618 677 //std::cout << " aNode: " << F.aNode(dfs); … … 622 681 typename MutableGraph::NodeIt w=F.bNode(dfs); 623 682 pred.set(w, dfs); 624 if ( pred.get(v).valid()) {625 free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));683 if (F.valid(pred.get(v))) { 684 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 626 685 } else { 627 free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);686 free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/); 628 687 } 629 688 if (w==tF) { … … 658 717 typename MutableGraph::NodeIt n=tF; 659 718 Number augment_value=free.get(tF); 660 while ( pred.get(n).valid()) {719 while (F.valid(pred.get(n))) { 661 720 typename MutableGraph::EdgeIt e=pred.get(n); 662 721 original_edge.get(e).augment(augment_value); 663 722 n=F.tail(e); 664 if ( free_on_edge.get(e)==augment_value)723 if (residual_capacity.get(e)==augment_value) 665 724 F.erase(e); 666 725 else 667 free_on_edge.set(e, free_on_edge.get(e)augment_value);726 residual_capacity.set(e, residual_capacity.get(e)augment_value); 668 727 } 669 728 } … … 691 750 Number flowValue() { 692 751 Number a=0; 693 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { 694 a+=flow.get(i); 752 OutEdgeIt e; 753 for(G>getFirst(e, s); G>valid(e); G>next(e)) { 754 a+=flow>get(e); 695 755 } 696 756 return a; 697 757 } 698 758 }; 699 700 701 /*702 template <typename Graph>703 class IteratorBoolNodeMap {704 typedef typename Graph::NodeIt NodeIt;705 typedef typename Graph::EachNodeIt EachNodeIt;706 class BoolItem {707 public:708 bool value;709 NodeIt prev;710 NodeIt next;711 BoolItem() : value(false), prev(), next() {}712 };713 NodeIt first_true;714 //NodeIt last_true;715 NodeIt first_false;716 //NodeIt last_false;717 const Graph& G;718 typename Graph::NodeMap<BoolItem> container;719 public:720 typedef bool ValueType;721 typedef NodeIt KeyType;722 IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {723 //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {724 //BoolItem b=container.get(e);725 //b.me=e;726 //container.set(b);727 //}728 G.getFirst(first_false);729 NodeIt e_prev;730 for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {731 container[e].prev=e_prev;732 if (e_prev.valid()) container[e_prev].next=e;733 e_prev=e;734 }735 }736 //NodeMap(const Graph& _G, T a) :737 // G(_G), container(G.node_id, a) { }738 //FIXME739 void set(NodeIt nit, T a) { container[G.id(nit)]=a; }740 T get(NodeIt nit) const { return container[G.id(nit)]; }741 //void update() { container.resize(G.node_id); }742 //void update(T a) { container.resize(G.node_id, a); }743 };744 */745 759 746 760
Note: See TracChangeset
for help on using the changeset viewer.