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

     2.1 --- a/test/bellman_ford_test.cc	Mon Aug 03 00:52:45 2009 +0200
     2.2 +++ b/test/bellman_ford_test.cc	Mon Aug 03 00:54:04 2009 +0200
     2.3 @@ -220,8 +220,64 @@
     2.4    }
     2.5  }
     2.6  
     2.7 +void checkBellmanFordNegativeCycle() {
     2.8 +  DIGRAPH_TYPEDEFS(SmartDigraph);
     2.9 +
    2.10 +  SmartDigraph gr;
    2.11 +  IntArcMap length(gr);
    2.12 +  
    2.13 +  Node n1 = gr.addNode();
    2.14 +  Node n2 = gr.addNode();
    2.15 +  Node n3 = gr.addNode();
    2.16 +  Node n4 = gr.addNode();
    2.17 +  
    2.18 +  Arc a1 = gr.addArc(n1, n2);
    2.19 +  Arc a2 = gr.addArc(n2, n2);
    2.20 +  
    2.21 +  length[a1] = 2;
    2.22 +  length[a2] = -1;
    2.23 +  
    2.24 +  {
    2.25 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
    2.26 +    bf.run(n1);
    2.27 +    StaticPath<SmartDigraph> p = bf.negativeCycle();
    2.28 +    check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
    2.29 +          "Wrong negative cycle.");
    2.30 +  }
    2.31 + 
    2.32 +  length[a2] = 0;
    2.33 +  
    2.34 +  {
    2.35 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
    2.36 +    bf.run(n1);
    2.37 +    check(bf.negativeCycle().empty(),
    2.38 +          "Negative cycle should not be found.");
    2.39 +  }
    2.40 +  
    2.41 +  length[gr.addArc(n1, n3)] = 5;
    2.42 +  length[gr.addArc(n4, n3)] = 1;
    2.43 +  length[gr.addArc(n2, n4)] = 2;
    2.44 +  length[gr.addArc(n3, n2)] = -4;
    2.45 +  
    2.46 +  {
    2.47 +    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
    2.48 +    bf.init();
    2.49 +    bf.addSource(n1);
    2.50 +    for (int i = 0; i < 4; ++i) {
    2.51 +      check(bf.negativeCycle().empty(),
    2.52 +            "Negative cycle should not be found.");
    2.53 +      bf.processNextRound();
    2.54 +    }
    2.55 +    StaticPath<SmartDigraph> p = bf.negativeCycle();
    2.56 +    check(p.length() == 3, "Wrong negative cycle.");
    2.57 +    check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
    2.58 +          "Wrong negative cycle.");
    2.59 +  }
    2.60 +}
    2.61 +
    2.62  int main() {
    2.63    checkBellmanFord<ListDigraph, int>();
    2.64    checkBellmanFord<SmartDigraph, double>();
    2.65 +  checkBellmanFordNegativeCycle();
    2.66    return 0;
    2.67  }