Changeset 808:5795860737f5 in lemon
- Timestamp:
- 08/06/09 20:28:28 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_mean_cycle.h
r807 r808 33 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 92 /// \addtogroup shortest_path 36 93 /// @{ … … 45 102 /// \tparam LEN The type of the length map. The default 46 103 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 47 ///48 /// \warning \c LEN::Value must be convertible to \c double.49 104 #ifdef DOXYGEN 50 template <typename GR, typename LEN >105 template <typename GR, typename LEN, typename TR> 51 106 #else 52 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 110 #endif 55 111 class MinMeanCycle … … 57 113 public: 58 114 59 /// The type of the digraph the algorithm runs on60 typedef GRDigraph;115 /// The type of the digraph 116 typedef typename TR::Digraph Digraph; 61 117 /// The type of the length map 62 typedef LENLengthMap;118 typedef typename TR::LengthMap LengthMap; 63 119 /// The type of the arc lengths 64 typedef typename LengthMap::Value Value; 65 /// The type of the paths 66 typedef lemon::Path<Digraph> Path; 120 typedef typename TR::Value Value; 121 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 143 private: … … 77 152 // Data for the found cycles 78 153 bool _curr_found, _best_found; 79 Value _curr_length, _best_length;154 LargeValue _curr_length, _best_length; 80 155 int _curr_size, _best_size; 81 156 Node _curr_node, _best_node; … … 88 163 typename Digraph::template NodeMap<bool> _reached; 89 164 typename Digraph::template NodeMap<int> _level; 90 typename Digraph::template NodeMap< double> _dist;165 typename Digraph::template NodeMap<LargeValue> _dist; 91 166 92 167 // Data for storing the strongly connected components … … 100 175 std::vector<Node> _queue; 101 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 222 public: … … 236 353 /// \pre \ref run() or \ref findMinMean() must be called before 237 354 /// using this function. 238 Value cycleLength() const {355 LargeValue cycleLength() const { 239 356 return _best_length; 240 357 } … … 285 402 // Initialize 286 403 void init() { 287 _tol.epsilon(1e-6);288 404 if (!_cycle_path) { 289 405 _local_path = true; … … 334 450 } 335 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 454 Node u, v; … … 357 473 _level[(*_nodes)[i]] = -1; 358 474 } 359 Value clength;475 LargeValue clength; 360 476 int csize; 361 477 Node u, v; … … 393 509 _reached[(*_nodes)[i]] = false; 394 510 } 395 double curr_mean = double(_curr_length) / _curr_size;396 511 _qfront = _qback = 0; 397 512 _queue[0] = _curr_node; … … 407 522 if (_policy[u] == e && !_reached[u]) { 408 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 525 _queue[++_qback] = u; 411 526 } … … 424 539 _reached[u] = true; 425 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 542 _queue[++_qback] = u; 428 543 } … … 437 552 e = _in_arcs[v][j]; 438 553 u = _gr.source(e); 439 double delta = _dist[v] + _length[e] - curr_mean;440 if (_tol .less(delta, _dist[u])) {554 LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length; 555 if (_tolerance.less(delta, _dist[u])) { 441 556 _dist[u] = delta; 442 557 _policy[u] = e;
Note: See TracChangeset
for help on using the changeset viewer.