1.1 --- a/lemon/bellman_ford.h Mon Aug 03 00:52:45 2009 +0200
1.2 +++ b/lemon/bellman_ford.h Mon Aug 03 00:54:04 2009 +0200
1.3 @@ -770,44 +770,34 @@
1.4 return (*_dist)[v] != OperationTraits::infinity();
1.5 }
1.6
1.7 - // TODO: implement negative cycle
1.8 -// /// \brief Gives back a negative cycle.
1.9 -// ///
1.10 -// /// This function gives back a negative cycle.
1.11 -// /// If the algorithm have not found yet negative cycle it will give back
1.12 -// /// an empty path.
1.13 -// Path negativeCycle() {
1.14 -// typename Digraph::template NodeMap<int> state(*digraph, 0);
1.15 -// for (ActiveIt it(*this); it != INVALID; ++it) {
1.16 -// if (state[it] == 0) {
1.17 -// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
1.18 -// if (state[t] == 0) {
1.19 -// state[t] = 1;
1.20 -// } else if (state[t] == 2) {
1.21 -// break;
1.22 -// } else {
1.23 -// p.clear();
1.24 -// typename Path::Builder b(p);
1.25 -// b.setStartNode(t);
1.26 -// b.pushFront(predArc(t));
1.27 -// for(Node s = predNode(t); s != t; s = predNode(s)) {
1.28 -// b.pushFront(predArc(s));
1.29 -// }
1.30 -// b.commit();
1.31 -// return true;
1.32 -// }
1.33 -// }
1.34 -// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
1.35 -// if (state[t] == 1) {
1.36 -// state[t] = 2;
1.37 -// } else {
1.38 -// break;
1.39 -// }
1.40 -// }
1.41 -// }
1.42 -// }
1.43 -// return false;
1.44 -// }
1.45 + /// \brief Gives back a negative cycle.
1.46 + ///
1.47 + /// This function gives back a directed cycle with negative total
1.48 + /// length if the algorithm has already found one.
1.49 + /// Otherwise it gives back an empty path.
1.50 + lemon::Path<Digraph> negativeCycle() {
1.51 + typename Digraph::template NodeMap<int> state(*_gr, -1);
1.52 + lemon::Path<Digraph> cycle;
1.53 + for (int i = 0; i < int(_process.size()); ++i) {
1.54 + if (state[_process[i]] != -1) continue;
1.55 + for (Node v = _process[i]; (*_pred)[v] != INVALID;
1.56 + v = _gr->source((*_pred)[v])) {
1.57 + if (state[v] == i) {
1.58 + cycle.addFront((*_pred)[v]);
1.59 + for (Node u = _gr->source((*_pred)[v]); u != v;
1.60 + u = _gr->source((*_pred)[u])) {
1.61 + cycle.addFront((*_pred)[u]);
1.62 + }
1.63 + return cycle;
1.64 + }
1.65 + else if (state[v] >= 0) {
1.66 + break;
1.67 + }
1.68 + state[v] = i;
1.69 + }
1.70 + }
1.71 + return cycle;
1.72 + }
1.73
1.74 ///@}
1.75 };