Changes in lemon/capacity_scaling.h [821:072ec8120958:840:2914b6f0fde0] in lemon-1.2
- File:
-
- 1 edited
-
lemon/capacity_scaling.h (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r821 r840 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 … … 135 140 136 141 typedef std::vector<int> IntVector; 137 typedef std::vector<char> BoolVector;138 142 typedef std::vector<Value> ValueVector; 139 143 typedef std::vector<Cost> CostVector; 144 typedef std::vector<char> BoolVector; 145 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 140 146 141 147 private: … … 315 321 "The cost type of CapacityScaling must be signed"); 316 322 323 // Reset data structures 324 reset(); 325 } 326 327 /// \name Parameters 328 /// The parameters of the algorithm can be specified using these 329 /// functions. 330 331 /// @{ 332 333 /// \brief Set the lower bounds on the arcs. 334 /// 335 /// This function sets the lower bounds on the arcs. 336 /// If it is not used before calling \ref run(), the lower bounds 337 /// will be set to zero on all arcs. 338 /// 339 /// \param map An arc map storing the lower bounds. 340 /// Its \c Value type must be convertible to the \c Value type 341 /// of the algorithm. 342 /// 343 /// \return <tt>(*this)</tt> 344 template <typename LowerMap> 345 CapacityScaling& lowerMap(const LowerMap& map) { 346 _have_lower = true; 347 for (ArcIt a(_graph); a != INVALID; ++a) { 348 _lower[_arc_idf[a]] = map[a]; 349 _lower[_arc_idb[a]] = map[a]; 350 } 351 return *this; 352 } 353 354 /// \brief Set the upper bounds (capacities) on the arcs. 355 /// 356 /// This function sets the upper bounds (capacities) on the arcs. 357 /// If it is not used before calling \ref run(), the upper bounds 358 /// will be set to \ref INF on all arcs (i.e. the flow value will be 359 /// unbounded from above). 360 /// 361 /// \param map An arc map storing the upper bounds. 362 /// Its \c Value type must be convertible to the \c Value type 363 /// of the algorithm. 364 /// 365 /// \return <tt>(*this)</tt> 366 template<typename UpperMap> 367 CapacityScaling& upperMap(const UpperMap& map) { 368 for (ArcIt a(_graph); a != INVALID; ++a) { 369 _upper[_arc_idf[a]] = map[a]; 370 } 371 return *this; 372 } 373 374 /// \brief Set the costs of the arcs. 375 /// 376 /// This function sets the costs of the arcs. 377 /// If it is not used before calling \ref run(), the costs 378 /// will be set to \c 1 on all arcs. 379 /// 380 /// \param map An arc map storing the costs. 381 /// Its \c Value type must be convertible to the \c Cost type 382 /// of the algorithm. 383 /// 384 /// \return <tt>(*this)</tt> 385 template<typename CostMap> 386 CapacityScaling& costMap(const CostMap& map) { 387 for (ArcIt a(_graph); a != INVALID; ++a) { 388 _cost[_arc_idf[a]] = map[a]; 389 _cost[_arc_idb[a]] = -map[a]; 390 } 391 return *this; 392 } 393 394 /// \brief Set the supply values of the nodes. 395 /// 396 /// This function sets the supply values of the nodes. 397 /// If neither this function nor \ref stSupply() is used before 398 /// calling \ref run(), the supply of each node will be set to zero. 399 /// 400 /// \param map A node map storing the supply values. 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 SupplyMap> 406 CapacityScaling& supplyMap(const SupplyMap& map) { 407 for (NodeIt n(_graph); n != INVALID; ++n) { 408 _supply[_node_id[n]] = map[n]; 409 } 410 return *this; 411 } 412 413 /// \brief Set single source and target nodes and a supply value. 414 /// 415 /// This function sets a single source node and a single target node 416 /// and the required flow value. 417 /// If neither this function nor \ref supplyMap() is used before 418 /// calling \ref run(), the supply of each node will be set to zero. 419 /// 420 /// Using this function has the same effect as using \ref supplyMap() 421 /// with such a map in which \c k is assigned to \c s, \c -k is 422 /// assigned to \c t and all other nodes have zero supply value. 423 /// 424 /// \param s The source node. 425 /// \param t The target node. 426 /// \param k The required amount of flow from node \c s to node \c t 427 /// (i.e. the supply of \c s and the demand of \c t). 428 /// 429 /// \return <tt>(*this)</tt> 430 CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { 431 for (int i = 0; i != _node_num; ++i) { 432 _supply[i] = 0; 433 } 434 _supply[_node_id[s]] = k; 435 _supply[_node_id[t]] = -k; 436 return *this; 437 } 438 439 /// @} 440 441 /// \name Execution control 442 /// The algorithm can be executed using \ref run(). 443 444 /// @{ 445 446 /// \brief Run the algorithm. 447 /// 448 /// This function runs the algorithm. 449 /// The paramters can be specified using functions \ref lowerMap(), 450 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 451 /// For example, 452 /// \code 453 /// CapacityScaling<ListDigraph> cs(graph); 454 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 455 /// .supplyMap(sup).run(); 456 /// \endcode 457 /// 458 /// This function can be called more than once. All the given parameters 459 /// are kept for the next call, unless \ref resetParams() or \ref reset() 460 /// is used, thus only the modified parameters have to be set again. 461 /// If the underlying digraph was also modified after the construction 462 /// of the class (or the last \ref reset() call), then the \ref reset() 463 /// function must be called. 464 /// 465 /// \param factor The capacity scaling factor. It must be larger than 466 /// one to use scaling. If it is less or equal to one, then scaling 467 /// will be disabled. 468 /// 469 /// \return \c INFEASIBLE if no feasible flow exists, 470 /// \n \c OPTIMAL if the problem has optimal solution 471 /// (i.e. it is feasible and bounded), and the algorithm has found 472 /// optimal flow and node potentials (primal and dual solutions), 473 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 474 /// and infinite upper bound. It means that the objective function 475 /// is unbounded on that arc, however, note that it could actually be 476 /// bounded over the feasible flows, but this algroithm cannot handle 477 /// these cases. 478 /// 479 /// \see ProblemType 480 /// \see resetParams(), reset() 481 ProblemType run(int factor = 4) { 482 _factor = factor; 483 ProblemType pt = init(); 484 if (pt != OPTIMAL) return pt; 485 return start(); 486 } 487 488 /// \brief Reset all the parameters that have been given before. 489 /// 490 /// This function resets all the paramaters that have been given 491 /// before using functions \ref lowerMap(), \ref upperMap(), 492 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 493 /// 494 /// It is useful for multiple \ref run() calls. Basically, all the given 495 /// parameters are kept for the next \ref run() call, unless 496 /// \ref resetParams() or \ref reset() is used. 497 /// If the underlying digraph was also modified after the construction 498 /// of the class or the last \ref reset() call, then the \ref reset() 499 /// function must be used, otherwise \ref resetParams() is sufficient. 500 /// 501 /// For example, 502 /// \code 503 /// CapacityScaling<ListDigraph> cs(graph); 504 /// 505 /// // First run 506 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 507 /// .supplyMap(sup).run(); 508 /// 509 /// // Run again with modified cost map (resetParams() is not called, 510 /// // so only the cost map have to be set again) 511 /// cost[e] += 100; 512 /// cs.costMap(cost).run(); 513 /// 514 /// // Run again from scratch using resetParams() 515 /// // (the lower bounds will be set to zero on all arcs) 516 /// cs.resetParams(); 517 /// cs.upperMap(capacity).costMap(cost) 518 /// .supplyMap(sup).run(); 519 /// \endcode 520 /// 521 /// \return <tt>(*this)</tt> 522 /// 523 /// \see reset(), run() 524 CapacityScaling& resetParams() { 525 for (int i = 0; i != _node_num; ++i) { 526 _supply[i] = 0; 527 } 528 for (int j = 0; j != _res_arc_num; ++j) { 529 _lower[j] = 0; 530 _upper[j] = INF; 531 _cost[j] = _forward[j] ? 1 : -1; 532 } 533 _have_lower = false; 534 return *this; 535 } 536 537 /// \brief Reset the internal data structures and all the parameters 538 /// that have been given before. 539 /// 540 /// This function resets the internal data structures and all the 541 /// paramaters that have been given before using functions \ref lowerMap(), 542 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 543 /// 544 /// It is useful for multiple \ref run() calls. Basically, all the given 545 /// parameters are kept for the next \ref run() call, unless 546 /// \ref resetParams() or \ref reset() is used. 547 /// If the underlying digraph was also modified after the construction 548 /// of the class or the last \ref reset() call, then the \ref reset() 549 /// function must be used, otherwise \ref resetParams() is sufficient. 550 /// 551 /// See \ref resetParams() for examples. 552 /// 553 /// \return <tt>(*this)</tt> 554 /// 555 /// \see resetParams(), run() 556 CapacityScaling& reset() { 317 557 // Resize vectors 318 558 _node_num = countNodes(_graph); … … 378 618 379 619 // 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; 620 resetParams(); 586 621 return *this; 587 622 } … … 765 800 if (_factor > 1) { 766 801 // With scaling 767 Value max_sup = 0, max_dem = 0 ;768 for (int i = 0; i != _ node_num; ++i) {802 Value max_sup = 0, max_dem = 0, max_cap = 0; 803 for (int i = 0; i != _root; ++i) { 769 804 Value ex = _excess[i]; 770 805 if ( ex > max_sup) max_sup = ex; 771 806 if (-ex > max_dem) max_dem = -ex; 772 }773 Value max_cap = 0;774 for (int j = 0; j != _res_arc_num; ++j) {775 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];807 int last_out = _first_out[i+1] - 1; 808 for (int j = _first_out[i]; j != last_out; ++j) { 809 if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; 810 } 776 811 } 777 812 max_sup = std::min(std::min(max_sup, max_dem), max_cap);
Note: See TracChangeset
for help on using the changeset viewer.
