464 bool isANodeExamined() const { return !(actual_edge.valid()); } |
466 bool isANodeExamined() const { return !(actual_edge.valid()); } |
465 const ReachedMap& getReachedMap() const { return reached; } |
467 const ReachedMap& getReachedMap() const { return reached; } |
466 const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; } |
468 const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; } |
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 } // namespace marci |
692 } // namespace marci |
470 |
693 |
471 #endif //BFS_ITERATOR_HH |
694 #endif //BFS_ITERATOR_HH |