45 /// \ref kellyoneill91netsimplex. |
45 /// \ref kellyoneill91netsimplex. |
46 /// This algorithm is a highly efficient specialized version of the |
46 /// This algorithm is a highly efficient specialized version of the |
47 /// linear programming simplex method directly for the minimum cost |
47 /// linear programming simplex method directly for the minimum cost |
48 /// flow problem. |
48 /// flow problem. |
49 /// |
49 /// |
50 /// In general, %NetworkSimplex is the fastest implementation available |
50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest |
51 /// in LEMON for this problem. |
51 /// implementations available in LEMON for this problem. |
52 /// Moreover, it supports both directions of the supply/demand inequality |
52 /// Furthermore, this class supports both directions of the supply/demand |
53 /// constraints. For more information, see \ref SupplyType. |
53 /// inequality constraints. For more information, see \ref SupplyType. |
54 /// |
54 /// |
55 /// Most of the parameters of the problem (except for the digraph) |
55 /// Most of the parameters of the problem (except for the digraph) |
56 /// can be given using separate functions, and the algorithm can be |
56 /// can be given using separate functions, and the algorithm can be |
57 /// executed using the \ref run() function. If some parameters are not |
57 /// executed using the \ref run() function. If some parameters are not |
58 /// specified, then default values will be used. |
58 /// specified, then default values will be used. |
124 /// |
124 /// |
125 /// \ref NetworkSimplex provides five different pivot rule |
125 /// \ref NetworkSimplex provides five different pivot rule |
126 /// implementations that significantly affect the running time |
126 /// implementations that significantly affect the running time |
127 /// of the algorithm. |
127 /// of the algorithm. |
128 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
128 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
129 /// proved to be the most efficient and the most robust on various |
129 /// turend out to be the most efficient and the most robust on various |
130 /// test inputs. |
130 /// test inputs. |
131 /// However, another pivot rule can be selected using the \ref run() |
131 /// However, another pivot rule can be selected using the \ref run() |
132 /// function with the proper parameter. |
132 /// function with the proper parameter. |
133 enum PivotRule { |
133 enum PivotRule { |
134 |
134 |
166 |
166 |
167 typedef std::vector<int> IntVector; |
167 typedef std::vector<int> IntVector; |
168 typedef std::vector<Value> ValueVector; |
168 typedef std::vector<Value> ValueVector; |
169 typedef std::vector<Cost> CostVector; |
169 typedef std::vector<Cost> CostVector; |
170 typedef std::vector<signed char> CharVector; |
170 typedef std::vector<signed char> CharVector; |
171 // Note: vector<signed char> is used instead of vector<ArcState> and |
171 // Note: vector<signed char> is used instead of vector<ArcState> and |
172 // vector<ArcDirection> for efficiency reasons |
172 // vector<ArcDirection> for efficiency reasons |
173 |
173 |
174 // State constants for arcs |
174 // State constants for arcs |
175 enum ArcState { |
175 enum ArcState { |
176 STATE_UPPER = -1, |
176 STATE_UPPER = -1, |
733 /// \param map A node map storing the supply values. |
733 /// \param map A node map storing the supply values. |
734 /// Its \c Value type must be convertible to the \c Value type |
734 /// Its \c Value type must be convertible to the \c Value type |
735 /// of the algorithm. |
735 /// of the algorithm. |
736 /// |
736 /// |
737 /// \return <tt>(*this)</tt> |
737 /// \return <tt>(*this)</tt> |
|
738 /// |
|
739 /// \sa supplyType() |
738 template<typename SupplyMap> |
740 template<typename SupplyMap> |
739 NetworkSimplex& supplyMap(const SupplyMap& map) { |
741 NetworkSimplex& supplyMap(const SupplyMap& map) { |
740 for (NodeIt n(_graph); n != INVALID; ++n) { |
742 for (NodeIt n(_graph); n != INVALID; ++n) { |
741 _supply[_node_id[n]] = map[n]; |
743 _supply[_node_id[n]] = map[n]; |
742 } |
744 } |
749 /// and the required flow value. |
751 /// and the required flow value. |
750 /// If neither this function nor \ref supplyMap() is used before |
752 /// If neither this function nor \ref supplyMap() is used before |
751 /// calling \ref run(), the supply of each node will be set to zero. |
753 /// calling \ref run(), the supply of each node will be set to zero. |
752 /// |
754 /// |
753 /// Using this function has the same effect as using \ref supplyMap() |
755 /// Using this function has the same effect as using \ref supplyMap() |
754 /// with such a map in which \c k is assigned to \c s, \c -k is |
756 /// with a map in which \c k is assigned to \c s, \c -k is |
755 /// assigned to \c t and all other nodes have zero supply value. |
757 /// assigned to \c t and all other nodes have zero supply value. |
756 /// |
758 /// |
757 /// \param s The source node. |
759 /// \param s The source node. |
758 /// \param t The target node. |
760 /// \param t The target node. |
759 /// \param k The required amount of flow from node \c s to node \c t |
761 /// \param k The required amount of flow from node \c s to node \c t |