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

 4 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r144 r148 545 545 546 546 template <typename Graph, typename OutEdgeIt, 547 typename ReachedMap =typename Graph::NodeMap<bool>>547 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 548 548 class BfsIterator4 { 549 549 typedef typename Graph::NodeIt NodeIt; … … 567 567 bfs_queue.push(s); 568 568 G.getFirst(actual_edge, s); 569 if ( actual_edge.valid()) {569 if (G.valid(actual_edge)/*.valid()*/) { 570 570 NodeIt w=G.bNode(actual_edge); 571 571 if (!reached.get(w)) { … … 583 583 BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 584 584 operator++() { 585 if ( actual_edge.valid()) {586 ++actual_edge;587 if ( actual_edge.valid()) {585 if (G.valid(actual_edge)/*.valid()*/) { 586 /*++*/G.next(actual_edge); 587 if (G.valid(actual_edge)/*.valid()*/) { 588 588 NodeIt w=G.bNode(actual_edge); 589 589 if (!reached.get(w)) { … … 599 599 if (!bfs_queue.empty()) { 600 600 G.getFirst(actual_edge, bfs_queue.front()); 601 if ( actual_edge.valid()) {601 if (G.valid(actual_edge)/*.valid()*/) { 602 602 NodeIt w=G.bNode(actual_edge); 603 603 if (!reached.get(w)) { … … 616 616 operator OutEdgeIt () const { return actual_edge; } 617 617 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 618 bool isANodeExamined() const { return !( actual_edge.valid()); }618 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 619 619 NodeIt aNode() const { return bfs_queue.front(); } 620 620 NodeIt bNode() const { return G.bNode(actual_edge); } … … 623 623 }; 624 624 625 626 template <typename GraphWrapper, typename OutEdgeIt, 627 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > 628 class BfsIterator5 { 629 typedef typename GraphWrapper::NodeIt NodeIt; 630 GraphWrapper G; 631 std::queue<NodeIt> bfs_queue; 632 ReachedMap& reached; 633 bool b_node_newly_reached; 634 OutEdgeIt actual_edge; 635 bool own_reached_map; 636 public: 637 BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 638 G(_G), reached(_reached), 639 own_reached_map(false) { } 640 BfsIterator5(const GraphWrapper& _G) : 641 G(_G), reached(*(new ReachedMap(G /*, false*/))), 642 own_reached_map(true) { } 643 ~BfsIterator5() { if (own_reached_map) delete &reached; } 644 void pushAndSetReached(NodeIt s) { 645 reached.set(s, true); 646 if (bfs_queue.empty()) { 647 bfs_queue.push(s); 648 G.getFirst(actual_edge, s); 649 if (G.valid(actual_edge)/*.valid()*/) { 650 NodeIt w=G.bNode(actual_edge); 651 if (!reached.get(w)) { 652 bfs_queue.push(w); 653 reached.set(w, true); 654 b_node_newly_reached=true; 655 } else { 656 b_node_newly_reached=false; 657 } 658 } 659 } else { 660 bfs_queue.push(s); 661 } 662 } 663 BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 664 operator++() { 665 if (G.valid(actual_edge)/*.valid()*/) { 666 /*++*/G.next(actual_edge); 667 if (G.valid(actual_edge)/*.valid()*/) { 668 NodeIt w=G.bNode(actual_edge); 669 if (!reached.get(w)) { 670 bfs_queue.push(w); 671 reached.set(w, true); 672 b_node_newly_reached=true; 673 } else { 674 b_node_newly_reached=false; 675 } 676 } 677 } else { 678 bfs_queue.pop(); 679 if (!bfs_queue.empty()) { 680 G.getFirst(actual_edge, bfs_queue.front()); 681 if (G.valid(actual_edge)/*.valid()*/) { 682 NodeIt w=G.bNode(actual_edge); 683 if (!reached.get(w)) { 684 bfs_queue.push(w); 685 reached.set(w, true); 686 b_node_newly_reached=true; 687 } else { 688 b_node_newly_reached=false; 689 } 690 } 691 } 692 } 693 return *this; 694 } 695 bool finished() const { return bfs_queue.empty(); } 696 operator OutEdgeIt () const { return actual_edge; } 697 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 698 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 699 NodeIt aNode() const { return bfs_queue.front(); } 700 NodeIt bNode() const { return G.bNode(actual_edge); } 701 const ReachedMap& getReachedMap() const { return reached; } 702 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 703 }; 704 625 705 template <typename Graph, typename OutEdgeIt, 626 typename ReachedMap =typename Graph::NodeMap<bool>>706 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 627 707 class DfsIterator4 { 628 708 typedef typename Graph::NodeIt NodeIt; … … 651 731 actual_edge=dfs_stack.top(); 652 732 //actual_node=G.aNode(actual_edge); 653 if ( actual_edge.valid()) {733 if (G.valid(actual_edge)/*.valid()*/) { 654 734 NodeIt w=G.bNode(actual_edge); 655 735 actual_node=w; … … 660 740 } else { 661 741 actual_node=G.aNode(actual_edge); 662 ++(dfs_stack.top());742 /*++*/G.next(dfs_stack.top()); 663 743 b_node_newly_reached=false; 664 744 } … … 672 752 operator OutEdgeIt () const { return actual_edge; } 673 753 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 674 bool isANodeExamined() const { return !( actual_edge.valid()); }754 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 675 755 NodeIt aNode() const { return actual_node; /*FIXME*/} 676 756 NodeIt bNode() const { return G.bNode(actual_edge); } … … 679 759 }; 680 760 681 682 683 template <typename GraphWrapper, typename ReachedMap> 684 class BfsIterator5 { 761 template <typename GraphWrapper, typename OutEdgeIt, 762 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > 763 class DfsIterator5 { 685 764 typedef typename GraphWrapper::NodeIt NodeIt; 686 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 687 GraphWrapper gw; 688 std::queue<NodeIt> bfs_queue; 689 ReachedMap reached; 690 bool b_node_newly_reached; 691 OutEdgeIt actual_edge; 765 GraphWrapper G; 766 std::stack<OutEdgeIt> dfs_stack; 767 bool b_node_newly_reached; 768 OutEdgeIt actual_edge; 769 NodeIt actual_node; 770 ReachedMap& reached; 771 bool own_reached_map; 692 772 public: 693 BfsIterator5(GraphWrapper _gw) : 694 gw(_gw), reached(_gw.getGraph()) { } 773 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 774 G(_G), reached(_reached), 775 own_reached_map(false) { } 776 DfsIterator5(const GraphWrapper& _G) : 777 G(_G), reached(*(new ReachedMap(G /*, false*/))), 778 own_reached_map(true) { } 779 ~DfsIterator5() { if (own_reached_map) delete &reached; } 695 780 void pushAndSetReached(NodeIt s) { 781 actual_node=s; 696 782 reached.set(s, true); 697 if (bfs_queue.empty()) { 698 bfs_queue.push(s); 699 gw.getFirst(actual_edge, s); 700 if (actual_edge.valid()) { 701 NodeIt w=gw.bNode(actual_edge); 702 if (!reached.get(w)) { 703 bfs_queue.push(w); 704 reached.set(w, true); 705 b_node_newly_reached=true; 706 } else { 707 b_node_newly_reached=false; 708 } 709 } 710 } else { 711 bfs_queue.push(s); 712 } 713 } 714 BfsIterator5<GraphWrapper, ReachedMap>& 783 dfs_stack.push(G.template first<OutEdgeIt>(s)); 784 } 785 DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 715 786 operator++() { 716 if (actual_edge.valid()) { 717 ++actual_edge; 718 if (actual_edge.valid()) { 719 NodeIt w=gw.bNode(actual_edge); 720 if (!reached.get(w)) { 721 bfs_queue.push(w); 722 reached.set(w, true); 723 b_node_newly_reached=true; 724 } else { 725 b_node_newly_reached=false; 726 } 727 } 728 } else { 729 bfs_queue.pop(); 730 if (!bfs_queue.empty()) { 731 gw.getFirst(actual_edge, bfs_queue.front()); 732 if (actual_edge.valid()) { 733 NodeIt w=gw.bNode(actual_edge); 734 if (!reached.get(w)) { 735 bfs_queue.push(w); 736 reached.set(w, true); 737 b_node_newly_reached=true; 738 } else { 739 b_node_newly_reached=false; 740 } 741 } 742 } 743 } 744 return *this; 745 } 746 bool finished() const { return bfs_queue.empty(); } 787 actual_edge=dfs_stack.top(); 788 //actual_node=G.aNode(actual_edge); 789 if (G.valid(actual_edge)/*.valid()*/) { 790 NodeIt w=G.bNode(actual_edge); 791 actual_node=w; 792 if (!reached.get(w)) { 793 dfs_stack.push(G.template first<OutEdgeIt>(w)); 794 reached.set(w, true); 795 b_node_newly_reached=true; 796 } else { 797 actual_node=G.aNode(actual_edge); 798 /*++*/G.next(dfs_stack.top()); 799 b_node_newly_reached=false; 800 } 801 } else { 802 //actual_node=G.aNode(dfs_stack.top()); 803 dfs_stack.pop(); 804 } 805 return *this; 806 } 807 bool finished() const { return dfs_stack.empty(); } 747 808 operator OutEdgeIt () const { return actual_edge; } 748 809 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 749 bool isANodeExamined() const { return !( actual_edge.valid()); }750 NodeIt aNode() const { return bfs_queue.front();}751 NodeIt bNode() const { return gw.bNode(actual_edge); }810 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 811 NodeIt aNode() const { return actual_node; /*FIXME*/} 812 NodeIt bNode() const { return G.bNode(actual_edge); } 752 813 const ReachedMap& getReachedMap() const { return reached; } 753 const std:: queue<NodeIt>& getBfsQueue() const { return bfs_queue; }754 };814 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 815 }; 755 816 756 817 
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 
src/work/list_graph.hh
r139 r148 303 303 } 304 304 305 bool valid(NodeIt n) const { return n.valid(); } 305 306 bool valid(EdgeIt e) const { return e.valid(); } 306 bool valid(NodeIt n) const { return n.valid(); }307 307 308 308 template <typename It> It getNext(It it) const { 
src/work/marci/graph_wrapper.h
r105 r148 276 276 277 277 278 // FIXME: comparison should be made better!!! 279 template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap> 280 class ResGraphWrapper 281 { 282 Graph* graph; 283 284 public: 285 typedef Graph BaseGraph; 286 287 typedef typename Graph::NodeIt NodeIt; 288 typedef typename Graph::EdgeIt EdgeIt; 289 290 typedef typename Graph::EachNodeIt EachNodeIt; 278 279 // // FIXME: comparison should be made better!!! 280 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap> 281 // class ResGraphWrapper 282 // { 283 // Graph* graph; 284 285 // public: 286 // typedef Graph BaseGraph; 287 288 // typedef typename Graph::NodeIt NodeIt; 289 // typedef typename Graph::EdgeIt EdgeIt; 290 291 // typedef typename Graph::EachNodeIt EachNodeIt; 291 292 292 class OutEdgeIt {293 public:294 //Graph::NodeIt n;295 bool out_or_in;296 typename Graph::OutEdgeIt o;297 typename Graph::InEdgeIt i;298 };299 class InEdgeIt {300 public:301 //Graph::NodeIt n;302 bool out_or_in;303 typename Graph::OutEdgeIt o;304 typename Graph::InEdgeIt i;305 };306 typedef typename Graph::SymEdgeIt SymEdgeIt;307 typedef typename Graph::EachEdgeIt EachEdgeIt;308 309 int nodeNum() const { return graph>nodeNum(); }310 int edgeNum() const { return graph>edgeNum(); }311 312 NodeIt& getFirst(NodeIt& n) const { return graph>getFirst(n); }313 314 // EachEdge and SymEdge is missing!!!!315 // EdgeIt <> In/OutEdgeIt conversion is missing!!!!316 317 //FIXME318 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const319 {320 e.n=n;321 graph>getFirst(e.o,n);322 while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o))323 graph>goNext(e.o);324 if(!graph>valid(e.o)) {325 graph>getFirst(e.i,n);326 while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))327 graph>goNext(e.i);328 }329 return e;330 }331 / *332 OutEdgeIt &goNext(OutEdgeIt &e)333 {334 if(graph>valid(e.o)) {335 while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o))336 graph>goNext(e.o);337 if(graph>valid(e.o)) return e;338 else graph>getFirst(e.i,e.n);339 }340 else {341 while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))342 graph>goNext(e.i);343 return e;344 }345 }346 OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}347 */348 //bool valid(const OutEdgeIt e) { return graph>valid(e.o)graph>valid(e.i);}349 350 //FIXME351 InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const352 {353 e.n=n;354 graph>getFirst(e.i,n);355 while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i))356 graph>goNext(e.i);357 if(!graph>valid(e.i)) {358 graph>getFirst(e.o,n);359 while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))360 graph>goNext(e.o);361 }362 return e;363 }364 / *365 InEdgeIt &goNext(InEdgeIt &e)366 {367 if(graph>valid(e.i)) {368 while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i))369 graph>goNext(e.i);370 if(graph>valid(e.i)) return e;371 else graph>getFirst(e.o,e.n);372 }373 else {374 while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))375 graph>goNext(e.o);376 return e;377 }378 }379 InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}380 */381 //bool valid(const InEdgeIt e) { return graph>valid(e.i)graph>valid(e.o);}382 383 //template<typename I> I &goNext(I &i); { return graph>goNext(i); }384 //template<typename I> I next(const I i); { return graph>goNext(i); }385 386 template< typename It > It first() const {387 It e; getFirst(e); return e; }388 389 template< typename It > It first(NodeIt v) const {390 It e; getFirst(e, v); return e; }391 392 NodeIt head(const EdgeIt& e) const { return graph>head(e); }393 NodeIt tail(const EdgeIt& e) const { return graph>tail(e); }394 395 template<typename I> NodeIt aNode(const I& e) const {396 return graph>aNode(e); }397 template<typename I> NodeIt bNode(const I& e) const {398 return graph>bNode(e); }399 400 //template<typename I> bool valid(const I i);401 //{ return graph>valid(i); }402 403 //template<typename I> void setInvalid(const I &i);404 //{ return graph>setInvalid(i); }405 406 NodeIt addNode() { return graph>addNode(); }407 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {408 return graph>addEdge(tail, head); }409 410 template<typename I> void erase(const I& i) { graph>erase(i); }411 412 void clear() { graph>clear(); }413 414 template<typename S> class NodeMap : public Graph::NodeMap<S> { };415 template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };416 417 void setGraph(Graph& _graph) { graph = &_graph; }418 Graph& getGraph() { return (*graph); }419 420 //ResGraphWrapper() : graph(0) { }421 ResGraphWrapper(Graph& _graph) : graph(&_graph) { }422 };423 424 425 // FIXME: comparison should be made better!!!426 template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>427 class ConstResGraphWrapper428 {429 const Graph* graph;430 const LowerMap* low;431 FlowMap* flow;432 const UpperMap* up;433 public:434 typedef Graph BaseGraph;435 436 typedef typename Graph::NodeIt NodeIt;437 typedef typename Graph::EdgeIt EdgeIt;438 439 typedef typename Graph::EachNodeIt EachNodeIt;293 // class OutEdgeIt { 294 // public: 295 // //Graph::NodeIt n; 296 // bool out_or_in; 297 // typename Graph::OutEdgeIt o; 298 // typename Graph::InEdgeIt i; 299 // }; 300 // class InEdgeIt { 301 // public: 302 // //Graph::NodeIt n; 303 // bool out_or_in; 304 // typename Graph::OutEdgeIt o; 305 // typename Graph::InEdgeIt i; 306 // }; 307 // typedef typename Graph::SymEdgeIt SymEdgeIt; 308 // typedef typename Graph::EachEdgeIt EachEdgeIt; 309 310 // int nodeNum() const { return graph>nodeNum(); } 311 // int edgeNum() const { return graph>edgeNum(); } 312 313 // NodeIt& getFirst(NodeIt& n) const { return graph>getFirst(n); } 314 315 // // EachEdge and SymEdge is missing!!!! 316 // // EdgeIt <> In/OutEdgeIt conversion is missing!!!! 317 318 // //FIXME 319 // OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const 320 // { 321 // e.n=n; 322 // graph>getFirst(e.o,n); 323 // while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) 324 // graph>goNext(e.o); 325 // if(!graph>valid(e.o)) { 326 // graph>getFirst(e.i,n); 327 // while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) 328 // graph>goNext(e.i); 329 // } 330 // return e; 331 // } 332 // /* 333 // OutEdgeIt &goNext(OutEdgeIt &e) 334 // { 335 // if(graph>valid(e.o)) { 336 // while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) 337 // graph>goNext(e.o); 338 // if(graph>valid(e.o)) return e; 339 // else graph>getFirst(e.i,e.n); 340 // } 341 // else { 342 // while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) 343 // graph>goNext(e.i); 344 // return e; 345 // } 346 // } 347 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} 348 // */ 349 // //bool valid(const OutEdgeIt e) { return graph>valid(e.o)graph>valid(e.i);} 350 351 // //FIXME 352 // InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const 353 // { 354 // e.n=n; 355 // graph>getFirst(e.i,n); 356 // while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) 357 // graph>goNext(e.i); 358 // if(!graph>valid(e.i)) { 359 // graph>getFirst(e.o,n); 360 // while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) 361 // graph>goNext(e.o); 362 // } 363 // return e; 364 // } 365 // /* 366 // InEdgeIt &goNext(InEdgeIt &e) 367 // { 368 // if(graph>valid(e.i)) { 369 // while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) 370 // graph>goNext(e.i); 371 // if(graph>valid(e.i)) return e; 372 // else graph>getFirst(e.o,e.n); 373 // } 374 // else { 375 // while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) 376 // graph>goNext(e.o); 377 // return e; 378 // } 379 // } 380 // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} 381 // */ 382 // //bool valid(const InEdgeIt e) { return graph>valid(e.i)graph>valid(e.o);} 383 384 // //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 385 // //template<typename I> I next(const I i); { return graph>goNext(i); } 386 387 // template< typename It > It first() const { 388 // It e; getFirst(e); return e; } 389 390 // template< typename It > It first(NodeIt v) const { 391 // It e; getFirst(e, v); return e; } 392 393 // NodeIt head(const EdgeIt& e) const { return graph>head(e); } 394 // NodeIt tail(const EdgeIt& e) const { return graph>tail(e); } 395 396 // template<typename I> NodeIt aNode(const I& e) const { 397 // return graph>aNode(e); } 398 // template<typename I> NodeIt bNode(const I& e) const { 399 // return graph>bNode(e); } 400 401 // //template<typename I> bool valid(const I i); 402 // //{ return graph>valid(i); } 403 404 // //template<typename I> void setInvalid(const I &i); 405 // //{ return graph>setInvalid(i); } 406 407 // NodeIt addNode() { return graph>addNode(); } 408 // EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 409 // return graph>addEdge(tail, head); } 410 411 // template<typename I> void erase(const I& i) { graph>erase(i); } 412 413 // void clear() { graph>clear(); } 414 415 // template<typename S> class NodeMap : public Graph::NodeMap<S> { }; 416 // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { }; 417 418 // void setGraph(Graph& _graph) { graph = &_graph; } 419 // Graph& getGraph() { return (*graph); } 420 421 // //ResGraphWrapper() : graph(0) { } 422 // ResGraphWrapper(Graph& _graph) : graph(&_graph) { } 423 // }; 424 425 426 // // FIXME: comparison should be made better!!! 427 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap> 428 // class ConstResGraphWrapper 429 // { 430 // const Graph* graph; 431 // const LowerMap* low; 432 // FlowMap* flow; 433 // const UpperMap* up; 434 // public: 435 // typedef Graph BaseGraph; 436 437 // typedef typename Graph::NodeIt NodeIt; 438 // typedef typename Graph::EdgeIt EdgeIt; 439 440 // typedef typename Graph::EachNodeIt EachNodeIt; 440 441 441 class OutEdgeIt {442 public:443 //Graph::NodeIt n;444 bool out_or_in;445 typename Graph::SymEdgeIt sym;446 };447 class InEdgeIt {448 public:449 //Graph::NodeIt n;450 bool out_or_in;451 typename Graph::OutEdgeIt sym;452 };453 //typedef typename Graph::SymEdgeIt SymEdgeIt;454 //typedef typename Graph::EachEdgeIt EachEdgeIt;455 456 int nodeNum() const { return graph>nodeNum(); }457 //int edgeNum() const { return graph>edgeNum(); }458 459 NodeIt& getFirst(NodeIt& n) const { return graph>getFirst(n); }460 461 // EachEdge and SymEdge is missing!!!!462 // EdgeIt <> In/OutEdgeIt conversion is missing!!!!442 // class OutEdgeIt { 443 // public: 444 // //Graph::NodeIt n; 445 // bool out_or_in; 446 // typename Graph::SymEdgeIt sym; 447 // }; 448 // class InEdgeIt { 449 // public: 450 // //Graph::NodeIt n; 451 // bool out_or_in; 452 // typename Graph::OutEdgeIt sym; 453 // }; 454 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 455 // //typedef typename Graph::EachEdgeIt EachEdgeIt; 456 457 // int nodeNum() const { return graph>nodeNum(); } 458 // //int edgeNum() const { return graph>edgeNum(); } 459 460 // NodeIt& getFirst(NodeIt& n) const { return graph>getFirst(n); } 461 462 // // EachEdge and SymEdge is missing!!!! 463 // // EdgeIt <> In/OutEdgeIt conversion is missing!!!! 463 464 464 465 465 //FIXME466 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const467 {468 e.n=n;469 graph>getFirst(e.o,n);470 while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o))471 graph>goNext(e.o);472 if(!graph>valid(e.o)) {473 graph>getFirst(e.i,n);474 while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))475 graph>goNext(e.i);476 }477 return e;478 }479 / *480 OutEdgeIt &goNext(OutEdgeIt &e)481 {482 if(graph>valid(e.o)) {483 while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o))484 graph>goNext(e.o);485 if(graph>valid(e.o)) return e;486 else graph>getFirst(e.i,e.n);487 }488 else {489 while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))490 graph>goNext(e.i);491 return e;492 }493 }494 OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}495 */496 //bool valid(const OutEdgeIt e) { return graph>valid(e.o)graph>valid(e.i);}497 498 //FIXME499 InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const500 {501 e.n=n;502 graph>getFirst(e.i,n);503 while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i))504 graph>goNext(e.i);505 if(!graph>valid(e.i)) {506 graph>getFirst(e.o,n);507 while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))508 graph>goNext(e.o);509 }510 return e;511 }512 / *513 InEdgeIt &goNext(InEdgeIt &e)514 {515 if(graph>valid(e.i)) {516 while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i))517 graph>goNext(e.i);518 if(graph>valid(e.i)) return e;519 else graph>getFirst(e.o,e.n);520 }521 else {522 while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))523 graph>goNext(e.o);524 return e;525 }526 }527 InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}528 */529 //bool valid(const InEdgeIt e) { return graph>valid(e.i)graph>valid(e.o);}530 531 //template<typename I> I &goNext(I &i); { return graph>goNext(i); }532 //template<typename I> I next(const I i); { return graph>goNext(i); }533 534 template< typename It > It first() const {535 It e; getFirst(e); return e; }536 537 template< typename It > It first(NodeIt v) const {538 It e; getFirst(e, v); return e; }539 540 NodeIt head(const EdgeIt& e) const { return graph>head(e); }541 NodeIt tail(const EdgeIt& e) const { return graph>tail(e); }542 543 template<typename I> NodeIt aNode(const I& e) const {544 return graph>aNode(e); }545 template<typename I> NodeIt bNode(const I& e) const {546 return graph>bNode(e); }547 548 //template<typename I> bool valid(const I i);549 //{ return graph>valid(i); }550 551 //template<typename I> void setInvalid(const I &i);552 //{ return graph>setInvalid(i); }553 554 NodeIt addNode() { return graph>addNode(); }555 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {556 return graph>addEdge(tail, head); }557 558 template<typename I> void erase(const I& i) { graph>erase(i); }559 560 void clear() { graph>clear(); }561 562 template<typename S> class NodeMap : public Graph::NodeMap<S> { };563 template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };564 565 void setGraph(const Graph& _graph) { graph = &_graph; }566 const Graph& getGraph() { return (*graph); }567 568 //ConstResGraphWrapper() : graph(0) { }569 ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }570 };466 // //FIXME 467 // OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const 468 // { 469 // e.n=n; 470 // graph>getFirst(e.o,n); 471 // while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) 472 // graph>goNext(e.o); 473 // if(!graph>valid(e.o)) { 474 // graph>getFirst(e.i,n); 475 // while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) 476 // graph>goNext(e.i); 477 // } 478 // return e; 479 // } 480 // /* 481 // OutEdgeIt &goNext(OutEdgeIt &e) 482 // { 483 // if(graph>valid(e.o)) { 484 // while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) 485 // graph>goNext(e.o); 486 // if(graph>valid(e.o)) return e; 487 // else graph>getFirst(e.i,e.n); 488 // } 489 // else { 490 // while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) 491 // graph>goNext(e.i); 492 // return e; 493 // } 494 // } 495 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} 496 // */ 497 // //bool valid(const OutEdgeIt e) { return graph>valid(e.o)graph>valid(e.i);} 498 499 // //FIXME 500 // InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const 501 // { 502 // e.n=n; 503 // graph>getFirst(e.i,n); 504 // while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) 505 // graph>goNext(e.i); 506 // if(!graph>valid(e.i)) { 507 // graph>getFirst(e.o,n); 508 // while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) 509 // graph>goNext(e.o); 510 // } 511 // return e; 512 // } 513 // /* 514 // InEdgeIt &goNext(InEdgeIt &e) 515 // { 516 // if(graph>valid(e.i)) { 517 // while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) 518 // graph>goNext(e.i); 519 // if(graph>valid(e.i)) return e; 520 // else graph>getFirst(e.o,e.n); 521 // } 522 // else { 523 // while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) 524 // graph>goNext(e.o); 525 // return e; 526 // } 527 // } 528 // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} 529 // */ 530 // //bool valid(const InEdgeIt e) { return graph>valid(e.i)graph>valid(e.o);} 531 532 // //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 533 // //template<typename I> I next(const I i); { return graph>goNext(i); } 534 535 // template< typename It > It first() const { 536 // It e; getFirst(e); return e; } 537 538 // template< typename It > It first(NodeIt v) const { 539 // It e; getFirst(e, v); return e; } 540 541 // NodeIt head(const EdgeIt& e) const { return graph>head(e); } 542 // NodeIt tail(const EdgeIt& e) const { return graph>tail(e); } 543 544 // template<typename I> NodeIt aNode(const I& e) const { 545 // return graph>aNode(e); } 546 // template<typename I> NodeIt bNode(const I& e) const { 547 // return graph>bNode(e); } 548 549 // //template<typename I> bool valid(const I i); 550 // //{ return graph>valid(i); } 551 552 // //template<typename I> void setInvalid(const I &i); 553 // //{ return graph>setInvalid(i); } 554 555 // NodeIt addNode() { return graph>addNode(); } 556 // EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 557 // return graph>addEdge(tail, head); } 558 559 // template<typename I> void erase(const I& i) { graph>erase(i); } 560 561 // void clear() { graph>clear(); } 562 563 // template<typename S> class NodeMap : public Graph::NodeMap<S> { }; 564 // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { }; 565 566 // void setGraph(const Graph& _graph) { graph = &_graph; } 567 // const Graph& getGraph() { return (*graph); } 568 569 // //ConstResGraphWrapper() : graph(0) { } 570 // ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { } 571 // }; 571 572 572 573
Note: See TracChangeset
for help on using the changeset viewer.