Changeset 898:75c97c3786d6 in lemon for lemon
 Timestamp:
 02/10/10 19:05:20 (11 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 4 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 } 
lemon/cost_scaling.h
r887 r898 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 } 
lemon/cycle_canceling.h
r886 r898 251 251 "The cost type of CycleCanceling must be signed"); 252 252 253 // Reset data structures 254 reset(); 255 } 256 257 /// \name Parameters 258 /// The parameters of the algorithm can be specified using these 259 /// functions. 260 261 /// @{ 262 263 /// \brief Set the lower bounds on the arcs. 264 /// 265 /// This function sets the lower bounds on the arcs. 266 /// If it is not used before calling \ref run(), the lower bounds 267 /// will be set to zero on all arcs. 268 /// 269 /// \param map An arc map storing the lower bounds. 270 /// Its \c Value type must be convertible to the \c Value type 271 /// of the algorithm. 272 /// 273 /// \return <tt>(*this)</tt> 274 template <typename LowerMap> 275 CycleCanceling& lowerMap(const LowerMap& map) { 276 _have_lower = true; 277 for (ArcIt a(_graph); a != INVALID; ++a) { 278 _lower[_arc_idf[a]] = map[a]; 279 _lower[_arc_idb[a]] = map[a]; 280 } 281 return *this; 282 } 283 284 /// \brief Set the upper bounds (capacities) on the arcs. 285 /// 286 /// This function sets the upper bounds (capacities) on the arcs. 287 /// If it is not used before calling \ref run(), the upper bounds 288 /// will be set to \ref INF on all arcs (i.e. the flow value will be 289 /// unbounded from above). 290 /// 291 /// \param map An arc map storing the upper bounds. 292 /// Its \c Value type must be convertible to the \c Value type 293 /// of the algorithm. 294 /// 295 /// \return <tt>(*this)</tt> 296 template<typename UpperMap> 297 CycleCanceling& upperMap(const UpperMap& map) { 298 for (ArcIt a(_graph); a != INVALID; ++a) { 299 _upper[_arc_idf[a]] = map[a]; 300 } 301 return *this; 302 } 303 304 /// \brief Set the costs of the arcs. 305 /// 306 /// This function sets the costs of the arcs. 307 /// If it is not used before calling \ref run(), the costs 308 /// will be set to \c 1 on all arcs. 309 /// 310 /// \param map An arc map storing the costs. 311 /// Its \c Value type must be convertible to the \c Cost type 312 /// of the algorithm. 313 /// 314 /// \return <tt>(*this)</tt> 315 template<typename CostMap> 316 CycleCanceling& costMap(const CostMap& map) { 317 for (ArcIt a(_graph); a != INVALID; ++a) { 318 _cost[_arc_idf[a]] = map[a]; 319 _cost[_arc_idb[a]] = map[a]; 320 } 321 return *this; 322 } 323 324 /// \brief Set the supply values of the nodes. 325 /// 326 /// This function sets the supply values of the nodes. 327 /// If neither this function nor \ref stSupply() is used before 328 /// calling \ref run(), the supply of each node will be set to zero. 329 /// 330 /// \param map A node map storing the supply values. 331 /// Its \c Value type must be convertible to the \c Value type 332 /// of the algorithm. 333 /// 334 /// \return <tt>(*this)</tt> 335 template<typename SupplyMap> 336 CycleCanceling& supplyMap(const SupplyMap& map) { 337 for (NodeIt n(_graph); n != INVALID; ++n) { 338 _supply[_node_id[n]] = map[n]; 339 } 340 return *this; 341 } 342 343 /// \brief Set single source and target nodes and a supply value. 344 /// 345 /// This function sets a single source node and a single target node 346 /// and the required flow value. 347 /// If neither this function nor \ref supplyMap() is used before 348 /// calling \ref run(), the supply of each node will be set to zero. 349 /// 350 /// Using this function has the same effect as using \ref supplyMap() 351 /// with such a map in which \c k is assigned to \c s, \c k is 352 /// assigned to \c t and all other nodes have zero supply value. 353 /// 354 /// \param s The source node. 355 /// \param t The target node. 356 /// \param k The required amount of flow from node \c s to node \c t 357 /// (i.e. the supply of \c s and the demand of \c t). 358 /// 359 /// \return <tt>(*this)</tt> 360 CycleCanceling& stSupply(const Node& s, const Node& t, Value k) { 361 for (int i = 0; i != _res_node_num; ++i) { 362 _supply[i] = 0; 363 } 364 _supply[_node_id[s]] = k; 365 _supply[_node_id[t]] = k; 366 return *this; 367 } 368 369 /// @} 370 371 /// \name Execution control 372 /// The algorithm can be executed using \ref run(). 373 374 /// @{ 375 376 /// \brief Run the algorithm. 377 /// 378 /// This function runs the algorithm. 379 /// The paramters can be specified using functions \ref lowerMap(), 380 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 381 /// For example, 382 /// \code 383 /// CycleCanceling<ListDigraph> cc(graph); 384 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 385 /// .supplyMap(sup).run(); 386 /// \endcode 387 /// 388 /// This function can be called more than once. All the given parameters 389 /// are kept for the next call, unless \ref resetParams() or \ref reset() 390 /// is used, thus only the modified parameters have to be set again. 391 /// If the underlying digraph was also modified after the construction 392 /// of the class (or the last \ref reset() call), then the \ref reset() 393 /// function must be called. 394 /// 395 /// \param method The cyclecanceling method that will be used. 396 /// For more information, see \ref Method. 397 /// 398 /// \return \c INFEASIBLE if no feasible flow exists, 399 /// \n \c OPTIMAL if the problem has optimal solution 400 /// (i.e. it is feasible and bounded), and the algorithm has found 401 /// optimal flow and node potentials (primal and dual solutions), 402 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 403 /// and infinite upper bound. It means that the objective function 404 /// is unbounded on that arc, however, note that it could actually be 405 /// bounded over the feasible flows, but this algroithm cannot handle 406 /// these cases. 407 /// 408 /// \see ProblemType, Method 409 /// \see resetParams(), reset() 410 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 411 ProblemType pt = init(); 412 if (pt != OPTIMAL) return pt; 413 start(method); 414 return OPTIMAL; 415 } 416 417 /// \brief Reset all the parameters that have been given before. 418 /// 419 /// This function resets all the paramaters that have been given 420 /// before using functions \ref lowerMap(), \ref upperMap(), 421 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 422 /// 423 /// It is useful for multiple \ref run() calls. Basically, all the given 424 /// parameters are kept for the next \ref run() call, unless 425 /// \ref resetParams() or \ref reset() is used. 426 /// If the underlying digraph was also modified after the construction 427 /// of the class or the last \ref reset() call, then the \ref reset() 428 /// function must be used, otherwise \ref resetParams() is sufficient. 429 /// 430 /// For example, 431 /// \code 432 /// CycleCanceling<ListDigraph> cs(graph); 433 /// 434 /// // First run 435 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 436 /// .supplyMap(sup).run(); 437 /// 438 /// // Run again with modified cost map (resetParams() is not called, 439 /// // so only the cost map have to be set again) 440 /// cost[e] += 100; 441 /// cc.costMap(cost).run(); 442 /// 443 /// // Run again from scratch using resetParams() 444 /// // (the lower bounds will be set to zero on all arcs) 445 /// cc.resetParams(); 446 /// cc.upperMap(capacity).costMap(cost) 447 /// .supplyMap(sup).run(); 448 /// \endcode 449 /// 450 /// \return <tt>(*this)</tt> 451 /// 452 /// \see reset(), run() 453 CycleCanceling& resetParams() { 454 for (int i = 0; i != _res_node_num; ++i) { 455 _supply[i] = 0; 456 } 457 int limit = _first_out[_root]; 458 for (int j = 0; j != limit; ++j) { 459 _lower[j] = 0; 460 _upper[j] = INF; 461 _cost[j] = _forward[j] ? 1 : 1; 462 } 463 for (int j = limit; j != _res_arc_num; ++j) { 464 _lower[j] = 0; 465 _upper[j] = INF; 466 _cost[j] = 0; 467 _cost[_reverse[j]] = 0; 468 } 469 _have_lower = false; 470 return *this; 471 } 472 473 /// \brief Reset the internal data structures and all the parameters 474 /// that have been given before. 475 /// 476 /// This function resets the internal data structures and all the 477 /// paramaters that have been given before using functions \ref lowerMap(), 478 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 479 /// 480 /// It is useful for multiple \ref run() calls. Basically, all the given 481 /// parameters are kept for the next \ref run() call, unless 482 /// \ref resetParams() or \ref reset() is used. 483 /// If the underlying digraph was also modified after the construction 484 /// of the class or the last \ref reset() call, then the \ref reset() 485 /// function must be used, otherwise \ref resetParams() is sufficient. 486 /// 487 /// See \ref resetParams() for examples. 488 /// 489 /// \return <tt>(*this)</tt> 490 /// 491 /// \see resetParams(), run() 492 CycleCanceling& reset() { 253 493 // Resize vectors 254 494 _node_num = countNodes(_graph); … … 316 556 317 557 // Reset parameters 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 CycleCanceling& 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 CycleCanceling& 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 CycleCanceling& 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 CycleCanceling& 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 CycleCanceling& stSupply(const Node& s, const Node& t, Value k) { 425 for (int i = 0; i != _res_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 /// CycleCanceling<ListDigraph> cc(graph); 448 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 449 /// .supplyMap(sup).run(); 450 /// \endcode 451 /// 452 /// This function can be called more than once. All the parameters 453 /// that have been given are kept for the next call, unless 454 /// \ref reset() is called, thus only the modified parameters 455 /// have to be set again. See \ref reset() for examples. 456 /// However, the underlying digraph must not be modified after this 457 /// class have been constructed, since it copies and extends the graph. 458 /// 459 /// \param method The cyclecanceling method that will be used. 460 /// For more information, see \ref Method. 461 /// 462 /// \return \c INFEASIBLE if no feasible flow exists, 463 /// \n \c OPTIMAL if the problem has optimal solution 464 /// (i.e. it is feasible and bounded), and the algorithm has found 465 /// optimal flow and node potentials (primal and dual solutions), 466 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 467 /// and infinite upper bound. It means that the objective function 468 /// is unbounded on that arc, however, note that it could actually be 469 /// bounded over the feasible flows, but this algroithm cannot handle 470 /// these cases. 471 /// 472 /// \see ProblemType, Method 473 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 474 ProblemType pt = init(); 475 if (pt != OPTIMAL) return pt; 476 start(method); 477 return OPTIMAL; 478 } 479 480 /// \brief Reset all the parameters that have been given before. 481 /// 482 /// This function resets all the paramaters that have been given 483 /// before using functions \ref lowerMap(), \ref upperMap(), 484 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 485 /// 486 /// It is useful for multiple run() calls. If this function is not 487 /// used, all the parameters given before are kept for the next 488 /// \ref run() call. 489 /// However, the underlying digraph must not be modified after this 490 /// class have been constructed, since it copies and extends the graph. 491 /// 492 /// For example, 493 /// \code 494 /// CycleCanceling<ListDigraph> cs(graph); 495 /// 496 /// // First run 497 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 498 /// .supplyMap(sup).run(); 499 /// 500 /// // Run again with modified cost map (reset() is not called, 501 /// // so only the cost map have to be set again) 502 /// cost[e] += 100; 503 /// cc.costMap(cost).run(); 504 /// 505 /// // Run again from scratch using reset() 506 /// // (the lower bounds will be set to zero on all arcs) 507 /// cc.reset(); 508 /// cc.upperMap(capacity).costMap(cost) 509 /// .supplyMap(sup).run(); 510 /// \endcode 511 /// 512 /// \return <tt>(*this)</tt> 513 CycleCanceling& reset() { 514 for (int i = 0; i != _res_node_num; ++i) { 515 _supply[i] = 0; 516 } 517 int limit = _first_out[_root]; 518 for (int j = 0; j != limit; ++j) { 519 _lower[j] = 0; 520 _upper[j] = INF; 521 _cost[j] = _forward[j] ? 1 : 1; 522 } 523 for (int j = limit; j != _res_arc_num; ++j) { 524 _lower[j] = 0; 525 _upper[j] = INF; 526 _cost[j] = 0; 527 _cost[_reverse[j]] = 0; 528 } 529 _have_lower = false; 558 resetParams(); 530 559 return *this; 531 560 } 
lemon/network_simplex.h
r878 r898 195 195 IntVector _source; 196 196 IntVector _target; 197 bool _arc_mixing; 197 198 198 199 // Node and arc data … … 634 635 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 635 636 _graph(graph), _node_id(graph), _arc_id(graph), 637 _arc_mixing(arc_mixing), 636 638 MAX(std::numeric_limits<Value>::max()), 637 639 INF(std::numeric_limits<Value>::has_infinity ? … … 644 646 "The cost type of NetworkSimplex must be signed"); 645 647 646 // Resize vectors 647 _node_num = countNodes(_graph); 648 _arc_num = countArcs(_graph); 649 int all_node_num = _node_num + 1; 650 int max_arc_num = _arc_num + 2 * _node_num; 651 652 _source.resize(max_arc_num); 653 _target.resize(max_arc_num); 654 655 _lower.resize(_arc_num); 656 _upper.resize(_arc_num); 657 _cap.resize(max_arc_num); 658 _cost.resize(max_arc_num); 659 _supply.resize(all_node_num); 660 _flow.resize(max_arc_num); 661 _pi.resize(all_node_num); 662 663 _parent.resize(all_node_num); 664 _pred.resize(all_node_num); 665 _forward.resize(all_node_num); 666 _thread.resize(all_node_num); 667 _rev_thread.resize(all_node_num); 668 _succ_num.resize(all_node_num); 669 _last_succ.resize(all_node_num); 670 _state.resize(max_arc_num); 671 672 // Copy the graph 673 int i = 0; 674 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 675 _node_id[n] = i; 676 } 677 if (arc_mixing) { 678 // Store the arcs in a mixed order 679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 680 int i = 0, j = 0; 681 for (ArcIt a(_graph); a != INVALID; ++a) { 682 _arc_id[a] = i; 683 _source[i] = _node_id[_graph.source(a)]; 684 _target[i] = _node_id[_graph.target(a)]; 685 if ((i += k) >= _arc_num) i = ++j; 686 } 687 } else { 688 // Store the arcs in the original order 689 int i = 0; 690 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 691 _arc_id[a] = i; 692 _source[i] = _node_id[_graph.source(a)]; 693 _target[i] = _node_id[_graph.target(a)]; 694 } 695 } 696 697 // Reset parameters 648 // Reset data structures 698 649 reset(); 699 650 } … … 843 794 /// \endcode 844 795 /// 845 /// This function can be called more than once. All the parameters846 /// that have been given are kept for the next call, unless847 /// \ref reset() is called, thus only the modified parameters848 /// have to be set again. See \ref reset() for examples.849 /// However, the underlying digraph must not be modified after this850 /// class have been constructed, since it copies and extends the graph.796 /// This function can be called more than once. All the given parameters 797 /// are kept for the next call, unless \ref resetParams() or \ref reset() 798 /// is used, thus only the modified parameters have to be set again. 799 /// If the underlying digraph was also modified after the construction 800 /// of the class (or the last \ref reset() call), then the \ref reset() 801 /// function must be called. 851 802 /// 852 803 /// \param pivot_rule The pivot rule that will be used during the … … 862 813 /// 863 814 /// \see ProblemType, PivotRule 815 /// \see resetParams(), reset() 864 816 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 865 817 if (!init()) return INFEASIBLE; … … 873 825 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 874 826 /// 875 /// It is useful for multiple run() calls. If this function is not 876 /// used, all the parameters given before are kept for the next 877 /// \ref run() call. 878 /// However, the underlying digraph must not be modified after this 879 /// class have been constructed, since it copies and extends the graph. 827 /// It is useful for multiple \ref run() calls. Basically, all the given 828 /// parameters are kept for the next \ref run() call, unless 829 /// \ref resetParams() or \ref reset() is used. 830 /// If the underlying digraph was also modified after the construction 831 /// of the class or the last \ref reset() call, then the \ref reset() 832 /// function must be used, otherwise \ref resetParams() is sufficient. 880 833 /// 881 834 /// For example, … … 887 840 /// .supplyMap(sup).run(); 888 841 /// 889 /// // Run again with modified cost map (reset () is not called,842 /// // Run again with modified cost map (resetParams() is not called, 890 843 /// // so only the cost map have to be set again) 891 844 /// cost[e] += 100; 892 845 /// ns.costMap(cost).run(); 893 846 /// 894 /// // Run again from scratch using reset ()847 /// // Run again from scratch using resetParams() 895 848 /// // (the lower bounds will be set to zero on all arcs) 896 /// ns.reset ();849 /// ns.resetParams(); 897 850 /// ns.upperMap(capacity).costMap(cost) 898 851 /// .supplyMap(sup).run(); … … 900 853 /// 901 854 /// \return <tt>(*this)</tt> 902 NetworkSimplex& reset() { 855 /// 856 /// \see reset(), run() 857 NetworkSimplex& resetParams() { 903 858 for (int i = 0; i != _node_num; ++i) { 904 859 _supply[i] = 0; … … 914 869 } 915 870 871 /// \brief Reset the internal data structures and all the parameters 872 /// that have been given before. 873 /// 874 /// This function resets the internal data structures and all the 875 /// paramaters that have been given before using functions \ref lowerMap(), 876 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 877 /// \ref supplyType(). 878 /// 879 /// It is useful for multiple \ref run() calls. Basically, all the given 880 /// parameters are kept for the next \ref run() call, unless 881 /// \ref resetParams() or \ref reset() is used. 882 /// If the underlying digraph was also modified after the construction 883 /// of the class or the last \ref reset() call, then the \ref reset() 884 /// function must be used, otherwise \ref resetParams() is sufficient. 885 /// 886 /// See \ref resetParams() for examples. 887 /// 888 /// \return <tt>(*this)</tt> 889 /// 890 /// \see resetParams(), run() 891 NetworkSimplex& reset() { 892 // Resize vectors 893 _node_num = countNodes(_graph); 894 _arc_num = countArcs(_graph); 895 int all_node_num = _node_num + 1; 896 int max_arc_num = _arc_num + 2 * _node_num; 897 898 _source.resize(max_arc_num); 899 _target.resize(max_arc_num); 900 901 _lower.resize(_arc_num); 902 _upper.resize(_arc_num); 903 _cap.resize(max_arc_num); 904 _cost.resize(max_arc_num); 905 _supply.resize(all_node_num); 906 _flow.resize(max_arc_num); 907 _pi.resize(all_node_num); 908 909 _parent.resize(all_node_num); 910 _pred.resize(all_node_num); 911 _forward.resize(all_node_num); 912 _thread.resize(all_node_num); 913 _rev_thread.resize(all_node_num); 914 _succ_num.resize(all_node_num); 915 _last_succ.resize(all_node_num); 916 _state.resize(max_arc_num); 917 918 // Copy the graph 919 int i = 0; 920 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 921 _node_id[n] = i; 922 } 923 if (_arc_mixing) { 924 // Store the arcs in a mixed order 925 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 926 int i = 0, j = 0; 927 for (ArcIt a(_graph); a != INVALID; ++a) { 928 _arc_id[a] = i; 929 _source[i] = _node_id[_graph.source(a)]; 930 _target[i] = _node_id[_graph.target(a)]; 931 if ((i += k) >= _arc_num) i = ++j; 932 } 933 } else { 934 // Store the arcs in the original order 935 int i = 0; 936 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 937 _arc_id[a] = i; 938 _source[i] = _node_id[_graph.source(a)]; 939 _target[i] = _node_id[_graph.target(a)]; 940 } 941 } 942 943 // Reset parameters 944 resetParams(); 945 return *this; 946 } 947 916 948 /// @} 917 949
Note: See TracChangeset
for help on using the changeset viewer.