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. |
123 /// |
123 /// |
124 /// \ref NetworkSimplex provides five different pivot rule |
124 /// \ref NetworkSimplex provides five different pivot rule |
125 /// implementations that significantly affect the running time |
125 /// implementations that significantly affect the running time |
126 /// of the algorithm. |
126 /// of the algorithm. |
127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
128 /// proved to be the most efficient and the most robust on various |
128 /// turend out to be the most efficient and the most robust on various |
129 /// test inputs. |
129 /// test inputs. |
130 /// However, another pivot rule can be selected using the \ref run() |
130 /// However, another pivot rule can be selected using the \ref run() |
131 /// function with the proper parameter. |
131 /// function with the proper parameter. |
132 enum PivotRule { |
132 enum PivotRule { |
133 |
133 |
165 |
165 |
166 typedef std::vector<int> IntVector; |
166 typedef std::vector<int> IntVector; |
167 typedef std::vector<Value> ValueVector; |
167 typedef std::vector<Value> ValueVector; |
168 typedef std::vector<Cost> CostVector; |
168 typedef std::vector<Cost> CostVector; |
169 typedef std::vector<signed char> CharVector; |
169 typedef std::vector<signed char> CharVector; |
170 // Note: vector<signed char> is used instead of vector<ArcState> and |
170 // Note: vector<signed char> is used instead of vector<ArcState> and |
171 // vector<ArcDirection> for efficiency reasons |
171 // vector<ArcDirection> for efficiency reasons |
172 |
172 |
173 // State constants for arcs |
173 // State constants for arcs |
174 enum ArcState { |
174 enum ArcState { |
175 STATE_UPPER = -1, |
175 STATE_UPPER = -1, |
732 /// \param map A node map storing the supply values. |
732 /// \param map A node map storing the supply values. |
733 /// Its \c Value type must be convertible to the \c Value type |
733 /// Its \c Value type must be convertible to the \c Value type |
734 /// of the algorithm. |
734 /// of the algorithm. |
735 /// |
735 /// |
736 /// \return <tt>(*this)</tt> |
736 /// \return <tt>(*this)</tt> |
|
737 /// |
|
738 /// \sa supplyType() |
737 template<typename SupplyMap> |
739 template<typename SupplyMap> |
738 NetworkSimplex& supplyMap(const SupplyMap& map) { |
740 NetworkSimplex& supplyMap(const SupplyMap& map) { |
739 for (NodeIt n(_graph); n != INVALID; ++n) { |
741 for (NodeIt n(_graph); n != INVALID; ++n) { |
740 _supply[_node_id[n]] = map[n]; |
742 _supply[_node_id[n]] = map[n]; |
741 } |
743 } |
748 /// and the required flow value. |
750 /// and the required flow value. |
749 /// If neither this function nor \ref supplyMap() is used before |
751 /// If neither this function nor \ref supplyMap() is used before |
750 /// calling \ref run(), the supply of each node will be set to zero. |
752 /// calling \ref run(), the supply of each node will be set to zero. |
751 /// |
753 /// |
752 /// Using this function has the same effect as using \ref supplyMap() |
754 /// Using this function has the same effect as using \ref supplyMap() |
753 /// with such a map in which \c k is assigned to \c s, \c -k is |
755 /// with a map in which \c k is assigned to \c s, \c -k is |
754 /// assigned to \c t and all other nodes have zero supply value. |
756 /// assigned to \c t and all other nodes have zero supply value. |
755 /// |
757 /// |
756 /// \param s The source node. |
758 /// \param s The source node. |
757 /// \param t The target node. |
759 /// \param t The target node. |
758 /// \param k The required amount of flow from node \c s to node \c t |
760 /// \param k The required amount of flow from node \c s to node \c t |