Changeset 830:75c97c3786d6 in lemon-main for lemon/cost_scaling.h
- Timestamp:
- 02/10/10 19:05:20 (14 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cost_scaling.h
r821 r830 333 333 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, 334 334 "The cost type of CostScaling must be signed"); 335 335 336 // Reset data structures 337 reset(); 338 } 339 340 /// \name Parameters 341 /// The parameters of the algorithm can be specified using these 342 /// functions. 343 344 /// @{ 345 346 /// \brief Set the lower bounds on the arcs. 347 /// 348 /// This function sets the lower bounds on the arcs. 349 /// If it is not used before calling \ref run(), the lower bounds 350 /// will be set to zero on all arcs. 351 /// 352 /// \param map An arc map storing the lower bounds. 353 /// Its \c Value type must be convertible to the \c Value type 354 /// of the algorithm. 355 /// 356 /// \return <tt>(*this)</tt> 357 template <typename LowerMap> 358 CostScaling& lowerMap(const LowerMap& map) { 359 _have_lower = true; 360 for (ArcIt a(_graph); a != INVALID; ++a) { 361 _lower[_arc_idf[a]] = map[a]; 362 _lower[_arc_idb[a]] = map[a]; 363 } 364 return *this; 365 } 366 367 /// \brief Set the upper bounds (capacities) on the arcs. 368 /// 369 /// This function sets the upper bounds (capacities) on the arcs. 370 /// If it is not used before calling \ref run(), the upper bounds 371 /// will be set to \ref INF on all arcs (i.e. the flow value will be 372 /// unbounded from above). 373 /// 374 /// \param map An arc map storing the upper bounds. 375 /// Its \c Value type must be convertible to the \c Value type 376 /// of the algorithm. 377 /// 378 /// \return <tt>(*this)</tt> 379 template<typename UpperMap> 380 CostScaling& upperMap(const UpperMap& map) { 381 for (ArcIt a(_graph); a != INVALID; ++a) { 382 _upper[_arc_idf[a]] = map[a]; 383 } 384 return *this; 385 } 386 387 /// \brief Set the costs of the arcs. 388 /// 389 /// This function sets the costs of the arcs. 390 /// If it is not used before calling \ref run(), the costs 391 /// will be set to \c 1 on all arcs. 392 /// 393 /// \param map An arc map storing the costs. 394 /// Its \c Value type must be convertible to the \c Cost type 395 /// of the algorithm. 396 /// 397 /// \return <tt>(*this)</tt> 398 template<typename CostMap> 399 CostScaling& costMap(const CostMap& map) { 400 for (ArcIt a(_graph); a != INVALID; ++a) { 401 _scost[_arc_idf[a]] = map[a]; 402 _scost[_arc_idb[a]] = -map[a]; 403 } 404 return *this; 405 } 406 407 /// \brief Set the supply values of the nodes. 408 /// 409 /// This function sets the supply values of the nodes. 410 /// If neither this function nor \ref stSupply() is used before 411 /// calling \ref run(), the supply of each node will be set to zero. 412 /// 413 /// \param map A node map storing the supply values. 414 /// Its \c Value type must be convertible to the \c Value type 415 /// of the algorithm. 416 /// 417 /// \return <tt>(*this)</tt> 418 template<typename SupplyMap> 419 CostScaling& supplyMap(const SupplyMap& map) { 420 for (NodeIt n(_graph); n != INVALID; ++n) { 421 _supply[_node_id[n]] = map[n]; 422 } 423 return *this; 424 } 425 426 /// \brief Set single source and target nodes and a supply value. 427 /// 428 /// This function sets a single source node and a single target node 429 /// and the required flow value. 430 /// If neither this function nor \ref supplyMap() is used before 431 /// calling \ref run(), the supply of each node will be set to zero. 432 /// 433 /// Using this function has the same effect as using \ref supplyMap() 434 /// with such a map in which \c k is assigned to \c s, \c -k is 435 /// assigned to \c t and all other nodes have zero supply value. 436 /// 437 /// \param s The source node. 438 /// \param t The target node. 439 /// \param k The required amount of flow from node \c s to node \c t 440 /// (i.e. the supply of \c s and the demand of \c t). 441 /// 442 /// \return <tt>(*this)</tt> 443 CostScaling& stSupply(const Node& s, const Node& t, Value k) { 444 for (int i = 0; i != _res_node_num; ++i) { 445 _supply[i] = 0; 446 } 447 _supply[_node_id[s]] = k; 448 _supply[_node_id[t]] = -k; 449 return *this; 450 } 451 452 /// @} 453 454 /// \name Execution control 455 /// The algorithm can be executed using \ref run(). 456 457 /// @{ 458 459 /// \brief Run the algorithm. 460 /// 461 /// This function runs the algorithm. 462 /// The paramters can be specified using functions \ref lowerMap(), 463 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 464 /// For example, 465 /// \code 466 /// CostScaling<ListDigraph> cs(graph); 467 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 468 /// .supplyMap(sup).run(); 469 /// \endcode 470 /// 471 /// This function can be called more than once. All the given parameters 472 /// are kept for the next call, unless \ref resetParams() or \ref reset() 473 /// is used, thus only the modified parameters have to be set again. 474 /// If the underlying digraph was also modified after the construction 475 /// of the class (or the last \ref reset() call), then the \ref reset() 476 /// function must be called. 477 /// 478 /// \param method The internal method that will be used in the 479 /// algorithm. For more information, see \ref Method. 480 /// \param factor The cost scaling factor. It must be larger than one. 481 /// 482 /// \return \c INFEASIBLE if no feasible flow exists, 483 /// \n \c OPTIMAL if the problem has optimal solution 484 /// (i.e. it is feasible and bounded), and the algorithm has found 485 /// optimal flow and node potentials (primal and dual solutions), 486 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 487 /// and infinite upper bound. It means that the objective function 488 /// is unbounded on that arc, however, note that it could actually be 489 /// bounded over the feasible flows, but this algroithm cannot handle 490 /// these cases. 491 /// 492 /// \see ProblemType, Method 493 /// \see resetParams(), reset() 494 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 495 _alpha = factor; 496 ProblemType pt = init(); 497 if (pt != OPTIMAL) return pt; 498 start(method); 499 return OPTIMAL; 500 } 501 502 /// \brief Reset all the parameters that have been given before. 503 /// 504 /// This function resets all the paramaters that have been given 505 /// before using functions \ref lowerMap(), \ref upperMap(), 506 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 507 /// 508 /// It is useful for multiple \ref run() calls. Basically, all the given 509 /// parameters are kept for the next \ref run() call, unless 510 /// \ref resetParams() or \ref reset() is used. 511 /// If the underlying digraph was also modified after the construction 512 /// of the class or the last \ref reset() call, then the \ref reset() 513 /// function must be used, otherwise \ref resetParams() is sufficient. 514 /// 515 /// For example, 516 /// \code 517 /// CostScaling<ListDigraph> cs(graph); 518 /// 519 /// // First run 520 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 521 /// .supplyMap(sup).run(); 522 /// 523 /// // Run again with modified cost map (resetParams() is not called, 524 /// // so only the cost map have to be set again) 525 /// cost[e] += 100; 526 /// cs.costMap(cost).run(); 527 /// 528 /// // Run again from scratch using resetParams() 529 /// // (the lower bounds will be set to zero on all arcs) 530 /// cs.resetParams(); 531 /// cs.upperMap(capacity).costMap(cost) 532 /// .supplyMap(sup).run(); 533 /// \endcode 534 /// 535 /// \return <tt>(*this)</tt> 536 /// 537 /// \see reset(), run() 538 CostScaling& resetParams() { 539 for (int i = 0; i != _res_node_num; ++i) { 540 _supply[i] = 0; 541 } 542 int limit = _first_out[_root]; 543 for (int j = 0; j != limit; ++j) { 544 _lower[j] = 0; 545 _upper[j] = INF; 546 _scost[j] = _forward[j] ? 1 : -1; 547 } 548 for (int j = limit; j != _res_arc_num; ++j) { 549 _lower[j] = 0; 550 _upper[j] = INF; 551 _scost[j] = 0; 552 _scost[_reverse[j]] = 0; 553 } 554 _have_lower = false; 555 return *this; 556 } 557 558 /// \brief Reset all the parameters that have been given before. 559 /// 560 /// This function resets all the paramaters that have been given 561 /// before using functions \ref lowerMap(), \ref upperMap(), 562 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 563 /// 564 /// It is useful for multiple run() calls. If this function is not 565 /// used, all the parameters given before are kept for the next 566 /// \ref run() call. 567 /// However, the underlying digraph must not be modified after this 568 /// class have been constructed, since it copies and extends the graph. 569 /// \return <tt>(*this)</tt> 570 CostScaling& reset() { 336 571 // Resize vectors 337 572 _node_num = countNodes(_graph); … … 401 636 402 637 // Reset parameters 403 reset(); 404 } 405 406 /// \name Parameters 407 /// The parameters of the algorithm can be specified using these 408 /// functions. 409 410 /// @{ 411 412 /// \brief Set the lower bounds on the arcs. 413 /// 414 /// This function sets the lower bounds on the arcs. 415 /// If it is not used before calling \ref run(), the lower bounds 416 /// will be set to zero on all arcs. 417 /// 418 /// \param map An arc map storing the lower bounds. 419 /// Its \c Value type must be convertible to the \c Value type 420 /// of the algorithm. 421 /// 422 /// \return <tt>(*this)</tt> 423 template <typename LowerMap> 424 CostScaling& lowerMap(const LowerMap& map) { 425 _have_lower = true; 426 for (ArcIt a(_graph); a != INVALID; ++a) { 427 _lower[_arc_idf[a]] = map[a]; 428 _lower[_arc_idb[a]] = map[a]; 429 } 430 return *this; 431 } 432 433 /// \brief Set the upper bounds (capacities) on the arcs. 434 /// 435 /// This function sets the upper bounds (capacities) on the arcs. 436 /// If it is not used before calling \ref run(), the upper bounds 437 /// will be set to \ref INF on all arcs (i.e. the flow value will be 438 /// unbounded from above). 439 /// 440 /// \param map An arc map storing the upper bounds. 441 /// Its \c Value type must be convertible to the \c Value type 442 /// of the algorithm. 443 /// 444 /// \return <tt>(*this)</tt> 445 template<typename UpperMap> 446 CostScaling& upperMap(const UpperMap& map) { 447 for (ArcIt a(_graph); a != INVALID; ++a) { 448 _upper[_arc_idf[a]] = map[a]; 449 } 450 return *this; 451 } 452 453 /// \brief Set the costs of the arcs. 454 /// 455 /// This function sets the costs of the arcs. 456 /// If it is not used before calling \ref run(), the costs 457 /// will be set to \c 1 on all arcs. 458 /// 459 /// \param map An arc map storing the costs. 460 /// Its \c Value type must be convertible to the \c Cost type 461 /// of the algorithm. 462 /// 463 /// \return <tt>(*this)</tt> 464 template<typename CostMap> 465 CostScaling& costMap(const CostMap& map) { 466 for (ArcIt a(_graph); a != INVALID; ++a) { 467 _scost[_arc_idf[a]] = map[a]; 468 _scost[_arc_idb[a]] = -map[a]; 469 } 470 return *this; 471 } 472 473 /// \brief Set the supply values of the nodes. 474 /// 475 /// This function sets the supply values of the nodes. 476 /// If neither this function nor \ref stSupply() is used before 477 /// calling \ref run(), the supply of each node will be set to zero. 478 /// 479 /// \param map A node map storing the supply values. 480 /// Its \c Value type must be convertible to the \c Value type 481 /// of the algorithm. 482 /// 483 /// \return <tt>(*this)</tt> 484 template<typename SupplyMap> 485 CostScaling& supplyMap(const SupplyMap& map) { 486 for (NodeIt n(_graph); n != INVALID; ++n) { 487 _supply[_node_id[n]] = map[n]; 488 } 489 return *this; 490 } 491 492 /// \brief Set single source and target nodes and a supply value. 493 /// 494 /// This function sets a single source node and a single target node 495 /// and the required flow value. 496 /// If neither this function nor \ref supplyMap() is used before 497 /// calling \ref run(), the supply of each node will be set to zero. 498 /// 499 /// Using this function has the same effect as using \ref supplyMap() 500 /// with such a map in which \c k is assigned to \c s, \c -k is 501 /// assigned to \c t and all other nodes have zero supply value. 502 /// 503 /// \param s The source node. 504 /// \param t The target node. 505 /// \param k The required amount of flow from node \c s to node \c t 506 /// (i.e. the supply of \c s and the demand of \c t). 507 /// 508 /// \return <tt>(*this)</tt> 509 CostScaling& stSupply(const Node& s, const Node& t, Value k) { 510 for (int i = 0; i != _res_node_num; ++i) { 511 _supply[i] = 0; 512 } 513 _supply[_node_id[s]] = k; 514 _supply[_node_id[t]] = -k; 515 return *this; 516 } 517 518 /// @} 519 520 /// \name Execution control 521 /// The algorithm can be executed using \ref run(). 522 523 /// @{ 524 525 /// \brief Run the algorithm. 526 /// 527 /// This function runs the algorithm. 528 /// The paramters can be specified using functions \ref lowerMap(), 529 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 530 /// For example, 531 /// \code 532 /// CostScaling<ListDigraph> cs(graph); 533 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 534 /// .supplyMap(sup).run(); 535 /// \endcode 536 /// 537 /// This function can be called more than once. All the parameters 538 /// that have been given are kept for the next call, unless 539 /// \ref reset() is called, thus only the modified parameters 540 /// have to be set again. See \ref reset() for examples. 541 /// However, the underlying digraph must not be modified after this 542 /// class have been constructed, since it copies and extends the graph. 543 /// 544 /// \param method The internal method that will be used in the 545 /// algorithm. For more information, see \ref Method. 546 /// \param factor The cost scaling factor. It must be larger than one. 547 /// 548 /// \return \c INFEASIBLE if no feasible flow exists, 549 /// \n \c OPTIMAL if the problem has optimal solution 550 /// (i.e. it is feasible and bounded), and the algorithm has found 551 /// optimal flow and node potentials (primal and dual solutions), 552 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 553 /// and infinite upper bound. It means that the objective function 554 /// is unbounded on that arc, however, note that it could actually be 555 /// bounded over the feasible flows, but this algroithm cannot handle 556 /// these cases. 557 /// 558 /// \see ProblemType, Method 559 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 560 _alpha = factor; 561 ProblemType pt = init(); 562 if (pt != OPTIMAL) return pt; 563 start(method); 564 return OPTIMAL; 565 } 566 567 /// \brief Reset all the parameters that have been given before. 568 /// 569 /// This function resets all the paramaters that have been given 570 /// before using functions \ref lowerMap(), \ref upperMap(), 571 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 572 /// 573 /// It is useful for multiple run() calls. If this function is not 574 /// used, all the parameters given before are kept for the next 575 /// \ref run() call. 576 /// However, the underlying digraph must not be modified after this 577 /// class have been constructed, since it copies and extends the graph. 578 /// 579 /// For example, 580 /// \code 581 /// CostScaling<ListDigraph> cs(graph); 582 /// 583 /// // First run 584 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 585 /// .supplyMap(sup).run(); 586 /// 587 /// // Run again with modified cost map (reset() is not called, 588 /// // so only the cost map have to be set again) 589 /// cost[e] += 100; 590 /// cs.costMap(cost).run(); 591 /// 592 /// // Run again from scratch using reset() 593 /// // (the lower bounds will be set to zero on all arcs) 594 /// cs.reset(); 595 /// cs.upperMap(capacity).costMap(cost) 596 /// .supplyMap(sup).run(); 597 /// \endcode 598 /// 599 /// \return <tt>(*this)</tt> 600 CostScaling& reset() { 601 for (int i = 0; i != _res_node_num; ++i) { 602 _supply[i] = 0; 603 } 604 int limit = _first_out[_root]; 605 for (int j = 0; j != limit; ++j) { 606 _lower[j] = 0; 607 _upper[j] = INF; 608 _scost[j] = _forward[j] ? 1 : -1; 609 } 610 for (int j = limit; j != _res_arc_num; ++j) { 611 _lower[j] = 0; 612 _upper[j] = INF; 613 _scost[j] = 0; 614 _scost[_reverse[j]] = 0; 615 } 616 _have_lower = false; 638 resetParams(); 617 639 return *this; 618 640 }
Note: See TracChangeset
for help on using the changeset viewer.