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