RhodeCode

    ///

    /// This function returns the number of arcs on the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    int cycleArcNum() const {

      return _best_size;

    }

    /// \brief Return the mean length of the found cycle.

    ///

    /// This function returns the mean length of the found cycle.

    ///

    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the

    /// following code.

    /// \code

    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();

    /// \endcode

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    double cycleMean() const {

      return static_cast<double>(_best_length) / _best_size;

    }

    /// \brief Return the found cycle.

    ///

    /// This function returns a const reference to the path structure

    /// storing the found cycle.

    ///

    /// \pre \ref run() or \ref findCycle() must be called before using

    /// this function.

    const Path& cycle() const {

      return *_cycle_path;

    }

    ///@}

  private:

    // Initialization

    void init() {

      if (!_cycle_path) {

        _local_path = true;

        _cycle_path = new Path;

      }

      _cycle_path->clear();

      _best_found = false;

      _best_length = 0;

      _best_size = 1;

      _cycle_path->clear();

      for (NodeIt u(_gr); u != INVALID; ++u)

        _data[u].clear();

    }

    // Find strongly connected components and initialize _comp_nodes

    // and _out_arcs

    void findComponents() {

      _comp_num = stronglyConnectedComponents(_gr, _comp);

      _comp_nodes.resize(_comp_num);

      if (_comp_num == 1) {

        _comp_nodes[0].clear();

        for (NodeIt n(_gr); n != INVALID; ++n) {

          _comp_nodes[0].push_back(n);

          _out_arcs[n].clear();

          for (OutArcIt a(_gr, n); a != INVALID; ++a) {

            _out_arcs[n].push_back(a);

          }

        }

      } else {

        for (int i = 0; i < _comp_num; ++i)

          _comp_nodes[i].clear();

        for (NodeIt n(_gr); n != INVALID; ++n) {

          int k = _comp[n];

          _comp_nodes[k].push_back(n);

          _out_arcs[n].clear();

          for (OutArcIt a(_gr, n); a != INVALID; ++a) {

            if (_comp[_gr.target(a)] == k) _out_arcs[n].push_back(a);

          }

        }

      }

    }

    // Initialize path data for the current component

    bool initComponent(int comp) {

      _nodes = &(_comp_nodes[comp]);

      int n = _nodes->size();

      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {

        return false;

      }      

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

        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));

      }

      return true;

    }

    // Process all rounds of computing path data for the current component.

    // _data[v][k] is the length of a shortest directed walk from the root

    // node to node v containing exactly k arcs.

    void processRounds() {

      Node start = (*_nodes)[0];

      _data[start][0] = PathData(0);

      _process.clear();

      _process.push_back(start);

      int k, n = _nodes->size();

      int next_check = 4;

      bool terminate = false;

      for (k = 1; k <= n && int(_process.size()) < n && !terminate; ++k) {

        processNextBuildRound(k);

        if (k == next_check || k == n) {

          terminate = checkTermination(k);

          next_check = next_check * 3 / 2;

        }

      }

      for ( ; k <= n && !terminate; ++k) {

        processNextFullRound(k);

        if (k == next_check || k == n) {

          terminate = checkTermination(k);

          next_check = next_check * 3 / 2;

        }

      }

    }

    // Process one round and rebuild _process

    void processNextBuildRound(int k) {

      std::vector<Node> next;

      Node u, v;

      Arc e;

      LargeValue d;

      for (int i = 0; i < int(_process.size()); ++i) {

        u = _process[i];

        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {

          e = _out_arcs[u][j];

          v = _gr.target(e);

          d = _data[u][k-1].dist + _length[e];

          if (_tolerance.less(d, _data[v][k].dist)) {

            if (_data[v][k].dist == INF) next.push_back(v);

            _data[v][k] = PathData(d, e);

          }

        }

      }

      _process.swap(next);

    }

    // Process one round using _nodes instead of _process

    void processNextFullRound(int k) {

      Node u, v;

      Arc e;

      LargeValue d;

      for (int i = 0; i < int(_nodes->size()); ++i) {

        u = (*_nodes)[i];

        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {

          e = _out_arcs[u][j];

          v = _gr.target(e);

          d = _data[u][k-1].dist + _length[e];

          if (_tolerance.less(d, _data[v][k].dist)) {

            _data[v][k] = PathData(d, e);

          }

        }

      }

    }

    // Check early termination

    bool checkTermination(int k) {

      typedef std::pair<int, int> Pair;

      typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0));

      typename GR::template NodeMap<LargeValue> pi(_gr);

      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;

          }

        }

        return done;

      }

      return (k == n);

    }

  }; //class HartmannOrlin

  ///@}

} //namespace lemon

#endif //LEMON_HARTMANN_ORLIN_H