lemon/howard_mmc.h
changeset 1046 387483bf0a56
parent 1002 f63ba40a60f4
child 1049 7bf489cf624e
equal deleted inserted replaced
2:dda750affcb4 3:7330624c4b89
   147     typedef typename TR::Path Path;
   147     typedef typename TR::Path Path;
   148 
   148 
   149     /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
   149     /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
   150     typedef TR Traits;
   150     typedef TR Traits;
   151 
   151 
       
   152     /// \brief Constants for the causes of search termination.
       
   153     ///
       
   154     /// Enum type containing constants for the different causes of search
       
   155     /// termination. The \ref findCycleMean() function returns one of
       
   156     /// these values.
       
   157     enum TerminationCause {
       
   158       
       
   159       /// No directed cycle can be found in the digraph.
       
   160       NO_CYCLE = 0,
       
   161     
       
   162       /// Optimal solution (minimum cycle mean) is found.
       
   163       OPTIMAL = 1,
       
   164 
       
   165       /// The iteration count limit is reached.
       
   166       ITERATION_LIMIT
       
   167     };
       
   168 
   152   private:
   169   private:
   153 
   170 
   154     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   171     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   155 
   172 
   156     // The digraph the algorithm runs on
   173     // The digraph the algorithm runs on
   322     /// \endcode
   339     /// \endcode
   323     bool run() {
   340     bool run() {
   324       return findCycleMean() && findCycle();
   341       return findCycleMean() && findCycle();
   325     }
   342     }
   326 
   343 
   327     /// \brief Find the minimum cycle mean.
   344     /// \brief Find the minimum cycle mean (or an upper bound).
   328     ///
   345     ///
   329     /// This function finds the minimum mean cost of the directed
   346     /// This function finds the minimum mean cost of the directed
   330     /// cycles in the digraph.
   347     /// cycles in the digraph (or an upper bound for it).
   331     ///
   348     ///
   332     /// \return \c true if a directed cycle exists in the digraph.
   349     /// By default, the function finds the exact minimum cycle mean,
   333     bool findCycleMean() {
   350     /// but an optional limit can also be specified for the number of
       
   351     /// iterations performed during the search process.
       
   352     /// The return value indicates if the optimal solution is found
       
   353     /// or the iteration limit is reached. In the latter case, an
       
   354     /// approximate solution is provided, which corresponds to a directed
       
   355     /// cycle whose mean cost is relatively small, but not necessarily
       
   356     /// minimal.
       
   357     ///
       
   358     /// \param limit  The maximum allowed number of iterations during
       
   359     /// the search process. Its default value implies that the algorithm 
       
   360     /// runs until it finds the exact optimal solution.
       
   361     ///
       
   362     /// \return The termination cause of the search process.
       
   363     /// For more information, see \ref TerminationCause. 
       
   364     TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
   334       // Initialize and find strongly connected components
   365       // Initialize and find strongly connected components
   335       init();
   366       init();
   336       findComponents();
   367       findComponents();
   337 
   368 
   338       // Find the minimum cycle mean in the components
   369       // Find the minimum cycle mean in the components
       
   370       int iter_count = 0;
       
   371       bool iter_limit_reached = false;
   339       for (int comp = 0; comp < _comp_num; ++comp) {
   372       for (int comp = 0; comp < _comp_num; ++comp) {
   340         // Find the minimum mean cycle in the current component
   373         // Find the minimum mean cycle in the current component
   341         if (!buildPolicyGraph(comp)) continue;
   374         if (!buildPolicyGraph(comp)) continue;
   342         while (true) {
   375         while (true) {
       
   376           if (++iter_count > limit) {
       
   377             iter_limit_reached = true;
       
   378             break;
       
   379           }
   343           findPolicyCycle();
   380           findPolicyCycle();
   344           if (!computeNodeDistances()) break;
   381           if (!computeNodeDistances()) break;
   345         }
   382         }
       
   383 
   346         // Update the best cycle (global minimum mean cycle)
   384         // Update the best cycle (global minimum mean cycle)
   347         if ( _curr_found && (!_best_found ||
   385         if ( _curr_found && (!_best_found ||
   348              _curr_cost * _best_size < _best_cost * _curr_size) ) {
   386              _curr_cost * _best_size < _best_cost * _curr_size) ) {
   349           _best_found = true;
   387           _best_found = true;
   350           _best_cost = _curr_cost;
   388           _best_cost = _curr_cost;
   351           _best_size = _curr_size;
   389           _best_size = _curr_size;
   352           _best_node = _curr_node;
   390           _best_node = _curr_node;
   353         }
   391         }
   354       }
   392         
   355       return _best_found;
   393         if (iter_limit_reached) break;
       
   394       }
       
   395 
       
   396       if (iter_limit_reached) {
       
   397         return ITERATION_LIMIT;
       
   398       } else {
       
   399         return _best_found ? OPTIMAL : NO_CYCLE;
       
   400       }
   356     }
   401     }
   357 
   402 
   358     /// \brief Find a minimum mean directed cycle.
   403     /// \brief Find a minimum mean directed cycle.
   359     ///
   404     ///
   360     /// This function finds a directed cycle of minimum mean cost
   405     /// This function finds a directed cycle of minimum mean cost