Changeset 876:3b53491bf643 in lemon for lemon/capacity_scaling.h
- Timestamp:
- 11/12/09 23:34:35 (14 years ago)
- Branch:
- default
- Phase:
- public
- Rebase:
- 31306464373530663736663634663865303635326136663934636335303533383063623764626530
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r873 r876 174 174 175 175 Value _delta; 176 int _ phase_num;176 int _factor; 177 177 IntVector _pred; 178 178 … … 514 514 /// have to be set again. See \ref reset() for examples. 515 515 /// However the underlying digraph must not be modified after this 516 /// class have been constructed, since it copies the digraph. 517 /// 518 /// \param scaling Enable or disable capacity scaling. 519 /// If the maximum upper bound and/or the amount of total supply 520 /// is rather small, the algorithm could be slightly faster without 521 /// scaling. 516 /// class have been constructed, since it copies and extends the graph. 517 /// 518 /// \param factor The capacity scaling factor. It must be larger than 519 /// one to use scaling. If it is less or equal to one, then scaling 520 /// will be disabled. 522 521 /// 523 522 /// \return \c INFEASIBLE if no feasible flow exists, … … 532 531 /// 533 532 /// \see ProblemType 534 ProblemType run(bool scaling = true) { 535 ProblemType pt = init(scaling); 533 ProblemType run(int factor = 4) { 534 _factor = factor; 535 ProblemType pt = init(); 536 536 if (pt != OPTIMAL) return pt; 537 537 return start(); … … 547 547 /// used, all the parameters given before are kept for the next 548 548 /// \ref run() call. 549 /// However the underlying digraph must not be modified after this549 /// However, the underlying digraph must not be modified after this 550 550 /// class have been constructed, since it copies and extends the graph. 551 551 /// … … 678 678 679 679 // Initialize the algorithm 680 ProblemType init( bool scaling) {680 ProblemType init() { 681 681 if (_node_num == 0) return INFEASIBLE; 682 682 … … 759 759 760 760 // Initialize delta value 761 if ( scaling) {761 if (_factor > 1) { 762 762 // With scaling 763 763 Value max_sup = 0, max_dem = 0; … … 771 771 } 772 772 max_sup = std::min(std::min(max_sup, max_dem), max_cap); 773 _phase_num = 0; 774 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) 775 ++_phase_num; 773 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ; 776 774 } else { 777 775 // Without scaling … … 812 810 // Perform capacity scaling phases 813 811 int s, t; 814 int phase_cnt = 0;815 int factor = 4;816 812 ResidualDijkstra _dijkstra(*this); 817 813 while (true) { … … 888 884 889 885 if (_delta == 1) break; 890 if (++phase_cnt == _phase_num / 4) factor = 2; 891 _delta = _delta <= factor ? 1 : _delta / factor; 886 _delta = _delta <= _factor ? 1 : _delta / _factor; 892 887 } 893 888
Note: See TracChangeset
for help on using the changeset viewer.