54 /// can be given using separate functions, and the algorithm can be |
54 /// can be given using separate functions, and the algorithm can be |
55 /// executed using the \ref run() function. If some parameters are not |
55 /// executed using the \ref run() function. If some parameters are not |
56 /// specified, then default values will be used. |
56 /// specified, then default values will be used. |
57 /// |
57 /// |
58 /// \tparam GR The digraph type the algorithm runs on. |
58 /// \tparam GR The digraph type the algorithm runs on. |
59 /// \tparam F The value type used for flow amounts, capacity bounds |
59 /// \tparam V The value type used for flow amounts, capacity bounds |
60 /// and supply values in the algorithm. By default it is \c int. |
60 /// and supply values in the algorithm. By default it is \c int. |
61 /// \tparam C The value type used for costs and potentials in the |
61 /// \tparam C The value type used for costs and potentials in the |
62 /// algorithm. By default it is the same as \c F. |
62 /// algorithm. By default it is the same as \c V. |
63 /// |
63 /// |
64 /// \warning Both value types must be signed and all input data must |
64 /// \warning Both value types must be signed and all input data must |
65 /// be integer. |
65 /// be integer. |
66 /// |
66 /// |
67 /// \note %NetworkSimplex provides five different pivot rule |
67 /// \note %NetworkSimplex provides five different pivot rule |
68 /// implementations, from which the most efficient one is used |
68 /// implementations, from which the most efficient one is used |
69 /// by default. For more information see \ref PivotRule. |
69 /// by default. For more information see \ref PivotRule. |
70 template <typename GR, typename F = int, typename C = F> |
70 template <typename GR, typename V = int, typename C = V> |
71 class NetworkSimplex |
71 class NetworkSimplex |
72 { |
72 { |
73 public: |
73 public: |
74 |
74 |
75 /// The flow type of the algorithm |
75 /// The flow type of the algorithm |
76 typedef F Flow; |
76 typedef V Value; |
77 /// The cost type of the algorithm |
77 /// The cost type of the algorithm |
78 typedef C Cost; |
78 typedef C Cost; |
79 #ifdef DOXYGEN |
79 #ifdef DOXYGEN |
80 /// The type of the flow map |
80 /// The type of the flow map |
81 typedef GR::ArcMap<Flow> FlowMap; |
81 typedef GR::ArcMap<Value> FlowMap; |
82 /// The type of the potential map |
82 /// The type of the potential map |
83 typedef GR::NodeMap<Cost> PotentialMap; |
83 typedef GR::NodeMap<Cost> PotentialMap; |
84 #else |
84 #else |
85 /// The type of the flow map |
85 /// The type of the flow map |
86 typedef typename GR::template ArcMap<Flow> FlowMap; |
86 typedef typename GR::template ArcMap<Value> FlowMap; |
87 /// The type of the potential map |
87 /// The type of the potential map |
88 typedef typename GR::template NodeMap<Cost> PotentialMap; |
88 typedef typename GR::template NodeMap<Cost> PotentialMap; |
89 #endif |
89 #endif |
90 |
90 |
91 public: |
91 public: |
204 |
204 |
205 private: |
205 private: |
206 |
206 |
207 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
207 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
208 |
208 |
209 typedef typename GR::template ArcMap<Flow> FlowArcMap; |
209 typedef typename GR::template ArcMap<Value> ValueArcMap; |
210 typedef typename GR::template ArcMap<Cost> CostArcMap; |
210 typedef typename GR::template ArcMap<Cost> CostArcMap; |
211 typedef typename GR::template NodeMap<Flow> FlowNodeMap; |
211 typedef typename GR::template NodeMap<Value> ValueNodeMap; |
212 |
212 |
213 typedef std::vector<Arc> ArcVector; |
213 typedef std::vector<Arc> ArcVector; |
214 typedef std::vector<Node> NodeVector; |
214 typedef std::vector<Node> NodeVector; |
215 typedef std::vector<int> IntVector; |
215 typedef std::vector<int> IntVector; |
216 typedef std::vector<bool> BoolVector; |
216 typedef std::vector<bool> BoolVector; |
217 typedef std::vector<Flow> FlowVector; |
217 typedef std::vector<Value> FlowVector; |
218 typedef std::vector<Cost> CostVector; |
218 typedef std::vector<Cost> CostVector; |
219 |
219 |
220 // State constants for arcs |
220 // State constants for arcs |
221 enum ArcStateEnum { |
221 enum ArcStateEnum { |
222 STATE_UPPER = -1, |
222 STATE_UPPER = -1, |
276 |
276 |
277 // Temporary data used in the current pivot iteration |
277 // Temporary data used in the current pivot iteration |
278 int in_arc, join, u_in, v_in, u_out, v_out; |
278 int in_arc, join, u_in, v_in, u_out, v_out; |
279 int first, second, right, last; |
279 int first, second, right, last; |
280 int stem, par_stem, new_stem; |
280 int stem, par_stem, new_stem; |
281 Flow delta; |
281 Value delta; |
282 |
282 |
283 public: |
283 public: |
284 |
284 |
285 /// \brief Constant for infinite upper bounds (capacities). |
285 /// \brief Constant for infinite upper bounds (capacities). |
286 /// |
286 /// |
287 /// Constant for infinite upper bounds (capacities). |
287 /// Constant for infinite upper bounds (capacities). |
288 /// It is \c std::numeric_limits<Flow>::infinity() if available, |
288 /// It is \c std::numeric_limits<Value>::infinity() if available, |
289 /// \c std::numeric_limits<Flow>::max() otherwise. |
289 /// \c std::numeric_limits<Value>::max() otherwise. |
290 const Flow INF; |
290 const Value INF; |
291 |
291 |
292 private: |
292 private: |
293 |
293 |
294 // Implementation of the First Eligible pivot rule |
294 // Implementation of the First Eligible pivot rule |
295 class FirstEligiblePivotRule |
295 class FirstEligiblePivotRule |
693 _plower(NULL), _pupper(NULL), _pcost(NULL), |
693 _plower(NULL), _pupper(NULL), _pcost(NULL), |
694 _psupply(NULL), _pstsup(false), _stype(GEQ), |
694 _psupply(NULL), _pstsup(false), _stype(GEQ), |
695 _flow_map(NULL), _potential_map(NULL), |
695 _flow_map(NULL), _potential_map(NULL), |
696 _local_flow(false), _local_potential(false), |
696 _local_flow(false), _local_potential(false), |
697 _node_id(graph), |
697 _node_id(graph), |
698 INF(std::numeric_limits<Flow>::has_infinity ? |
698 INF(std::numeric_limits<Value>::has_infinity ? |
699 std::numeric_limits<Flow>::infinity() : |
699 std::numeric_limits<Value>::infinity() : |
700 std::numeric_limits<Flow>::max()) |
700 std::numeric_limits<Value>::max()) |
701 { |
701 { |
702 // Check the value types |
702 // Check the value types |
703 LEMON_ASSERT(std::numeric_limits<Flow>::is_signed, |
703 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
704 "The flow type of NetworkSimplex must be signed"); |
704 "The flow type of NetworkSimplex must be signed"); |
705 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
705 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
706 "The cost type of NetworkSimplex must be signed"); |
706 "The cost type of NetworkSimplex must be signed"); |
707 } |
707 } |
708 |
708 |
723 /// This function sets the lower bounds on the arcs. |
723 /// This function sets the lower bounds on the arcs. |
724 /// If it is not used before calling \ref run(), the lower bounds |
724 /// If it is not used before calling \ref run(), the lower bounds |
725 /// will be set to zero on all arcs. |
725 /// will be set to zero on all arcs. |
726 /// |
726 /// |
727 /// \param map An arc map storing the lower bounds. |
727 /// \param map An arc map storing the lower bounds. |
728 /// Its \c Value type must be convertible to the \c Flow type |
728 /// Its \c Value type must be convertible to the \c Value type |
729 /// of the algorithm. |
729 /// of the algorithm. |
730 /// |
730 /// |
731 /// \return <tt>(*this)</tt> |
731 /// \return <tt>(*this)</tt> |
732 template <typename LowerMap> |
732 template <typename LowerMap> |
733 NetworkSimplex& lowerMap(const LowerMap& map) { |
733 NetworkSimplex& lowerMap(const LowerMap& map) { |
734 delete _plower; |
734 delete _plower; |
735 _plower = new FlowArcMap(_graph); |
735 _plower = new ValueArcMap(_graph); |
736 for (ArcIt a(_graph); a != INVALID; ++a) { |
736 for (ArcIt a(_graph); a != INVALID; ++a) { |
737 (*_plower)[a] = map[a]; |
737 (*_plower)[a] = map[a]; |
738 } |
738 } |
739 return *this; |
739 return *this; |
740 } |
740 } |
745 /// If it is not used before calling \ref run(), the upper bounds |
745 /// If it is not used before calling \ref run(), the upper bounds |
746 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
746 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
747 /// unbounded from above on each arc). |
747 /// unbounded from above on each arc). |
748 /// |
748 /// |
749 /// \param map An arc map storing the upper bounds. |
749 /// \param map An arc map storing the upper bounds. |
750 /// Its \c Value type must be convertible to the \c Flow type |
750 /// Its \c Value type must be convertible to the \c Value type |
751 /// of the algorithm. |
751 /// of the algorithm. |
752 /// |
752 /// |
753 /// \return <tt>(*this)</tt> |
753 /// \return <tt>(*this)</tt> |
754 template<typename UpperMap> |
754 template<typename UpperMap> |
755 NetworkSimplex& upperMap(const UpperMap& map) { |
755 NetworkSimplex& upperMap(const UpperMap& map) { |
756 delete _pupper; |
756 delete _pupper; |
757 _pupper = new FlowArcMap(_graph); |
757 _pupper = new ValueArcMap(_graph); |
758 for (ArcIt a(_graph); a != INVALID; ++a) { |
758 for (ArcIt a(_graph); a != INVALID; ++a) { |
759 (*_pupper)[a] = map[a]; |
759 (*_pupper)[a] = map[a]; |
760 } |
760 } |
761 return *this; |
761 return *this; |
762 } |
762 } |
788 /// If neither this function nor \ref stSupply() is used before |
788 /// If neither this function nor \ref stSupply() is used before |
789 /// calling \ref run(), the supply of each node will be set to zero. |
789 /// calling \ref run(), the supply of each node will be set to zero. |
790 /// (It makes sense only if non-zero lower bounds are given.) |
790 /// (It makes sense only if non-zero lower bounds are given.) |
791 /// |
791 /// |
792 /// \param map A node map storing the supply values. |
792 /// \param map A node map storing the supply values. |
793 /// Its \c Value type must be convertible to the \c Flow type |
793 /// Its \c Value type must be convertible to the \c Value type |
794 /// of the algorithm. |
794 /// of the algorithm. |
795 /// |
795 /// |
796 /// \return <tt>(*this)</tt> |
796 /// \return <tt>(*this)</tt> |
797 template<typename SupplyMap> |
797 template<typename SupplyMap> |
798 NetworkSimplex& supplyMap(const SupplyMap& map) { |
798 NetworkSimplex& supplyMap(const SupplyMap& map) { |
799 delete _psupply; |
799 delete _psupply; |
800 _pstsup = false; |
800 _pstsup = false; |
801 _psupply = new FlowNodeMap(_graph); |
801 _psupply = new ValueNodeMap(_graph); |
802 for (NodeIt n(_graph); n != INVALID; ++n) { |
802 for (NodeIt n(_graph); n != INVALID; ++n) { |
803 (*_psupply)[n] = map[n]; |
803 (*_psupply)[n] = map[n]; |
804 } |
804 } |
805 return *this; |
805 return *this; |
806 } |
806 } |
821 /// \param t The target node. |
821 /// \param t The target node. |
822 /// \param k The required amount of flow from node \c s to node \c t |
822 /// \param k The required amount of flow from node \c s to node \c t |
823 /// (i.e. the supply of \c s and the demand of \c t). |
823 /// (i.e. the supply of \c s and the demand of \c t). |
824 /// |
824 /// |
825 /// \return <tt>(*this)</tt> |
825 /// \return <tt>(*this)</tt> |
826 NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) { |
826 NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) { |
827 delete _psupply; |
827 delete _psupply; |
828 _psupply = NULL; |
828 _psupply = NULL; |
829 _pstsup = true; |
829 _pstsup = true; |
830 _psource = s; |
830 _psource = s; |
831 _ptarget = t; |
831 _ptarget = t; |
1023 /// \brief Return the flow on the given arc. |
1023 /// \brief Return the flow on the given arc. |
1024 /// |
1024 /// |
1025 /// This function returns the flow on the given arc. |
1025 /// This function returns the flow on the given arc. |
1026 /// |
1026 /// |
1027 /// \pre \ref run() must be called before using this function. |
1027 /// \pre \ref run() must be called before using this function. |
1028 Flow flow(const Arc& a) const { |
1028 Value flow(const Arc& a) const { |
1029 return (*_flow_map)[a]; |
1029 return (*_flow_map)[a]; |
1030 } |
1030 } |
1031 |
1031 |
1032 /// \brief Return a const reference to the flow map. |
1032 /// \brief Return a const reference to the flow map. |
1033 /// |
1033 /// |
1313 |
1313 |
1314 // Change _flow and _state vectors |
1314 // Change _flow and _state vectors |
1315 void changeFlow(bool change) { |
1315 void changeFlow(bool change) { |
1316 // Augment along the cycle |
1316 // Augment along the cycle |
1317 if (delta > 0) { |
1317 if (delta > 0) { |
1318 Flow val = _state[in_arc] * delta; |
1318 Value val = _state[in_arc] * delta; |
1319 _flow[in_arc] += val; |
1319 _flow[in_arc] += val; |
1320 for (int u = _source[in_arc]; u != join; u = _parent[u]) { |
1320 for (int u = _source[in_arc]; u != join; u = _parent[u]) { |
1321 _flow[_pred[u]] += _forward[u] ? -val : val; |
1321 _flow[_pred[u]] += _forward[u] ? -val : val; |
1322 } |
1322 } |
1323 for (int u = _target[in_arc]; u != join; u = _parent[u]) { |
1323 for (int u = _target[in_arc]; u != join; u = _parent[u]) { |