Changeset 1363:a7d841273c68 in lemon
 Timestamp:
 10/08/15 10:03:29 (9 years ago)
 Branch:
 1.3
 Parents:
 1358:48a0d237db3c (diff), 1362:43647f48e971 (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
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/capacity_scaling.h
r1298 r1363 28 28 #include <limits> 29 29 #include <lemon/core.h> 30 #include <lemon/maps.h> 30 31 #include <lemon/bin_heap.h> 31 32 
lemon/capacity_scaling.h
r1362 r1363 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 085 * Copyright (C) 20032013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 68 68 /// \ref CapacityScaling implements the capacity scaling version 69 69 /// of the successive shortest path algorithm for finding a 70 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, 71 /// \ref edmondskarp72theoretical. It is an efficient dual 72 /// solution method. 70 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, 71 /// \cite edmondskarp72theoretical. It is an efficient dual 72 /// solution method, which runs in polynomial time 73 /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum 74 /// of node supply and arc capacity values. 75 /// 76 /// This algorithm is typically slower than \ref CostScaling and 77 /// \ref NetworkSimplex, but in special cases, it can be more 78 /// efficient than them. 79 /// (For more information, see \ref min_cost_flow_algs "the module page".) 73 80 /// 74 81 /// Most of the parameters of the problem (except for the digraph) … … 79 86 /// \tparam GR The digraph type the algorithm runs on. 80 87 /// \tparam V The number type used for flow amounts, capacity bounds 81 /// and supply values in the algorithm. By default it is \c int.88 /// and supply values in the algorithm. By default, it is \c int. 82 89 /// \tparam C The number type used for costs and potentials in the 83 /// algorithm. By default it is the same as \c V. 90 /// algorithm. By default, it is the same as \c V. 91 /// \tparam TR The traits class that defines various types used by the 92 /// algorithm. By default, it is \ref CapacityScalingDefaultTraits 93 /// "CapacityScalingDefaultTraits<GR, V, C>". 94 /// In most cases, this parameter should not be set directly, 95 /// consider to use the named template parameters instead. 84 96 /// 85 /// \warning Both number types must be signed and all input data must 86 /// be integer. 87 /// \warning This algorithm does not support negative costs for such 88 /// arcs that have infinite upper bound. 97 /// \warning Both \c V and \c C must be signed number types. 98 /// \warning Capacity bounds and supply values must be integer, but 99 /// arc costs can be arbitrary real numbers. 100 /// \warning This algorithm does not support negative costs for 101 /// arcs having infinite upper bound. 89 102 #ifdef DOXYGEN 90 103 template <typename GR, typename V, typename C, typename TR> … … 107 120 typedef typename TR::Heap Heap; 108 121 109 /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm 122 /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class" 123 /// of the algorithm 110 124 typedef TR Traits; 111 125 … … 130 144 UNBOUNDED 131 145 }; 132 146 133 147 private: 134 148 … … 136 150 137 151 typedef std::vector<int> IntVector; 138 typedef std::vector<char> BoolVector;139 152 typedef std::vector<Value> ValueVector; 140 153 typedef std::vector<Cost> CostVector; 154 typedef std::vector<char> BoolVector; 155 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 141 156 142 157 private: … … 150 165 151 166 // Parameters of the problem 152 bool _ha ve_lower;167 bool _has_lower; 153 168 Value _sum_supply; 154 169 … … 180 195 181 196 public: 182 197 183 198 /// \brief Constant for infinite upper bounds (capacities). 184 199 /// … … 207 222 CostVector &_pi; 208 223 IntVector &_pred; 209 224 210 225 IntVector _proc_nodes; 211 226 CostVector _dist; 212 227 213 228 public: 214 229 … … 297 312 /// @} 298 313 314 protected: 315 316 CapacityScaling() {} 317 299 318 public: 300 319 … … 316 335 "The cost type of CapacityScaling must be signed"); 317 336 337 // Reset data structures 338 reset(); 339 } 340 341 /// \name Parameters 342 /// The parameters of the algorithm can be specified using these 343 /// functions. 344 345 /// @{ 346 347 /// \brief Set the lower bounds on the arcs. 348 /// 349 /// This function sets the lower bounds on the arcs. 350 /// If it is not used before calling \ref run(), the lower bounds 351 /// will be set to zero on all arcs. 352 /// 353 /// \param map An arc map storing the lower bounds. 354 /// Its \c Value type must be convertible to the \c Value type 355 /// of the algorithm. 356 /// 357 /// \return <tt>(*this)</tt> 358 template <typename LowerMap> 359 CapacityScaling& lowerMap(const LowerMap& map) { 360 _has_lower = true; 361 for (ArcIt a(_graph); a != INVALID; ++a) { 362 _lower[_arc_idf[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 CapacityScaling& 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 CapacityScaling& costMap(const CostMap& map) { 400 for (ArcIt a(_graph); a != INVALID; ++a) { 401 _cost[_arc_idf[a]] = map[a]; 402 _cost[_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 CapacityScaling& 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 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 CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { 444 for (int i = 0; i != _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 /// CapacityScaling<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 factor The capacity scaling factor. It must be larger than 479 /// one to use scaling. If it is less or equal to one, then scaling 480 /// will be disabled. 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 493 /// \see resetParams(), reset() 494 ProblemType run(int factor = 4) { 495 _factor = factor; 496 ProblemType pt = init(); 497 if (pt != OPTIMAL) return pt; 498 return start(); 499 } 500 501 /// \brief Reset all the parameters that have been given before. 502 /// 503 /// This function resets all the paramaters that have been given 504 /// before using functions \ref lowerMap(), \ref upperMap(), 505 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 506 /// 507 /// It is useful for multiple \ref run() calls. Basically, all the given 508 /// parameters are kept for the next \ref run() call, unless 509 /// \ref resetParams() or \ref reset() is used. 510 /// If the underlying digraph was also modified after the construction 511 /// of the class or the last \ref reset() call, then the \ref reset() 512 /// function must be used, otherwise \ref resetParams() is sufficient. 513 /// 514 /// For example, 515 /// \code 516 /// CapacityScaling<ListDigraph> cs(graph); 517 /// 518 /// // First run 519 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 520 /// .supplyMap(sup).run(); 521 /// 522 /// // Run again with modified cost map (resetParams() is not called, 523 /// // so only the cost map have to be set again) 524 /// cost[e] += 100; 525 /// cs.costMap(cost).run(); 526 /// 527 /// // Run again from scratch using resetParams() 528 /// // (the lower bounds will be set to zero on all arcs) 529 /// cs.resetParams(); 530 /// cs.upperMap(capacity).costMap(cost) 531 /// .supplyMap(sup).run(); 532 /// \endcode 533 /// 534 /// \return <tt>(*this)</tt> 535 /// 536 /// \see reset(), run() 537 CapacityScaling& resetParams() { 538 for (int i = 0; i != _node_num; ++i) { 539 _supply[i] = 0; 540 } 541 for (int j = 0; j != _res_arc_num; ++j) { 542 _lower[j] = 0; 543 _upper[j] = INF; 544 _cost[j] = _forward[j] ? 1 : 1; 545 } 546 _has_lower = false; 547 return *this; 548 } 549 550 /// \brief Reset the internal data structures and all the parameters 551 /// that have been given before. 552 /// 553 /// This function resets the internal data structures and all the 554 /// paramaters that have been given before using functions \ref lowerMap(), 555 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 556 /// 557 /// It is useful for multiple \ref run() calls. Basically, all the given 558 /// parameters are kept for the next \ref run() call, unless 559 /// \ref resetParams() or \ref reset() is used. 560 /// If the underlying digraph was also modified after the construction 561 /// of the class or the last \ref reset() call, then the \ref reset() 562 /// function must be used, otherwise \ref resetParams() is sufficient. 563 /// 564 /// See \ref resetParams() for examples. 565 /// 566 /// \return <tt>(*this)</tt> 567 /// 568 /// \see resetParams(), run() 569 CapacityScaling& reset() { 318 570 // Resize vectors 319 571 _node_num = countNodes(_graph); … … 333 585 _cost.resize(_res_arc_num); 334 586 _supply.resize(_node_num); 335 587 336 588 _res_cap.resize(_res_arc_num); 337 589 _pi.resize(_node_num); … … 377 629 _reverse[bi] = fi; 378 630 } 379 631 380 632 // 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; 633 resetParams(); 587 634 return *this; 588 635 } … … 600 647 /// 601 648 /// This function returns the total cost of the found flow. 602 /// Its complexity is O( e).649 /// Its complexity is O(m). 603 650 /// 604 651 /// \note The return type of the function can be specified as a … … 638 685 } 639 686 640 /// \brief Return the flow map (the primal solution). 687 /// \brief Copy the flow values (the primal solution) into the 688 /// given map. 641 689 /// 642 690 /// This function copies the flow value on each arc into the given … … 662 710 } 663 711 664 /// \brief Return the potential map (the dual solution). 712 /// \brief Copy the potential values (the dual solution) into the 713 /// given map. 665 714 /// 666 715 /// This function copies the potential (dual value) of each node … … 691 740 } 692 741 if (_sum_supply > 0) return INFEASIBLE; 693 742 743 // Check lower and upper bounds 744 LEMON_DEBUG(checkBoundMaps(), 745 "Upper bounds must be greater or equal to the lower bounds"); 746 747 694 748 // Initialize vectors 695 749 for (int i = 0; i != _root; ++i) { … … 701 755 const Value MAX = std::numeric_limits<Value>::max(); 702 756 int last_out; 703 if (_ha ve_lower) {757 if (_has_lower) { 704 758 for (int i = 0; i != _root; ++i) { 705 759 last_out = _first_out[i+1]; … … 739 793 } 740 794 } 741 795 742 796 // Handle GEQ supply type 743 797 if (_sum_supply < 0) { … … 766 820 if (_factor > 1) { 767 821 // With scaling 768 Value max_sup = 0, max_dem = 0 ;769 for (int i = 0; i != _ node_num; ++i) {822 Value max_sup = 0, max_dem = 0, max_cap = 0; 823 for (int i = 0; i != _root; ++i) { 770 824 Value ex = _excess[i]; 771 825 if ( ex > max_sup) max_sup = ex; 772 826 if (ex > max_dem) max_dem = ex; 773 }774 Value max_cap = 0;775 for (int j = 0; j != _res_arc_num; ++j) {776 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];827 int last_out = _first_out[i+1]  1; 828 for (int j = _first_out[i]; j != last_out; ++j) { 829 if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; 830 } 777 831 } 778 832 max_sup = std::min(std::min(max_sup, max_dem), max_cap); … … 784 838 785 839 return OPTIMAL; 840 } 841 842 // Check if the upper bound is greater than or equal to the lower bound 843 // on each forward arc. 844 bool checkBoundMaps() { 845 for (int j = 0; j != _res_arc_num; ++j) { 846 if (_forward[j] && _upper[j] < _lower[j]) return false; 847 } 848 return true; 786 849 } 787 850 … … 795 858 796 859 // Handle nonzero lower bounds 797 if (_ha ve_lower) {860 if (_has_lower) { 798 861 int limit = _first_out[_root]; 799 862 for (int j = 0; j != limit; ++j) { 800 if ( !_forward[j]) _res_cap[j] += _lower[j];863 if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; 801 864 } 802 865 } … … 807 870 for (int i = 0; i != _node_num; ++i) { 808 871 _pi[i] = pr; 809 } 810 } 811 872 } 873 } 874 812 875 return pt; 813 876 }
Note: See TracChangeset
for help on using the changeset viewer.