Changeset 133:0631992fe7a1 in lemon0.x
 Timestamp:
 02/27/04 13:39:15 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@180
 Location:
 src/work
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r105 r133 645 645 } 646 646 void pushAndSetReached(NodeIt s) { 647 actual_node=s; 647 648 reached.set(s, true); 648 649 dfs_stack.push(G.template first<OutEdgeIt>(s)); … … 660 661 b_node_newly_reached=true; 661 662 } else { 663 actual_node=G.aNode(actual_edge); 662 664 ++(dfs_stack.top()); 663 665 b_node_newly_reached=false; … … 673 675 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 674 676 bool isANodeExamined() const { return !(actual_edge.valid()); } 675 NodeIt aNode() const { return actual_node; }677 NodeIt aNode() const { return actual_node; /*FIXME*/} 676 678 NodeIt bNode() const { return G.bNode(actual_edge); } 677 679 const ReachedMap& getReachedMap() const { return reached; } 
src/work/edmonds_karp.hh
r127 r133 7 7 8 8 #include <bfs_iterator.hh> 9 #include <time_measure.h>9 //#include <time_measure.h> 10 10 11 11 namespace hugo { … … 282 282 public: 283 283 EdgeIt() : out_or_in(1) { } 284 //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) { } 284 285 Number free() const { 285 286 if (out_or_in) { … … 298 299 } 299 300 } 301 void print() { 302 if (out_or_in) { 303 std::cout << "out "; 304 if (out.valid()) 305 std::cout << G>id(G>tail(out)) << ""<< G>id(out) <<">"<< G>id(G>head(out)); 306 else 307 std::cout << "invalid"; 308 } 309 else { 310 std::cout << "in "; 311 if (in.valid()) 312 std::cout << G>id(G>head(in)) << "<"<< G>id(in) <<""<< G>id(G>tail(in)); 313 else 314 std::cout << "invalid"; 315 } 316 std::cout << std::endl; 317 } 300 318 }; 301 319 … … 309 327 flow=&_flow; 310 328 capacity=&_capacity; 311 out=/*resG>*/G>template first<OldOutEdgeIt>(v); 329 //out=/*resG>*/G>template first<OldOutEdgeIt>(v); 330 G>getFirst(out, v); 312 331 while( out.valid() && !(free()>0) ) { ++out; } 313 332 if (!out.valid()) { 314 333 out_or_in=0; 315 in=/*resG>*/G>template first<OldInEdgeIt>(v); 334 //in=/*resG>*/G>template first<OldInEdgeIt>(v); 335 G>getFirst(in, v); 316 336 while( in.valid() && !(free()>0) ) { ++in; } 317 337 } … … 325 345 if (!out.valid()) { 326 346 out_or_in=0; 327 in=/*resG>*/G>template first<OldInEdgeIt>(v);347 G>getFirst(in, v); //=/*resG>*/G>template first<OldInEdgeIt>(v); 328 348 while( in.valid() && !(free()>0) ) { ++in; } 329 349 } … … 336 356 }; 337 357 358 class EachEdgeIt : public EdgeIt { 359 typename Graph::EachNodeIt v; 360 public: 361 EachEdgeIt() { } 362 //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; 368 G>getFirst(v); 369 if (v.valid()) G>getFirst(out, v); else out=OldOutEdgeIt(); 370 while (out.valid() && !(free()>0) ) { ++out; } 371 while (v.valid() && !out.valid()) { 372 ++v; 373 if (v.valid()) G>getFirst(out, v); 374 while (out.valid() && !(free()>0) ) { ++out; } 375 } 376 if (!out.valid()) { 377 out_or_in=0; 378 G>getFirst(v); 379 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt(); 380 while (in.valid() && !(free()>0) ) { ++in; } 381 while (v.valid() && !in.valid()) { 382 ++v; 383 if (v.valid()) G>getFirst(in, v); 384 while (in.valid() && !(free()>0) ) { ++in; } 385 } 386 } 387 } 388 EachEdgeIt& operator++() { 389 if (out_or_in) { 390 ++out; 391 while (out.valid() && !(free()>0) ) { ++out; } 392 while (v.valid() && !out.valid()) { 393 ++v; 394 if (v.valid()) G>getFirst(out, v); 395 while (out.valid() && !(free()>0) ) { ++out; } 396 } 397 if (!out.valid()) { 398 out_or_in=0; 399 G>getFirst(v); 400 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt(); 401 while (in.valid() && !(free()>0) ) { ++in; } 402 while (v.valid() && !in.valid()) { 403 ++v; 404 if (v.valid()) G>getFirst(in, v); 405 while (in.valid() && !(free()>0) ) { ++in; } 406 } 407 } 408 } else { 409 ++in; 410 while (in.valid() && !(free()>0) ) { ++in; } 411 while (v.valid() && !in.valid()) { 412 ++v; 413 if (v.valid()) G>getFirst(in, v); 414 while (in.valid() && !(free()>0) ) { ++in; } 415 } 416 } 417 return *this; 418 } 419 }; 420 338 421 void getFirst(OutEdgeIt& e, NodeIt v) const { 339 422 e=OutEdgeIt(G, v, flow, capacity); 423 } 424 void getFirst(EachEdgeIt& e) const { 425 e=EachEdgeIt(G, flow, capacity); 340 426 } 341 427 void getFirst(EachNodeIt& v) const { G.getFirst(v); } … … 402 488 //typedef typename AugGraph::NodeMap<bool> ReachedMap; 403 489 //typename AugGraph::NodeMap<AugEdgeIt> pred; 404 //typename AugGraph::NodeMap< int> free;490 //typename AugGraph::NodeMap<Number> free; 405 491 public: 406 492 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : … … 408 494 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 409 495 { } 410 bool augment () {496 bool augmentOnShortestPath() { 411 497 AugGraph res_graph(G, flow, capacity); 412 498 bool _augment=false; … … 420 506 //pred.set(s, AugEdgeIt()); 421 507 422 typename AugGraph::NodeMap< int> free(res_graph);508 typename AugGraph::NodeMap<Number> free(res_graph); 423 509 424 510 //searching for augmenting path … … 452 538 return _augment; 453 539 } 454 bool augmentWithBlockingFlow() { 455 BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G); 540 template<typename MutableGraph> bool augmentOnBlockingFlow() { 541 bool _augment=false; 542 543 AugGraph res_graph(G, flow, capacity); 544 545 typedef typename AugGraph::NodeMap<bool> ReachedMap; 546 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 547 456 548 bfs.pushAndSetReached(s); 457 typename Graph::NodeMap<int> dist(G); //filled up with 0's549 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 458 550 while ( !bfs.finished() ) { 459 OutEdgeIt e=OutEdgeIt(bfs);551 AugOutEdgeIt e=AugOutEdgeIt(bfs); 460 552 if (e.valid() && bfs.isBNodeNewlyReached()) { 461 dist.set(G.head(e), dist.get(G.tail(e))+1); 462 //NodeIt v=res_graph.tail(e); 463 //NodeIt w=res_graph.head(e); 464 //pred.set(w, e); 465 //if (pred.get(v).valid()) { 466 // free.set(w, std::min(free.get(v), e.free())); 467 //} else { 468 // free.set(w, e.free()); 469 //} 470 //if (res_graph.head(e)==t) { _augment=true; break; } 553 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 471 554 } 472 555 473 556 ++bfs; 474 } //end of searching augmenting path 475 476 double pre_time_copy=currTime(); 477 typedef Graph MutableGraph; 557 } //computing distances from s in the residual graph 558 478 559 MutableGraph F; 479 typename Graph::NodeMap<NodeIt> G_to_F(G); 480 for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) { 481 G_to_F.set(n, F.addNode()); 482 } 483 for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) { 484 if (dist.get(G.head(e))==dist.get(G.tail(e))+1) { 485 F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e))); 486 } 487 } 488 double post_time_copy=currTime(); 489 std::cout << "copy time: " << post_time_copypre_time_copy << " sec"<< std::endl; 490 491 return 0; 560 typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph); 561 for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) { 562 res_graph_to_F.set(n, F.addNode()); 563 } 564 565 typename MutableGraph::NodeIt sF=res_graph_to_F.get(s); 566 typename MutableGraph::NodeIt tF=res_graph_to_F.get(t); 567 568 typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F); 569 typename MutableGraph::EdgeMap<Number> free_on_edge(F); 570 571 //Making F to the graph containing the edges of the residual graph 572 //which are in some shortest paths 573 for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) { 574 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 575 typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 576 original_edge.update(); 577 original_edge.set(f, e); 578 free_on_edge.update(); 579 free_on_edge.set(f, e.free()); 580 } 581 } 582 583 bool __augment=true; 584 585 while (__augment) { 586 __augment=false; 587 //computing blocking flow with dfs 588 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; 589 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); 590 typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators 591 typename MutableGraph::NodeMap<Number> free(F); 592 593 dfs.pushAndSetReached(sF); 594 while (!dfs.finished()) { 595 ++dfs; 596 if (typename MutableGraph::OutEdgeIt(dfs).valid()) { 597 //std::cout << "OutEdgeIt: " << dfs; 598 //std::cout << " aNode: " << F.aNode(dfs); 599 //std::cout << " bNode: " << F.bNode(dfs) << " "; 600 601 typename MutableGraph::NodeIt v=F.aNode(dfs); 602 typename MutableGraph::NodeIt w=F.bNode(dfs); 603 pred.set(w, dfs); 604 if (pred.get(v).valid()) { 605 free.set(w, std::min(free.get(v), free_on_edge.get(dfs))); 606 } else { 607 free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/); 608 } 609 if (w==tF) { 610 //std::cout << "AUGMENTATION"<<std::endl; 611 __augment=true; 612 _augment=true; 613 break; 614 } 615 } else { 616 //std::cout << "OutEdgeIt: " << "invalid"; 617 //std::cout << " aNode: " << dfs.aNode(); 618 //std::cout << " bNode: " << "invalid" << " "; 619 } 620 if (dfs.isBNodeNewlyReached()) { 621 //std::cout << "bNodeIsNewlyReached "; 622 } else { 623 //std::cout << "bNodeIsNotNewlyReached "; 624 if (typename MutableGraph::OutEdgeIt(dfs).valid()) { 625 //std::cout << "DELETE "; 626 F.erase(typename MutableGraph::OutEdgeIt(dfs)); 627 } 628 } 629 //if (dfs.isANodeExamined()) { 630 //std::cout << "aNodeIsExamined "; 631 //} else { 632 //std::cout << "aNodeIsNotExamined "; 633 //} 634 //std::cout<<std::endl; 635 } 636 637 if (__augment) { 638 typename MutableGraph::NodeIt n=tF; 639 Number augment_value=free.get(tF); 640 while (pred.get(n).valid()) { 641 typename MutableGraph::EdgeIt e=pred.get(n); 642 original_edge.get(e).augment(augment_value); 643 n=F.tail(e); 644 F.erase(e); 645 } 646 } 647 648 } 649 650 return _augment; 492 651 } 493 652 void run() { 494 653 //int num_of_augmentations=0; 495 while (augment()) { 654 while (augmentOnShortestPath()) { 655 //while (augmentOnBlockingFlow<MutableGraph>()) { 656 //std::cout << ++num_of_augmentations << " "; 657 //std::cout<<std::endl; 658 } 659 } 660 template<typename MutableGraph> void run() { 661 //int num_of_augmentations=0; 662 //while (augmentOnShortestPath()) { 663 while (augmentOnBlockingFlow<MutableGraph>()) { 496 664 //std::cout << ++num_of_augmentations << " "; 497 665 //std::cout<<std::endl; … … 600 768 //filled up with invalid iterators 601 769 602 typename AugGraph::NodeMap< int> free(res_graph);770 typename AugGraph::NodeMap<Number> free(res_graph); 603 771 604 772 //searching for augmenting path 
src/work/marci/edmonds_karp_demo.cc
r105 r133 20 20 readDimacsMaxFlow(std::cin, G, s, t, cap); 21 21 22 /* 23 double pre_time_copy=currTime(); 24 ListGraph F; 25 ListGraph::NodeMap<NodeIt> G_to_F(G); 26 typedef ListGraph::EachNodeIt EachNodeIt; 27 for(EachNodeIt n=G.first<EachNodeIt>(); n.valid(); ++n) { 28 G_to_F.set(n, F.addNode()); 29 } 30 for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 31 F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e))); 32 } 33 double post_time_copy=currTime(); 34 std::cout << "copy time: " << post_time_copypre_time_copy << " sec"<< std::endl; 35 */ 36 37 std::cout << "edmonds karp demo..." << std::endl; 22 { 23 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; 38 24 ListGraph::EdgeMap<int> flow(G); //0 flow 39 25 40 26 double pre_time=currTime(); 41 27 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 42 max_flow_test.augmentWithBlockingFlow();43 max_flow_test.run ();28 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 29 max_flow_test.run<ListGraph>(); 44 30 double post_time=currTime(); 31 45 32 //std::cout << "maximum flow: "<< std::endl; 46 33 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { … … 50 37 std::cout << "elapsed time: " << post_timepre_time << " sec"<< std::endl; 51 38 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 39 } 40 41 { 42 std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl; 43 ListGraph::EdgeMap<int> flow(G); //0 flow 44 45 double pre_time=currTime(); 46 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 47 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 48 max_flow_test.run(); 49 double post_time=currTime(); 50 51 //std::cout << "maximum flow: "<< std::endl; 52 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 53 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 54 //} 55 //std::cout<<std::endl; 56 std::cout << "elapsed time: " << post_timepre_time << " sec"<< std::endl; 57 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 58 } 52 59 53 60 return 0; 
src/work/marci_graph_demo.cc
r107 r133 226 226 ListGraph::EdgeMap<int> flow(flowG, 0); 227 227 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap); 228 /* 229 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 230 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 231 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 232 } 233 std::cout<<std::endl; 234 max_flow_test.augmentOnBlockingFlow<ListGraph>(); 235 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 236 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 237 } 238 std::cout<<std::endl;*/ 228 239 max_flow_test.run(); 229 240
Note: See TracChangeset
for help on using the changeset viewer.