Changeset 168:27fbd1559fb7 in lemon-0.x for src/work/marci
- Timestamp:
- 03/11/04 15:15:07 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@239
- Location:
- src/work/marci
- Files:
-
- 3 edited
-
edmonds_karp_demo.cc (modified) (2 diffs)
-
graph_wrapper.h (modified) (19 diffs)
-
makefile (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/edmonds_karp_demo.cc
r155 r168 88 88 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 89 89 int i=0; 90 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; } 90 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { 91 // for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 92 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 93 // } 94 // std::cout<<std::endl; 95 ++i; 96 } 97 //double post_time=currTime(); 98 99 //std::cout << "maximum flow: "<< std::endl; 100 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 101 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 102 //} 103 //std::cout<<std::endl; 104 std::cout << "elapsed time: " << ts << std::endl; 105 std::cout << "number of augmentation phases: " << i << std::endl; 106 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 107 } 108 109 { 110 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; 111 ListGraph::EdgeMap<int> flow(G); //0 flow 112 113 Timer ts; 114 ts.reset(); 115 //double pre_time=currTime(); 116 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 117 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 118 int i=0; 119 while (max_flow_test.augmentOnBlockingFlow2()) { 120 // for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 121 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 122 // } 123 // std::cout<<std::endl; 124 ++i; 125 } 91 126 //double post_time=currTime(); 92 127 … … 111 146 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 112 147 int i=0; 113 while (max_flow_test.augmentOnShortestPath()) { ++i; } 148 while (max_flow_test.augmentOnShortestPath()) { 149 // for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 150 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 151 // } 152 // std::cout<<std::endl; 153 ++i; 154 } 114 155 //double post_time=currTime(); 115 156 -
src/work/marci/graph_wrapper.h
r158 r168 20 20 //typedef typename Graph::SymEdgeIt SymEdgeIt; 21 21 typedef typename Graph::EachEdgeIt EachEdgeIt; 22 23 //TrivGraphWrapper() : graph(0) { } 24 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } 25 26 void setGraph(Graph& _graph) { graph = &_graph; } 27 Graph& getGraph() const { return (*graph); } 22 28 23 29 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } … … 67 73 Graph::NodeMap<T>(_G.getGraph(), a) { } 68 74 }; 75 69 76 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 70 77 public: … … 74 81 Graph::EdgeMap<T>(_G.getGraph(), a) { } 75 82 }; 76 77 void setGraph(Graph& _graph) { graph = &_graph; }78 Graph& getGraph() const { return (*graph); }79 80 //TrivGraphWrapper() : graph(0) { }81 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }82 83 }; 83 84 … … 98 99 //typedef typename Graph::SymEdgeIt SymEdgeIt; 99 100 typedef typename Graph::EachEdgeIt EachEdgeIt; 101 102 //RevGraphWrapper() : graph(0) { } 103 RevGraphWrapper(Graph& _graph) : graph(&_graph) { } 104 105 void setGraph(Graph& _graph) { graph = &_graph; } 106 Graph& getGraph() const { return (*graph); } 100 107 101 108 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } … … 145 152 Graph::NodeMap<T>(_G.getGraph(), a) { } 146 153 }; 154 147 155 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 148 156 public: … … 152 160 Graph::EdgeMap<T>(_G.getGraph(), a) { } 153 161 }; 154 155 void setGraph(Graph& _graph) { graph = &_graph; }156 Graph& getGraph() const { return (*graph); }157 158 //RevGraphWrapper() : graph(0) { }159 RevGraphWrapper(Graph& _graph) : graph(&_graph) { }160 162 }; 161 163 … … 183 185 //public: 184 186 187 //UndirGraphWrapper() : graph(0) { } 188 UndirGraphWrapper(Graph& _graph) : graph(&_graph) { } 189 190 void setGraph(Graph& _graph) { graph = &_graph; } 191 Graph& getGraph() const { return (*graph); } 192 185 193 class EdgeIt { 186 194 friend class UndirGraphWrapper<Graph>; … … 197 205 class OutEdgeIt : public EdgeIt { 198 206 friend class UndirGraphWrapper<Graph>; 199 //bool out_or_in; //true iff out200 //GraphOutEdgeIt out;201 //GraphInEdgeIt in;202 207 public: 203 208 OutEdgeIt() : EdgeIt() { } … … 288 293 Graph::NodeMap<T>(_G.getGraph(), a) { } 289 294 }; 295 290 296 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 291 297 public: … … 295 301 Graph::EdgeMap<T>(_G.getGraph(), a) { } 296 302 }; 297 298 void setGraph(Graph& _graph) { graph = &_graph; }299 Graph& getGraph() const { return (*graph); }300 301 //TrivGraphWrapper() : graph(0) { }302 UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }303 303 }; 304 304 … … 387 387 const CapacityMap* capacity; 388 388 public: 389 389 390 ResGraphWrapper(const Graph& _G, FlowMap& _flow, 390 391 const CapacityMap& _capacity) : … … 392 393 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 393 394 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } 394 void setGraph(Graph& _graph) { graph = &_graph; } 395 Graph& getGraph() const { return (*graph); } 395 396 void setGraph(const Graph& _graph) { graph = &_graph; } 397 const Graph& getGraph() const { return (*G); } 398 396 399 class EdgeIt; 397 400 class OutEdgeIt; … … 402 405 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 403 406 protected: 404 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG; 405 const Graph* G; 406 FlowMap* flow; 407 const CapacityMap* capacity; 408 //OldSymEdgeIt sym; 407 bool out_or_in; //true, iff out 409 408 OldOutEdgeIt out; 410 409 OldInEdgeIt in; 411 bool out_or_in; //true, iff out412 410 public: 413 411 EdgeIt() : out_or_in(true) { } 414 EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : 415 G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { } 416 //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) { } 417 Number free() const { 418 if (out_or_in) { 419 return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 420 } else { 421 return (/*resG->*/flow->get(in)); 412 // bool valid() const { 413 // return out_or_in && out.valid() || in.valid(); } 414 }; 415 416 417 class OutEdgeIt : public EdgeIt { 418 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 419 public: 420 OutEdgeIt() { } 421 //FIXME 422 OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { } 423 private: 424 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() { 425 resG.G->getFirst(out, v); 426 while( out.valid() && !(resG.free(out)>0) ) { ++out; } 427 if (!out.valid()) { 428 out_or_in=0; 429 resG.G->getFirst(in, v); 430 while( in.valid() && !(resG.free(in)>0) ) { ++in; } 422 431 } 423 432 } 424 bool valid() const { 425 return out_or_in && out.valid() || in.valid(); } 426 void augment(Number a) const { 427 if (out_or_in) { 428 /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a); 429 } else { 430 /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a); 431 } 432 } 433 void print() { 434 if (out_or_in) { 435 std::cout << "out "; 436 if (out.valid()) 437 std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); 438 else 439 std::cout << "invalid"; 440 } 441 else { 442 std::cout << "in "; 443 if (in.valid()) 444 std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); 445 else 446 std::cout << "invalid"; 447 } 448 std::cout << std::endl; 449 } 450 }; 451 452 Number free(OldOutEdgeIt out) const { 453 return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 454 } 455 Number free(OldInEdgeIt in) const { 456 return (/*resG->*/flow->get(in)); 457 } 458 459 class OutEdgeIt : public EdgeIt { 460 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 461 public: 462 OutEdgeIt() { } 463 private: 464 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 465 //out=/*resG->*/G->template first<OldOutEdgeIt>(v); 466 G->getFirst(out, v); 467 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 468 if (!out.valid()) { 469 out_or_in=0; 470 //in=/*resG->*/G->template first<OldInEdgeIt>(v); 471 G->getFirst(in, v); 472 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 473 } 474 } 475 public: 476 OutEdgeIt& operator++() { 477 if (out_or_in) { 478 NodeIt v=/*resG->*/G->aNode(out); 479 ++out; 480 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 481 if (!out.valid()) { 482 out_or_in=0; 483 G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v); 484 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 485 } 486 } else { 487 ++in; 488 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 489 } 490 return *this; 491 } 433 // public: 434 // OutEdgeIt& operator++() { 435 // if (out_or_in) { 436 // NodeIt v=/*resG->*/G->aNode(out); 437 // ++out; 438 // while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 439 // if (!out.valid()) { 440 // out_or_in=0; 441 // G->getFirst(in, v); 442 // while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 443 // } 444 // } else { 445 // ++in; 446 // while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 447 // } 448 // return *this; 449 // } 492 450 }; 493 451 … … 498 456 EachEdgeIt() { } 499 457 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } 500 EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 501 out_or_in=true; 502 G->getFirst(v); 503 if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt(); 504 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 458 EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() { 459 resG.G->getFirst(v); 460 if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt(); 461 while (out.valid() && !(resG.free(out)>0) ) { ++out; } 505 462 while (v.valid() && !out.valid()) { 506 463 ++v; 507 if (v.valid()) G->getFirst(out, v);508 while (out.valid() && !( EdgeIt::free()>0) ) { ++out; }464 if (v.valid()) resG.G->getFirst(out, v); 465 while (out.valid() && !(resG.free(out)>0) ) { ++out; } 509 466 } 510 467 if (!out.valid()) { 511 468 out_or_in=0; 512 G->getFirst(v);513 if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();514 while (in.valid() && !( EdgeIt::free()>0) ) { ++in; }469 resG.G->getFirst(v); 470 if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt(); 471 while (in.valid() && !(resG.free(in)>0) ) { ++in; } 515 472 while (v.valid() && !in.valid()) { 516 473 ++v; 517 if (v.valid()) G->getFirst(in, v);518 while (in.valid() && !( EdgeIt::free()>0) ) { ++in; }474 if (v.valid()) resG.G->getFirst(in, v); 475 while (in.valid() && !(resG.free(in)>0) ) { ++in; } 519 476 } 520 477 } 521 478 } 522 EachEdgeIt& operator++() {523 if (out_or_in) {524 ++out;525 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }526 while (v.valid() && !out.valid()) {527 ++v;528 if (v.valid()) G->getFirst(out, v);529 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }530 }531 if (!out.valid()) {532 out_or_in=0;533 G->getFirst(v);534 if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();535 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }536 while (v.valid() && !in.valid()) {537 ++v;538 if (v.valid()) G->getFirst(in, v);539 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }540 }541 }542 } else {543 ++in;544 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }545 while (v.valid() && !in.valid()) {546 ++v;547 if (v.valid()) G->getFirst(in, v);548 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }549 }550 }551 return *this;552 }553 }; 554 555 voidgetFirst(EachNodeIt& v) const { G->getFirst(v); }556 voidgetFirst(OutEdgeIt& e, NodeIt v) const {557 e=OutEdgeIt(* G, v, *flow, *capacity);558 } 559 voidgetFirst(EachEdgeIt& e) const {560 e=EachEdgeIt(* G, *flow, *capacity);479 // EachEdgeIt& operator++() { 480 // if (out_or_in) { 481 // ++out; 482 // while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 483 // while (v.valid() && !out.valid()) { 484 // ++v; 485 // if (v.valid()) G->getFirst(out, v); 486 // while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 487 // } 488 // if (!out.valid()) { 489 // out_or_in=0; 490 // G->getFirst(v); 491 // if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); 492 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 493 // while (v.valid() && !in.valid()) { 494 // ++v; 495 // if (v.valid()) G->getFirst(in, v); 496 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 497 // } 498 // } 499 // } else { 500 // ++in; 501 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 502 // while (v.valid() && !in.valid()) { 503 // ++v; 504 // if (v.valid()) G->getFirst(in, v); 505 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 506 // } 507 // } 508 // return *this; 509 // } 510 }; 511 512 EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); } 513 OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 514 e=OutEdgeIt(*this, v); 515 } 516 EachEdgeIt& getFirst(EachEdgeIt& e) const { 517 e=EachEdgeIt(*this); 561 518 } 562 519 … … 567 524 NodeIt v=G->aNode(e.out); 568 525 ++(e.out); 569 while( G->valid(e.out) && !( e.free()>0) ) { ++(e.out); }526 while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } 570 527 if (!G->valid(e.out)) { 571 528 e.out_or_in=0; 572 G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);573 while( G->valid(e.in) && !( e.free()>0) ) { ++(e.in); }529 G->getFirst(e.in, v); 530 while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 574 531 } 575 532 } else { 576 533 ++(e.in); 577 while( G->valid(e.in) && !( e.free()>0) ) { ++(e.in); }534 while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 578 535 } 579 536 return e; … … 583 540 if (e.out_or_in) { 584 541 ++(e.out); 585 while (G->valid(e.out) && !( e.free()>0) ) { ++(e.out); }542 while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } 586 543 while (G->valid(e.v) && !G->valid(e.out)) { 587 544 ++(e.v); 588 545 if (G->valid(e.v)) G->getFirst(e.out, e.v); 589 while (G->valid(e.out) && !( e.free()>0) ) { ++(e.out); }546 while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } 590 547 } 591 548 if (!G->valid(e.out)) { … … 593 550 G->getFirst(e.v); 594 551 if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt(); 595 while (G->valid(e.in) && !( e.free()>0) ) { ++(e.in); }552 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 596 553 while (G->valid(e.v) && !G->valid(e.in)) { 597 554 ++(e.v); 598 555 if (G->valid(e.v)) G->getFirst(e.in, e.v); 599 while (G->valid(e.in) && !( e.free()>0) ) { ++(e.in); }556 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 600 557 } 601 558 } 602 559 } else { 603 560 ++(e.in); 604 while (G->valid(e.in) && !( e.free()>0) ) { ++(e.in); }561 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 605 562 while (G->valid(e.v) && !G->valid(e.in)) { 606 563 ++(e.v); 607 564 if (G->valid(e.v)) G->getFirst(e.in, e.v); 608 while (G->valid(e.in) && !( e.free()>0) ) { ++(e.in); }565 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 609 566 } 610 567 } … … 642 599 bool valid(EdgeIt e) const { 643 600 return e.out_or_in ? G->valid(e.out) : G->valid(e.in); } 601 602 void augment(const EdgeIt& e, Number a) const { 603 if (e.out_or_in) 604 flow->set(e.out, flow->get(e.out)+a); 605 else 606 flow->set(e.in, flow->get(e.in)-a); 607 } 608 609 Number free(const EdgeIt& e) const { 610 if (e.out_or_in) 611 return (capacity->get(e.out)-flow->get(e.out)); 612 else 613 return (flow->get(e.in)); 614 } 615 616 Number free(OldOutEdgeIt out) const { 617 return (capacity->get(out)-flow->get(out)); 618 } 619 620 Number free(OldInEdgeIt in) const { 621 return (flow->get(in)); 622 } 644 623 645 624 template<typename T> class NodeMap : public Graph::NodeMap<T> { … … 680 659 } 681 660 }; 661 }; 662 663 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 664 class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> { 665 protected: 666 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges; 667 //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist; 668 public: 669 ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, 670 const CapacityMap& _capacity) : 671 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), 672 first_out_edges(*this) /*, dist(*this)*/ { 673 for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) { 674 OutEdgeIt e; 675 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n); 676 first_out_edges.set(n, e); 677 } 678 } 679 680 //void setGraph(Graph& _graph) { graph = &_graph; } 681 //Graph& getGraph() const { return (*graph); } 682 683 //TrivGraphWrapper() : graph(0) { } 684 //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { } 685 686 //typedef Graph BaseGraph; 687 688 //typedef typename Graph::NodeIt NodeIt; 689 //typedef typename Graph::EachNodeIt EachNodeIt; 690 691 //typedef typename Graph::EdgeIt EdgeIt; 692 //typedef typename Graph::OutEdgeIt OutEdgeIt; 693 //typedef typename Graph::InEdgeIt InEdgeIt; 694 //typedef typename Graph::SymEdgeIt SymEdgeIt; 695 //typedef typename Graph::EachEdgeIt EachEdgeIt; 696 697 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; 698 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt; 699 700 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; 701 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; 702 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; 703 //typedef typename Graph::SymEdgeIt SymEdgeIt; 704 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt; 705 706 EachNodeIt& getFirst(EachNodeIt& n) const { 707 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n); 708 } 709 710 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { 711 e=first_out_edges.get(n); 712 return e; 713 } 714 715 //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); } 716 //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const { 717 // return getFirst(i, p); } 718 719 //template<typename I> I getNext(const I& i) const { 720 // return graph->getNext(i); } 721 //template<typename I> I& next(I &i) const { return graph->next(i); } 722 723 template< typename It > It first() const { 724 It e; getFirst(e); return e; } 725 726 template< typename It > It first(const NodeIt& v) const { 727 It e; getFirst(e, v); return e; } 728 729 //NodeIt head(const EdgeIt& e) const { return graph->head(e); } 730 //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } 731 732 //template<typename I> bool valid(const I& i) const 733 // { return graph->valid(i); } 734 735 //int nodeNum() const { return graph->nodeNum(); } 736 //int edgeNum() const { return graph->edgeNum(); } 737 738 //template<typename I> NodeIt aNode(const I& e) const { 739 // return graph->aNode(e); } 740 //template<typename I> NodeIt bNode(const I& e) const { 741 // return graph->bNode(e); } 742 743 //NodeIt addNode() const { return graph->addNode(); } 744 //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 745 // return graph->addEdge(tail, head); } 746 747 //void erase(const OutEdgeIt& e) { 748 // first_out_edge(this->tail(e))=e; 749 //} 750 void erase(const EdgeIt& e) { 751 OutEdgeIt f(e); 752 next(f); 753 first_out_edges.set(this->tail(e), f); 754 } 755 //template<typename I> void erase(const I& i) const { graph->erase(i); } 756 757 //void clear() const { graph->clear(); } 758 759 template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> { 760 public: 761 NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : 762 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { } 763 NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : 764 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { } 765 }; 766 767 template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> { 768 public: 769 EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : 770 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { } 771 EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : 772 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { } 773 }; 774 }; 775 776 template<typename GraphWrapper> 777 class FilterGraphWrapper { 778 }; 779 780 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 781 class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> { 782 783 //Graph* graph; 784 785 public: 786 //typedef Graph BaseGraph; 787 788 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; 789 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt; 790 791 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; 792 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; 793 //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; 794 //typedef typename Graph::SymEdgeIt SymEdgeIt; 795 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt; 796 797 //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges; 798 799 public: 800 FilterGraphWrapper(const Graph& _G, FlowMap& _flow, 801 const CapacityMap& _capacity) : 802 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { 803 } 804 805 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { 806 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n); 807 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 808 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 809 return e; 810 } 811 812 EachNodeIt& next(EachNodeIt& e) const { 813 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 814 } 815 816 OutEdgeIt& next(OutEdgeIt& e) const { 817 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 818 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 819 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 820 return e; 821 } 822 823 EachNodeIt& getFirst(EachNodeIt& n) const { 824 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n); 825 } 826 827 void erase(const EdgeIt& e) { 828 OutEdgeIt f(e); 829 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); 830 while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) 831 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); 832 first_out_edges.set(this->tail(e), f); 833 } 834 835 //TrivGraphWrapper() : graph(0) { } 836 //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } 837 838 //void setGraph(Graph& _graph) { graph = &_graph; } 839 //Graph& getGraph() const { return (*graph); } 840 841 //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } 842 //template<typename I, typename P> I& getFirst(I& i, const P& p) const { 843 // return graph->getFirst(i, p); } 844 845 //template<typename I> I getNext(const I& i) const { 846 // return graph->getNext(i); } 847 //template<typename I> I& next(I &i) const { return graph->next(i); } 848 849 template< typename It > It first() const { 850 It e; getFirst(e); return e; } 851 852 template< typename It > It first(const NodeIt& v) const { 853 It e; getFirst(e, v); return e; } 854 855 //NodeIt head(const EdgeIt& e) const { return graph->head(e); } 856 //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } 857 858 //template<typename I> bool valid(const I& i) const 859 // { return graph->valid(i); } 860 861 //template<typename I> void setInvalid(const I &i); 862 //{ return graph->setInvalid(i); } 863 864 //int nodeNum() const { return graph->nodeNum(); } 865 //int edgeNum() const { return graph->edgeNum(); } 866 867 //template<typename I> NodeIt aNode(const I& e) const { 868 // return graph->aNode(e); } 869 //template<typename I> NodeIt bNode(const I& e) const { 870 // return graph->bNode(e); } 871 872 //NodeIt addNode() const { return graph->addNode(); } 873 //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 874 // return graph->addEdge(tail, head); } 875 876 //template<typename I> void erase(const I& i) const { graph->erase(i); } 877 878 //void clear() const { graph->clear(); } 879 880 template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> { 881 public: 882 NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) : 883 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { } 884 NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) : 885 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { } 886 }; 887 888 template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> { 889 public: 890 EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) : 891 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { } 892 EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) : 893 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { } 894 }; 895 896 public: 897 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist; 682 898 683 899 }; -
src/work/marci/makefile
r125 r168 17 17 18 18 edmonds_karp_demo: 19 $(CXX3) $(CXXFLAGS) - O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc20 $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo .cc19 $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc 20 $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc 21 21 22 22 edmonds_karp_demo_alpar:
Note: See TracChangeset
for help on using the changeset viewer.
