lemon/min_mean_cycle.h
changeset 808 5795860737f5
parent 807 83ce7ce39f21
child 809 03887b5e0f6f
equal deleted inserted replaced
2:14291f853d9a 3:1090a4d02439
    30 #include <lemon/tolerance.h>
    30 #include <lemon/tolerance.h>
    31 #include <lemon/connectivity.h>
    31 #include <lemon/connectivity.h>
    32 
    32 
    33 namespace lemon {
    33 namespace lemon {
    34 
    34 
       
    35   /// \brief Default traits class of MinMeanCycle class.
       
    36   ///
       
    37   /// Default traits class of MinMeanCycle class.
       
    38   /// \tparam GR The type of the digraph.
       
    39   /// \tparam LEN The type of the length map.
       
    40   /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
       
    41 #ifdef DOXYGEN
       
    42   template <typename GR, typename LEN>
       
    43 #else
       
    44   template <typename GR, typename LEN,
       
    45     bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
       
    46 #endif
       
    47   struct MinMeanCycleDefaultTraits
       
    48   {
       
    49     /// The type of the digraph
       
    50     typedef GR Digraph;
       
    51     /// The type of the length map
       
    52     typedef LEN LengthMap;
       
    53     /// The type of the arc lengths
       
    54     typedef typename LengthMap::Value Value;
       
    55 
       
    56     /// \brief The large value type used for internal computations
       
    57     ///
       
    58     /// The large value type used for internal computations.
       
    59     /// It is \c long \c long if the \c Value type is integer,
       
    60     /// otherwise it is \c double.
       
    61     /// \c Value must be convertible to \c LargeValue.
       
    62     typedef double LargeValue;
       
    63 
       
    64     /// The tolerance type used for internal computations
       
    65     typedef lemon::Tolerance<LargeValue> Tolerance;
       
    66 
       
    67     /// \brief The path type of the found cycles
       
    68     ///
       
    69     /// The path type of the found cycles.
       
    70     /// It must conform to the \ref lemon::concepts::Path "Path" concept
       
    71     /// and it must have an \c addBack() function.
       
    72     typedef lemon::Path<Digraph> Path;
       
    73   };
       
    74 
       
    75   // Default traits class for integer value types
       
    76   template <typename GR, typename LEN>
       
    77   struct MinMeanCycleDefaultTraits<GR, LEN, true>
       
    78   {
       
    79     typedef GR Digraph;
       
    80     typedef LEN LengthMap;
       
    81     typedef typename LengthMap::Value Value;
       
    82 #ifdef LEMON_HAVE_LONG_LONG
       
    83     typedef long long LargeValue;
       
    84 #else
       
    85     typedef long LargeValue;
       
    86 #endif
       
    87     typedef lemon::Tolerance<LargeValue> Tolerance;
       
    88     typedef lemon::Path<Digraph> Path;
       
    89   };
       
    90 
       
    91 
    35   /// \addtogroup shortest_path
    92   /// \addtogroup shortest_path
    36   /// @{
    93   /// @{
    37 
    94 
    38   /// \brief Implementation of Howard's algorithm for finding a minimum
    95   /// \brief Implementation of Howard's algorithm for finding a minimum
    39   /// mean cycle.
    96   /// mean cycle.
    42   /// directed cycle of minimum mean length (cost) in a digraph.
    99   /// directed cycle of minimum mean length (cost) in a digraph.
    43   ///
   100   ///
    44   /// \tparam GR The type of the digraph the algorithm runs on.
   101   /// \tparam GR The type of the digraph the algorithm runs on.
    45   /// \tparam LEN The type of the length map. The default
   102   /// \tparam LEN The type of the length map. The default
    46   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   103   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    47   ///
       
    48   /// \warning \c LEN::Value must be convertible to \c double.
       
    49 #ifdef DOXYGEN
   104 #ifdef DOXYGEN
    50   template <typename GR, typename LEN>
   105   template <typename GR, typename LEN, typename TR>
    51 #else
   106 #else
    52   template < typename GR,
   107   template < typename GR,
    53              typename LEN = typename GR::template ArcMap<int> >
   108              typename LEN = typename GR::template ArcMap<int>,
       
   109              typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
    54 #endif
   110 #endif
    55   class MinMeanCycle
   111   class MinMeanCycle
    56   {
   112   {
    57   public:
   113   public:
    58   
   114   
    59     /// The type of the digraph the algorithm runs on
   115     /// The type of the digraph
    60     typedef GR Digraph;
   116     typedef typename TR::Digraph Digraph;
    61     /// The type of the length map
   117     /// The type of the length map
    62     typedef LEN LengthMap;
   118     typedef typename TR::LengthMap LengthMap;
    63     /// The type of the arc lengths
   119     /// The type of the arc lengths
    64     typedef typename LengthMap::Value Value;
   120     typedef typename TR::Value Value;
    65     /// The type of the paths
   121 
    66     typedef lemon::Path<Digraph> Path;
   122     /// \brief The large value type
       
   123     ///
       
   124     /// The large value type used for internal computations.
       
   125     /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
       
   126     /// it is \c long \c long if the \c Value type is integer,
       
   127     /// otherwise it is \c double.
       
   128     typedef typename TR::LargeValue LargeValue;
       
   129 
       
   130     /// The tolerance type
       
   131     typedef typename TR::Tolerance Tolerance;
       
   132 
       
   133     /// \brief The path type of the found cycles
       
   134     ///
       
   135     /// The path type of the found cycles.
       
   136     /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
       
   137     /// it is \ref lemon::Path "Path<Digraph>".
       
   138     typedef typename TR::Path Path;
       
   139 
       
   140     /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
       
   141     typedef TR Traits;
    67 
   142 
    68   private:
   143   private:
    69 
   144 
    70     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   145     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    71   
   146   
    74     // The length of the arcs
   149     // The length of the arcs
    75     const LengthMap &_length;
   150     const LengthMap &_length;
    76 
   151 
    77     // Data for the found cycles
   152     // Data for the found cycles
    78     bool _curr_found, _best_found;
   153     bool _curr_found, _best_found;
    79     Value _curr_length, _best_length;
   154     LargeValue _curr_length, _best_length;
    80     int _curr_size, _best_size;
   155     int _curr_size, _best_size;
    81     Node _curr_node, _best_node;
   156     Node _curr_node, _best_node;
    82 
   157 
    83     Path *_cycle_path;
   158     Path *_cycle_path;
    84     bool _local_path;
   159     bool _local_path;
    85 
   160 
    86     // Internal data used by the algorithm
   161     // Internal data used by the algorithm
    87     typename Digraph::template NodeMap<Arc> _policy;
   162     typename Digraph::template NodeMap<Arc> _policy;
    88     typename Digraph::template NodeMap<bool> _reached;
   163     typename Digraph::template NodeMap<bool> _reached;
    89     typename Digraph::template NodeMap<int> _level;
   164     typename Digraph::template NodeMap<int> _level;
    90     typename Digraph::template NodeMap<double> _dist;
   165     typename Digraph::template NodeMap<LargeValue> _dist;
    91 
   166 
    92     // Data for storing the strongly connected components
   167     // Data for storing the strongly connected components
    93     int _comp_num;
   168     int _comp_num;
    94     typename Digraph::template NodeMap<int> _comp;
   169     typename Digraph::template NodeMap<int> _comp;
    95     std::vector<std::vector<Node> > _comp_nodes;
   170     std::vector<std::vector<Node> > _comp_nodes;
    97     typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
   172     typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
    98     
   173     
    99     // Queue used for BFS search
   174     // Queue used for BFS search
   100     std::vector<Node> _queue;
   175     std::vector<Node> _queue;
   101     int _qfront, _qback;
   176     int _qfront, _qback;
       
   177 
       
   178     Tolerance _tolerance;
       
   179   
       
   180   public:
       
   181   
       
   182     /// \name Named Template Parameters
       
   183     /// @{
       
   184 
       
   185     template <typename T>
       
   186     struct SetLargeValueTraits : public Traits {
       
   187       typedef T LargeValue;
       
   188       typedef lemon::Tolerance<T> Tolerance;
       
   189     };
       
   190 
       
   191     /// \brief \ref named-templ-param "Named parameter" for setting
       
   192     /// \c LargeValue type.
       
   193     ///
       
   194     /// \ref named-templ-param "Named parameter" for setting \c LargeValue
       
   195     /// type. It is used for internal computations in the algorithm.
       
   196     template <typename T>
       
   197     struct SetLargeValue
       
   198       : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
       
   199       typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
       
   200     };
       
   201 
       
   202     template <typename T>
       
   203     struct SetPathTraits : public Traits {
       
   204       typedef T Path;
       
   205     };
       
   206 
       
   207     /// \brief \ref named-templ-param "Named parameter" for setting
       
   208     /// \c %Path type.
       
   209     ///
       
   210     /// \ref named-templ-param "Named parameter" for setting the \c %Path
       
   211     /// type of the found cycles.
       
   212     /// It must conform to the \ref lemon::concepts::Path "Path" concept
       
   213     /// and it must have an \c addBack() function.
       
   214     template <typename T>
       
   215     struct SetPath
       
   216       : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
       
   217       typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
       
   218     };
   102     
   219     
   103     Tolerance<double> _tol;
   220     /// @}
   104 
   221 
   105   public:
   222   public:
   106 
   223 
   107     /// \brief Constructor.
   224     /// \brief Constructor.
   108     ///
   225     ///
   233     ///
   350     ///
   234     /// This function returns the total length of the found cycle.
   351     /// This function returns the total length of the found cycle.
   235     ///
   352     ///
   236     /// \pre \ref run() or \ref findMinMean() must be called before
   353     /// \pre \ref run() or \ref findMinMean() must be called before
   237     /// using this function.
   354     /// using this function.
   238     Value cycleLength() const {
   355     LargeValue cycleLength() const {
   239       return _best_length;
   356       return _best_length;
   240     }
   357     }
   241 
   358 
   242     /// \brief Return the number of arcs on the found cycle.
   359     /// \brief Return the number of arcs on the found cycle.
   243     ///
   360     ///
   282 
   399 
   283   private:
   400   private:
   284 
   401 
   285     // Initialize
   402     // Initialize
   286     void init() {
   403     void init() {
   287       _tol.epsilon(1e-6);
       
   288       if (!_cycle_path) {
   404       if (!_cycle_path) {
   289         _local_path = true;
   405         _local_path = true;
   290         _cycle_path = new Path;
   406         _cycle_path = new Path;
   291       }
   407       }
   292       _queue.resize(countNodes(_gr));
   408       _queue.resize(countNodes(_gr));
   331       if (_nodes->size() < 1 ||
   447       if (_nodes->size() < 1 ||
   332           (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
   448           (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
   333         return false;
   449         return false;
   334       }
   450       }
   335       for (int i = 0; i < int(_nodes->size()); ++i) {
   451       for (int i = 0; i < int(_nodes->size()); ++i) {
   336         _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
   452         _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
   337       }
   453       }
   338       Node u, v;
   454       Node u, v;
   339       Arc e;
   455       Arc e;
   340       for (int i = 0; i < int(_nodes->size()); ++i) {
   456       for (int i = 0; i < int(_nodes->size()); ++i) {
   341         v = (*_nodes)[i];
   457         v = (*_nodes)[i];
   354     // Find the minimum mean cycle in the policy graph
   470     // Find the minimum mean cycle in the policy graph
   355     void findPolicyCycle() {
   471     void findPolicyCycle() {
   356       for (int i = 0; i < int(_nodes->size()); ++i) {
   472       for (int i = 0; i < int(_nodes->size()); ++i) {
   357         _level[(*_nodes)[i]] = -1;
   473         _level[(*_nodes)[i]] = -1;
   358       }
   474       }
   359       Value clength;
   475       LargeValue clength;
   360       int csize;
   476       int csize;
   361       Node u, v;
   477       Node u, v;
   362       _curr_found = false;
   478       _curr_found = false;
   363       for (int i = 0; i < int(_nodes->size()); ++i) {
   479       for (int i = 0; i < int(_nodes->size()); ++i) {
   364         u = (*_nodes)[i];
   480         u = (*_nodes)[i];
   390       // Find the component of the main cycle and compute node distances
   506       // Find the component of the main cycle and compute node distances
   391       // using reverse BFS
   507       // using reverse BFS
   392       for (int i = 0; i < int(_nodes->size()); ++i) {
   508       for (int i = 0; i < int(_nodes->size()); ++i) {
   393         _reached[(*_nodes)[i]] = false;
   509         _reached[(*_nodes)[i]] = false;
   394       }
   510       }
   395       double curr_mean = double(_curr_length) / _curr_size;
       
   396       _qfront = _qback = 0;
   511       _qfront = _qback = 0;
   397       _queue[0] = _curr_node;
   512       _queue[0] = _curr_node;
   398       _reached[_curr_node] = true;
   513       _reached[_curr_node] = true;
   399       _dist[_curr_node] = 0;
   514       _dist[_curr_node] = 0;
   400       Node u, v;
   515       Node u, v;
   404         for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
   519         for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
   405           e = _in_arcs[v][j];
   520           e = _in_arcs[v][j];
   406           u = _gr.source(e);
   521           u = _gr.source(e);
   407           if (_policy[u] == e && !_reached[u]) {
   522           if (_policy[u] == e && !_reached[u]) {
   408             _reached[u] = true;
   523             _reached[u] = true;
   409             _dist[u] = _dist[v] + _length[e] - curr_mean;
   524             _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
   410             _queue[++_qback] = u;
   525             _queue[++_qback] = u;
   411           }
   526           }
   412         }
   527         }
   413       }
   528       }
   414 
   529 
   421           e = _in_arcs[v][j];
   536           e = _in_arcs[v][j];
   422           u = _gr.source(e);
   537           u = _gr.source(e);
   423           if (!_reached[u]) {
   538           if (!_reached[u]) {
   424             _reached[u] = true;
   539             _reached[u] = true;
   425             _policy[u] = e;
   540             _policy[u] = e;
   426             _dist[u] = _dist[v] + _length[e] - curr_mean;
   541             _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
   427             _queue[++_qback] = u;
   542             _queue[++_qback] = u;
   428           }
   543           }
   429         }
   544         }
   430       }
   545       }
   431 
   546 
   434       for (int i = 0; i < int(_nodes->size()); ++i) {
   549       for (int i = 0; i < int(_nodes->size()); ++i) {
   435         v = (*_nodes)[i];
   550         v = (*_nodes)[i];
   436         for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
   551         for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
   437           e = _in_arcs[v][j];
   552           e = _in_arcs[v][j];
   438           u = _gr.source(e);
   553           u = _gr.source(e);
   439           double delta = _dist[v] + _length[e] - curr_mean;
   554           LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
   440           if (_tol.less(delta, _dist[u])) {
   555           if (_tolerance.less(delta, _dist[u])) {
   441             _dist[u] = delta;
   556             _dist[u] = delta;
   442             _policy[u] = e;
   557             _policy[u] = e;
   443             improved = true;
   558             improved = true;
   444           }
   559           }
   445         }
   560         }