RhodeCode

      int n = _nodes->size();

      LargeValue length;

      int size;

      Node u;

      // Search for cycles that are already found

      _curr_found = false;

      for (int i = 0; i < n; ++i) {

        u = (*_nodes)[i];

        if (_data[u][k].dist == INF) continue;

        for (int j = k; j >= 0; --j) {

          if (level[u].first == i && level[u].second > 0) {

            // A cycle is found

            length = _data[u][level[u].second].dist - _data[u][j].dist;

            size = level[u].second - j;

            if (!_curr_found || length * _curr_size < _curr_length * size) {

              _curr_length = length;

              _curr_size = size;

              _curr_node = u;

              _curr_level = level[u].second;

              _curr_found = true;

            }

          }

          level[u] = Pair(i, j);

          u = _gr.source(_data[u][j].pred);

        }

      }

      // If at least one cycle is found, check the optimality condition

      LargeValue d;

      if (_curr_found && k < n) {

        // Find node potentials

        for (int i = 0; i < n; ++i) {

          u = (*_nodes)[i];

          pi[u] = INF;

          for (int j = 0; j <= k; ++j) {

            if (_data[u][j].dist < INF) {

              d = _data[u][j].dist * _curr_size - j * _curr_length;

              if (_tolerance.less(d, pi[u])) pi[u] = d;

            }

          }

        }

        // Check the optimality condition for all arcs

        bool done = true;

        for (ArcIt a(_gr); a != INVALID; ++a) {

          if (_tolerance.less(_length[a] * _curr_size - _curr_length,

                              pi[_gr.target(a)] - pi[_gr.source(a)]) ) {

            done = false;

            break;

          }