equal
deleted
inserted
replaced
95 /// \ref goldberg97efficient, \ref bunnagel98efficient. |
95 /// \ref goldberg97efficient, \ref bunnagel98efficient. |
96 /// It is a highly efficient primal-dual solution method, which |
96 /// It is a highly efficient primal-dual solution method, which |
97 /// can be viewed as the generalization of the \ref Preflow |
97 /// can be viewed as the generalization of the \ref Preflow |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
99 /// |
99 /// |
|
100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest |
|
101 /// implementations available in LEMON for this problem. |
|
102 /// |
100 /// Most of the parameters of the problem (except for the digraph) |
103 /// Most of the parameters of the problem (except for the digraph) |
101 /// can be given using separate functions, and the algorithm can be |
104 /// can be given using separate functions, and the algorithm can be |
102 /// executed using the \ref run() function. If some parameters are not |
105 /// executed using the \ref run() function. If some parameters are not |
103 /// specified, then default values will be used. |
106 /// specified, then default values will be used. |
104 /// |
107 /// |
113 /// In most cases, this parameter should not be set directly, |
116 /// In most cases, this parameter should not be set directly, |
114 /// consider to use the named template parameters instead. |
117 /// consider to use the named template parameters instead. |
115 /// |
118 /// |
116 /// \warning Both number types must be signed and all input data must |
119 /// \warning Both number types must be signed and all input data must |
117 /// be integer. |
120 /// be integer. |
118 /// \warning This algorithm does not support negative costs for such |
121 /// \warning This algorithm does not support negative costs for |
119 /// arcs that have infinite upper bound. |
122 /// arcs having infinite upper bound. |
120 /// |
123 /// |
121 /// \note %CostScaling provides three different internal methods, |
124 /// \note %CostScaling provides three different internal methods, |
122 /// from which the most efficient one is used by default. |
125 /// from which the most efficient one is used by default. |
123 /// For more information, see \ref Method. |
126 /// For more information, see \ref Method. |
124 #ifdef DOXYGEN |
127 #ifdef DOXYGEN |
176 /// |
179 /// |
177 /// \ref CostScaling provides three internal methods that differ mainly |
180 /// \ref CostScaling provides three internal methods that differ mainly |
178 /// in their base operations, which are used in conjunction with the |
181 /// in their base operations, which are used in conjunction with the |
179 /// relabel operation. |
182 /// relabel operation. |
180 /// By default, the so called \ref PARTIAL_AUGMENT |
183 /// By default, the so called \ref PARTIAL_AUGMENT |
181 /// "Partial Augment-Relabel" method is used, which proved to be |
184 /// "Partial Augment-Relabel" method is used, which turned out to be |
182 /// the most efficient and the most robust on various test inputs. |
185 /// the most efficient and the most robust on various test inputs. |
183 /// However, the other methods can be selected using the \ref run() |
186 /// However, the other methods can be selected using the \ref run() |
184 /// function with the proper parameter. |
187 /// function with the proper parameter. |
185 enum Method { |
188 enum Method { |
186 /// Local push operations are used, i.e. flow is moved only on one |
189 /// Local push operations are used, i.e. flow is moved only on one |
445 /// and the required flow value. |
448 /// and the required flow value. |
446 /// If neither this function nor \ref supplyMap() is used before |
449 /// If neither this function nor \ref supplyMap() is used before |
447 /// calling \ref run(), the supply of each node will be set to zero. |
450 /// calling \ref run(), the supply of each node will be set to zero. |
448 /// |
451 /// |
449 /// Using this function has the same effect as using \ref supplyMap() |
452 /// Using this function has the same effect as using \ref supplyMap() |
450 /// with such a map in which \c k is assigned to \c s, \c -k is |
453 /// with a map in which \c k is assigned to \c s, \c -k is |
451 /// assigned to \c t and all other nodes have zero supply value. |
454 /// assigned to \c t and all other nodes have zero supply value. |
452 /// |
455 /// |
453 /// \param s The source node. |
456 /// \param s The source node. |
454 /// \param t The target node. |
457 /// \param t The target node. |
455 /// \param k The required amount of flow from node \c s to node \c t |
458 /// \param k The required amount of flow from node \c s to node \c t |