equal
deleted
inserted
replaced
196 int _arc_num; |
196 int _arc_num; |
197 int _all_arc_num; |
197 int _all_arc_num; |
198 int _search_arc_num; |
198 int _search_arc_num; |
199 |
199 |
200 // Parameters of the problem |
200 // Parameters of the problem |
201 bool _have_lower; |
201 bool _has_lower; |
202 SupplyType _stype; |
202 SupplyType _stype; |
203 Value _sum_supply; |
203 Value _sum_supply; |
204 |
204 |
205 // Data structures for storing the digraph |
205 // Data structures for storing the digraph |
206 IntNodeMap _node_id; |
206 IntNodeMap _node_id; |
680 /// of the algorithm. |
680 /// of the algorithm. |
681 /// |
681 /// |
682 /// \return <tt>(*this)</tt> |
682 /// \return <tt>(*this)</tt> |
683 template <typename LowerMap> |
683 template <typename LowerMap> |
684 NetworkSimplex& lowerMap(const LowerMap& map) { |
684 NetworkSimplex& lowerMap(const LowerMap& map) { |
685 _have_lower = true; |
685 _has_lower = true; |
686 for (ArcIt a(_graph); a != INVALID; ++a) { |
686 for (ArcIt a(_graph); a != INVALID; ++a) { |
687 _lower[_arc_id[a]] = map[a]; |
687 _lower[_arc_id[a]] = map[a]; |
688 } |
688 } |
689 return *this; |
689 return *this; |
690 } |
690 } |
877 for (int i = 0; i != _arc_num; ++i) { |
877 for (int i = 0; i != _arc_num; ++i) { |
878 _lower[i] = 0; |
878 _lower[i] = 0; |
879 _upper[i] = INF; |
879 _upper[i] = INF; |
880 _cost[i] = 1; |
880 _cost[i] = 1; |
881 } |
881 } |
882 _have_lower = false; |
882 _has_lower = false; |
883 _stype = GEQ; |
883 _stype = GEQ; |
884 return *this; |
884 return *this; |
885 } |
885 } |
886 |
886 |
887 /// \brief Reset the internal data structures and all the parameters |
887 /// \brief Reset the internal data structures and all the parameters |
1070 // Check lower and upper bounds |
1070 // Check lower and upper bounds |
1071 LEMON_DEBUG(checkBoundMaps(), |
1071 LEMON_DEBUG(checkBoundMaps(), |
1072 "Upper bounds must be greater or equal to the lower bounds"); |
1072 "Upper bounds must be greater or equal to the lower bounds"); |
1073 |
1073 |
1074 // Remove non-zero lower bounds |
1074 // Remove non-zero lower bounds |
1075 if (_have_lower) { |
1075 if (_has_lower) { |
1076 for (int i = 0; i != _arc_num; ++i) { |
1076 for (int i = 0; i != _arc_num; ++i) { |
1077 Value c = _lower[i]; |
1077 Value c = _lower[i]; |
1078 if (c >= 0) { |
1078 if (c >= 0) { |
1079 _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF; |
1079 _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF; |
1080 } else { |
1080 } else { |
1233 } |
1233 } |
1234 |
1234 |
1235 return true; |
1235 return true; |
1236 } |
1236 } |
1237 |
1237 |
1238 // Check if the upper bound is greater or equal to the lower bound |
1238 // Check if the upper bound is greater than or equal to the lower bound |
1239 // on each arc. |
1239 // on each arc. |
1240 bool checkBoundMaps() { |
1240 bool checkBoundMaps() { |
1241 for (int j = 0; j != _arc_num; ++j) { |
1241 for (int j = 0; j != _arc_num; ++j) { |
1242 if (_upper[j] < _lower[j]) return false; |
1242 if (_upper[j] < _lower[j]) return false; |
1243 } |
1243 } |
1610 for (int e = _search_arc_num; e != _all_arc_num; ++e) { |
1610 for (int e = _search_arc_num; e != _all_arc_num; ++e) { |
1611 if (_flow[e] != 0) return INFEASIBLE; |
1611 if (_flow[e] != 0) return INFEASIBLE; |
1612 } |
1612 } |
1613 |
1613 |
1614 // Transform the solution and the supply map to the original form |
1614 // Transform the solution and the supply map to the original form |
1615 if (_have_lower) { |
1615 if (_has_lower) { |
1616 for (int i = 0; i != _arc_num; ++i) { |
1616 for (int i = 0; i != _arc_num; ++i) { |
1617 Value c = _lower[i]; |
1617 Value c = _lower[i]; |
1618 if (c != 0) { |
1618 if (c != 0) { |
1619 _flow[i] += c; |
1619 _flow[i] += c; |
1620 _supply[_source[i]] += c; |
1620 _supply[_source[i]] += c; |