*

  *

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

              typename TR = HowardMmcDefaultTraits<GR, CM> >

              typename TR = HowardMmcDefaultTraits<GR, CM> >

 #endif

 #endif

   class HowardMmc

   class HowardMmc

   {

   {

   public:

   public:

     /// The type of the digraph

     /// The type of the digraph

     typedef typename TR::Digraph Digraph;

     typedef typename TR::Digraph Digraph;

     /// The type of the cost map

     /// The type of the cost map

     typedef typename TR::CostMap CostMap;

     typedef typename TR::CostMap CostMap;

     /// The type of the arc costs

     /// The type of the arc costs

     typedef TR Traits;

     typedef TR Traits;

   private:

   private:

     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

     // The digraph the algorithm runs on

     // The digraph the algorithm runs on

     const Digraph &_gr;

     const Digraph &_gr;

     // The cost of the arcs

     // The cost of the arcs

     const CostMap &_cost;

     const CostMap &_cost;

     int _comp_num;

     int _comp_num;

     typename Digraph::template NodeMap<int> _comp;

     typename Digraph::template NodeMap<int> _comp;

     std::vector<std::vector<Node> > _comp_nodes;

     std::vector<std::vector<Node> > _comp_nodes;

     std::vector<Node>* _nodes;

     std::vector<Node>* _nodes;

     typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;

     typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;

     // Queue used for BFS search

     // Queue used for BFS search

     std::vector<Node> _queue;

     std::vector<Node> _queue;

     int _qfront, _qback;

     int _qfront, _qback;

     Tolerance _tolerance;

     Tolerance _tolerance;

     // Infinite constant

     // Infinite constant

     const LargeCost INF;

     const LargeCost INF;

   public:

   public:

     /// \name Named Template Parameters

     /// \name Named Template Parameters

     /// @{

     /// @{

     template <typename T>

     template <typename T>

     struct SetLargeCostTraits : public Traits {

     struct SetLargeCostTraits : public Traits {

     template <typename T>

     template <typename T>

     struct SetPath

     struct SetPath

       : public HowardMmc<GR, CM, SetPathTraits<T> > {

       : public HowardMmc<GR, CM, SetPathTraits<T> > {

       typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;

       typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;

     };

     };

     /// @}

     /// @}

   protected:

   protected:

     HowardMmc() {}

     HowardMmc() {}

     /// \return \c true if a directed cycle exists in the digraph.

     /// \return \c true if a directed cycle exists in the digraph.

     bool findCycleMean() {

     bool findCycleMean() {

       // Initialize and find strongly connected components

       // Initialize and find strongly connected components

       init();

       init();

       findComponents();

       findComponents();

       // Find the minimum cycle mean in the components

       // Find the minimum cycle mean in the components

       for (int comp = 0; comp < _comp_num; ++comp) {

       for (int comp = 0; comp < _comp_num; ++comp) {

         // Find the minimum mean cycle in the current component

         // Find the minimum mean cycle in the current component

         if (!buildPolicyGraph(comp)) continue;

         if (!buildPolicyGraph(comp)) continue;

         while (true) {

         while (true) {

       _best_found = false;

       _best_found = false;

       _best_cost = 0;

       _best_cost = 0;

       _best_size = 1;

       _best_size = 1;

       _cycle_path->clear();

       _cycle_path->clear();

     }

     }

     // Find strongly connected components and initialize _comp_nodes

     // Find strongly connected components and initialize _comp_nodes

     // and _in_arcs

     // and _in_arcs

     void findComponents() {

     void findComponents() {

       _comp_num = stronglyConnectedComponents(_gr, _comp);

       _comp_num = stronglyConnectedComponents(_gr, _comp);

       _comp_nodes.resize(_comp_num);

       _comp_nodes.resize(_comp_num);