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