Changeset 75:87623302a68f in lemon0.x for src/work/bfs_iterator.hh
 Timestamp:
 02/16/04 12:29:48 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@98
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r64 r75 4 4 #include <queue> 5 5 #include <stack> 6 #include <utility> 7 #include <graph_wrapper.h> 6 8 7 9 namespace marci { … … 467 469 }; 468 470 471 472 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 473 class BfsIterator3 { 474 typedef typename Graph::NodeIt NodeIt; 475 const Graph& G; 476 std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue; 477 ReachedMap reached; 478 bool b_node_newly_reached; 479 OutEdgeIt actual_edge; 480 public: 481 BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { } 482 void pushAndSetReached(NodeIt s) { 483 reached.set(s, true); 484 if (bfs_queue.empty()) { 485 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); 486 actual_edge=bfs_queue.front().second; 487 if (actual_edge.valid()) { 488 NodeIt w=G.bNode(actual_edge); 489 if (!reached.get(w)) { 490 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); 491 reached.set(w, true); 492 b_node_newly_reached=true; 493 } else { 494 b_node_newly_reached=false; 495 } 496 } //else { 497 //} 498 } else { 499 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); 500 } 501 } 502 BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 503 operator++() { 504 if (bfs_queue.front().second.valid()) { 505 ++(bfs_queue.front().second); 506 actual_edge=bfs_queue.front().second; 507 if (actual_edge.valid()) { 508 NodeIt w=G.bNode(actual_edge); 509 if (!reached.get(w)) { 510 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); 511 reached.set(w, true); 512 b_node_newly_reached=true; 513 } else { 514 b_node_newly_reached=false; 515 } 516 } 517 } else { 518 bfs_queue.pop(); 519 if (!bfs_queue.empty()) { 520 actual_edge=bfs_queue.front().second; 521 if (actual_edge.valid()) { 522 NodeIt w=G.bNode(actual_edge); 523 if (!reached.get(w)) { 524 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); 525 reached.set(w, true); 526 b_node_newly_reached=true; 527 } else { 528 b_node_newly_reached=false; 529 } 530 } 531 } 532 } 533 return *this; 534 } 535 bool finished() const { return bfs_queue.empty(); } 536 operator OutEdgeIt () const { return actual_edge; } 537 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 538 bool isANodeExamined() const { return !(actual_edge.valid()); } 539 NodeIt aNode() const { return bfs_queue.front().first; } 540 NodeIt bNode() const { return G.bNode(actual_edge); } 541 const ReachedMap& getReachedMap() const { return reached; } 542 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } 543 }; 544 545 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 546 class BfsIterator4 { 547 typedef typename Graph::NodeIt NodeIt; 548 const Graph& G; 549 std::queue<NodeIt> bfs_queue; 550 ReachedMap reached; 551 bool b_node_newly_reached; 552 OutEdgeIt actual_edge; 553 public: 554 BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { } 555 void pushAndSetReached(NodeIt s) { 556 reached.set(s, true); 557 if (bfs_queue.empty()) { 558 bfs_queue.push(s); 559 G.getFirst(actual_edge, s); 560 if (actual_edge.valid()) { 561 NodeIt w=G.bNode(actual_edge); 562 if (!reached.get(w)) { 563 bfs_queue.push(w); 564 reached.set(w, true); 565 b_node_newly_reached=true; 566 } else { 567 b_node_newly_reached=false; 568 } 569 } 570 } else { 571 bfs_queue.push(s); 572 } 573 } 574 BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 575 operator++() { 576 if (actual_edge.valid()) { 577 ++actual_edge; 578 if (actual_edge.valid()) { 579 NodeIt w=G.bNode(actual_edge); 580 if (!reached.get(w)) { 581 bfs_queue.push(w); 582 reached.set(w, true); 583 b_node_newly_reached=true; 584 } else { 585 b_node_newly_reached=false; 586 } 587 } 588 } else { 589 bfs_queue.pop(); 590 if (!bfs_queue.empty()) { 591 G.getFirst(actual_edge, bfs_queue.front()); 592 if (actual_edge.valid()) { 593 NodeIt w=G.bNode(actual_edge); 594 if (!reached.get(w)) { 595 bfs_queue.push(w); 596 reached.set(w, true); 597 b_node_newly_reached=true; 598 } else { 599 b_node_newly_reached=false; 600 } 601 } 602 } 603 } 604 return *this; 605 } 606 bool finished() const { return bfs_queue.empty(); } 607 operator OutEdgeIt () const { return actual_edge; } 608 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 609 bool isANodeExamined() const { return !(actual_edge.valid()); } 610 NodeIt aNode() const { return bfs_queue.front(); } 611 NodeIt bNode() const { return G.bNode(actual_edge); } 612 const ReachedMap& getReachedMap() const { return reached; } 613 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 614 }; 615 616 617 template <typename GraphWrapper, typename ReachedMap> 618 class BfsIterator5 { 619 typedef typename GraphWrapper::NodeIt NodeIt; 620 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 621 GraphWrapper gw; 622 std::queue<NodeIt> bfs_queue; 623 ReachedMap reached; 624 bool b_node_newly_reached; 625 OutEdgeIt actual_edge; 626 public: 627 BfsIterator5(GraphWrapper _gw) : 628 gw(_gw), reached(_gw.getGraph()) { } 629 void pushAndSetReached(NodeIt s) { 630 reached.set(s, true); 631 if (bfs_queue.empty()) { 632 bfs_queue.push(s); 633 gw.getFirst(actual_edge, s); 634 if (actual_edge.valid()) { 635 NodeIt w=gw.bNode(actual_edge); 636 if (!reached.get(w)) { 637 bfs_queue.push(w); 638 reached.set(w, true); 639 b_node_newly_reached=true; 640 } else { 641 b_node_newly_reached=false; 642 } 643 } 644 } else { 645 bfs_queue.push(s); 646 } 647 } 648 BfsIterator5<GraphWrapper, ReachedMap>& 649 operator++() { 650 if (actual_edge.valid()) { 651 ++actual_edge; 652 if (actual_edge.valid()) { 653 NodeIt w=gw.bNode(actual_edge); 654 if (!reached.get(w)) { 655 bfs_queue.push(w); 656 reached.set(w, true); 657 b_node_newly_reached=true; 658 } else { 659 b_node_newly_reached=false; 660 } 661 } 662 } else { 663 bfs_queue.pop(); 664 if (!bfs_queue.empty()) { 665 gw.getFirst(actual_edge, bfs_queue.front()); 666 if (actual_edge.valid()) { 667 NodeIt w=gw.bNode(actual_edge); 668 if (!reached.get(w)) { 669 bfs_queue.push(w); 670 reached.set(w, true); 671 b_node_newly_reached=true; 672 } else { 673 b_node_newly_reached=false; 674 } 675 } 676 } 677 } 678 return *this; 679 } 680 bool finished() const { return bfs_queue.empty(); } 681 operator OutEdgeIt () const { return actual_edge; } 682 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 683 bool isANodeExamined() const { return !(actual_edge.valid()); } 684 NodeIt aNode() const { return bfs_queue.front(); } 685 NodeIt bNode() const { return gw.bNode(actual_edge); } 686 const ReachedMap& getReachedMap() const { return reached; } 687 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 688 }; 689 690 691 469 692 } // namespace marci 470 693
Note: See TracChangeset
for help on using the changeset viewer.