equal
deleted
inserted
replaced
137 private: |
137 private: |
138 |
138 |
139 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
139 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
140 |
140 |
141 typedef std::vector<int> IntVector; |
141 typedef std::vector<int> IntVector; |
142 typedef std::vector<char> BoolVector; |
|
143 typedef std::vector<Value> ValueVector; |
142 typedef std::vector<Value> ValueVector; |
144 typedef std::vector<Cost> CostVector; |
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 private: |
147 private: |
147 |
148 |
148 // Data related to the underlying digraph |
149 // Data related to the underlying digraph |
149 const GR &_graph; |
150 const GR &_graph; |
796 } |
797 } |
797 |
798 |
798 // Initialize delta value |
799 // Initialize delta value |
799 if (_factor > 1) { |
800 if (_factor > 1) { |
800 // With scaling |
801 // With scaling |
801 Value max_sup = 0, max_dem = 0; |
802 Value max_sup = 0, max_dem = 0, max_cap = 0; |
802 for (int i = 0; i != _node_num; ++i) { |
803 for (int i = 0; i != _root; ++i) { |
803 Value ex = _excess[i]; |
804 Value ex = _excess[i]; |
804 if ( ex > max_sup) max_sup = ex; |
805 if ( ex > max_sup) max_sup = ex; |
805 if (-ex > max_dem) max_dem = -ex; |
806 if (-ex > max_dem) max_dem = -ex; |
806 } |
807 int last_out = _first_out[i+1] - 1; |
807 Value max_cap = 0; |
808 for (int j = _first_out[i]; j != last_out; ++j) { |
808 for (int j = 0; j != _res_arc_num; ++j) { |
809 if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; |
809 if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; |
810 } |
810 } |
811 } |
811 max_sup = std::min(std::min(max_sup, max_dem), max_cap); |
812 max_sup = std::min(std::min(max_sup, max_dem), max_cap); |
812 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ; |
813 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ; |
813 } else { |
814 } else { |
814 // Without scaling |
815 // Without scaling |