Changeset 840:2914b6f0fde0 in lemon-1.2 for lemon
- Timestamp:
- 02/26/10 14:00:20 (15 years ago)
- Branch:
- default
- Parents:
- 838:2c35bef44dd1 (diff), 839:f3bc4e9b5f3a (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:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r831 r840 140 140 141 141 typedef std::vector<int> IntVector; 142 typedef std::vector<char> BoolVector;143 142 typedef std::vector<Value> ValueVector; 144 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 145 146 146 147 private: … … 799 800 if (_factor > 1) { 800 801 // With scaling 801 Value max_sup = 0, max_dem = 0 ;802 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) { 803 804 Value ex = _excess[i]; 804 805 if ( ex > max_sup) max_sup = ex; 805 806 if (-ex > max_dem) max_dem = -ex; 806 }807 Value max_cap = 0;808 for (int j = 0; j != _res_arc_num; ++j) {809 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 } 810 811 } 811 812 max_sup = std::min(std::min(max_sup, max_dem), max_cap); -
lemon/capacity_scaling.h
r839 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 … … 316 321 "The cost type of CapacityScaling must be signed"); 317 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() { 318 557 // Resize vectors 319 558 _node_num = countNodes(_graph); … … 379 618 380 619 // Reset parameters 381 reset(); 382 } 383 384 /// \name Parameters 385 /// The parameters of the algorithm can be specified using these 386 /// functions. 387 388 /// @{ 389 390 /// \brief Set the lower bounds on the arcs. 391 /// 392 /// This function sets the lower bounds on the arcs. 393 /// If it is not used before calling \ref run(), the lower bounds 394 /// will be set to zero on all arcs. 395 /// 396 /// \param map An arc map storing the lower bounds. 397 /// Its \c Value type must be convertible to the \c Value type 398 /// of the algorithm. 399 /// 400 /// \return <tt>(*this)</tt> 401 template <typename LowerMap> 402 CapacityScaling& lowerMap(const LowerMap& map) { 403 _have_lower = true; 404 for (ArcIt a(_graph); a != INVALID; ++a) { 405 _lower[_arc_idf[a]] = map[a]; 406 _lower[_arc_idb[a]] = map[a]; 407 } 408 return *this; 409 } 410 411 /// \brief Set the upper bounds (capacities) on the arcs. 412 /// 413 /// This function sets the upper bounds (capacities) on the arcs. 414 /// If it is not used before calling \ref run(), the upper bounds 415 /// will be set to \ref INF on all arcs (i.e. the flow value will be 416 /// unbounded from above). 417 /// 418 /// \param map An arc map storing the upper 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 UpperMap> 424 CapacityScaling& upperMap(const UpperMap& map) { 425 for (ArcIt a(_graph); a != INVALID; ++a) { 426 _upper[_arc_idf[a]] = map[a]; 427 } 428 return *this; 429 } 430 431 /// \brief Set the costs of the arcs. 432 /// 433 /// This function sets the costs of the arcs. 434 /// If it is not used before calling \ref run(), the costs 435 /// will be set to \c 1 on all arcs. 436 /// 437 /// \param map An arc map storing the costs. 438 /// Its \c Value type must be convertible to the \c Cost type 439 /// of the algorithm. 440 /// 441 /// \return <tt>(*this)</tt> 442 template<typename CostMap> 443 CapacityScaling& costMap(const CostMap& map) { 444 for (ArcIt a(_graph); a != INVALID; ++a) { 445 _cost[_arc_idf[a]] = map[a]; 446 _cost[_arc_idb[a]] = -map[a]; 447 } 448 return *this; 449 } 450 451 /// \brief Set the supply values of the nodes. 452 /// 453 /// This function sets the supply values of the nodes. 454 /// If neither this function nor \ref stSupply() is used before 455 /// calling \ref run(), the supply of each node will be set to zero. 456 /// 457 /// \param map A node map storing the supply values. 458 /// Its \c Value type must be convertible to the \c Value type 459 /// of the algorithm. 460 /// 461 /// \return <tt>(*this)</tt> 462 template<typename SupplyMap> 463 CapacityScaling& supplyMap(const SupplyMap& map) { 464 for (NodeIt n(_graph); n != INVALID; ++n) { 465 _supply[_node_id[n]] = map[n]; 466 } 467 return *this; 468 } 469 470 /// \brief Set single source and target nodes and a supply value. 471 /// 472 /// This function sets a single source node and a single target node 473 /// and the required flow value. 474 /// If neither this function nor \ref supplyMap() is used before 475 /// calling \ref run(), the supply of each node will be set to zero. 476 /// 477 /// Using this function has the same effect as using \ref supplyMap() 478 /// with such a map in which \c k is assigned to \c s, \c -k is 479 /// assigned to \c t and all other nodes have zero supply value. 480 /// 481 /// \param s The source node. 482 /// \param t The target node. 483 /// \param k The required amount of flow from node \c s to node \c t 484 /// (i.e. the supply of \c s and the demand of \c t). 485 /// 486 /// \return <tt>(*this)</tt> 487 CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { 488 for (int i = 0; i != _node_num; ++i) { 489 _supply[i] = 0; 490 } 491 _supply[_node_id[s]] = k; 492 _supply[_node_id[t]] = -k; 493 return *this; 494 } 495 496 /// @} 497 498 /// \name Execution control 499 /// The algorithm can be executed using \ref run(). 500 501 /// @{ 502 503 /// \brief Run the algorithm. 504 /// 505 /// This function runs the algorithm. 506 /// The paramters can be specified using functions \ref lowerMap(), 507 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 508 /// For example, 509 /// \code 510 /// CapacityScaling<ListDigraph> cs(graph); 511 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 512 /// .supplyMap(sup).run(); 513 /// \endcode 514 /// 515 /// This function can be called more than once. All the parameters 516 /// that have been given are kept for the next call, unless 517 /// \ref reset() is called, thus only the modified parameters 518 /// have to be set again. See \ref reset() for examples. 519 /// However, the underlying digraph must not be modified after this 520 /// class have been constructed, since it copies and extends the graph. 521 /// 522 /// \param factor The capacity scaling factor. It must be larger than 523 /// one to use scaling. If it is less or equal to one, then scaling 524 /// will be disabled. 525 /// 526 /// \return \c INFEASIBLE if no feasible flow exists, 527 /// \n \c OPTIMAL if the problem has optimal solution 528 /// (i.e. it is feasible and bounded), and the algorithm has found 529 /// optimal flow and node potentials (primal and dual solutions), 530 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 531 /// and infinite upper bound. It means that the objective function 532 /// is unbounded on that arc, however, note that it could actually be 533 /// bounded over the feasible flows, but this algroithm cannot handle 534 /// these cases. 535 /// 536 /// \see ProblemType 537 ProblemType run(int factor = 4) { 538 _factor = factor; 539 ProblemType pt = init(); 540 if (pt != OPTIMAL) return pt; 541 return start(); 542 } 543 544 /// \brief Reset all the parameters that have been given before. 545 /// 546 /// This function resets all the paramaters that have been given 547 /// before using functions \ref lowerMap(), \ref upperMap(), 548 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 549 /// 550 /// It is useful for multiple run() calls. If this function is not 551 /// used, all the parameters given before are kept for the next 552 /// \ref run() call. 553 /// However, the underlying digraph must not be modified after this 554 /// class have been constructed, since it copies and extends the graph. 555 /// 556 /// For example, 557 /// \code 558 /// CapacityScaling<ListDigraph> cs(graph); 559 /// 560 /// // First run 561 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 562 /// .supplyMap(sup).run(); 563 /// 564 /// // Run again with modified cost map (reset() is not called, 565 /// // so only the cost map have to be set again) 566 /// cost[e] += 100; 567 /// cs.costMap(cost).run(); 568 /// 569 /// // Run again from scratch using reset() 570 /// // (the lower bounds will be set to zero on all arcs) 571 /// cs.reset(); 572 /// cs.upperMap(capacity).costMap(cost) 573 /// .supplyMap(sup).run(); 574 /// \endcode 575 /// 576 /// \return <tt>(*this)</tt> 577 CapacityScaling& reset() { 578 for (int i = 0; i != _node_num; ++i) { 579 _supply[i] = 0; 580 } 581 for (int j = 0; j != _res_arc_num; ++j) { 582 _lower[j] = 0; 583 _upper[j] = INF; 584 _cost[j] = _forward[j] ? 1 : -1; 585 } 586 _have_lower = false; 620 resetParams(); 587 621 return *this; 588 622 } -
lemon/cost_scaling.h
r831 r840 202 202 203 203 typedef std::vector<int> IntVector; 204 typedef std::vector<char> BoolVector;205 204 typedef std::vector<Value> ValueVector; 206 205 typedef std::vector<Cost> CostVector; 207 206 typedef std::vector<LargeCost> LargeCostVector; 207 typedef std::vector<char> BoolVector; 208 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 208 209 209 210 private: … … 249 250 bool _have_lower; 250 251 Value _sum_supply; 252 int _sup_node_num; 251 253 252 254 // Data structures for storing the digraph … … 277 279 int _alpha; 278 280 281 IntVector _buckets; 282 IntVector _bucket_next; 283 IntVector _bucket_prev; 284 IntVector _rank; 285 int _max_rank; 286 279 287 // Data for a StaticDigraph structure 280 288 typedef std::pair<int, int> IntPair; … … 829 837 } 830 838 839 _sup_node_num = 0; 840 for (NodeIt n(_graph); n != INVALID; ++n) { 841 if (sup[n] > 0) ++_sup_node_num; 842 } 843 831 844 // Find a feasible flow using Circulation 832 845 Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap> … … 863 876 for (int a = _first_out[_root]; a != _res_arc_num; ++a) { 864 877 int ra = _reverse[a]; 865 _res_cap[a] = 1;878 _res_cap[a] = 0; 866 879 _res_cap[ra] = 0; 867 880 _cost[a] = 0; … … 877 890 // Maximum path length for partial augment 878 891 const int MAX_PATH_LENGTH = 4; 879 892 893 // Initialize data structures for buckets 894 _max_rank = _alpha * _res_node_num; 895 _buckets.resize(_max_rank); 896 _bucket_next.resize(_res_node_num + 1); 897 _bucket_prev.resize(_res_node_num + 1); 898 _rank.resize(_res_node_num + 1); 899 880 900 // Execute the algorithm 881 901 switch (method) { … … 916 936 } 917 937 } 938 939 // Initialize a cost scaling phase 940 void initPhase() { 941 // Saturate arcs not satisfying the optimality condition 942 for (int u = 0; u != _res_node_num; ++u) { 943 int last_out = _first_out[u+1]; 944 LargeCost pi_u = _pi[u]; 945 for (int a = _first_out[u]; a != last_out; ++a) { 946 int v = _target[a]; 947 if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) { 948 Value delta = _res_cap[a]; 949 _excess[u] -= delta; 950 _excess[v] += delta; 951 _res_cap[a] = 0; 952 _res_cap[_reverse[a]] += delta; 953 } 954 } 955 } 956 957 // Find active nodes (i.e. nodes with positive excess) 958 for (int u = 0; u != _res_node_num; ++u) { 959 if (_excess[u] > 0) _active_nodes.push_back(u); 960 } 961 962 // Initialize the next arcs 963 for (int u = 0; u != _res_node_num; ++u) { 964 _next_out[u] = _first_out[u]; 965 } 966 } 967 968 // Early termination heuristic 969 bool earlyTermination() { 970 const double EARLY_TERM_FACTOR = 3.0; 971 972 // Build a static residual graph 973 _arc_vec.clear(); 974 _cost_vec.clear(); 975 for (int j = 0; j != _res_arc_num; ++j) { 976 if (_res_cap[j] > 0) { 977 _arc_vec.push_back(IntPair(_source[j], _target[j])); 978 _cost_vec.push_back(_cost[j] + 1); 979 } 980 } 981 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 982 983 // Run Bellman-Ford algorithm to check if the current flow is optimal 984 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 985 bf.init(0); 986 bool done = false; 987 int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num))); 988 for (int i = 0; i < K && !done; ++i) { 989 done = bf.processNextWeakRound(); 990 } 991 return done; 992 } 993 994 // Global potential update heuristic 995 void globalUpdate() { 996 int bucket_end = _root + 1; 997 998 // Initialize buckets 999 for (int r = 0; r != _max_rank; ++r) { 1000 _buckets[r] = bucket_end; 1001 } 1002 Value total_excess = 0; 1003 for (int i = 0; i != _res_node_num; ++i) { 1004 if (_excess[i] < 0) { 1005 _rank[i] = 0; 1006 _bucket_next[i] = _buckets[0]; 1007 _bucket_prev[_buckets[0]] = i; 1008 _buckets[0] = i; 1009 } else { 1010 total_excess += _excess[i]; 1011 _rank[i] = _max_rank; 1012 } 1013 } 1014 if (total_excess == 0) return; 1015 1016 // Search the buckets 1017 int r = 0; 1018 for ( ; r != _max_rank; ++r) { 1019 while (_buckets[r] != bucket_end) { 1020 // Remove the first node from the current bucket 1021 int u = _buckets[r]; 1022 _buckets[r] = _bucket_next[u]; 1023 1024 // Search the incomming arcs of u 1025 LargeCost pi_u = _pi[u]; 1026 int last_out = _first_out[u+1]; 1027 for (int a = _first_out[u]; a != last_out; ++a) { 1028 int ra = _reverse[a]; 1029 if (_res_cap[ra] > 0) { 1030 int v = _source[ra]; 1031 int old_rank_v = _rank[v]; 1032 if (r < old_rank_v) { 1033 // Compute the new rank of v 1034 LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon; 1035 int new_rank_v = old_rank_v; 1036 if (nrc < LargeCost(_max_rank)) 1037 new_rank_v = r + 1 + int(nrc); 1038 1039 // Change the rank of v 1040 if (new_rank_v < old_rank_v) { 1041 _rank[v] = new_rank_v; 1042 _next_out[v] = _first_out[v]; 1043 1044 // Remove v from its old bucket 1045 if (old_rank_v < _max_rank) { 1046 if (_buckets[old_rank_v] == v) { 1047 _buckets[old_rank_v] = _bucket_next[v]; 1048 } else { 1049 _bucket_next[_bucket_prev[v]] = _bucket_next[v]; 1050 _bucket_prev[_bucket_next[v]] = _bucket_prev[v]; 1051 } 1052 } 1053 1054 // Insert v to its new bucket 1055 _bucket_next[v] = _buckets[new_rank_v]; 1056 _bucket_prev[_buckets[new_rank_v]] = v; 1057 _buckets[new_rank_v] = v; 1058 } 1059 } 1060 } 1061 } 1062 1063 // Finish search if there are no more active nodes 1064 if (_excess[u] > 0) { 1065 total_excess -= _excess[u]; 1066 if (total_excess <= 0) break; 1067 } 1068 } 1069 if (total_excess <= 0) break; 1070 } 1071 1072 // Relabel nodes 1073 for (int u = 0; u != _res_node_num; ++u) { 1074 int k = std::min(_rank[u], r); 1075 if (k > 0) { 1076 _pi[u] -= _epsilon * k; 1077 _next_out[u] = _first_out[u]; 1078 } 1079 } 1080 } 918 1081 919 1082 /// Execute the algorithm performing augment and relabel operations 920 1083 void startAugment(int max_length = std::numeric_limits<int>::max()) { 921 1084 // Paramters for heuristics 922 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 923 const int BF_HEURISTIC_BOUND_FACTOR = 3; 924 1085 const int EARLY_TERM_EPSILON_LIMIT = 1000; 1086 const double GLOBAL_UPDATE_FACTOR = 3.0; 1087 1088 const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * 1089 (_res_node_num + _sup_node_num * _sup_node_num)); 1090 int next_update_limit = global_update_freq; 1091 1092 int relabel_cnt = 0; 1093 925 1094 // Perform cost scaling phases 926 IntVector pred_arc(_res_node_num); 927 std::vector<int> path_nodes; 1095 std::vector<int> path; 928 1096 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 929 1097 1 : _epsilon / _alpha ) 930 1098 { 931 // "Early Termination" heuristic: use Bellman-Ford algorithm 932 // to check if the current flow is optimal 933 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 934 _arc_vec.clear(); 935 _cost_vec.clear(); 936 for (int j = 0; j != _res_arc_num; ++j) { 937 if (_res_cap[j] > 0) { 938 _arc_vec.push_back(IntPair(_source[j], _target[j])); 939 _cost_vec.push_back(_cost[j] + 1); 940 } 941 } 942 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 943 944 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 945 bf.init(0); 946 bool done = false; 947 int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num)); 948 for (int i = 0; i < K && !done; ++i) 949 done = bf.processNextWeakRound(); 950 if (done) break; 951 } 952 953 // Saturate arcs not satisfying the optimality condition 954 for (int a = 0; a != _res_arc_num; ++a) { 955 if (_res_cap[a] > 0 && 956 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 957 Value delta = _res_cap[a]; 958 _excess[_source[a]] -= delta; 959 _excess[_target[a]] += delta; 960 _res_cap[a] = 0; 961 _res_cap[_reverse[a]] += delta; 962 } 1099 // Early termination heuristic 1100 if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { 1101 if (earlyTermination()) break; 963 1102 } 964 1103 965 // Find active nodes (i.e. nodes with positive excess) 966 for (int u = 0; u != _res_node_num; ++u) { 967 if (_excess[u] > 0) _active_nodes.push_back(u); 968 } 969 970 // Initialize the next arcs 971 for (int u = 0; u != _res_node_num; ++u) { 972 _next_out[u] = _first_out[u]; 973 } 974 1104 // Initialize current phase 1105 initPhase(); 1106 975 1107 // Perform partial augment and relabel operations 976 1108 while (true) { … … 982 1114 if (_active_nodes.size() == 0) break; 983 1115 int start = _active_nodes.front(); 984 path_nodes.clear();985 path_nodes.push_back(start);986 1116 987 1117 // Find an augmenting path from the start node 1118 path.clear(); 988 1119 int tip = start; 989 while (_excess[tip] >= 0 && 990 int(path_nodes.size()) <= max_length) { 1120 while (_excess[tip] >= 0 && int(path.size()) < max_length) { 991 1121 int u; 992 LargeCost min_red_cost, rc; 993 int last_out = _sum_supply < 0 ? 994 _first_out[tip+1] : _first_out[tip+1] - 1; 1122 LargeCost min_red_cost, rc, pi_tip = _pi[tip]; 1123 int last_out = _first_out[tip+1]; 995 1124 for (int a = _next_out[tip]; a != last_out; ++a) { 996 if (_res_cap[a] > 0 && 997 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 998 u = _target[a]; 999 pred_arc[u] = a; 1125 u = _target[a]; 1126 if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) { 1127 path.push_back(a); 1000 1128 _next_out[tip] = a; 1001 1129 tip = u; 1002 path_nodes.push_back(tip);1003 1130 goto next_step; 1004 1131 } … … 1006 1133 1007 1134 // Relabel tip node 1008 min_red_cost = std::numeric_limits<LargeCost>::max() / 2; 1135 min_red_cost = std::numeric_limits<LargeCost>::max(); 1136 if (tip != start) { 1137 int ra = _reverse[path.back()]; 1138 min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]]; 1139 } 1009 1140 for (int a = _first_out[tip]; a != last_out; ++a) { 1010 rc = _cost[a] + _pi[_source[a]]- _pi[_target[a]];1141 rc = _cost[a] + pi_tip - _pi[_target[a]]; 1011 1142 if (_res_cap[a] > 0 && rc < min_red_cost) { 1012 1143 min_red_cost = rc; … … 1014 1145 } 1015 1146 _pi[tip] -= min_red_cost + _epsilon; 1016 1017 // Reset the next arc of tip1018 1147 _next_out[tip] = _first_out[tip]; 1148 ++relabel_cnt; 1019 1149 1020 1150 // Step back 1021 1151 if (tip != start) { 1022 path_nodes.pop_back();1023 tip = path_nodes.back();1152 tip = _source[path.back()]; 1153 path.pop_back(); 1024 1154 } 1025 1155 … … 1029 1159 // Augment along the found path (as much flow as possible) 1030 1160 Value delta; 1031 int u, v = path_nodes.front(), pa; 1032 for (int i = 1; i < int(path_nodes.size()); ++i) { 1161 int pa, u, v = start; 1162 for (int i = 0; i != int(path.size()); ++i) { 1163 pa = path[i]; 1033 1164 u = v; 1034 v = path_nodes[i]; 1035 pa = pred_arc[v]; 1165 v = _target[pa]; 1036 1166 delta = std::min(_res_cap[pa], _excess[u]); 1037 1167 _res_cap[pa] -= delta; … … 1042 1172 _active_nodes.push_back(v); 1043 1173 } 1174 1175 // Global update heuristic 1176 if (relabel_cnt >= next_update_limit) { 1177 globalUpdate(); 1178 next_update_limit += global_update_freq; 1179 } 1044 1180 } 1045 1181 } … … 1049 1185 void startPush() { 1050 1186 // Paramters for heuristics 1051 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 1052 const int BF_HEURISTIC_BOUND_FACTOR = 3; 1053 1187 const int EARLY_TERM_EPSILON_LIMIT = 1000; 1188 const double GLOBAL_UPDATE_FACTOR = 2.0; 1189 1190 const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * 1191 (_res_node_num + _sup_node_num * _sup_node_num)); 1192 int next_update_limit = global_update_freq; 1193 1194 int relabel_cnt = 0; 1195 1054 1196 // Perform cost scaling phases 1055 1197 BoolVector hyper(_res_node_num, false); 1198 LargeCostVector hyper_cost(_res_node_num); 1056 1199 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 1057 1200 1 : _epsilon / _alpha ) 1058 1201 { 1059 // "Early Termination" heuristic: use Bellman-Ford algorithm 1060 // to check if the current flow is optimal 1061 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 1062 _arc_vec.clear(); 1063 _cost_vec.clear(); 1064 for (int j = 0; j != _res_arc_num; ++j) { 1065 if (_res_cap[j] > 0) { 1066 _arc_vec.push_back(IntPair(_source[j], _target[j])); 1067 _cost_vec.push_back(_cost[j] + 1); 1068 } 1069 } 1070 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 1071 1072 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 1073 bf.init(0); 1074 bool done = false; 1075 int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num)); 1076 for (int i = 0; i < K && !done; ++i) 1077 done = bf.processNextWeakRound(); 1078 if (done) break; 1079 } 1080 1081 // Saturate arcs not satisfying the optimality condition 1082 for (int a = 0; a != _res_arc_num; ++a) { 1083 if (_res_cap[a] > 0 && 1084 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 1085 Value delta = _res_cap[a]; 1086 _excess[_source[a]] -= delta; 1087 _excess[_target[a]] += delta; 1088 _res_cap[a] = 0; 1089 _res_cap[_reverse[a]] += delta; 1090 } 1091 } 1092 1093 // Find active nodes (i.e. nodes with positive excess) 1094 for (int u = 0; u != _res_node_num; ++u) { 1095 if (_excess[u] > 0) _active_nodes.push_back(u); 1096 } 1097 1098 // Initialize the next arcs 1099 for (int u = 0; u != _res_node_num; ++u) { 1100 _next_out[u] = _first_out[u]; 1101 } 1202 // Early termination heuristic 1203 if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { 1204 if (earlyTermination()) break; 1205 } 1206 1207 // Initialize current phase 1208 initPhase(); 1102 1209 1103 1210 // Perform push and relabel operations 1104 1211 while (_active_nodes.size() > 0) { 1105 LargeCost min_red_cost, rc ;1212 LargeCost min_red_cost, rc, pi_n; 1106 1213 Value delta; 1107 1214 int n, t, a, last_out = _res_arc_num; 1108 1215 1216 next_node: 1109 1217 // Select an active node (FIFO selection) 1110 next_node:1111 1218 n = _active_nodes.front(); 1112 last_out = _ sum_supply < 0 ?1113 _first_out[n+1] : _first_out[n+1] - 1;1114 1219 last_out = _first_out[n+1]; 1220 pi_n = _pi[n]; 1221 1115 1222 // Perform push operations if there are admissible arcs 1116 1223 if (_excess[n] > 0) { 1117 1224 for (a = _next_out[n]; a != last_out; ++a) { 1118 1225 if (_res_cap[a] > 0 && 1119 _cost[a] + _pi[_source[a]]- _pi[_target[a]] < 0) {1226 _cost[a] + pi_n - _pi[_target[a]] < 0) { 1120 1227 delta = std::min(_res_cap[a], _excess[n]); 1121 1228 t = _target[a]; … … 1123 1230 // Push-look-ahead heuristic 1124 1231 Value ahead = -_excess[t]; 1125 int last_out_t = _ sum_supply < 0 ?1126 _first_out[t+1] : _first_out[t+1] - 1;1232 int last_out_t = _first_out[t+1]; 1233 LargeCost pi_t = _pi[t]; 1127 1234 for (int ta = _next_out[t]; ta != last_out_t; ++ta) { 1128 1235 if (_res_cap[ta] > 0 && 1129 _cost[ta] + _pi[_source[ta]]- _pi[_target[ta]] < 0)1236 _cost[ta] + pi_t - _pi[_target[ta]] < 0) 1130 1237 ahead += _res_cap[ta]; 1131 1238 if (ahead >= delta) break; … … 1134 1241 1135 1242 // Push flow along the arc 1136 if (ahead < delta ) {1243 if (ahead < delta && !hyper[t]) { 1137 1244 _res_cap[a] -= ahead; 1138 1245 _res_cap[_reverse[a]] += ahead; … … 1141 1248 _active_nodes.push_front(t); 1142 1249 hyper[t] = true; 1250 hyper_cost[t] = _cost[a] + pi_n - pi_t; 1143 1251 _next_out[n] = a; 1144 1252 goto next_node; … … 1163 1271 // Relabel the node if it is still active (or hyper) 1164 1272 if (_excess[n] > 0 || hyper[n]) { 1165 min_red_cost = std::numeric_limits<LargeCost>::max() / 2; 1273 min_red_cost = hyper[n] ? -hyper_cost[n] : 1274 std::numeric_limits<LargeCost>::max(); 1166 1275 for (int a = _first_out[n]; a != last_out; ++a) { 1167 rc = _cost[a] + _pi[_source[a]]- _pi[_target[a]];1276 rc = _cost[a] + pi_n - _pi[_target[a]]; 1168 1277 if (_res_cap[a] > 0 && rc < min_red_cost) { 1169 1278 min_red_cost = rc; … … 1171 1280 } 1172 1281 _pi[n] -= min_red_cost + _epsilon; 1282 _next_out[n] = _first_out[n]; 1173 1283 hyper[n] = false; 1174 1175 // Reset the next arc 1176 _next_out[n] = _first_out[n]; 1284 ++relabel_cnt; 1177 1285 } 1178 1286 … … 1184 1292 _active_nodes.pop_front(); 1185 1293 } 1294 1295 // Global update heuristic 1296 if (relabel_cnt >= next_update_limit) { 1297 globalUpdate(); 1298 for (int u = 0; u != _res_node_num; ++u) 1299 hyper[u] = false; 1300 next_update_limit += global_update_freq; 1301 } 1186 1302 } 1187 1303 } -
lemon/cost_scaling.h
r839 r840 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; … … 341 345 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, 342 346 "The cost type of CostScaling must be signed"); 343 347 348 // Reset data structures 349 reset(); 350 } 351 352 /// \name Parameters 353 /// The parameters of the algorithm can be specified using these 354 /// functions. 355 356 /// @{ 357 358 /// \brief Set the lower bounds on the arcs. 359 /// 360 /// This function sets the lower bounds on the arcs. 361 /// If it is not used before calling \ref run(), the lower bounds 362 /// will be set to zero on all arcs. 363 /// 364 /// \param map An arc map storing the lower bounds. 365 /// Its \c Value type must be convertible to the \c Value type 366 /// of the algorithm. 367 /// 368 /// \return <tt>(*this)</tt> 369 template <typename LowerMap> 370 CostScaling& lowerMap(const LowerMap& map) { 371 _have_lower = true; 372 for (ArcIt a(_graph); a != INVALID; ++a) { 373 _lower[_arc_idf[a]] = map[a]; 374 _lower[_arc_idb[a]] = map[a]; 375 } 376 return *this; 377 } 378 379 /// \brief Set the upper bounds (capacities) on the arcs. 380 /// 381 /// This function sets the upper bounds (capacities) on the arcs. 382 /// If it is not used before calling \ref run(), the upper bounds 383 /// will be set to \ref INF on all arcs (i.e. the flow value will be 384 /// unbounded from above). 385 /// 386 /// \param map An arc map storing the upper bounds. 387 /// Its \c Value type must be convertible to the \c Value type 388 /// of the algorithm. 389 /// 390 /// \return <tt>(*this)</tt> 391 template<typename UpperMap> 392 CostScaling& upperMap(const UpperMap& map) { 393 for (ArcIt a(_graph); a != INVALID; ++a) { 394 _upper[_arc_idf[a]] = map[a]; 395 } 396 return *this; 397 } 398 399 /// \brief Set the costs of the arcs. 400 /// 401 /// This function sets the costs of the arcs. 402 /// If it is not used before calling \ref run(), the costs 403 /// will be set to \c 1 on all arcs. 404 /// 405 /// \param map An arc map storing the costs. 406 /// Its \c Value type must be convertible to the \c Cost type 407 /// of the algorithm. 408 /// 409 /// \return <tt>(*this)</tt> 410 template<typename CostMap> 411 CostScaling& costMap(const CostMap& map) { 412 for (ArcIt a(_graph); a != INVALID; ++a) { 413 _scost[_arc_idf[a]] = map[a]; 414 _scost[_arc_idb[a]] = -map[a]; 415 } 416 return *this; 417 } 418 419 /// \brief Set the supply values of the nodes. 420 /// 421 /// This function sets the supply values of the nodes. 422 /// If neither this function nor \ref stSupply() is used before 423 /// calling \ref run(), the supply of each node will be set to zero. 424 /// 425 /// \param map A node map storing the supply values. 426 /// Its \c Value type must be convertible to the \c Value type 427 /// of the algorithm. 428 /// 429 /// \return <tt>(*this)</tt> 430 template<typename SupplyMap> 431 CostScaling& supplyMap(const SupplyMap& map) { 432 for (NodeIt n(_graph); n != INVALID; ++n) { 433 _supply[_node_id[n]] = map[n]; 434 } 435 return *this; 436 } 437 438 /// \brief Set single source and target nodes and a supply value. 439 /// 440 /// This function sets a single source node and a single target node 441 /// and the required flow value. 442 /// If neither this function nor \ref supplyMap() is used before 443 /// calling \ref run(), the supply of each node will be set to zero. 444 /// 445 /// Using this function has the same effect as using \ref supplyMap() 446 /// with such a map in which \c k is assigned to \c s, \c -k is 447 /// assigned to \c t and all other nodes have zero supply value. 448 /// 449 /// \param s The source node. 450 /// \param t The target node. 451 /// \param k The required amount of flow from node \c s to node \c t 452 /// (i.e. the supply of \c s and the demand of \c t). 453 /// 454 /// \return <tt>(*this)</tt> 455 CostScaling& stSupply(const Node& s, const Node& t, Value k) { 456 for (int i = 0; i != _res_node_num; ++i) { 457 _supply[i] = 0; 458 } 459 _supply[_node_id[s]] = k; 460 _supply[_node_id[t]] = -k; 461 return *this; 462 } 463 464 /// @} 465 466 /// \name Execution control 467 /// The algorithm can be executed using \ref run(). 468 469 /// @{ 470 471 /// \brief Run the algorithm. 472 /// 473 /// This function runs the algorithm. 474 /// The paramters can be specified using functions \ref lowerMap(), 475 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 476 /// For example, 477 /// \code 478 /// CostScaling<ListDigraph> cs(graph); 479 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 480 /// .supplyMap(sup).run(); 481 /// \endcode 482 /// 483 /// This function can be called more than once. All the given parameters 484 /// are kept for the next call, unless \ref resetParams() or \ref reset() 485 /// is used, thus only the modified parameters have to be set again. 486 /// If the underlying digraph was also modified after the construction 487 /// of the class (or the last \ref reset() call), then the \ref reset() 488 /// function must be called. 489 /// 490 /// \param method The internal method that will be used in the 491 /// algorithm. For more information, see \ref Method. 492 /// \param factor The cost scaling factor. It must be larger than one. 493 /// 494 /// \return \c INFEASIBLE if no feasible flow exists, 495 /// \n \c OPTIMAL if the problem has optimal solution 496 /// (i.e. it is feasible and bounded), and the algorithm has found 497 /// optimal flow and node potentials (primal and dual solutions), 498 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 499 /// and infinite upper bound. It means that the objective function 500 /// is unbounded on that arc, however, note that it could actually be 501 /// bounded over the feasible flows, but this algroithm cannot handle 502 /// these cases. 503 /// 504 /// \see ProblemType, Method 505 /// \see resetParams(), reset() 506 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 507 _alpha = factor; 508 ProblemType pt = init(); 509 if (pt != OPTIMAL) return pt; 510 start(method); 511 return OPTIMAL; 512 } 513 514 /// \brief Reset all the parameters that have been given before. 515 /// 516 /// This function resets all the paramaters that have been given 517 /// before using functions \ref lowerMap(), \ref upperMap(), 518 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 519 /// 520 /// It is useful for multiple \ref run() calls. Basically, all the given 521 /// parameters are kept for the next \ref run() call, unless 522 /// \ref resetParams() or \ref reset() is used. 523 /// If the underlying digraph was also modified after the construction 524 /// of the class or the last \ref reset() call, then the \ref reset() 525 /// function must be used, otherwise \ref resetParams() is sufficient. 526 /// 527 /// For example, 528 /// \code 529 /// CostScaling<ListDigraph> cs(graph); 530 /// 531 /// // First run 532 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 533 /// .supplyMap(sup).run(); 534 /// 535 /// // Run again with modified cost map (resetParams() is not called, 536 /// // so only the cost map have to be set again) 537 /// cost[e] += 100; 538 /// cs.costMap(cost).run(); 539 /// 540 /// // Run again from scratch using resetParams() 541 /// // (the lower bounds will be set to zero on all arcs) 542 /// cs.resetParams(); 543 /// cs.upperMap(capacity).costMap(cost) 544 /// .supplyMap(sup).run(); 545 /// \endcode 546 /// 547 /// \return <tt>(*this)</tt> 548 /// 549 /// \see reset(), run() 550 CostScaling& resetParams() { 551 for (int i = 0; i != _res_node_num; ++i) { 552 _supply[i] = 0; 553 } 554 int limit = _first_out[_root]; 555 for (int j = 0; j != limit; ++j) { 556 _lower[j] = 0; 557 _upper[j] = INF; 558 _scost[j] = _forward[j] ? 1 : -1; 559 } 560 for (int j = limit; j != _res_arc_num; ++j) { 561 _lower[j] = 0; 562 _upper[j] = INF; 563 _scost[j] = 0; 564 _scost[_reverse[j]] = 0; 565 } 566 _have_lower = false; 567 return *this; 568 } 569 570 /// \brief Reset all the parameters that have been given before. 571 /// 572 /// This function resets all the paramaters that have been given 573 /// before using functions \ref lowerMap(), \ref upperMap(), 574 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 575 /// 576 /// It is useful for multiple run() calls. If this function is not 577 /// used, all the parameters given before are kept for the next 578 /// \ref run() call. 579 /// However, the underlying digraph must not be modified after this 580 /// class have been constructed, since it copies and extends the graph. 581 /// \return <tt>(*this)</tt> 582 CostScaling& reset() { 344 583 // Resize vectors 345 584 _node_num = countNodes(_graph); … … 409 648 410 649 // Reset parameters 411 reset(); 412 } 413 414 /// \name Parameters 415 /// The parameters of the algorithm can be specified using these 416 /// functions. 417 418 /// @{ 419 420 /// \brief Set the lower bounds on the arcs. 421 /// 422 /// This function sets the lower bounds on the arcs. 423 /// If it is not used before calling \ref run(), the lower bounds 424 /// will be set to zero on all arcs. 425 /// 426 /// \param map An arc map storing the lower bounds. 427 /// Its \c Value type must be convertible to the \c Value type 428 /// of the algorithm. 429 /// 430 /// \return <tt>(*this)</tt> 431 template <typename LowerMap> 432 CostScaling& lowerMap(const LowerMap& map) { 433 _have_lower = true; 434 for (ArcIt a(_graph); a != INVALID; ++a) { 435 _lower[_arc_idf[a]] = map[a]; 436 _lower[_arc_idb[a]] = map[a]; 437 } 438 return *this; 439 } 440 441 /// \brief Set the upper bounds (capacities) on the arcs. 442 /// 443 /// This function sets the upper bounds (capacities) on the arcs. 444 /// If it is not used before calling \ref run(), the upper bounds 445 /// will be set to \ref INF on all arcs (i.e. the flow value will be 446 /// unbounded from above). 447 /// 448 /// \param map An arc map storing the upper bounds. 449 /// Its \c Value type must be convertible to the \c Value type 450 /// of the algorithm. 451 /// 452 /// \return <tt>(*this)</tt> 453 template<typename UpperMap> 454 CostScaling& upperMap(const UpperMap& map) { 455 for (ArcIt a(_graph); a != INVALID; ++a) { 456 _upper[_arc_idf[a]] = map[a]; 457 } 458 return *this; 459 } 460 461 /// \brief Set the costs of the arcs. 462 /// 463 /// This function sets the costs of the arcs. 464 /// If it is not used before calling \ref run(), the costs 465 /// will be set to \c 1 on all arcs. 466 /// 467 /// \param map An arc map storing the costs. 468 /// Its \c Value type must be convertible to the \c Cost type 469 /// of the algorithm. 470 /// 471 /// \return <tt>(*this)</tt> 472 template<typename CostMap> 473 CostScaling& costMap(const CostMap& map) { 474 for (ArcIt a(_graph); a != INVALID; ++a) { 475 _scost[_arc_idf[a]] = map[a]; 476 _scost[_arc_idb[a]] = -map[a]; 477 } 478 return *this; 479 } 480 481 /// \brief Set the supply values of the nodes. 482 /// 483 /// This function sets the supply values of the nodes. 484 /// If neither this function nor \ref stSupply() is used before 485 /// calling \ref run(), the supply of each node will be set to zero. 486 /// 487 /// \param map A node map storing the supply values. 488 /// Its \c Value type must be convertible to the \c Value type 489 /// of the algorithm. 490 /// 491 /// \return <tt>(*this)</tt> 492 template<typename SupplyMap> 493 CostScaling& supplyMap(const SupplyMap& map) { 494 for (NodeIt n(_graph); n != INVALID; ++n) { 495 _supply[_node_id[n]] = map[n]; 496 } 497 return *this; 498 } 499 500 /// \brief Set single source and target nodes and a supply value. 501 /// 502 /// This function sets a single source node and a single target node 503 /// and the required flow value. 504 /// If neither this function nor \ref supplyMap() is used before 505 /// calling \ref run(), the supply of each node will be set to zero. 506 /// 507 /// Using this function has the same effect as using \ref supplyMap() 508 /// with such a map in which \c k is assigned to \c s, \c -k is 509 /// assigned to \c t and all other nodes have zero supply value. 510 /// 511 /// \param s The source node. 512 /// \param t The target node. 513 /// \param k The required amount of flow from node \c s to node \c t 514 /// (i.e. the supply of \c s and the demand of \c t). 515 /// 516 /// \return <tt>(*this)</tt> 517 CostScaling& stSupply(const Node& s, const Node& t, Value k) { 518 for (int i = 0; i != _res_node_num; ++i) { 519 _supply[i] = 0; 520 } 521 _supply[_node_id[s]] = k; 522 _supply[_node_id[t]] = -k; 523 return *this; 524 } 525 526 /// @} 527 528 /// \name Execution control 529 /// The algorithm can be executed using \ref run(). 530 531 /// @{ 532 533 /// \brief Run the algorithm. 534 /// 535 /// This function runs the algorithm. 536 /// The paramters can be specified using functions \ref lowerMap(), 537 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 538 /// For example, 539 /// \code 540 /// CostScaling<ListDigraph> cs(graph); 541 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 542 /// .supplyMap(sup).run(); 543 /// \endcode 544 /// 545 /// This function can be called more than once. All the parameters 546 /// that have been given are kept for the next call, unless 547 /// \ref reset() is called, thus only the modified parameters 548 /// have to be set again. See \ref reset() for examples. 549 /// However, the underlying digraph must not be modified after this 550 /// class have been constructed, since it copies and extends the graph. 551 /// 552 /// \param method The internal method that will be used in the 553 /// algorithm. For more information, see \ref Method. 554 /// \param factor The cost scaling factor. It must be larger than one. 555 /// 556 /// \return \c INFEASIBLE if no feasible flow exists, 557 /// \n \c OPTIMAL if the problem has optimal solution 558 /// (i.e. it is feasible and bounded), and the algorithm has found 559 /// optimal flow and node potentials (primal and dual solutions), 560 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 561 /// and infinite upper bound. It means that the objective function 562 /// is unbounded on that arc, however, note that it could actually be 563 /// bounded over the feasible flows, but this algroithm cannot handle 564 /// these cases. 565 /// 566 /// \see ProblemType, Method 567 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 568 _alpha = factor; 569 ProblemType pt = init(); 570 if (pt != OPTIMAL) return pt; 571 start(method); 572 return OPTIMAL; 573 } 574 575 /// \brief Reset all the parameters that have been given before. 576 /// 577 /// This function resets all the paramaters that have been given 578 /// before using functions \ref lowerMap(), \ref upperMap(), 579 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 580 /// 581 /// It is useful for multiple run() calls. If this function is not 582 /// used, all the parameters given before are kept for the next 583 /// \ref run() call. 584 /// However, the underlying digraph must not be modified after this 585 /// class have been constructed, since it copies and extends the graph. 586 /// 587 /// For example, 588 /// \code 589 /// CostScaling<ListDigraph> cs(graph); 590 /// 591 /// // First run 592 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 593 /// .supplyMap(sup).run(); 594 /// 595 /// // Run again with modified cost map (reset() is not called, 596 /// // so only the cost map have to be set again) 597 /// cost[e] += 100; 598 /// cs.costMap(cost).run(); 599 /// 600 /// // Run again from scratch using reset() 601 /// // (the lower bounds will be set to zero on all arcs) 602 /// cs.reset(); 603 /// cs.upperMap(capacity).costMap(cost) 604 /// .supplyMap(sup).run(); 605 /// \endcode 606 /// 607 /// \return <tt>(*this)</tt> 608 CostScaling& reset() { 609 for (int i = 0; i != _res_node_num; ++i) { 610 _supply[i] = 0; 611 } 612 int limit = _first_out[_root]; 613 for (int j = 0; j != limit; ++j) { 614 _lower[j] = 0; 615 _upper[j] = INF; 616 _scost[j] = _forward[j] ? 1 : -1; 617 } 618 for (int j = limit; j != _res_arc_num; ++j) { 619 _lower[j] = 0; 620 _upper[j] = INF; 621 _scost[j] = 0; 622 _scost[_reverse[j]] = 0; 623 } 624 _have_lower = false; 650 resetParams(); 625 651 return *this; 626 652 } -
lemon/cycle_canceling.h
r830 r840 145 145 146 146 typedef std::vector<int> IntVector; 147 typedef std::vector<char> CharVector;148 147 typedef std::vector<double> DoubleVector; 149 148 typedef std::vector<Value> ValueVector; 150 149 typedef std::vector<Cost> CostVector; 150 typedef std::vector<char> BoolVector; 151 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 151 152 152 153 private: … … 199 200 IntArcMap _arc_idb; 200 201 IntVector _first_out; 201 CharVector _forward;202 BoolVector _forward; 202 203 IntVector _source; 203 204 IntVector _target; … … 963 964 DoubleVector pi(_res_node_num, 0.0); 964 965 IntVector level(_res_node_num); 965 CharVector reached(_res_node_num);966 CharVector processed(_res_node_num);966 BoolVector reached(_res_node_num); 967 BoolVector processed(_res_node_num); 967 968 IntVector pred_node(_res_node_num); 968 969 IntVector pred_arc(_res_node_num); -
lemon/cycle_canceling.h
r839 r840 252 252 "The cost type of CycleCanceling must be signed"); 253 253 254 // Reset data structures 255 reset(); 256 } 257 258 /// \name Parameters 259 /// The parameters of the algorithm can be specified using these 260 /// functions. 261 262 /// @{ 263 264 /// \brief Set the lower bounds on the arcs. 265 /// 266 /// This function sets the lower bounds on the arcs. 267 /// If it is not used before calling \ref run(), the lower bounds 268 /// will be set to zero on all arcs. 269 /// 270 /// \param map An arc map storing the lower bounds. 271 /// Its \c Value type must be convertible to the \c Value type 272 /// of the algorithm. 273 /// 274 /// \return <tt>(*this)</tt> 275 template <typename LowerMap> 276 CycleCanceling& lowerMap(const LowerMap& map) { 277 _have_lower = true; 278 for (ArcIt a(_graph); a != INVALID; ++a) { 279 _lower[_arc_idf[a]] = map[a]; 280 _lower[_arc_idb[a]] = map[a]; 281 } 282 return *this; 283 } 284 285 /// \brief Set the upper bounds (capacities) on the arcs. 286 /// 287 /// This function sets the upper bounds (capacities) on the arcs. 288 /// If it is not used before calling \ref run(), the upper bounds 289 /// will be set to \ref INF on all arcs (i.e. the flow value will be 290 /// unbounded from above). 291 /// 292 /// \param map An arc map storing the upper bounds. 293 /// Its \c Value type must be convertible to the \c Value type 294 /// of the algorithm. 295 /// 296 /// \return <tt>(*this)</tt> 297 template<typename UpperMap> 298 CycleCanceling& upperMap(const UpperMap& map) { 299 for (ArcIt a(_graph); a != INVALID; ++a) { 300 _upper[_arc_idf[a]] = map[a]; 301 } 302 return *this; 303 } 304 305 /// \brief Set the costs of the arcs. 306 /// 307 /// This function sets the costs of the arcs. 308 /// If it is not used before calling \ref run(), the costs 309 /// will be set to \c 1 on all arcs. 310 /// 311 /// \param map An arc map storing the costs. 312 /// Its \c Value type must be convertible to the \c Cost type 313 /// of the algorithm. 314 /// 315 /// \return <tt>(*this)</tt> 316 template<typename CostMap> 317 CycleCanceling& costMap(const CostMap& map) { 318 for (ArcIt a(_graph); a != INVALID; ++a) { 319 _cost[_arc_idf[a]] = map[a]; 320 _cost[_arc_idb[a]] = -map[a]; 321 } 322 return *this; 323 } 324 325 /// \brief Set the supply values of the nodes. 326 /// 327 /// This function sets the supply values of the nodes. 328 /// If neither this function nor \ref stSupply() is used before 329 /// calling \ref run(), the supply of each node will be set to zero. 330 /// 331 /// \param map A node map storing the supply values. 332 /// Its \c Value type must be convertible to the \c Value type 333 /// of the algorithm. 334 /// 335 /// \return <tt>(*this)</tt> 336 template<typename SupplyMap> 337 CycleCanceling& supplyMap(const SupplyMap& map) { 338 for (NodeIt n(_graph); n != INVALID; ++n) { 339 _supply[_node_id[n]] = map[n]; 340 } 341 return *this; 342 } 343 344 /// \brief Set single source and target nodes and a supply value. 345 /// 346 /// This function sets a single source node and a single target node 347 /// and the required flow value. 348 /// If neither this function nor \ref supplyMap() is used before 349 /// calling \ref run(), the supply of each node will be set to zero. 350 /// 351 /// Using this function has the same effect as using \ref supplyMap() 352 /// with such a map in which \c k is assigned to \c s, \c -k is 353 /// assigned to \c t and all other nodes have zero supply value. 354 /// 355 /// \param s The source node. 356 /// \param t The target node. 357 /// \param k The required amount of flow from node \c s to node \c t 358 /// (i.e. the supply of \c s and the demand of \c t). 359 /// 360 /// \return <tt>(*this)</tt> 361 CycleCanceling& stSupply(const Node& s, const Node& t, Value k) { 362 for (int i = 0; i != _res_node_num; ++i) { 363 _supply[i] = 0; 364 } 365 _supply[_node_id[s]] = k; 366 _supply[_node_id[t]] = -k; 367 return *this; 368 } 369 370 /// @} 371 372 /// \name Execution control 373 /// The algorithm can be executed using \ref run(). 374 375 /// @{ 376 377 /// \brief Run the algorithm. 378 /// 379 /// This function runs the algorithm. 380 /// The paramters can be specified using functions \ref lowerMap(), 381 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 382 /// For example, 383 /// \code 384 /// CycleCanceling<ListDigraph> cc(graph); 385 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 386 /// .supplyMap(sup).run(); 387 /// \endcode 388 /// 389 /// This function can be called more than once. All the given parameters 390 /// are kept for the next call, unless \ref resetParams() or \ref reset() 391 /// is used, thus only the modified parameters have to be set again. 392 /// If the underlying digraph was also modified after the construction 393 /// of the class (or the last \ref reset() call), then the \ref reset() 394 /// function must be called. 395 /// 396 /// \param method The cycle-canceling method that will be used. 397 /// For more information, see \ref Method. 398 /// 399 /// \return \c INFEASIBLE if no feasible flow exists, 400 /// \n \c OPTIMAL if the problem has optimal solution 401 /// (i.e. it is feasible and bounded), and the algorithm has found 402 /// optimal flow and node potentials (primal and dual solutions), 403 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 404 /// and infinite upper bound. It means that the objective function 405 /// is unbounded on that arc, however, note that it could actually be 406 /// bounded over the feasible flows, but this algroithm cannot handle 407 /// these cases. 408 /// 409 /// \see ProblemType, Method 410 /// \see resetParams(), reset() 411 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 412 ProblemType pt = init(); 413 if (pt != OPTIMAL) return pt; 414 start(method); 415 return OPTIMAL; 416 } 417 418 /// \brief Reset all the parameters that have been given before. 419 /// 420 /// This function resets all the paramaters that have been given 421 /// before using functions \ref lowerMap(), \ref upperMap(), 422 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 423 /// 424 /// It is useful for multiple \ref run() calls. Basically, all the given 425 /// parameters are kept for the next \ref run() call, unless 426 /// \ref resetParams() or \ref reset() is used. 427 /// If the underlying digraph was also modified after the construction 428 /// of the class or the last \ref reset() call, then the \ref reset() 429 /// function must be used, otherwise \ref resetParams() is sufficient. 430 /// 431 /// For example, 432 /// \code 433 /// CycleCanceling<ListDigraph> cs(graph); 434 /// 435 /// // First run 436 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 437 /// .supplyMap(sup).run(); 438 /// 439 /// // Run again with modified cost map (resetParams() is not called, 440 /// // so only the cost map have to be set again) 441 /// cost[e] += 100; 442 /// cc.costMap(cost).run(); 443 /// 444 /// // Run again from scratch using resetParams() 445 /// // (the lower bounds will be set to zero on all arcs) 446 /// cc.resetParams(); 447 /// cc.upperMap(capacity).costMap(cost) 448 /// .supplyMap(sup).run(); 449 /// \endcode 450 /// 451 /// \return <tt>(*this)</tt> 452 /// 453 /// \see reset(), run() 454 CycleCanceling& resetParams() { 455 for (int i = 0; i != _res_node_num; ++i) { 456 _supply[i] = 0; 457 } 458 int limit = _first_out[_root]; 459 for (int j = 0; j != limit; ++j) { 460 _lower[j] = 0; 461 _upper[j] = INF; 462 _cost[j] = _forward[j] ? 1 : -1; 463 } 464 for (int j = limit; j != _res_arc_num; ++j) { 465 _lower[j] = 0; 466 _upper[j] = INF; 467 _cost[j] = 0; 468 _cost[_reverse[j]] = 0; 469 } 470 _have_lower = false; 471 return *this; 472 } 473 474 /// \brief Reset the internal data structures and all the parameters 475 /// that have been given before. 476 /// 477 /// This function resets the internal data structures and all the 478 /// paramaters that have been given before using functions \ref lowerMap(), 479 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 480 /// 481 /// It is useful for multiple \ref run() calls. Basically, all the given 482 /// parameters are kept for the next \ref run() call, unless 483 /// \ref resetParams() or \ref reset() is used. 484 /// If the underlying digraph was also modified after the construction 485 /// of the class or the last \ref reset() call, then the \ref reset() 486 /// function must be used, otherwise \ref resetParams() is sufficient. 487 /// 488 /// See \ref resetParams() for examples. 489 /// 490 /// \return <tt>(*this)</tt> 491 /// 492 /// \see resetParams(), run() 493 CycleCanceling& reset() { 254 494 // Resize vectors 255 495 _node_num = countNodes(_graph); … … 317 557 318 558 // Reset parameters 319 reset(); 320 } 321 322 /// \name Parameters 323 /// The parameters of the algorithm can be specified using these 324 /// functions. 325 326 /// @{ 327 328 /// \brief Set the lower bounds on the arcs. 329 /// 330 /// This function sets the lower bounds on the arcs. 331 /// If it is not used before calling \ref run(), the lower bounds 332 /// will be set to zero on all arcs. 333 /// 334 /// \param map An arc map storing the lower bounds. 335 /// Its \c Value type must be convertible to the \c Value type 336 /// of the algorithm. 337 /// 338 /// \return <tt>(*this)</tt> 339 template <typename LowerMap> 340 CycleCanceling& lowerMap(const LowerMap& map) { 341 _have_lower = true; 342 for (ArcIt a(_graph); a != INVALID; ++a) { 343 _lower[_arc_idf[a]] = map[a]; 344 _lower[_arc_idb[a]] = map[a]; 345 } 346 return *this; 347 } 348 349 /// \brief Set the upper bounds (capacities) on the arcs. 350 /// 351 /// This function sets the upper bounds (capacities) on the arcs. 352 /// If it is not used before calling \ref run(), the upper bounds 353 /// will be set to \ref INF on all arcs (i.e. the flow value will be 354 /// unbounded from above). 355 /// 356 /// \param map An arc map storing the upper 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 UpperMap> 362 CycleCanceling& upperMap(const UpperMap& map) { 363 for (ArcIt a(_graph); a != INVALID; ++a) { 364 _upper[_arc_idf[a]] = map[a]; 365 } 366 return *this; 367 } 368 369 /// \brief Set the costs of the arcs. 370 /// 371 /// This function sets the costs of the arcs. 372 /// If it is not used before calling \ref run(), the costs 373 /// will be set to \c 1 on all arcs. 374 /// 375 /// \param map An arc map storing the costs. 376 /// Its \c Value type must be convertible to the \c Cost type 377 /// of the algorithm. 378 /// 379 /// \return <tt>(*this)</tt> 380 template<typename CostMap> 381 CycleCanceling& costMap(const CostMap& map) { 382 for (ArcIt a(_graph); a != INVALID; ++a) { 383 _cost[_arc_idf[a]] = map[a]; 384 _cost[_arc_idb[a]] = -map[a]; 385 } 386 return *this; 387 } 388 389 /// \brief Set the supply values of the nodes. 390 /// 391 /// This function sets the supply values of the nodes. 392 /// If neither this function nor \ref stSupply() is used before 393 /// calling \ref run(), the supply of each node will be set to zero. 394 /// 395 /// \param map A node map storing the supply values. 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 SupplyMap> 401 CycleCanceling& supplyMap(const SupplyMap& map) { 402 for (NodeIt n(_graph); n != INVALID; ++n) { 403 _supply[_node_id[n]] = map[n]; 404 } 405 return *this; 406 } 407 408 /// \brief Set single source and target nodes and a supply value. 409 /// 410 /// This function sets a single source node and a single target node 411 /// and the required flow value. 412 /// If neither this function nor \ref supplyMap() is used before 413 /// calling \ref run(), the supply of each node will be set to zero. 414 /// 415 /// Using this function has the same effect as using \ref supplyMap() 416 /// with such a map in which \c k is assigned to \c s, \c -k is 417 /// assigned to \c t and all other nodes have zero supply value. 418 /// 419 /// \param s The source node. 420 /// \param t The target node. 421 /// \param k The required amount of flow from node \c s to node \c t 422 /// (i.e. the supply of \c s and the demand of \c t). 423 /// 424 /// \return <tt>(*this)</tt> 425 CycleCanceling& stSupply(const Node& s, const Node& t, Value k) { 426 for (int i = 0; i != _res_node_num; ++i) { 427 _supply[i] = 0; 428 } 429 _supply[_node_id[s]] = k; 430 _supply[_node_id[t]] = -k; 431 return *this; 432 } 433 434 /// @} 435 436 /// \name Execution control 437 /// The algorithm can be executed using \ref run(). 438 439 /// @{ 440 441 /// \brief Run the algorithm. 442 /// 443 /// This function runs the algorithm. 444 /// The paramters can be specified using functions \ref lowerMap(), 445 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 446 /// For example, 447 /// \code 448 /// CycleCanceling<ListDigraph> cc(graph); 449 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 450 /// .supplyMap(sup).run(); 451 /// \endcode 452 /// 453 /// This function can be called more than once. All the parameters 454 /// that have been given are kept for the next call, unless 455 /// \ref reset() is called, thus only the modified parameters 456 /// have to be set again. See \ref reset() for examples. 457 /// However, the underlying digraph must not be modified after this 458 /// class have been constructed, since it copies and extends the graph. 459 /// 460 /// \param method The cycle-canceling method that will be used. 461 /// For more information, see \ref Method. 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, Method 474 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 475 ProblemType pt = init(); 476 if (pt != OPTIMAL) return pt; 477 start(method); 478 return OPTIMAL; 479 } 480 481 /// \brief Reset all the parameters that have been given before. 482 /// 483 /// This function resets all the paramaters that have been given 484 /// before using functions \ref lowerMap(), \ref upperMap(), 485 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 486 /// 487 /// It is useful for multiple run() calls. If this function is not 488 /// used, all the parameters given before are kept for the next 489 /// \ref run() call. 490 /// However, the underlying digraph must not be modified after this 491 /// class have been constructed, since it copies and extends the graph. 492 /// 493 /// For example, 494 /// \code 495 /// CycleCanceling<ListDigraph> cs(graph); 496 /// 497 /// // First run 498 /// cc.lowerMap(lower).upperMap(upper).costMap(cost) 499 /// .supplyMap(sup).run(); 500 /// 501 /// // Run again with modified cost map (reset() is not called, 502 /// // so only the cost map have to be set again) 503 /// cost[e] += 100; 504 /// cc.costMap(cost).run(); 505 /// 506 /// // Run again from scratch using reset() 507 /// // (the lower bounds will be set to zero on all arcs) 508 /// cc.reset(); 509 /// cc.upperMap(capacity).costMap(cost) 510 /// .supplyMap(sup).run(); 511 /// \endcode 512 /// 513 /// \return <tt>(*this)</tt> 514 CycleCanceling& reset() { 515 for (int i = 0; i != _res_node_num; ++i) { 516 _supply[i] = 0; 517 } 518 int limit = _first_out[_root]; 519 for (int j = 0; j != limit; ++j) { 520 _lower[j] = 0; 521 _upper[j] = INF; 522 _cost[j] = _forward[j] ? 1 : -1; 523 } 524 for (int j = limit; j != _res_arc_num; ++j) { 525 _lower[j] = 0; 526 _upper[j] = INF; 527 _cost[j] = 0; 528 _cost[_reverse[j]] = 0; 529 } 530 _have_lower = false; 559 resetParams(); 531 560 return *this; 532 561 } -
lemon/network_simplex.h
r830 r840 165 165 166 166 typedef std::vector<int> IntVector; 167 typedef std::vector<char> CharVector;168 167 typedef std::vector<Value> ValueVector; 169 168 typedef std::vector<Cost> CostVector; 169 typedef std::vector<char> BoolVector; 170 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 170 171 171 172 // State constants for arcs … … 214 215 IntVector _last_succ; 215 216 IntVector _dirty_revs; 216 CharVector _forward;217 CharVector _state;217 BoolVector _forward; 218 BoolVector _state; 218 219 int _root; 219 220 … … 246 247 const IntVector &_target; 247 248 const CostVector &_cost; 248 const CharVector &_state;249 const BoolVector &_state; 249 250 const CostVector &_pi; 250 251 int &_in_arc; … … 267 268 bool findEnteringArc() { 268 269 Cost c; 269 for (int e = _next_arc; e <_search_arc_num; ++e) {270 for (int e = _next_arc; e != _search_arc_num; ++e) { 270 271 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 271 272 if (c < 0) { … … 275 276 } 276 277 } 277 for (int e = 0; e <_next_arc; ++e) {278 for (int e = 0; e != _next_arc; ++e) { 278 279 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 279 280 if (c < 0) { … … 298 299 const IntVector &_target; 299 300 const CostVector &_cost; 300 const CharVector &_state;301 const BoolVector &_state; 301 302 const CostVector &_pi; 302 303 int &_in_arc; … … 315 316 bool findEnteringArc() { 316 317 Cost c, min = 0; 317 for (int e = 0; e <_search_arc_num; ++e) {318 for (int e = 0; e != _search_arc_num; ++e) { 318 319 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 319 320 if (c < min) { … … 337 338 const IntVector &_target; 338 339 const CostVector &_cost; 339 const CharVector &_state;340 const BoolVector &_state; 340 341 const CostVector &_pi; 341 342 int &_in_arc; … … 356 357 { 357 358 // The main parameters of the pivot rule 358 const double BLOCK_SIZE_FACTOR = 0.5;359 const double BLOCK_SIZE_FACTOR = 1.0; 359 360 const int MIN_BLOCK_SIZE = 10; 360 361 … … 369 370 int cnt = _block_size; 370 371 int e; 371 for (e = _next_arc; e <_search_arc_num; ++e) {372 for (e = _next_arc; e != _search_arc_num; ++e) { 372 373 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 373 374 if (c < min) { … … 380 381 } 381 382 } 382 for (e = 0; e <_next_arc; ++e) {383 for (e = 0; e != _next_arc; ++e) { 383 384 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 384 385 if (c < min) { … … 410 411 const IntVector &_target; 411 412 const CostVector &_cost; 412 const CharVector &_state;413 const BoolVector &_state; 413 414 const CostVector &_pi; 414 415 int &_in_arc; … … 471 472 min = 0; 472 473 _curr_length = 0; 473 for (e = _next_arc; e <_search_arc_num; ++e) {474 for (e = _next_arc; e != _search_arc_num; ++e) { 474 475 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 475 476 if (c < 0) { … … 482 483 } 483 484 } 484 for (e = 0; e <_next_arc; ++e) {485 for (e = 0; e != _next_arc; ++e) { 485 486 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 486 487 if (c < 0) { … … 513 514 const IntVector &_target; 514 515 const CostVector &_cost; 515 const CharVector &_state;516 const BoolVector &_state; 516 517 const CostVector &_pi; 517 518 int &_in_arc; … … 566 567 // Check the current candidate list 567 568 int e; 568 for (int i = 0; i <_curr_length; ++i) {569 for (int i = 0; i != _curr_length; ++i) { 569 570 e = _candidates[i]; 570 571 _cand_cost[e] = _state[e] * … … 579 580 int limit = _head_length; 580 581 581 for (e = _next_arc; e <_search_arc_num; ++e) {582 for (e = _next_arc; e != _search_arc_num; ++e) { 582 583 _cand_cost[e] = _state[e] * 583 584 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 591 592 } 592 593 } 593 for (e = 0; e <_next_arc; ++e) {594 for (e = 0; e != _next_arc; ++e) { 594 595 _cand_cost[e] = _state[e] * 595 596 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 1361 1362 1362 1363 // Update _rev_thread using the new _thread values 1363 for (int i = 0; i <int(_dirty_revs.size()); ++i) {1364 for (int i = 0; i != int(_dirty_revs.size()); ++i) { 1364 1365 u = _dirty_revs[i]; 1365 1366 _rev_thread[_thread[u]] = u; … … 1431 1432 _pi[u] += sigma; 1432 1433 } 1434 } 1435 1436 // Heuristic initial pivots 1437 bool initialPivots() { 1438 Value curr, total = 0; 1439 std::vector<Node> supply_nodes, demand_nodes; 1440 for (NodeIt u(_graph); u != INVALID; ++u) { 1441 curr = _supply[_node_id[u]]; 1442 if (curr > 0) { 1443 total += curr; 1444 supply_nodes.push_back(u); 1445 } 1446 else if (curr < 0) { 1447 demand_nodes.push_back(u); 1448 } 1449 } 1450 if (_sum_supply > 0) total -= _sum_supply; 1451 if (total <= 0) return true; 1452 1453 IntVector arc_vector; 1454 if (_sum_supply >= 0) { 1455 if (supply_nodes.size() == 1 && demand_nodes.size() == 1) { 1456 // Perform a reverse graph search from the sink to the source 1457 typename GR::template NodeMap<bool> reached(_graph, false); 1458 Node s = supply_nodes[0], t = demand_nodes[0]; 1459 std::vector<Node> stack; 1460 reached[t] = true; 1461 stack.push_back(t); 1462 while (!stack.empty()) { 1463 Node u, v = stack.back(); 1464 stack.pop_back(); 1465 if (v == s) break; 1466 for (InArcIt a(_graph, v); a != INVALID; ++a) { 1467 if (reached[u = _graph.source(a)]) continue; 1468 int j = _arc_id[a]; 1469 if (_cap[j] >= total) { 1470 arc_vector.push_back(j); 1471 reached[u] = true; 1472 stack.push_back(u); 1473 } 1474 } 1475 } 1476 } else { 1477 // Find the min. cost incomming arc for each demand node 1478 for (int i = 0; i != int(demand_nodes.size()); ++i) { 1479 Node v = demand_nodes[i]; 1480 Cost c, min_cost = std::numeric_limits<Cost>::max(); 1481 Arc min_arc = INVALID; 1482 for (InArcIt a(_graph, v); a != INVALID; ++a) { 1483 c = _cost[_arc_id[a]]; 1484 if (c < min_cost) { 1485 min_cost = c; 1486 min_arc = a; 1487 } 1488 } 1489 if (min_arc != INVALID) { 1490 arc_vector.push_back(_arc_id[min_arc]); 1491 } 1492 } 1493 } 1494 } else { 1495 // Find the min. cost outgoing arc for each supply node 1496 for (int i = 0; i != int(supply_nodes.size()); ++i) { 1497 Node u = supply_nodes[i]; 1498 Cost c, min_cost = std::numeric_limits<Cost>::max(); 1499 Arc min_arc = INVALID; 1500 for (OutArcIt a(_graph, u); a != INVALID; ++a) { 1501 c = _cost[_arc_id[a]]; 1502 if (c < min_cost) { 1503 min_cost = c; 1504 min_arc = a; 1505 } 1506 } 1507 if (min_arc != INVALID) { 1508 arc_vector.push_back(_arc_id[min_arc]); 1509 } 1510 } 1511 } 1512 1513 // Perform heuristic initial pivots 1514 for (int i = 0; i != int(arc_vector.size()); ++i) { 1515 in_arc = arc_vector[i]; 1516 if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] - 1517 _pi[_target[in_arc]]) >= 0) continue; 1518 findJoinNode(); 1519 bool change = findLeavingArc(); 1520 if (delta >= MAX) return false; 1521 changeFlow(change); 1522 if (change) { 1523 updateTreeStructure(); 1524 updatePotential(); 1525 } 1526 } 1527 return true; 1433 1528 } 1434 1529 … … 1455 1550 PivotRuleImpl pivot(*this); 1456 1551 1552 // Perform heuristic initial pivots 1553 if (!initialPivots()) return UNBOUNDED; 1554 1457 1555 // Execute the Network Simplex algorithm 1458 1556 while (pivot.findEnteringArc()) { -
lemon/network_simplex.h
r839 r840 196 196 IntVector _source; 197 197 IntVector _target; 198 bool _arc_mixing; 198 199 199 200 // Node and arc data … … 635 636 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 636 637 _graph(graph), _node_id(graph), _arc_id(graph), 638 _arc_mixing(arc_mixing), 637 639 MAX(std::numeric_limits<Value>::max()), 638 640 INF(std::numeric_limits<Value>::has_infinity ? … … 645 647 "The cost type of NetworkSimplex must be signed"); 646 648 647 // Resize vectors 648 _node_num = countNodes(_graph); 649 _arc_num = countArcs(_graph); 650 int all_node_num = _node_num + 1; 651 int max_arc_num = _arc_num + 2 * _node_num; 652 653 _source.resize(max_arc_num); 654 _target.resize(max_arc_num); 655 656 _lower.resize(_arc_num); 657 _upper.resize(_arc_num); 658 _cap.resize(max_arc_num); 659 _cost.resize(max_arc_num); 660 _supply.resize(all_node_num); 661 _flow.resize(max_arc_num); 662 _pi.resize(all_node_num); 663 664 _parent.resize(all_node_num); 665 _pred.resize(all_node_num); 666 _forward.resize(all_node_num); 667 _thread.resize(all_node_num); 668 _rev_thread.resize(all_node_num); 669 _succ_num.resize(all_node_num); 670 _last_succ.resize(all_node_num); 671 _state.resize(max_arc_num); 672 673 // Copy the graph 674 int i = 0; 675 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 676 _node_id[n] = i; 677 } 678 if (arc_mixing) { 679 // Store the arcs in a mixed order 680 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 681 int i = 0, j = 0; 682 for (ArcIt a(_graph); a != INVALID; ++a) { 683 _arc_id[a] = i; 684 _source[i] = _node_id[_graph.source(a)]; 685 _target[i] = _node_id[_graph.target(a)]; 686 if ((i += k) >= _arc_num) i = ++j; 687 } 688 } else { 689 // Store the arcs in the original order 690 int i = 0; 691 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 692 _arc_id[a] = i; 693 _source[i] = _node_id[_graph.source(a)]; 694 _target[i] = _node_id[_graph.target(a)]; 695 } 696 } 697 698 // Reset parameters 649 // Reset data structures 699 650 reset(); 700 651 } … … 844 795 /// \endcode 845 796 /// 846 /// This function can be called more than once. All the parameters847 /// that have been given are kept for the next call, unless848 /// \ref reset() is called, thus only the modified parameters849 /// have to be set again. See \ref reset() for examples.850 /// However, the underlying digraph must not be modified after this851 /// class have been constructed, since it copies and extends the graph.797 /// This function can be called more than once. All the given parameters 798 /// are kept for the next call, unless \ref resetParams() or \ref reset() 799 /// is used, thus only the modified parameters have to be set again. 800 /// If the underlying digraph was also modified after the construction 801 /// of the class (or the last \ref reset() call), then the \ref reset() 802 /// function must be called. 852 803 /// 853 804 /// \param pivot_rule The pivot rule that will be used during the … … 863 814 /// 864 815 /// \see ProblemType, PivotRule 816 /// \see resetParams(), reset() 865 817 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 866 818 if (!init()) return INFEASIBLE; … … 874 826 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 875 827 /// 876 /// It is useful for multiple run() calls. If this function is not 877 /// used, all the parameters given before are kept for the next 878 /// \ref run() call. 879 /// However, the underlying digraph must not be modified after this 880 /// class have been constructed, since it copies and extends the graph. 828 /// It is useful for multiple \ref run() calls. Basically, all the given 829 /// parameters are kept for the next \ref run() call, unless 830 /// \ref resetParams() or \ref reset() is used. 831 /// If the underlying digraph was also modified after the construction 832 /// of the class or the last \ref reset() call, then the \ref reset() 833 /// function must be used, otherwise \ref resetParams() is sufficient. 881 834 /// 882 835 /// For example, … … 888 841 /// .supplyMap(sup).run(); 889 842 /// 890 /// // Run again with modified cost map (reset () is not called,843 /// // Run again with modified cost map (resetParams() is not called, 891 844 /// // so only the cost map have to be set again) 892 845 /// cost[e] += 100; 893 846 /// ns.costMap(cost).run(); 894 847 /// 895 /// // Run again from scratch using reset ()848 /// // Run again from scratch using resetParams() 896 849 /// // (the lower bounds will be set to zero on all arcs) 897 /// ns.reset ();850 /// ns.resetParams(); 898 851 /// ns.upperMap(capacity).costMap(cost) 899 852 /// .supplyMap(sup).run(); … … 901 854 /// 902 855 /// \return <tt>(*this)</tt> 903 NetworkSimplex& reset() { 856 /// 857 /// \see reset(), run() 858 NetworkSimplex& resetParams() { 904 859 for (int i = 0; i != _node_num; ++i) { 905 860 _supply[i] = 0; … … 915 870 } 916 871 872 /// \brief Reset the internal data structures and all the parameters 873 /// that have been given before. 874 /// 875 /// This function resets the internal data structures and all the 876 /// paramaters that have been given before using functions \ref lowerMap(), 877 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 878 /// \ref supplyType(). 879 /// 880 /// It is useful for multiple \ref run() calls. Basically, all the given 881 /// parameters are kept for the next \ref run() call, unless 882 /// \ref resetParams() or \ref reset() is used. 883 /// If the underlying digraph was also modified after the construction 884 /// of the class or the last \ref reset() call, then the \ref reset() 885 /// function must be used, otherwise \ref resetParams() is sufficient. 886 /// 887 /// See \ref resetParams() for examples. 888 /// 889 /// \return <tt>(*this)</tt> 890 /// 891 /// \see resetParams(), run() 892 NetworkSimplex& reset() { 893 // Resize vectors 894 _node_num = countNodes(_graph); 895 _arc_num = countArcs(_graph); 896 int all_node_num = _node_num + 1; 897 int max_arc_num = _arc_num + 2 * _node_num; 898 899 _source.resize(max_arc_num); 900 _target.resize(max_arc_num); 901 902 _lower.resize(_arc_num); 903 _upper.resize(_arc_num); 904 _cap.resize(max_arc_num); 905 _cost.resize(max_arc_num); 906 _supply.resize(all_node_num); 907 _flow.resize(max_arc_num); 908 _pi.resize(all_node_num); 909 910 _parent.resize(all_node_num); 911 _pred.resize(all_node_num); 912 _forward.resize(all_node_num); 913 _thread.resize(all_node_num); 914 _rev_thread.resize(all_node_num); 915 _succ_num.resize(all_node_num); 916 _last_succ.resize(all_node_num); 917 _state.resize(max_arc_num); 918 919 // Copy the graph 920 int i = 0; 921 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 922 _node_id[n] = i; 923 } 924 if (_arc_mixing) { 925 // Store the arcs in a mixed order 926 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 927 int i = 0, j = 0; 928 for (ArcIt a(_graph); a != INVALID; ++a) { 929 _arc_id[a] = i; 930 _source[i] = _node_id[_graph.source(a)]; 931 _target[i] = _node_id[_graph.target(a)]; 932 if ((i += k) >= _arc_num) i = ++j; 933 } 934 } else { 935 // Store the arcs in the original order 936 int i = 0; 937 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 938 _arc_id[a] = i; 939 _source[i] = _node_id[_graph.source(a)]; 940 _target[i] = _node_id[_graph.target(a)]; 941 } 942 } 943 944 // Reset parameters 945 resetParams(); 946 return *this; 947 } 948 917 949 /// @} 918 950
Note: See TracChangeset
for help on using the changeset viewer.