Changeset 942:d3ea191c3412 in lemon for lemon/howard_mmc.h
 Timestamp:
 03/13/10 22:01:38 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 moved
Legend:
 Unmodified
 Added
 Removed

lemon/howard_mmc.h
r941 r942 17 17 */ 18 18 19 #ifndef LEMON_HOWARD_ H20 #define LEMON_HOWARD_ H19 #ifndef LEMON_HOWARD_MMC_H 20 #define LEMON_HOWARD_MMC_H 21 21 22 22 /// \ingroup min_mean_cycle … … 34 34 namespace lemon { 35 35 36 /// \brief Default traits class of Howard class.36 /// \brief Default traits class of HowardMmc class. 37 37 /// 38 /// Default traits class of Howard class.38 /// Default traits class of HowardMmc class. 39 39 /// \tparam GR The type of the digraph. 40 /// \tparam LEN The type of the lengthmap.40 /// \tparam CM The type of the cost map. 41 41 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 42 42 #ifdef DOXYGEN 43 template <typename GR, typename LEN>43 template <typename GR, typename CM> 44 44 #else 45 template <typename GR, typename LEN,46 bool integer = std::numeric_limits<typename LEN::Value>::is_integer>45 template <typename GR, typename CM, 46 bool integer = std::numeric_limits<typename CM::Value>::is_integer> 47 47 #endif 48 struct Howard DefaultTraits48 struct HowardMmcDefaultTraits 49 49 { 50 50 /// The type of the digraph 51 51 typedef GR Digraph; 52 /// The type of the lengthmap53 typedef LEN LengthMap;54 /// The type of the arc lengths55 typedef typename LengthMap::Value Value;56 57 /// \brief The large valuetype used for internal computations58 /// 59 /// The large valuetype used for internal computations.60 /// It is \c long \c long if the \c Valuetype is integer,52 /// The type of the cost map 53 typedef CM CostMap; 54 /// The type of the arc costs 55 typedef typename CostMap::Value Cost; 56 57 /// \brief The large cost type used for internal computations 58 /// 59 /// The large cost type used for internal computations. 60 /// It is \c long \c long if the \c Cost type is integer, 61 61 /// otherwise it is \c double. 62 /// \c Value must be convertible to \c LargeValue.63 typedef double Large Value;62 /// \c Cost must be convertible to \c LargeCost. 63 typedef double LargeCost; 64 64 65 65 /// The tolerance type used for internal computations 66 typedef lemon::Tolerance<Large Value> Tolerance;66 typedef lemon::Tolerance<LargeCost> Tolerance; 67 67 68 68 /// \brief The path type of the found cycles … … 74 74 }; 75 75 76 // Default traits class for integer valuetypes77 template <typename GR, typename LEN>78 struct Howard DefaultTraits<GR, LEN, true>76 // Default traits class for integer cost types 77 template <typename GR, typename CM> 78 struct HowardMmcDefaultTraits<GR, CM, true> 79 79 { 80 80 typedef GR Digraph; 81 typedef LEN LengthMap;82 typedef typename LengthMap::Value Value;81 typedef CM CostMap; 82 typedef typename CostMap::Value Cost; 83 83 #ifdef LEMON_HAVE_LONG_LONG 84 typedef long long Large Value;84 typedef long long LargeCost; 85 85 #else 86 typedef long Large Value;86 typedef long LargeCost; 87 87 #endif 88 typedef lemon::Tolerance<Large Value> Tolerance;88 typedef lemon::Tolerance<LargeCost> Tolerance; 89 89 typedef lemon::Path<Digraph> Path; 90 90 }; … … 98 98 /// 99 99 /// This class implements Howard's policy iteration algorithm for finding 100 /// a directed cycle of minimum mean length (cost)in a digraph100 /// a directed cycle of minimum mean cost in a digraph 101 101 /// \ref amo93networkflows, \ref dasdan98minmeancycle. 102 102 /// This class provides the most efficient algorithm for the … … 105 105 /// 106 106 /// \tparam GR The type of the digraph the algorithm runs on. 107 /// \tparam LEN The type of the lengthmap. The default107 /// \tparam CM The type of the cost map. The default 108 108 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 109 109 /// \tparam TR The traits class that defines various types used by the 110 /// algorithm. By default, it is \ref Howard DefaultTraits111 /// "Howard DefaultTraits<GR, LEN>".110 /// algorithm. By default, it is \ref HowardMmcDefaultTraits 111 /// "HowardMmcDefaultTraits<GR, CM>". 112 112 /// In most cases, this parameter should not be set directly, 113 113 /// consider to use the named template parameters instead. 114 114 #ifdef DOXYGEN 115 template <typename GR, typename LEN, typename TR>115 template <typename GR, typename CM, typename TR> 116 116 #else 117 117 template < typename GR, 118 typename LEN= typename GR::template ArcMap<int>,119 typename TR = Howard DefaultTraits<GR, LEN> >118 typename CM = typename GR::template ArcMap<int>, 119 typename TR = HowardMmcDefaultTraits<GR, CM> > 120 120 #endif 121 class Howard 121 class HowardMmc 122 122 { 123 123 public: … … 125 125 /// The type of the digraph 126 126 typedef typename TR::Digraph Digraph; 127 /// The type of the lengthmap128 typedef typename TR:: LengthMap LengthMap;129 /// The type of the arc lengths130 typedef typename TR:: Value Value;131 132 /// \brief The large valuetype133 /// 134 /// The large valuetype used for internal computations.135 /// By default, it is \c long \c long if the \c Valuetype is integer,127 /// The type of the cost map 128 typedef typename TR::CostMap CostMap; 129 /// The type of the arc costs 130 typedef typename TR::Cost Cost; 131 132 /// \brief The large cost type 133 /// 134 /// The large cost type used for internal computations. 135 /// By default, it is \c long \c long if the \c Cost type is integer, 136 136 /// otherwise it is \c double. 137 typedef typename TR::Large Value LargeValue;137 typedef typename TR::LargeCost LargeCost; 138 138 139 139 /// The tolerance type … … 143 143 /// 144 144 /// The path type of the found cycles. 145 /// Using the \ref Howard DefaultTraits "default traits class",145 /// Using the \ref HowardMmcDefaultTraits "default traits class", 146 146 /// it is \ref lemon::Path "Path<Digraph>". 147 147 typedef typename TR::Path Path; 148 148 149 /// The \ref Howard DefaultTraits "traits class" of the algorithm149 /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm 150 150 typedef TR Traits; 151 151 … … 156 156 // The digraph the algorithm runs on 157 157 const Digraph &_gr; 158 // The lengthof the arcs159 const LengthMap &_length;158 // The cost of the arcs 159 const CostMap &_cost; 160 160 161 161 // Data for the found cycles 162 162 bool _curr_found, _best_found; 163 Large Value _curr_length, _best_length;163 LargeCost _curr_cost, _best_cost; 164 164 int _curr_size, _best_size; 165 165 Node _curr_node, _best_node; … … 172 172 typename Digraph::template NodeMap<bool> _reached; 173 173 typename Digraph::template NodeMap<int> _level; 174 typename Digraph::template NodeMap<Large Value> _dist;174 typename Digraph::template NodeMap<LargeCost> _dist; 175 175 176 176 // Data for storing the strongly connected components … … 188 188 189 189 // Infinite constant 190 const Large ValueINF;190 const LargeCost INF; 191 191 192 192 public: … … 196 196 197 197 template <typename T> 198 struct SetLarge ValueTraits : public Traits {199 typedef T Large Value;198 struct SetLargeCostTraits : public Traits { 199 typedef T LargeCost; 200 200 typedef lemon::Tolerance<T> Tolerance; 201 201 }; 202 202 203 203 /// \brief \ref namedtemplparam "Named parameter" for setting 204 /// \c Large Valuetype.205 /// 206 /// \ref namedtemplparam "Named parameter" for setting \c Large Value204 /// \c LargeCost type. 205 /// 206 /// \ref namedtemplparam "Named parameter" for setting \c LargeCost 207 207 /// type. It is used for internal computations in the algorithm. 208 208 template <typename T> 209 struct SetLarge Value210 : public Howard <GR, LEN, SetLargeValueTraits<T> > {211 typedef Howard <GR, LEN, SetLargeValueTraits<T> > Create;209 struct SetLargeCost 210 : public HowardMmc<GR, CM, SetLargeCostTraits<T> > { 211 typedef HowardMmc<GR, CM, SetLargeCostTraits<T> > Create; 212 212 }; 213 213 … … 226 226 template <typename T> 227 227 struct SetPath 228 : public Howard <GR, LEN, SetPathTraits<T> > {229 typedef Howard <GR, LEN, SetPathTraits<T> > Create;228 : public HowardMmc<GR, CM, SetPathTraits<T> > { 229 typedef HowardMmc<GR, CM, SetPathTraits<T> > Create; 230 230 }; 231 231 … … 234 234 protected: 235 235 236 Howard () {}236 HowardMmc() {} 237 237 238 238 public: … … 243 243 /// 244 244 /// \param digraph The digraph the algorithm runs on. 245 /// \param length The lengths (costs)of the arcs.246 Howard ( const Digraph &digraph,247 const LengthMap &length) :248 _gr(digraph), _ length(length), _best_found(false),249 _best_ length(0), _best_size(1), _cycle_path(NULL), _local_path(false),245 /// \param cost The costs of the arcs. 246 HowardMmc( const Digraph &digraph, 247 const CostMap &cost ) : 248 _gr(digraph), _cost(cost), _best_found(false), 249 _best_cost(0), _best_size(1), _cycle_path(NULL), _local_path(false), 250 250 _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph), 251 251 _comp(digraph), _in_arcs(digraph), 252 INF(std::numeric_limits<Large Value>::has_infinity ?253 std::numeric_limits<Large Value>::infinity() :254 std::numeric_limits<Large Value>::max())252 INF(std::numeric_limits<LargeCost>::has_infinity ? 253 std::numeric_limits<LargeCost>::infinity() : 254 std::numeric_limits<LargeCost>::max()) 255 255 {} 256 256 257 257 /// Destructor. 258 ~Howard () {258 ~HowardMmc() { 259 259 if (_local_path) delete _cycle_path; 260 260 } … … 266 266 /// 267 267 /// If you don't call this function before calling \ref run() or 268 /// \ref find MinMean(), it will allocate a local \ref Path "path"268 /// \ref findCycleMean(), it will allocate a local \ref Path "path" 269 269 /// structure. The destuctor deallocates this automatically 270 270 /// allocated object, of course. … … 274 274 /// 275 275 /// \return <tt>(*this)</tt> 276 Howard & cycle(Path &path) {276 HowardMmc& cycle(Path &path) { 277 277 if (_local_path) { 278 278 delete _cycle_path; … … 288 288 /// 289 289 /// \return <tt>(*this)</tt> 290 Howard & tolerance(const Tolerance& tolerance) {290 HowardMmc& tolerance(const Tolerance& tolerance) { 291 291 _tolerance = tolerance; 292 292 return *this; … … 304 304 /// The simplest way to execute the algorithm is to call the \ref run() 305 305 /// function.\n 306 /// If you only need the minimum mean length, you may call307 /// \ref find MinMean().306 /// If you only need the minimum mean cost, you may call 307 /// \ref findCycleMean(). 308 308 309 309 /// @{ … … 313 313 /// This function runs the algorithm. 314 314 /// It can be called more than once (e.g. if the underlying digraph 315 /// and/or the arc lengths have been modified).315 /// and/or the arc costs have been modified). 316 316 /// 317 317 /// \return \c true if a directed cycle exists in the digraph. … … 319 319 /// \note <tt>mmc.run()</tt> is just a shortcut of the following code. 320 320 /// \code 321 /// return mmc.find MinMean() && mmc.findCycle();321 /// return mmc.findCycleMean() && mmc.findCycle(); 322 322 /// \endcode 323 323 bool run() { 324 return find MinMean() && findCycle();324 return findCycleMean() && findCycle(); 325 325 } 326 326 327 327 /// \brief Find the minimum cycle mean. 328 328 /// 329 /// This function finds the minimum mean lengthof the directed329 /// This function finds the minimum mean cost of the directed 330 330 /// cycles in the digraph. 331 331 /// 332 332 /// \return \c true if a directed cycle exists in the digraph. 333 bool find MinMean() {333 bool findCycleMean() { 334 334 // Initialize and find strongly connected components 335 335 init(); … … 346 346 // Update the best cycle (global minimum mean cycle) 347 347 if ( _curr_found && (!_best_found  348 _curr_ length * _best_size < _best_length* _curr_size) ) {348 _curr_cost * _best_size < _best_cost * _curr_size) ) { 349 349 _best_found = true; 350 _best_ length = _curr_length;350 _best_cost = _curr_cost; 351 351 _best_size = _curr_size; 352 352 _best_node = _curr_node; … … 358 358 /// \brief Find a minimum mean directed cycle. 359 359 /// 360 /// This function finds a directed cycle of minimum mean length361 /// in the digraph using the data computed by find MinMean().360 /// This function finds a directed cycle of minimum mean cost 361 /// in the digraph using the data computed by findCycleMean(). 362 362 /// 363 363 /// \return \c true if a directed cycle exists in the digraph. 364 364 /// 365 /// \pre \ref find MinMean() must be called before using this function.365 /// \pre \ref findCycleMean() must be called before using this function. 366 366 bool findCycle() { 367 367 if (!_best_found) return false; … … 383 383 /// @{ 384 384 385 /// \brief Return the total lengthof the found cycle.386 /// 387 /// This function returns the total lengthof the found cycle.388 /// 389 /// \pre \ref run() or \ref find MinMean() must be called before385 /// \brief Return the total cost of the found cycle. 386 /// 387 /// This function returns the total cost of the found cycle. 388 /// 389 /// \pre \ref run() or \ref findCycleMean() must be called before 390 390 /// using this function. 391 Value cycleLength() const {392 return static_cast< Value>(_best_length);391 Cost cycleCost() const { 392 return static_cast<Cost>(_best_cost); 393 393 } 394 394 … … 397 397 /// This function returns the number of arcs on the found cycle. 398 398 /// 399 /// \pre \ref run() or \ref find MinMean() must be called before399 /// \pre \ref run() or \ref findCycleMean() must be called before 400 400 /// using this function. 401 int cycle ArcNum() const {401 int cycleSize() const { 402 402 return _best_size; 403 403 } 404 404 405 /// \brief Return the mean lengthof the found cycle.406 /// 407 /// This function returns the mean lengthof the found cycle.405 /// \brief Return the mean cost of the found cycle. 406 /// 407 /// This function returns the mean cost of the found cycle. 408 408 /// 409 409 /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the 410 410 /// following code. 411 411 /// \code 412 /// return static_cast<double>(alg.cycle Length()) / alg.cycleArcNum();412 /// return static_cast<double>(alg.cycleCost()) / alg.cycleSize(); 413 413 /// \endcode 414 414 /// 415 /// \pre \ref run() or \ref find MinMean() must be called before415 /// \pre \ref run() or \ref findCycleMean() must be called before 416 416 /// using this function. 417 417 double cycleMean() const { 418 return static_cast<double>(_best_ length) / _best_size;418 return static_cast<double>(_best_cost) / _best_size; 419 419 } 420 420 … … 442 442 _queue.resize(countNodes(_gr)); 443 443 _best_found = false; 444 _best_ length= 0;444 _best_cost = 0; 445 445 _best_size = 1; 446 446 _cycle_path>clear(); … … 493 493 e = _in_arcs[v][j]; 494 494 u = _gr.source(e); 495 if (_ length[e] < _dist[u]) {496 _dist[u] = _ length[e];495 if (_cost[e] < _dist[u]) { 496 _dist[u] = _cost[e]; 497 497 _policy[u] = e; 498 498 } … … 507 507 _level[(*_nodes)[i]] = 1; 508 508 } 509 Large Value clength;509 LargeCost ccost; 510 510 int csize; 511 511 Node u, v; … … 519 519 if (_level[u] == i) { 520 520 // A cycle is found 521 c length = _length[_policy[u]];521 ccost = _cost[_policy[u]]; 522 522 csize = 1; 523 523 for (v = u; (v = _gr.target(_policy[v])) != u; ) { 524 c length += _length[_policy[v]];524 ccost += _cost[_policy[v]]; 525 525 ++csize; 526 526 } 527 527 if ( !_curr_found  528 (c length * _curr_size < _curr_length* csize) ) {528 (ccost * _curr_size < _curr_cost * csize) ) { 529 529 _curr_found = true; 530 _curr_ length = clength;530 _curr_cost = ccost; 531 531 _curr_size = csize; 532 532 _curr_node = u; … … 556 556 if (_policy[u] == e && !_reached[u]) { 557 557 _reached[u] = true; 558 _dist[u] = _dist[v] + _ length[e] * _curr_size  _curr_length;558 _dist[u] = _dist[v] + _cost[e] * _curr_size  _curr_cost; 559 559 _queue[++_qback] = u; 560 560 } … … 573 573 _reached[u] = true; 574 574 _policy[u] = e; 575 _dist[u] = _dist[v] + _ length[e] * _curr_size  _curr_length;575 _dist[u] = _dist[v] + _cost[e] * _curr_size  _curr_cost; 576 576 _queue[++_qback] = u; 577 577 } … … 586 586 e = _in_arcs[v][j]; 587 587 u = _gr.source(e); 588 Large Value delta = _dist[v] + _length[e] * _curr_size  _curr_length;588 LargeCost delta = _dist[v] + _cost[e] * _curr_size  _curr_cost; 589 589 if (_tolerance.less(delta, _dist[u])) { 590 590 _dist[u] = delta; … … 597 597 } 598 598 599 }; //class Howard 599 }; //class HowardMmc 600 600 601 601 ///@} … … 603 603 } //namespace lemon 604 604 605 #endif //LEMON_HOWARD_ H605 #endif //LEMON_HOWARD_MMC_H
Note: See TracChangeset
for help on using the changeset viewer.