603 /// Before the use of these functions, |
603 /// Before the use of these functions, |
604 /// either run() or start() must be called. |
604 /// either run() or start() must be called. |
605 |
605 |
606 ///@{ |
606 ///@{ |
607 |
607 |
|
608 /// \brief Lemon iterator for get a active nodes. |
|
609 /// |
|
610 /// Lemon iterator for get a active nodes. This class provides a |
|
611 /// common style lemon iterator which gives back a subset of the |
|
612 /// nodes. The iterated nodes are active in the algorithm after |
|
613 /// the last phase so these should be checked in the next phase to |
|
614 /// find augmenting edges from these. |
|
615 class ActiveIt { |
|
616 public: |
|
617 |
|
618 /// \brief Constructor. |
|
619 /// |
|
620 /// Constructor for get the nodeset of the variable. |
|
621 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) |
|
622 { |
|
623 _index = _algorithm->_process.size() - 1; |
|
624 } |
|
625 |
|
626 /// \brief Invalid constructor. |
|
627 /// |
|
628 /// Invalid constructor. |
|
629 ActiveIt(Invalid) : _algorithm(0), _index(-1) {} |
|
630 |
|
631 /// \brief Conversion to node. |
|
632 /// |
|
633 /// Conversion to node. |
|
634 operator Node() const { |
|
635 return _index >= 0 ? _algorithm->_process[_index] : INVALID; |
|
636 } |
|
637 |
|
638 /// \brief Increment operator. |
|
639 /// |
|
640 /// Increment operator. |
|
641 ActiveIt& operator++() { |
|
642 --_index; |
|
643 return *this; |
|
644 } |
|
645 |
|
646 bool operator==(const ActiveIt& it) const { |
|
647 return (Node)(*this) == (Node)it; |
|
648 } |
|
649 bool operator!=(const ActiveIt& it) const { |
|
650 return (Node)(*this) != (Node)it; |
|
651 } |
|
652 bool operator<(const ActiveIt& it) const { |
|
653 return (Node)(*this) < (Node)it; |
|
654 } |
|
655 |
|
656 private: |
|
657 const BellmanFord* _algorithm; |
|
658 int _index; |
|
659 }; |
|
660 |
608 /// \brief Copies the shortest path to \c t into \c p |
661 /// \brief Copies the shortest path to \c t into \c p |
609 /// |
662 /// |
610 /// This function copies the shortest path to \c t into \c p. |
663 /// This function copies the shortest path to \c t into \c p. |
611 /// If it \c t is a source itself or unreachable, then it does not |
664 /// If it \c t is a source itself or unreachable, then it does not |
612 /// alter \c p. |
665 /// alter \c p. |
621 typename Path::Builder b(p); |
674 typename Path::Builder b(p); |
622 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) |
675 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) |
623 b.pushFront(predEdge(t)); |
676 b.pushFront(predEdge(t)); |
624 b.commit(); |
677 b.commit(); |
625 return true; |
678 return true; |
|
679 } |
|
680 return false; |
|
681 } |
|
682 |
|
683 /// \brief Copies a negative cycle into path \c p. |
|
684 /// |
|
685 /// This function copies a negative cycle into path \c p. |
|
686 /// If the algorithm have not found yet negative cycle it will not change |
|
687 /// the given path and gives back false. |
|
688 /// |
|
689 /// \return Returns \c true if a cycle was actually copied to \c p, |
|
690 /// \c false otherwise. |
|
691 /// \sa DirPath |
|
692 template <typename Path> |
|
693 bool getNegativeCycle(Path& p) { |
|
694 typename Graph::template NodeMap<int> state(*graph, 0); |
|
695 for (ActiveIt it(*this); it != INVALID; ++it) { |
|
696 if (state[it] == 0) { |
|
697 for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { |
|
698 if (state[t] == 0) { |
|
699 state[t] = 1; |
|
700 } else if (state[t] == 2) { |
|
701 break; |
|
702 } else { |
|
703 p.clear(); |
|
704 typename Path::Builder b(p); |
|
705 b.setStartNode(t); |
|
706 b.pushFront(predEdge(t)); |
|
707 for(Node s = predNode(t); s != t; s = predNode(s)) { |
|
708 b.pushFront(predEdge(s)); |
|
709 } |
|
710 b.commit(); |
|
711 return true; |
|
712 } |
|
713 } |
|
714 for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { |
|
715 if (state[t] == 1) { |
|
716 state[t] = 2; |
|
717 } else { |
|
718 break; |
|
719 } |
|
720 } |
|
721 } |
626 } |
722 } |
627 return false; |
723 return false; |
628 } |
724 } |
629 |
725 |
630 /// \brief The distance of a node from the root. |
726 /// \brief The distance of a node from the root. |