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    };