lemon/min_mean_cycle.h
 changeset 808 5795860737f5 parent 807 83ce7ce39f21 child 809 03887b5e0f6f
equal 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>".
    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() {
   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       }
   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         }