768 /// using this function. |
768 /// using this function. |
769 bool reached(Node v) const { |
769 bool reached(Node v) const { |
770 return (*_dist)[v] != OperationTraits::infinity(); |
770 return (*_dist)[v] != OperationTraits::infinity(); |
771 } |
771 } |
772 |
772 |
773 // TODO: implement negative cycle |
773 /// \brief Gives back a negative cycle. |
774 // /// \brief Gives back a negative cycle. |
774 /// |
775 // /// |
775 /// This function gives back a directed cycle with negative total |
776 // /// This function gives back a negative cycle. |
776 /// length if the algorithm has already found one. |
777 // /// If the algorithm have not found yet negative cycle it will give back |
777 /// Otherwise it gives back an empty path. |
778 // /// an empty path. |
778 lemon::Path<Digraph> negativeCycle() { |
779 // Path negativeCycle() { |
779 typename Digraph::template NodeMap<int> state(*_gr, -1); |
780 // typename Digraph::template NodeMap<int> state(*digraph, 0); |
780 lemon::Path<Digraph> cycle; |
781 // for (ActiveIt it(*this); it != INVALID; ++it) { |
781 for (int i = 0; i < int(_process.size()); ++i) { |
782 // if (state[it] == 0) { |
782 if (state[_process[i]] != -1) continue; |
783 // for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { |
783 for (Node v = _process[i]; (*_pred)[v] != INVALID; |
784 // if (state[t] == 0) { |
784 v = _gr->source((*_pred)[v])) { |
785 // state[t] = 1; |
785 if (state[v] == i) { |
786 // } else if (state[t] == 2) { |
786 cycle.addFront((*_pred)[v]); |
787 // break; |
787 for (Node u = _gr->source((*_pred)[v]); u != v; |
788 // } else { |
788 u = _gr->source((*_pred)[u])) { |
789 // p.clear(); |
789 cycle.addFront((*_pred)[u]); |
790 // typename Path::Builder b(p); |
790 } |
791 // b.setStartNode(t); |
791 return cycle; |
792 // b.pushFront(predArc(t)); |
792 } |
793 // for(Node s = predNode(t); s != t; s = predNode(s)) { |
793 else if (state[v] >= 0) { |
794 // b.pushFront(predArc(s)); |
794 break; |
795 // } |
795 } |
796 // b.commit(); |
796 state[v] = i; |
797 // return true; |
797 } |
798 // } |
798 } |
799 // } |
799 return cycle; |
800 // for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { |
800 } |
801 // if (state[t] == 1) { |
|
802 // state[t] = 2; |
|
803 // } else { |
|
804 // break; |
|
805 // } |
|
806 // } |
|
807 // } |
|
808 // } |
|
809 // return false; |
|
810 // } |
|
811 |
801 |
812 ///@} |
802 ///@} |
813 }; |
803 }; |
814 |
804 |
815 /// \brief Default traits class of bellmanFord() function. |
805 /// \brief Default traits class of bellmanFord() function. |