Changeset 2620:8f41a3129746 in lemon-0.x
- Timestamp:
- 10/05/08 15:37:17 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3505
- Location:
- lemon
- Files:
-
- 6 edited
-
capacity_scaling.h (modified) (15 diffs)
-
cost_scaling.h (modified) (13 diffs)
-
cycle_canceling.h (modified) (13 diffs)
-
min_cost_flow.h (modified) (1 diff)
-
min_cost_max_flow.h (modified) (9 diffs)
-
min_mean_cycle.h (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r2589 r2620 53 53 /// 54 54 /// \author Peter Kovacs 55 56 55 template < typename Graph, 57 56 typename LowerMap = typename Graph::template EdgeMap<int>, … … 126 125 {} 127 126 128 /// Run sthe algorithm from the given source node.127 /// Run the algorithm from the given source node. 129 128 Node run(Node s, Capacity delta = 1) { 130 129 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); … … 372 371 } 373 372 374 /// \brief Set sthe flow map.375 /// 376 /// Set sthe flow map.373 /// \brief Set the flow map. 374 /// 375 /// Set the flow map. 377 376 /// 378 377 /// \return \c (*this) … … 386 385 } 387 386 388 /// \brief Set sthe potential map.389 /// 390 /// Set sthe potential map.387 /// \brief Set the potential map. 388 /// 389 /// Set the potential map. 391 390 /// 392 391 /// \return \c (*this) … … 401 400 402 401 /// \name Execution control 403 /// The only way to execute the algorithm is to call the run()404 /// function.405 402 406 403 /// @{ 407 404 408 /// \brief Run sthe algorithm.409 /// 410 /// Runs the algorithm.405 /// \brief Run the algorithm. 406 /// 407 /// This function runs the algorithm. 411 408 /// 412 409 /// \param scaling Enable or disable capacity scaling. … … 423 420 424 421 /// \name Query Functions 425 /// The result of the algorithm can be obtained using these 426 /// functions. 427 /// \n run() must be called before using them. 422 /// The results of the algorithm can be obtained using these 423 /// functions.\n 424 /// \ref lemon::CapacityScaling::run() "run()" must be called before 425 /// using them. 428 426 429 427 /// @{ 430 428 431 /// \brief Return sa const reference to the edge map storing the429 /// \brief Return a const reference to the edge map storing the 432 430 /// found flow. 433 431 /// 434 /// Return sa const reference to the edge map storing the found flow.432 /// Return a const reference to the edge map storing the found flow. 435 433 /// 436 434 /// \pre \ref run() must be called before using this function. … … 439 437 } 440 438 441 /// \brief Return sa const reference to the node map storing the439 /// \brief Return a const reference to the node map storing the 442 440 /// found potentials (the dual solution). 443 441 /// 444 /// Return sa const reference to the node map storing the found442 /// Return a const reference to the node map storing the found 445 443 /// potentials (the dual solution). 446 444 /// … … 450 448 } 451 449 452 /// \brief Return sthe flow on the given edge.453 /// 454 /// Return sthe flow on the given edge.450 /// \brief Return the flow on the given edge. 451 /// 452 /// Return the flow on the given edge. 455 453 /// 456 454 /// \pre \ref run() must be called before using this function. … … 459 457 } 460 458 461 /// \brief Return sthe potential of the given node.462 /// 463 /// Return sthe potential of the given node.459 /// \brief Return the potential of the given node. 460 /// 461 /// Return the potential of the given node. 464 462 /// 465 463 /// \pre \ref run() must be called before using this function. … … 468 466 } 469 467 470 /// \brief Return sthe total cost of the found flow.471 /// 472 /// Return sthe total cost of the found flow. The complexity of the468 /// \brief Return the total cost of the found flow. 469 /// 470 /// Return the total cost of the found flow. The complexity of the 473 471 /// function is \f$ O(e) \f$. 474 472 /// … … 485 483 private: 486 484 487 /// Initialize sthe algorithm.485 /// Initialize the algorithm. 488 486 bool init(bool scaling) { 489 487 if (!_valid_supply) return false; … … 536 534 } 537 535 538 /// Execute sthe capacity scaling algorithm.536 /// Execute the capacity scaling algorithm. 539 537 bool startWithScaling() { 540 538 // Processing capacity scaling phases … … 568 566 if (_excess[n] <= -_delta) _deficit_nodes.push_back(n); 569 567 } 570 int next_node = 0 ;568 int next_node = 0, next_def_node = 0; 571 569 572 570 // Finding augmenting shortest paths … … 575 573 if (_delta > 1) { 576 574 bool delta_deficit = false; 577 for (int i = 0; i < int(_deficit_nodes.size()); ++i) { 578 if (_excess[_deficit_nodes[i]] <= -_delta) { 575 for ( ; next_def_node < int(_deficit_nodes.size()); 576 ++next_def_node ) { 577 if (_excess[_deficit_nodes[next_def_node]] <= -_delta) { 579 578 delta_deficit = true; 580 579 break; … … 642 641 } 643 642 644 /// Execute sthe successive shortest path algorithm.643 /// Execute the successive shortest path algorithm. 645 644 bool startWithoutScaling() { 646 645 // Finding excess nodes -
lemon/cost_scaling.h
r2588 r2620 65 65 /// 66 66 /// \author Peter Kovacs 67 68 67 template < typename Graph, 69 68 typename LowerMap = typename Graph::template EdgeMap<int>, … … 103 102 /// \brief Map adaptor class for handling residual edge costs. 104 103 /// 105 /// \ref ResidualCostMap is a map adaptor class for handling 106 /// residual edge costs. 104 /// Map adaptor class for handling residual edge costs. 107 105 template <typename Map> 108 106 class ResidualCostMap : public MapBase<ResEdge, typename Map::Value> … … 127 125 /// \brief Map adaptor class for handling reduced edge costs. 128 126 /// 129 /// \ref ReducedCostMap is a map adaptor class for handling reduced 130 /// edge costs. 127 /// Map adaptor class for handling reduced edge costs. 131 128 class ReducedCostMap : public MapBase<Edge, LCost> 132 129 { … … 327 324 } 328 325 329 /// \brief Set sthe flow map.330 /// 331 /// Set sthe flow map.326 /// \brief Set the flow map. 327 /// 328 /// Set the flow map. 332 329 /// 333 330 /// \return \c (*this) … … 341 338 } 342 339 343 /// \brief Set sthe potential map.344 /// 345 /// Set sthe potential map.340 /// \brief Set the potential map. 341 /// 342 /// Set the potential map. 346 343 /// 347 344 /// \return \c (*this) … … 356 353 357 354 /// \name Execution control 358 /// The only way to execute the algorithm is to call the run()359 /// function.360 355 361 356 /// @{ 362 357 363 /// \brief Run sthe algorithm.364 /// 365 /// Run sthe algorithm.358 /// \brief Run the algorithm. 359 /// 360 /// Run the algorithm. 366 361 /// 367 362 /// \return \c true if a feasible flow can be found. … … 374 369 /// \name Query Functions 375 370 /// The result of the algorithm can be obtained using these 376 /// functions. 377 /// \n run() must be called before using them. 371 /// functions.\n 372 /// \ref lemon::CostScaling::run() "run()" must be called before 373 /// using them. 378 374 379 375 /// @{ 380 376 381 /// \brief Return sa const reference to the edge map storing the377 /// \brief Return a const reference to the edge map storing the 382 378 /// found flow. 383 379 /// 384 /// Return sa const reference to the edge map storing the found flow.380 /// Return a const reference to the edge map storing the found flow. 385 381 /// 386 382 /// \pre \ref run() must be called before using this function. … … 389 385 } 390 386 391 /// \brief Return sa const reference to the node map storing the387 /// \brief Return a const reference to the node map storing the 392 388 /// found potentials (the dual solution). 393 389 /// 394 /// Return sa const reference to the node map storing the found390 /// Return a const reference to the node map storing the found 395 391 /// potentials (the dual solution). 396 392 /// … … 400 396 } 401 397 402 /// \brief Return sthe flow on the given edge.403 /// 404 /// Return sthe flow on the given edge.398 /// \brief Return the flow on the given edge. 399 /// 400 /// Return the flow on the given edge. 405 401 /// 406 402 /// \pre \ref run() must be called before using this function. … … 409 405 } 410 406 411 /// \brief Return sthe potential of the given node.412 /// 413 /// Return sthe potential of the given node.407 /// \brief Return the potential of the given node. 408 /// 409 /// Return the potential of the given node. 414 410 /// 415 411 /// \pre \ref run() must be called before using this function. … … 418 414 } 419 415 420 /// \brief Return sthe total cost of the found flow.421 /// 422 /// Return sthe total cost of the found flow. The complexity of the416 /// \brief Return the total cost of the found flow. 417 /// 418 /// Return the total cost of the found flow. The complexity of the 423 419 /// function is \f$ O(e) \f$. 424 420 /// … … 435 431 private: 436 432 437 /// Initialize sthe algorithm.433 /// Initialize the algorithm. 438 434 bool init() { 439 435 if (!_valid_supply) return false; … … 470 466 471 467 472 /// Execute sthe algorithm.468 /// Execute the algorithm. 473 469 bool start() { 474 470 std::deque<Node> active_nodes; -
lemon/cycle_canceling.h
r2593 r2620 65 65 /// 66 66 /// \author Peter Kovacs 67 68 67 template < typename Graph, 69 68 typename LowerMap = typename Graph::template EdgeMap<int>, … … 99 98 /// \brief Map adaptor class for handling residual edge costs. 100 99 /// 101 /// \ref ResidualCostMap is a map adaptor class for handling 102 /// residual edge costs. 100 /// Map adaptor class for handling residual edge costs. 103 101 class ResidualCostMap : public MapBase<ResEdge, Cost> 104 102 { … … 279 277 } 280 278 281 /// \brief Set sthe flow map.282 /// 283 /// Set sthe flow map.279 /// \brief Set the flow map. 280 /// 281 /// Set the flow map. 284 282 /// 285 283 /// \return \c (*this) … … 293 291 } 294 292 295 /// \brief Set sthe potential map.296 /// 297 /// Set sthe potential map.293 /// \brief Set the potential map. 294 /// 295 /// Set the potential map. 298 296 /// 299 297 /// \return \c (*this) … … 308 306 309 307 /// \name Execution control 310 /// The only way to execute the algorithm is to call the run()311 /// function.312 308 313 309 /// @{ 314 310 315 /// \brief Run sthe algorithm.316 /// 317 /// Run sthe algorithm.311 /// \brief Run the algorithm. 312 /// 313 /// Run the algorithm. 318 314 /// 319 315 /// \param min_mean_cc Set this parameter to \c true to run the … … 330 326 /// \name Query Functions 331 327 /// The result of the algorithm can be obtained using these 332 /// functions. 333 /// \n run() must be called before using them. 328 /// functions.\n 329 /// \ref lemon::CycleCanceling::run() "run()" must be called before 330 /// using them. 334 331 335 332 /// @{ 336 333 337 /// \brief Return sa const reference to the edge map storing the334 /// \brief Return a const reference to the edge map storing the 338 335 /// found flow. 339 336 /// 340 /// Return sa const reference to the edge map storing the found flow.337 /// Return a const reference to the edge map storing the found flow. 341 338 /// 342 339 /// \pre \ref run() must be called before using this function. … … 345 342 } 346 343 347 /// \brief Return sa const reference to the node map storing the344 /// \brief Return a const reference to the node map storing the 348 345 /// found potentials (the dual solution). 349 346 /// 350 /// Return sa const reference to the node map storing the found347 /// Return a const reference to the node map storing the found 351 348 /// potentials (the dual solution). 352 349 /// … … 356 353 } 357 354 358 /// \brief Return sthe flow on the given edge.359 /// 360 /// Return sthe flow on the given edge.355 /// \brief Return the flow on the given edge. 356 /// 357 /// Return the flow on the given edge. 361 358 /// 362 359 /// \pre \ref run() must be called before using this function. … … 365 362 } 366 363 367 /// \brief Return sthe potential of the given node.368 /// 369 /// Return sthe potential of the given node.364 /// \brief Return the potential of the given node. 365 /// 366 /// Return the potential of the given node. 370 367 /// 371 368 /// \pre \ref run() must be called before using this function. … … 374 371 } 375 372 376 /// \brief Return sthe total cost of the found flow.377 /// 378 /// Return sthe total cost of the found flow. The complexity of the373 /// \brief Return the total cost of the found flow. 374 /// 375 /// Return the total cost of the found flow. The complexity of the 379 376 /// function is \f$ O(e) \f$. 380 377 /// … … 391 388 private: 392 389 393 /// Initialize sthe algorithm.390 /// Initialize the algorithm. 394 391 bool init() { 395 392 if (!_valid_supply) return false; … … 429 426 } 430 427 431 /// \brief Execute sthe algorithm using \ref BellmanFord.432 /// 433 /// Execute sthe algorithm using the \ref BellmanFord428 /// \brief Execute the algorithm using \ref BellmanFord. 429 /// 430 /// Execute the algorithm using the \ref BellmanFord 434 431 /// "Bellman-Ford" algorithm for negative cycle detection with 435 432 /// successively larger limit for the number of iterations. … … 507 504 } 508 505 509 /// \brief Execute sthe algorithm using \ref MinMeanCycle.510 /// 511 /// Execute sthe algorithm using \ref MinMeanCycle for negative506 /// \brief Execute the algorithm using \ref MinMeanCycle. 507 /// 508 /// Execute the algorithm using \ref MinMeanCycle for negative 512 509 /// cycle detection. 513 510 void startMinMean() { -
lemon/min_cost_flow.h
r2588 r2620 63 63 /// 64 64 /// \author Peter Kovacs 65 66 65 template < typename Graph, 67 66 typename LowerMap = typename Graph::template EdgeMap<int>, -
lemon/min_cost_max_flow.h
r2587 r2620 59 59 /// 60 60 /// \author Peter Kovacs 61 62 61 template < typename Graph, 63 62 typename CapacityMap = typename Graph::template EdgeMap<int>, … … 128 127 } 129 128 130 /// \brief Set sthe flow map.131 /// 132 /// Set sthe flow map.129 /// \brief Set the flow map. 130 /// 131 /// Set the flow map. 133 132 /// 134 133 /// \return \c (*this) … … 142 141 } 143 142 144 /// \brief Set sthe potential map.145 /// 146 /// Set sthe potential map.143 /// \brief Set the potential map. 144 /// 145 /// Set the potential map. 147 146 /// 148 147 /// \return \c (*this) … … 157 156 158 157 /// \name Execution control 159 /// The only way to execute the algorithm is to call the run()160 /// function.161 158 162 159 /// @{ 163 160 164 /// \brief Run sthe algorithm.165 /// 166 /// Run sthe algorithm.161 /// \brief Run the algorithm. 162 /// 163 /// Run the algorithm. 167 164 void run() { 168 165 // Initializing maps … … 187 184 188 185 /// \name Query Functions 189 /// The result of the algorithm can be obtained using these 190 /// functions. 191 /// \n run() must be called before using them. 186 /// The results of the algorithm can be obtained using these 187 /// functions.\n 188 /// \ref lemon::MinCostMaxFlow::run() "run()" must be called before 189 /// using them. 192 190 193 191 /// @{ 194 192 195 /// \brief Return sa const reference to the edge map storing the193 /// \brief Return a const reference to the edge map storing the 196 194 /// found flow. 197 195 /// 198 /// Return sa const reference to the edge map storing the found flow.196 /// Return a const reference to the edge map storing the found flow. 199 197 /// 200 198 /// \pre \ref run() must be called before using this function. … … 203 201 } 204 202 205 /// \brief Return sa const reference to the node map storing the203 /// \brief Return a const reference to the node map storing the 206 204 /// found potentials (the dual solution). 207 205 /// 208 /// Return sa const reference to the node map storing the found206 /// Return a const reference to the node map storing the found 209 207 /// potentials (the dual solution). 210 208 /// … … 214 212 } 215 213 216 /// \brief Return sthe flow on the given edge.217 /// 218 /// Return sthe flow on the given edge.214 /// \brief Return the flow on the given edge. 215 /// 216 /// Return the flow on the given edge. 219 217 /// 220 218 /// \pre \ref run() must be called before using this function. … … 223 221 } 224 222 225 /// \brief Return sthe potential of the given node.226 /// 227 /// Return sthe potential of the given node.223 /// \brief Return the potential of the given node. 224 /// 225 /// Return the potential of the given node. 228 226 /// 229 227 /// \pre \ref run() must be called before using this function. … … 232 230 } 233 231 234 /// \brief Return sthe total cost of the found flow.235 /// 236 /// Return sthe total cost of the found flow. The complexity of the232 /// \brief Return the total cost of the found flow. 233 /// 234 /// Return the total cost of the found flow. The complexity of the 237 235 /// function is \f$ O(e) \f$. 238 236 /// -
lemon/min_mean_cycle.h
r2618 r2620 233 233 return true; 234 234 } 235 235 236 236 /// @} 237 237 … … 242 242 243 243 /// @{ 244 244 245 245 /// \brief Returns the total length of the found cycle. 246 246 /// … … 292 292 return *_cycle_path; 293 293 } 294 294 295 295 ///@} 296 296 297 297 private: 298 298
Note: See TracChangeset
for help on using the changeset viewer.
