Changeset 811:fe80a8145653 in lemon-main for lemon/capacity_scaling.h
- Timestamp:
- 11/12/09 23:45:15 (14 years ago)
- Branch:
- default
- Phase:
- public
- Rebase:
- 35386664633435303433383038316635626132313231366463363862653565653936303733646463
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r810 r811 134 134 135 135 typedef std::vector<int> IntVector; 136 typedef std::vector< bool> BoolVector;136 typedef std::vector<char> BoolVector; 137 137 typedef std::vector<Value> ValueVector; 138 138 typedef std::vector<Cost> CostVector; … … 197 197 198 198 int _node_num; 199 bool _geq; 199 200 const IntVector &_first_out; 200 201 const IntVector &_target; … … 211 212 212 213 ResidualDijkstra(CapacityScaling& cs) : 213 _node_num(cs._node_num), _ first_out(cs._first_out),214 _ target(cs._target), _cost(cs._cost), _res_cap(cs._res_cap),215 _ excess(cs._excess), _pi(cs._pi), _pred(cs._pred),216 _ dist(cs._node_num)214 _node_num(cs._node_num), _geq(cs._sum_supply < 0), 215 _first_out(cs._first_out), _target(cs._target), _cost(cs._cost), 216 _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi), 217 _pred(cs._pred), _dist(cs._node_num) 217 218 {} 218 219 … … 233 234 234 235 // Traverse outgoing residual arcs 235 for (int a = _first_out[u]; a != _first_out[u+1]; ++a) { 236 int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1; 237 for (int a = _first_out[u]; a != last_out; ++a) { 236 238 if (_res_cap[a] < delta) continue; 237 239 v = _target[a]; … … 688 690 if (_sum_supply > 0) return INFEASIBLE; 689 691 690 // Initialize maps692 // Initialize vectors 691 693 for (int i = 0; i != _root; ++i) { 692 694 _pi[i] = 0; … … 695 697 696 698 // Remove non-zero lower bounds 699 const Value MAX = std::numeric_limits<Value>::max(); 700 int last_out; 697 701 if (_have_lower) { 698 702 for (int i = 0; i != _root; ++i) { 699 for (int j = _first_out[i]; j != _first_out[i+1]; ++j) { 703 last_out = _first_out[i+1]; 704 for (int j = _first_out[i]; j != last_out; ++j) { 700 705 if (_forward[j]) { 701 706 Value c = _lower[j]; 702 707 if (c >= 0) { 703 _res_cap[j] = _upper[j] < INF? _upper[j] - c : INF;708 _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF; 704 709 } else { 705 _res_cap[j] = _upper[j] < INF+ c ? _upper[j] - c : INF;710 _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF; 706 711 } 707 712 _excess[i] -= c; … … 719 724 720 725 // Handle negative costs 721 for (int u = 0; u != _root; ++u) { 722 for (int a = _first_out[u]; a != _first_out[u+1]; ++a) { 723 Value rc = _res_cap[a]; 724 if (_cost[a] < 0 && rc > 0) { 725 if (rc == INF) return UNBOUNDED; 726 _excess[u] -= rc; 727 _excess[_target[a]] += rc; 728 _res_cap[a] = 0; 729 _res_cap[_reverse[a]] += rc; 726 for (int i = 0; i != _root; ++i) { 727 last_out = _first_out[i+1] - 1; 728 for (int j = _first_out[i]; j != last_out; ++j) { 729 Value rc = _res_cap[j]; 730 if (_cost[j] < 0 && rc > 0) { 731 if (rc >= MAX) return UNBOUNDED; 732 _excess[i] -= rc; 733 _excess[_target[j]] += rc; 734 _res_cap[j] = 0; 735 _res_cap[_reverse[j]] += rc; 730 736 } 731 737 } … … 737 743 _excess[_root] = -_sum_supply; 738 744 for (int a = _first_out[_root]; a != _res_arc_num; ++a) { 739 int u = _target[a]; 740 if (_excess[u] < 0) { 741 _res_cap[a] = -_excess[u] + 1; 742 } else { 743 _res_cap[a] = 1; 744 } 745 _res_cap[_reverse[a]] = 0; 745 int ra = _reverse[a]; 746 _res_cap[a] = -_sum_supply + 1; 747 _res_cap[ra] = 0; 746 748 _cost[a] = 0; 747 _cost[ _reverse[a]] = 0;749 _cost[ra] = 0; 748 750 } 749 751 } else { … … 751 753 _excess[_root] = 0; 752 754 for (int a = _first_out[_root]; a != _res_arc_num; ++a) { 755 int ra = _reverse[a]; 753 756 _res_cap[a] = 1; 754 _res_cap[ _reverse[a]] = 0;757 _res_cap[ra] = 0; 755 758 _cost[a] = 0; 756 _cost[ _reverse[a]] = 0;759 _cost[ra] = 0; 757 760 } 758 761 } … … 763 766 Value max_sup = 0, max_dem = 0; 764 767 for (int i = 0; i != _node_num; ++i) { 765 if ( _excess[i] > max_sup) max_sup = _excess[i]; 766 if (-_excess[i] > max_dem) max_dem = -_excess[i]; 768 Value ex = _excess[i]; 769 if ( ex > max_sup) max_sup = ex; 770 if (-ex > max_dem) max_dem = -ex; 767 771 } 768 772 Value max_cap = 0; … … 790 794 // Handle non-zero lower bounds 791 795 if (_have_lower) { 792 for (int j = 0; j != _res_arc_num - _node_num + 1; ++j) { 796 int limit = _first_out[_root]; 797 for (int j = 0; j != limit; ++j) { 793 798 if (!_forward[j]) _res_cap[j] += _lower[j]; 794 799 } … … 813 818 while (true) { 814 819 // Saturate all arcs not satisfying the optimality condition 820 int last_out; 815 821 for (int u = 0; u != _node_num; ++u) { 816 for (int a = _first_out[u]; a != _first_out[u+1]; ++a) { 822 last_out = _sum_supply < 0 ? 823 _first_out[u+1] : _first_out[u+1] - 1; 824 for (int a = _first_out[u]; a != last_out; ++a) { 817 825 int v = _target[a]; 818 826 Cost c = _cost[a] + _pi[u] - _pi[v]; … … 831 839 _deficit_nodes.clear(); 832 840 for (int u = 0; u != _node_num; ++u) { 833 if (_excess[u] >= _delta) _excess_nodes.push_back(u); 834 if (_excess[u] <= -_delta) _deficit_nodes.push_back(u); 841 Value ex = _excess[u]; 842 if (ex >= _delta) _excess_nodes.push_back(u); 843 if (ex <= -_delta) _deficit_nodes.push_back(u); 835 844 } 836 845 int next_node = 0, next_def_node = 0;
Note: See TracChangeset
for help on using the changeset viewer.