425 /// calculate the distances exactly for all at most \f$ k + 1 \f$ |
426 /// calculate the distances exactly for all at most \f$ k + 1 \f$ |
426 /// length path lengths. With \f$ k \f$ iteration this function |
427 /// length path lengths. With \f$ k \f$ iteration this function |
427 /// calculates the at most \f$ k \f$ length path lengths. |
428 /// calculates the at most \f$ k \f$ length path lengths. |
428 /// |
429 /// |
429 /// \warning The paths with limited edge number cannot be retrieved |
430 /// \warning The paths with limited edge number cannot be retrieved |
430 /// easily with \ref getPath() or \ref predEdge() functions. If you |
431 /// easily with \ref path() or \ref predEdge() functions. If you |
431 /// need the shortest path and not just the distance you should store |
432 /// need the shortest path and not just the distance you should store |
432 /// after each iteration the \ref predEdgeMap() map and manually build |
433 /// after each iteration the \ref predEdgeMap() map and manually build |
433 /// the path. |
434 /// the path. |
434 /// |
435 /// |
435 /// \return %True when the algorithm have not found more shorter |
436 /// \return %True when the algorithm have not found more shorter |
538 /// This method runs the %BellmanFord algorithm from the root |
539 /// This method runs the %BellmanFord algorithm from the root |
539 /// node(s) in order to compute the shortest path lengths with at |
540 /// node(s) in order to compute the shortest path lengths with at |
540 /// most \c num edge. |
541 /// most \c num edge. |
541 /// |
542 /// |
542 /// \warning The paths with limited edge number cannot be retrieved |
543 /// \warning The paths with limited edge number cannot be retrieved |
543 /// easily with \ref getPath() or \ref predEdge() functions. If you |
544 /// easily with \ref path() or \ref predEdge() functions. If you |
544 /// need the shortest path and not just the distance you should store |
545 /// need the shortest path and not just the distance you should store |
545 /// after each iteration the \ref predEdgeMap() map and manually build |
546 /// after each iteration the \ref predEdgeMap() map and manually build |
546 /// the path. |
547 /// the path. |
547 /// |
548 /// |
548 /// The algorithm computes |
549 /// The algorithm computes |
656 private: |
657 private: |
657 const BellmanFord* _algorithm; |
658 const BellmanFord* _algorithm; |
658 int _index; |
659 int _index; |
659 }; |
660 }; |
660 |
661 |
661 /// \brief Copies the shortest path to \c t into \c p |
662 typedef PredMapPath<Graph, PredMap> Path; |
|
663 |
|
664 /// \brief Gives back the shortest path. |
662 /// |
665 /// |
663 /// This function copies the shortest path to \c t into \c p. |
666 /// Gives back the shortest path. |
664 /// If it \c t is a source itself or unreachable, then it does not |
667 /// \pre The \c t should be reachable from the source. |
665 /// alter \c p. |
668 Path path(Node t) |
666 /// |
669 { |
667 /// \return Returns \c true if a path to \c t was actually copied to \c p, |
670 return Path(*graph, *_pred, t); |
668 /// \c false otherwise. |
671 } |
669 /// \sa DirPath |
672 |
670 template <typename Path> |
673 |
671 bool getPath(Path &p, Node t) { |
674 // TODO : implement negative cycle |
672 if(reached(t)) { |
675 // /// \brief Gives back a negative cycle. |
673 p.clear(); |
676 // /// |
674 typename Path::Builder b(p); |
677 // /// This function gives back a negative cycle. |
675 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) |
678 // /// If the algorithm have not found yet negative cycle it will give back |
676 b.pushFront(predEdge(t)); |
679 // /// an empty path. |
677 b.commit(); |
680 // Path negativeCycle() { |
678 return true; |
681 // typename Graph::template NodeMap<int> state(*graph, 0); |
679 } |
682 // for (ActiveIt it(*this); it != INVALID; ++it) { |
680 return false; |
683 // if (state[it] == 0) { |
681 } |
684 // for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { |
682 |
685 // if (state[t] == 0) { |
683 /// \brief Copies a negative cycle into path \c p. |
686 // state[t] = 1; |
684 /// |
687 // } else if (state[t] == 2) { |
685 /// This function copies a negative cycle into path \c p. |
688 // break; |
686 /// If the algorithm have not found yet negative cycle it will not change |
689 // } else { |
687 /// the given path and gives back false. |
690 // p.clear(); |
688 /// |
691 // typename Path::Builder b(p); |
689 /// \return Returns \c true if a cycle was actually copied to \c p, |
692 // b.setStartNode(t); |
690 /// \c false otherwise. |
693 // b.pushFront(predEdge(t)); |
691 /// \sa DirPath |
694 // for(Node s = predNode(t); s != t; s = predNode(s)) { |
692 template <typename Path> |
695 // b.pushFront(predEdge(s)); |
693 bool getNegativeCycle(Path& p) { |
696 // } |
694 typename Graph::template NodeMap<int> state(*graph, 0); |
697 // b.commit(); |
695 for (ActiveIt it(*this); it != INVALID; ++it) { |
698 // return true; |
696 if (state[it] == 0) { |
699 // } |
697 for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { |
700 // } |
698 if (state[t] == 0) { |
701 // for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { |
699 state[t] = 1; |
702 // if (state[t] == 1) { |
700 } else if (state[t] == 2) { |
703 // state[t] = 2; |
701 break; |
704 // } else { |
702 } else { |
705 // break; |
703 p.clear(); |
706 // } |
704 typename Path::Builder b(p); |
707 // } |
705 b.setStartNode(t); |
708 // } |
706 b.pushFront(predEdge(t)); |
709 // } |
707 for(Node s = predNode(t); s != t; s = predNode(s)) { |
710 // return false; |
708 b.pushFront(predEdge(s)); |
711 // } |
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 } |
|
722 } |
|
723 return false; |
|
724 } |
|
725 |
712 |
726 /// \brief The distance of a node from the root. |
713 /// \brief The distance of a node from the root. |
727 /// |
714 /// |
728 /// Returns the distance of a node from the root. |
715 /// Returns the distance of a node from the root. |
729 /// \pre \ref run() must be called before using this function. |
716 /// \pre \ref run() must be called before using this function. |