Changeset 864:d3ea191c3412 in lemon-1.2 for lemon/karp_mmc.h
- Timestamp:
- 03/13/10 22:01:38 (14 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
lemon/karp_mmc.h
r863 r864 17 17 */ 18 18 19 #ifndef LEMON_KARP_ H20 #define LEMON_KARP_ H19 #ifndef LEMON_KARP_MMC_H 20 #define LEMON_KARP_MMC_H 21 21 22 22 /// \ingroup min_mean_cycle … … 34 34 namespace lemon { 35 35 36 /// \brief Default traits class of Karp algorithm.36 /// \brief Default traits class of KarpMmc class. 37 37 /// 38 /// Default traits class of Karp algorithm.38 /// Default traits class of KarpMmc 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 Karp DefaultTraits48 struct KarpMmcDefaultTraits 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 Karp DefaultTraits<GR, LEN, true>76 // Default traits class for integer cost types 77 template <typename GR, typename CM> 78 struct KarpMmcDefaultTraits<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 Karp's algorithm for finding a directed 100 /// cycle of minimum mean length (cost)in a digraph100 /// cycle of minimum mean cost in a digraph 101 101 /// \ref amo93networkflows, \ref dasdan98minmeancycle. 102 102 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). 103 103 /// 104 104 /// \tparam GR The type of the digraph the algorithm runs on. 105 /// \tparam LEN The type of the lengthmap. The default105 /// \tparam CM The type of the cost map. The default 106 106 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 107 107 /// \tparam TR The traits class that defines various types used by the 108 /// algorithm. By default, it is \ref Karp DefaultTraits109 /// "Karp DefaultTraits<GR, LEN>".108 /// algorithm. By default, it is \ref KarpMmcDefaultTraits 109 /// "KarpMmcDefaultTraits<GR, CM>". 110 110 /// In most cases, this parameter should not be set directly, 111 111 /// consider to use the named template parameters instead. 112 112 #ifdef DOXYGEN 113 template <typename GR, typename LEN, typename TR>113 template <typename GR, typename CM, typename TR> 114 114 #else 115 115 template < typename GR, 116 typename LEN= typename GR::template ArcMap<int>,117 typename TR = Karp DefaultTraits<GR, LEN> >116 typename CM = typename GR::template ArcMap<int>, 117 typename TR = KarpMmcDefaultTraits<GR, CM> > 118 118 #endif 119 class Karp 119 class KarpMmc 120 120 { 121 121 public: … … 123 123 /// The type of the digraph 124 124 typedef typename TR::Digraph Digraph; 125 /// The type of the lengthmap126 typedef typename TR:: LengthMap LengthMap;127 /// The type of the arc lengths128 typedef typename TR:: Value Value;129 130 /// \brief The large valuetype131 /// 132 /// The large valuetype used for internal computations.133 /// By default, it is \c long \c long if the \c Valuetype is integer,125 /// The type of the cost map 126 typedef typename TR::CostMap CostMap; 127 /// The type of the arc costs 128 typedef typename TR::Cost Cost; 129 130 /// \brief The large cost type 131 /// 132 /// The large cost type used for internal computations. 133 /// By default, it is \c long \c long if the \c Cost type is integer, 134 134 /// otherwise it is \c double. 135 typedef typename TR::Large Value LargeValue;135 typedef typename TR::LargeCost LargeCost; 136 136 137 137 /// The tolerance type … … 141 141 /// 142 142 /// The path type of the found cycles. 143 /// Using the \ref Karp DefaultTraits "default traits class",143 /// Using the \ref KarpMmcDefaultTraits "default traits class", 144 144 /// it is \ref lemon::Path "Path<Digraph>". 145 145 typedef typename TR::Path Path; 146 146 147 /// The \ref Karp DefaultTraits "traits class" of the algorithm147 /// The \ref KarpMmcDefaultTraits "traits class" of the algorithm 148 148 typedef TR Traits; 149 149 … … 155 155 struct PathData 156 156 { 157 Large Valuedist;157 LargeCost dist; 158 158 Arc pred; 159 PathData(Large Valued, Arc p = INVALID) :159 PathData(LargeCost d, Arc p = INVALID) : 160 160 dist(d), pred(p) {} 161 161 }; … … 168 168 // The digraph the algorithm runs on 169 169 const Digraph &_gr; 170 // The lengthof the arcs171 const LengthMap &_length;170 // The cost of the arcs 171 const CostMap &_cost; 172 172 173 173 // Data for storing the strongly connected components … … 179 179 180 180 // Data for the found cycle 181 Large Value _cycle_length;181 LargeCost _cycle_cost; 182 182 int _cycle_size; 183 183 Node _cycle_node; … … 194 194 195 195 // Infinite constant 196 const Large ValueINF;196 const LargeCost INF; 197 197 198 198 public: … … 202 202 203 203 template <typename T> 204 struct SetLarge ValueTraits : public Traits {205 typedef T Large Value;204 struct SetLargeCostTraits : public Traits { 205 typedef T LargeCost; 206 206 typedef lemon::Tolerance<T> Tolerance; 207 207 }; 208 208 209 209 /// \brief \ref named-templ-param "Named parameter" for setting 210 /// \c Large Valuetype.211 /// 212 /// \ref named-templ-param "Named parameter" for setting \c Large Value210 /// \c LargeCost type. 211 /// 212 /// \ref named-templ-param "Named parameter" for setting \c LargeCost 213 213 /// type. It is used for internal computations in the algorithm. 214 214 template <typename T> 215 struct SetLarge Value216 : public Karp <GR, LEN, SetLargeValueTraits<T> > {217 typedef Karp <GR, LEN, SetLargeValueTraits<T> > Create;215 struct SetLargeCost 216 : public KarpMmc<GR, CM, SetLargeCostTraits<T> > { 217 typedef KarpMmc<GR, CM, SetLargeCostTraits<T> > Create; 218 218 }; 219 219 … … 232 232 template <typename T> 233 233 struct SetPath 234 : public Karp <GR, LEN, SetPathTraits<T> > {235 typedef Karp <GR, LEN, SetPathTraits<T> > Create;234 : public KarpMmc<GR, CM, SetPathTraits<T> > { 235 typedef KarpMmc<GR, CM, SetPathTraits<T> > Create; 236 236 }; 237 237 … … 240 240 protected: 241 241 242 Karp () {}242 KarpMmc() {} 243 243 244 244 public: … … 249 249 /// 250 250 /// \param digraph The digraph the algorithm runs on. 251 /// \param length The lengths (costs)of the arcs.252 Karp ( const Digraph &digraph,253 const LengthMap &length) :254 _gr(digraph), _ length(length), _comp(digraph), _out_arcs(digraph),255 _cycle_ length(0), _cycle_size(1), _cycle_node(INVALID),251 /// \param cost The costs of the arcs. 252 KarpMmc( const Digraph &digraph, 253 const CostMap &cost ) : 254 _gr(digraph), _cost(cost), _comp(digraph), _out_arcs(digraph), 255 _cycle_cost(0), _cycle_size(1), _cycle_node(INVALID), 256 256 _cycle_path(NULL), _local_path(false), _data(digraph), 257 INF(std::numeric_limits<Large Value>::has_infinity ?258 std::numeric_limits<Large Value>::infinity() :259 std::numeric_limits<Large Value>::max())257 INF(std::numeric_limits<LargeCost>::has_infinity ? 258 std::numeric_limits<LargeCost>::infinity() : 259 std::numeric_limits<LargeCost>::max()) 260 260 {} 261 261 262 262 /// Destructor. 263 ~Karp () {263 ~KarpMmc() { 264 264 if (_local_path) delete _cycle_path; 265 265 } … … 271 271 /// 272 272 /// If you don't call this function before calling \ref run() or 273 /// \ref find MinMean(), it will allocate a local \ref Path "path"273 /// \ref findCycleMean(), it will allocate a local \ref Path "path" 274 274 /// structure. The destuctor deallocates this automatically 275 275 /// allocated object, of course. … … 279 279 /// 280 280 /// \return <tt>(*this)</tt> 281 Karp & cycle(Path &path) {281 KarpMmc& cycle(Path &path) { 282 282 if (_local_path) { 283 283 delete _cycle_path; … … 293 293 /// 294 294 /// \return <tt>(*this)</tt> 295 Karp & tolerance(const Tolerance& tolerance) {295 KarpMmc& tolerance(const Tolerance& tolerance) { 296 296 _tolerance = tolerance; 297 297 return *this; … … 309 309 /// The simplest way to execute the algorithm is to call the \ref run() 310 310 /// function.\n 311 /// If you only need the minimum mean length, you may call312 /// \ref find MinMean().311 /// If you only need the minimum mean cost, you may call 312 /// \ref findCycleMean(). 313 313 314 314 /// @{ … … 318 318 /// This function runs the algorithm. 319 319 /// It can be called more than once (e.g. if the underlying digraph 320 /// and/or the arc lengths have been modified).320 /// and/or the arc costs have been modified). 321 321 /// 322 322 /// \return \c true if a directed cycle exists in the digraph. … … 324 324 /// \note <tt>mmc.run()</tt> is just a shortcut of the following code. 325 325 /// \code 326 /// return mmc.find MinMean() && mmc.findCycle();326 /// return mmc.findCycleMean() && mmc.findCycle(); 327 327 /// \endcode 328 328 bool run() { 329 return find MinMean() && findCycle();329 return findCycleMean() && findCycle(); 330 330 } 331 331 332 332 /// \brief Find the minimum cycle mean. 333 333 /// 334 /// This function finds the minimum mean lengthof the directed334 /// This function finds the minimum mean cost of the directed 335 335 /// cycles in the digraph. 336 336 /// 337 337 /// \return \c true if a directed cycle exists in the digraph. 338 bool find MinMean() {338 bool findCycleMean() { 339 339 // Initialization and find strongly connected components 340 340 init(); … … 352 352 /// \brief Find a minimum mean directed cycle. 353 353 /// 354 /// This function finds a directed cycle of minimum mean length355 /// in the digraph using the data computed by find MinMean().354 /// This function finds a directed cycle of minimum mean cost 355 /// in the digraph using the data computed by findCycleMean(). 356 356 /// 357 357 /// \return \c true if a directed cycle exists in the digraph. 358 358 /// 359 /// \pre \ref find MinMean() must be called before using this function.359 /// \pre \ref findCycleMean() must be called before using this function. 360 360 bool findCycle() { 361 361 if (_cycle_node == INVALID) return false; … … 370 370 Arc e = _data[u][r].pred; 371 371 _cycle_path->addFront(e); 372 _cycle_ length = _length[e];372 _cycle_cost = _cost[e]; 373 373 _cycle_size = 1; 374 374 Node v; … … 376 376 e = _data[v][--r].pred; 377 377 _cycle_path->addFront(e); 378 _cycle_ length += _length[e];378 _cycle_cost += _cost[e]; 379 379 ++_cycle_size; 380 380 } … … 391 391 /// @{ 392 392 393 /// \brief Return the total lengthof the found cycle.394 /// 395 /// This function returns the total lengthof the found cycle.396 /// 397 /// \pre \ref run() or \ref find MinMean() must be called before393 /// \brief Return the total cost of the found cycle. 394 /// 395 /// This function returns the total cost of the found cycle. 396 /// 397 /// \pre \ref run() or \ref findCycleMean() must be called before 398 398 /// using this function. 399 Value cycleLength() const {400 return static_cast< Value>(_cycle_length);399 Cost cycleCost() const { 400 return static_cast<Cost>(_cycle_cost); 401 401 } 402 402 … … 405 405 /// This function returns the number of arcs on the found cycle. 406 406 /// 407 /// \pre \ref run() or \ref find MinMean() must be called before407 /// \pre \ref run() or \ref findCycleMean() must be called before 408 408 /// using this function. 409 int cycle ArcNum() const {409 int cycleSize() const { 410 410 return _cycle_size; 411 411 } 412 412 413 /// \brief Return the mean lengthof the found cycle.414 /// 415 /// This function returns the mean lengthof the found cycle.413 /// \brief Return the mean cost of the found cycle. 414 /// 415 /// This function returns the mean cost of the found cycle. 416 416 /// 417 417 /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the 418 418 /// following code. 419 419 /// \code 420 /// return static_cast<double>(alg.cycle Length()) / alg.cycleArcNum();420 /// return static_cast<double>(alg.cycleCost()) / alg.cycleSize(); 421 421 /// \endcode 422 422 /// 423 /// \pre \ref run() or \ref find MinMean() must be called before423 /// \pre \ref run() or \ref findCycleMean() must be called before 424 424 /// using this function. 425 425 double cycleMean() const { 426 return static_cast<double>(_cycle_ length) / _cycle_size;426 return static_cast<double>(_cycle_cost) / _cycle_size; 427 427 } 428 428 … … 449 449 } 450 450 _cycle_path->clear(); 451 _cycle_ length= 0;451 _cycle_cost = 0; 452 452 _cycle_size = 1; 453 453 _cycle_node = INVALID; … … 498 498 499 499 // Process all rounds of computing path data for the current component. 500 // _data[v][k] is the lengthof a shortest directed walk from the root500 // _data[v][k] is the cost of a shortest directed walk from the root 501 501 // node to node v containing exactly k arcs. 502 502 void processRounds() { … … 520 520 Node u, v; 521 521 Arc e; 522 Large Valued;522 LargeCost d; 523 523 for (int i = 0; i < int(_process.size()); ++i) { 524 524 u = _process[i]; … … 526 526 e = _out_arcs[u][j]; 527 527 v = _gr.target(e); 528 d = _data[u][k-1].dist + _ length[e];528 d = _data[u][k-1].dist + _cost[e]; 529 529 if (_tolerance.less(d, _data[v][k].dist)) { 530 530 if (_data[v][k].dist == INF) next.push_back(v); … … 540 540 Node u, v; 541 541 Arc e; 542 Large Valued;542 LargeCost d; 543 543 for (int i = 0; i < int(_nodes->size()); ++i) { 544 544 u = (*_nodes)[i]; … … 546 546 e = _out_arcs[u][j]; 547 547 v = _gr.target(e); 548 d = _data[u][k-1].dist + _ length[e];548 d = _data[u][k-1].dist + _cost[e]; 549 549 if (_tolerance.less(d, _data[v][k].dist)) { 550 550 _data[v][k] = PathData(d, e); … … 560 560 Node u = (*_nodes)[i]; 561 561 if (_data[u][n].dist == INF) continue; 562 Large Value length, max_length= 0;562 LargeCost cost, max_cost = 0; 563 563 int size, max_size = 1; 564 564 bool found_curr = false; 565 565 for (int k = 0; k < n; ++k) { 566 566 if (_data[u][k].dist == INF) continue; 567 length= _data[u][n].dist - _data[u][k].dist;567 cost = _data[u][n].dist - _data[u][k].dist; 568 568 size = n - k; 569 if (!found_curr || length * max_size > max_length* size) {569 if (!found_curr || cost * max_size > max_cost * size) { 570 570 found_curr = true; 571 max_ length = length;571 max_cost = cost; 572 572 max_size = size; 573 573 } 574 574 } 575 575 if ( found_curr && (_cycle_node == INVALID || 576 max_ length * _cycle_size < _cycle_length* max_size) ) {577 _cycle_ length = max_length;576 max_cost * _cycle_size < _cycle_cost * max_size) ) { 577 _cycle_cost = max_cost; 578 578 _cycle_size = max_size; 579 579 _cycle_node = u; … … 582 582 } 583 583 584 }; //class Karp 584 }; //class KarpMmc 585 585 586 586 ///@} … … 588 588 } //namespace lemon 589 589 590 #endif //LEMON_KARP_ H590 #endif //LEMON_KARP_MMC_H
Note: See TracChangeset
for help on using the changeset viewer.