Changeset 864:d3ea191c3412 in lemon-main for lemon/hartmann_orlin_mmc.h
- Timestamp:
- 03/13/10 22:01:38 (14 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
lemon/hartmann_orlin_mmc.h
r863 r864 17 17 */ 18 18 19 #ifndef LEMON_HARTMANN_ORLIN_ H20 #define LEMON_HARTMANN_ORLIN_ H19 #ifndef LEMON_HARTMANN_ORLIN_MMC_H 20 #define LEMON_HARTMANN_ORLIN_MMC_H 21 21 22 22 /// \ingroup min_mean_cycle … … 34 34 namespace lemon { 35 35 36 /// \brief Default traits class of HartmannOrlin algorithm.36 /// \brief Default traits class of HartmannOrlinMmc class. 37 37 /// 38 /// Default traits class of HartmannOrlin algorithm.38 /// Default traits class of HartmannOrlinMmc 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::Rea_data "Rea_data" 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 HartmannOrlin DefaultTraits48 struct HartmannOrlinMmcDefaultTraits 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 HartmannOrlin DefaultTraits<GR, LEN, true>76 // Default traits class for integer cost types 77 template <typename GR, typename CM> 78 struct HartmannOrlinMmcDefaultTraits<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 the Hartmann-Orlin 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 /// It is an improved version of \ref Karp "Karp"'s original algorithm, … … 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 HartmannOrlin DefaultTraits111 /// "HartmannOrlin DefaultTraits<GR, LEN>".110 /// algorithm. By default, it is \ref HartmannOrlinMmcDefaultTraits 111 /// "HartmannOrlinMmcDefaultTraits<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 = HartmannOrlin DefaultTraits<GR, LEN> >118 typename CM = typename GR::template ArcMap<int>, 119 typename TR = HartmannOrlinMmcDefaultTraits<GR, CM> > 120 120 #endif 121 class HartmannOrlin 121 class HartmannOrlinMmc 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 HartmannOrlin DefaultTraits "default traits class",145 /// Using the \ref HartmannOrlinMmcDefaultTraits "default traits class", 146 146 /// it is \ref lemon::Path "Path<Digraph>". 147 147 typedef typename TR::Path Path; 148 148 149 /// The \ref HartmannOrlin DefaultTraits "traits class" of the algorithm149 /// The \ref HartmannOrlinMmcDefaultTraits "traits class" of the algorithm 150 150 typedef TR Traits; 151 151 … … 157 157 struct PathData 158 158 { 159 Large Valuedist;159 LargeCost dist; 160 160 Arc pred; 161 PathData(Large Valued, Arc p = INVALID) :161 PathData(LargeCost d, Arc p = INVALID) : 162 162 dist(d), pred(p) {} 163 163 }; … … 170 170 // The digraph the algorithm runs on 171 171 const Digraph &_gr; 172 // The lengthof the arcs173 const LengthMap &_length;172 // The cost of the arcs 173 const CostMap &_cost; 174 174 175 175 // Data for storing the strongly connected components … … 182 182 // Data for the found cycles 183 183 bool _curr_found, _best_found; 184 Large Value _curr_length, _best_length;184 LargeCost _curr_cost, _best_cost; 185 185 int _curr_size, _best_size; 186 186 Node _curr_node, _best_node; … … 198 198 199 199 // Infinite constant 200 const Large ValueINF;200 const LargeCost INF; 201 201 202 202 public: … … 206 206 207 207 template <typename T> 208 struct SetLarge ValueTraits : public Traits {209 typedef T Large Value;208 struct SetLargeCostTraits : public Traits { 209 typedef T LargeCost; 210 210 typedef lemon::Tolerance<T> Tolerance; 211 211 }; 212 212 213 213 /// \brief \ref named-templ-param "Named parameter" for setting 214 /// \c Large Valuetype.215 /// 216 /// \ref named-templ-param "Named parameter" for setting \c Large Value214 /// \c LargeCost type. 215 /// 216 /// \ref named-templ-param "Named parameter" for setting \c LargeCost 217 217 /// type. It is used for internal computations in the algorithm. 218 218 template <typename T> 219 struct SetLarge Value220 : public HartmannOrlin <GR, LEN, SetLargeValueTraits<T> > {221 typedef HartmannOrlin <GR, LEN, SetLargeValueTraits<T> > Create;219 struct SetLargeCost 220 : public HartmannOrlinMmc<GR, CM, SetLargeCostTraits<T> > { 221 typedef HartmannOrlinMmc<GR, CM, SetLargeCostTraits<T> > Create; 222 222 }; 223 223 … … 236 236 template <typename T> 237 237 struct SetPath 238 : public HartmannOrlin <GR, LEN, SetPathTraits<T> > {239 typedef HartmannOrlin <GR, LEN, SetPathTraits<T> > Create;238 : public HartmannOrlinMmc<GR, CM, SetPathTraits<T> > { 239 typedef HartmannOrlinMmc<GR, CM, SetPathTraits<T> > Create; 240 240 }; 241 241 … … 244 244 protected: 245 245 246 HartmannOrlin () {}246 HartmannOrlinMmc() {} 247 247 248 248 public: … … 253 253 /// 254 254 /// \param digraph The digraph the algorithm runs on. 255 /// \param length The lengths (costs)of the arcs.256 HartmannOrlin ( const Digraph &digraph,257 const LengthMap &length) :258 _gr(digraph), _ length(length), _comp(digraph), _out_arcs(digraph),259 _best_found(false), _best_ length(0), _best_size(1),255 /// \param cost The costs of the arcs. 256 HartmannOrlinMmc( const Digraph &digraph, 257 const CostMap &cost ) : 258 _gr(digraph), _cost(cost), _comp(digraph), _out_arcs(digraph), 259 _best_found(false), _best_cost(0), _best_size(1), 260 260 _cycle_path(NULL), _local_path(false), _data(digraph), 261 INF(std::numeric_limits<Large Value>::has_infinity ?262 std::numeric_limits<Large Value>::infinity() :263 std::numeric_limits<Large Value>::max())261 INF(std::numeric_limits<LargeCost>::has_infinity ? 262 std::numeric_limits<LargeCost>::infinity() : 263 std::numeric_limits<LargeCost>::max()) 264 264 {} 265 265 266 266 /// Destructor. 267 ~HartmannOrlin () {267 ~HartmannOrlinMmc() { 268 268 if (_local_path) delete _cycle_path; 269 269 } … … 275 275 /// 276 276 /// If you don't call this function before calling \ref run() or 277 /// \ref find MinMean(), it will allocate a local \ref Path "path"277 /// \ref findCycleMean(), it will allocate a local \ref Path "path" 278 278 /// structure. The destuctor deallocates this automatically 279 279 /// allocated object, of course. … … 283 283 /// 284 284 /// \return <tt>(*this)</tt> 285 HartmannOrlin & cycle(Path &path) {285 HartmannOrlinMmc& cycle(Path &path) { 286 286 if (_local_path) { 287 287 delete _cycle_path; … … 297 297 /// 298 298 /// \return <tt>(*this)</tt> 299 HartmannOrlin & tolerance(const Tolerance& tolerance) {299 HartmannOrlinMmc& tolerance(const Tolerance& tolerance) { 300 300 _tolerance = tolerance; 301 301 return *this; … … 313 313 /// The simplest way to execute the algorithm is to call the \ref run() 314 314 /// function.\n 315 /// If you only need the minimum mean length, you may call316 /// \ref find MinMean().315 /// If you only need the minimum mean cost, you may call 316 /// \ref findCycleMean(). 317 317 318 318 /// @{ … … 322 322 /// This function runs the algorithm. 323 323 /// It can be called more than once (e.g. if the underlying digraph 324 /// and/or the arc lengths have been modified).324 /// and/or the arc costs have been modified). 325 325 /// 326 326 /// \return \c true if a directed cycle exists in the digraph. … … 328 328 /// \note <tt>mmc.run()</tt> is just a shortcut of the following code. 329 329 /// \code 330 /// return mmc.find MinMean() && mmc.findCycle();330 /// return mmc.findCycleMean() && mmc.findCycle(); 331 331 /// \endcode 332 332 bool run() { 333 return find MinMean() && findCycle();333 return findCycleMean() && findCycle(); 334 334 } 335 335 336 336 /// \brief Find the minimum cycle mean. 337 337 /// 338 /// This function finds the minimum mean lengthof the directed338 /// This function finds the minimum mean cost of the directed 339 339 /// cycles in the digraph. 340 340 /// 341 341 /// \return \c true if a directed cycle exists in the digraph. 342 bool find MinMean() {342 bool findCycleMean() { 343 343 // Initialization and find strongly connected components 344 344 init(); … … 352 352 // Update the best cycle (global minimum mean cycle) 353 353 if ( _curr_found && (!_best_found || 354 _curr_ length * _best_size < _best_length* _curr_size) ) {354 _curr_cost * _best_size < _best_cost * _curr_size) ) { 355 355 _best_found = true; 356 _best_ length = _curr_length;356 _best_cost = _curr_cost; 357 357 _best_size = _curr_size; 358 358 _best_node = _curr_node; … … 365 365 /// \brief Find a minimum mean directed cycle. 366 366 /// 367 /// This function finds a directed cycle of minimum mean length368 /// in the digraph using the data computed by find MinMean().367 /// This function finds a directed cycle of minimum mean cost 368 /// in the digraph using the data computed by findCycleMean(). 369 369 /// 370 370 /// \return \c true if a directed cycle exists in the digraph. 371 371 /// 372 /// \pre \ref find MinMean() must be called before using this function.372 /// \pre \ref findCycleMean() must be called before using this function. 373 373 bool findCycle() { 374 374 if (!_best_found) return false; … … 383 383 Arc e = _data[u][r].pred; 384 384 _cycle_path->addFront(e); 385 _best_ length = _length[e];385 _best_cost = _cost[e]; 386 386 _best_size = 1; 387 387 Node v; … … 389 389 e = _data[v][--r].pred; 390 390 _cycle_path->addFront(e); 391 _best_ length += _length[e];391 _best_cost += _cost[e]; 392 392 ++_best_size; 393 393 } … … 404 404 /// @{ 405 405 406 /// \brief Return the total lengthof the found cycle.407 /// 408 /// This function returns the total lengthof the found cycle.409 /// 410 /// \pre \ref run() or \ref find MinMean() must be called before406 /// \brief Return the total cost of the found cycle. 407 /// 408 /// This function returns the total cost of the found cycle. 409 /// 410 /// \pre \ref run() or \ref findCycleMean() must be called before 411 411 /// using this function. 412 Value cycleLength() const {413 return static_cast< Value>(_best_length);412 Cost cycleCost() const { 413 return static_cast<Cost>(_best_cost); 414 414 } 415 415 … … 418 418 /// This function returns the number of arcs on the found cycle. 419 419 /// 420 /// \pre \ref run() or \ref find MinMean() must be called before420 /// \pre \ref run() or \ref findCycleMean() must be called before 421 421 /// using this function. 422 int cycle ArcNum() const {422 int cycleSize() const { 423 423 return _best_size; 424 424 } 425 425 426 /// \brief Return the mean lengthof the found cycle.427 /// 428 /// This function returns the mean lengthof the found cycle.426 /// \brief Return the mean cost of the found cycle. 427 /// 428 /// This function returns the mean cost of the found cycle. 429 429 /// 430 430 /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the 431 431 /// following code. 432 432 /// \code 433 /// return static_cast<double>(alg.cycle Length()) / alg.cycleArcNum();433 /// return static_cast<double>(alg.cycleCost()) / alg.cycleSize(); 434 434 /// \endcode 435 435 /// 436 /// \pre \ref run() or \ref find MinMean() must be called before436 /// \pre \ref run() or \ref findCycleMean() must be called before 437 437 /// using this function. 438 438 double cycleMean() const { 439 return static_cast<double>(_best_ length) / _best_size;439 return static_cast<double>(_best_cost) / _best_size; 440 440 } 441 441 … … 463 463 _cycle_path->clear(); 464 464 _best_found = false; 465 _best_ length= 0;465 _best_cost = 0; 466 466 _best_size = 1; 467 467 _cycle_path->clear(); … … 512 512 513 513 // Process all rounds of computing path data for the current component. 514 // _data[v][k] is the lengthof a shortest directed walk from the root514 // _data[v][k] is the cost of a shortest directed walk from the root 515 515 // node to node v containing exactly k arcs. 516 516 void processRounds() { … … 544 544 Node u, v; 545 545 Arc e; 546 Large Valued;546 LargeCost d; 547 547 for (int i = 0; i < int(_process.size()); ++i) { 548 548 u = _process[i]; … … 550 550 e = _out_arcs[u][j]; 551 551 v = _gr.target(e); 552 d = _data[u][k-1].dist + _ length[e];552 d = _data[u][k-1].dist + _cost[e]; 553 553 if (_tolerance.less(d, _data[v][k].dist)) { 554 554 if (_data[v][k].dist == INF) next.push_back(v); … … 564 564 Node u, v; 565 565 Arc e; 566 Large Valued;566 LargeCost d; 567 567 for (int i = 0; i < int(_nodes->size()); ++i) { 568 568 u = (*_nodes)[i]; … … 570 570 e = _out_arcs[u][j]; 571 571 v = _gr.target(e); 572 d = _data[u][k-1].dist + _ length[e];572 d = _data[u][k-1].dist + _cost[e]; 573 573 if (_tolerance.less(d, _data[v][k].dist)) { 574 574 _data[v][k] = PathData(d, e); … … 582 582 typedef std::pair<int, int> Pair; 583 583 typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0)); 584 typename GR::template NodeMap<Large Value> pi(_gr);584 typename GR::template NodeMap<LargeCost> pi(_gr); 585 585 int n = _nodes->size(); 586 Large Value length;586 LargeCost cost; 587 587 int size; 588 588 Node u; … … 596 596 if (level[u].first == i && level[u].second > 0) { 597 597 // A cycle is found 598 length= _data[u][level[u].second].dist - _data[u][j].dist;598 cost = _data[u][level[u].second].dist - _data[u][j].dist; 599 599 size = level[u].second - j; 600 if (!_curr_found || length * _curr_size < _curr_length* size) {601 _curr_ length = length;600 if (!_curr_found || cost * _curr_size < _curr_cost * size) { 601 _curr_cost = cost; 602 602 _curr_size = size; 603 603 _curr_node = u; … … 614 614 615 615 // If at least one cycle is found, check the optimality condition 616 Large Valued;616 LargeCost d; 617 617 if (_curr_found && k < n) { 618 618 // Find node potentials … … 622 622 for (int j = 0; j <= k; ++j) { 623 623 if (_data[u][j].dist < INF) { 624 d = _data[u][j].dist * _curr_size - j * _curr_ length;624 d = _data[u][j].dist * _curr_size - j * _curr_cost; 625 625 if (_tolerance.less(d, pi[u])) pi[u] = d; 626 626 } … … 631 631 bool done = true; 632 632 for (ArcIt a(_gr); a != INVALID; ++a) { 633 if (_tolerance.less(_ length[a] * _curr_size - _curr_length,633 if (_tolerance.less(_cost[a] * _curr_size - _curr_cost, 634 634 pi[_gr.target(a)] - pi[_gr.source(a)]) ) { 635 635 done = false; … … 642 642 } 643 643 644 }; //class HartmannOrlin 644 }; //class HartmannOrlinMmc 645 645 646 646 ///@} … … 648 648 } //namespace lemon 649 649 650 #endif //LEMON_HARTMANN_ORLIN_ H650 #endif //LEMON_HARTMANN_ORLIN_MMC_H
Note: See TracChangeset
for help on using the changeset viewer.