equal
deleted
inserted
replaced
193 int _res_node_num; |
193 int _res_node_num; |
194 int _res_arc_num; |
194 int _res_arc_num; |
195 int _root; |
195 int _root; |
196 |
196 |
197 // Parameters of the problem |
197 // Parameters of the problem |
198 bool _have_lower; |
198 bool _has_lower; |
199 Value _sum_supply; |
199 Value _sum_supply; |
200 |
200 |
201 // Data structures for storing the digraph |
201 // Data structures for storing the digraph |
202 IntNodeMap _node_id; |
202 IntNodeMap _node_id; |
203 IntArcMap _arc_idf; |
203 IntArcMap _arc_idf; |
276 /// of the algorithm. |
276 /// of the algorithm. |
277 /// |
277 /// |
278 /// \return <tt>(*this)</tt> |
278 /// \return <tt>(*this)</tt> |
279 template <typename LowerMap> |
279 template <typename LowerMap> |
280 CycleCanceling& lowerMap(const LowerMap& map) { |
280 CycleCanceling& lowerMap(const LowerMap& map) { |
281 _have_lower = true; |
281 _has_lower = true; |
282 for (ArcIt a(_graph); a != INVALID; ++a) { |
282 for (ArcIt a(_graph); a != INVALID; ++a) { |
283 _lower[_arc_idf[a]] = map[a]; |
283 _lower[_arc_idf[a]] = map[a]; |
284 _lower[_arc_idb[a]] = map[a]; |
|
285 } |
284 } |
286 return *this; |
285 return *this; |
287 } |
286 } |
288 |
287 |
289 /// \brief Set the upper bounds (capacities) on the arcs. |
288 /// \brief Set the upper bounds (capacities) on the arcs. |
469 _lower[j] = 0; |
468 _lower[j] = 0; |
470 _upper[j] = INF; |
469 _upper[j] = INF; |
471 _cost[j] = 0; |
470 _cost[j] = 0; |
472 _cost[_reverse[j]] = 0; |
471 _cost[_reverse[j]] = 0; |
473 } |
472 } |
474 _have_lower = false; |
473 _has_lower = false; |
475 return *this; |
474 return *this; |
476 } |
475 } |
477 |
476 |
478 /// \brief Reset the internal data structures and all the parameters |
477 /// \brief Reset the internal data structures and all the parameters |
479 /// that have been given before. |
478 /// that have been given before. |
682 ValueVector excess(_supply); |
681 ValueVector excess(_supply); |
683 |
682 |
684 // Remove infinite upper bounds and check negative arcs |
683 // Remove infinite upper bounds and check negative arcs |
685 const Value MAX = std::numeric_limits<Value>::max(); |
684 const Value MAX = std::numeric_limits<Value>::max(); |
686 int last_out; |
685 int last_out; |
687 if (_have_lower) { |
686 if (_has_lower) { |
688 for (int i = 0; i != _root; ++i) { |
687 for (int i = 0; i != _root; ++i) { |
689 last_out = _first_out[i+1]; |
688 last_out = _first_out[i+1]; |
690 for (int j = _first_out[i]; j != last_out; ++j) { |
689 for (int j = _first_out[i]; j != last_out; ++j) { |
691 if (_forward[j]) { |
690 if (_forward[j]) { |
692 Value c = _cost[j] < 0 ? _upper[j] : _lower[j]; |
691 Value c = _cost[j] < 0 ? _upper[j] : _lower[j]; |
725 ValueArcMap cap(_graph), flow(_graph); |
724 ValueArcMap cap(_graph), flow(_graph); |
726 ValueNodeMap sup(_graph); |
725 ValueNodeMap sup(_graph); |
727 for (NodeIt n(_graph); n != INVALID; ++n) { |
726 for (NodeIt n(_graph); n != INVALID; ++n) { |
728 sup[n] = _supply[_node_id[n]]; |
727 sup[n] = _supply[_node_id[n]]; |
729 } |
728 } |
730 if (_have_lower) { |
729 if (_has_lower) { |
731 for (ArcIt a(_graph); a != INVALID; ++a) { |
730 for (ArcIt a(_graph); a != INVALID; ++a) { |
732 int j = _arc_idf[a]; |
731 int j = _arc_idf[a]; |
733 Value c = _lower[j]; |
732 Value c = _lower[j]; |
734 cap[a] = _upper[j] - c; |
733 cap[a] = _upper[j] - c; |
735 sup[_graph.source(a)] -= c; |
734 sup[_graph.source(a)] -= c; |
782 } |
781 } |
783 |
782 |
784 return OPTIMAL; |
783 return OPTIMAL; |
785 } |
784 } |
786 |
785 |
787 // Check if the upper bound is greater or equal to the lower bound |
786 // Check if the upper bound is greater than or equal to the lower bound |
788 // on each arc. |
787 // on each forward arc. |
789 bool checkBoundMaps() { |
788 bool checkBoundMaps() { |
790 for (int j = 0; j != _res_arc_num; ++j) { |
789 for (int j = 0; j != _res_arc_num; ++j) { |
791 if (_upper[j] < _lower[j]) return false; |
790 if (_forward[j] && _upper[j] < _lower[j]) return false; |
792 } |
791 } |
793 return true; |
792 return true; |
794 } |
793 } |
795 |
794 |
796 // Build a StaticDigraph structure containing the current |
795 // Build a StaticDigraph structure containing the current |
833 bf.init(0); |
832 bf.init(0); |
834 bf.start(); |
833 bf.start(); |
835 } |
834 } |
836 |
835 |
837 // Handle non-zero lower bounds |
836 // Handle non-zero lower bounds |
838 if (_have_lower) { |
837 if (_has_lower) { |
839 int limit = _first_out[_root]; |
838 int limit = _first_out[_root]; |
840 for (int j = 0; j != limit; ++j) { |
839 for (int j = 0; j != limit; ++j) { |
841 if (!_forward[j]) _res_cap[j] += _lower[j]; |
840 if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; |
842 } |
841 } |
843 } |
842 } |
844 } |
843 } |
845 |
844 |
846 // Execute the "Simple Cycle Canceling" method |
845 // Execute the "Simple Cycle Canceling" method |