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 /// |
114 /// consider to use the named template parameters instead. |
117 /// consider to use the named template parameters instead. |
115 /// |
118 /// |
116 /// \warning Both \c V and \c C must be signed number types. |
119 /// \warning Both \c V and \c C must be signed number types. |
117 /// \warning All input data (capacities, supply values, and costs) must |
120 /// \warning All input data (capacities, supply values, and costs) must |
118 /// be integer. |
121 /// be integer. |
119 /// \warning This algorithm does not support negative costs for such |
122 /// \warning This algorithm does not support negative costs for |
120 /// arcs that have infinite upper bound. |
123 /// arcs having infinite upper bound. |
121 /// |
124 /// |
122 /// \note %CostScaling provides three different internal methods, |
125 /// \note %CostScaling provides three different internal methods, |
123 /// from which the most efficient one is used by default. |
126 /// from which the most efficient one is used by default. |
124 /// For more information, see \ref Method. |
127 /// For more information, see \ref Method. |
125 #ifdef DOXYGEN |
128 #ifdef DOXYGEN |
177 /// |
180 /// |
178 /// \ref CostScaling provides three internal methods that differ mainly |
181 /// \ref CostScaling provides three internal methods that differ mainly |
179 /// in their base operations, which are used in conjunction with the |
182 /// in their base operations, which are used in conjunction with the |
180 /// relabel operation. |
183 /// relabel operation. |
181 /// By default, the so called \ref PARTIAL_AUGMENT |
184 /// By default, the so called \ref PARTIAL_AUGMENT |
182 /// "Partial Augment-Relabel" method is used, which proved to be |
185 /// "Partial Augment-Relabel" method is used, which turned out to be |
183 /// the most efficient and the most robust on various test inputs. |
186 /// the most efficient and the most robust on various test inputs. |
184 /// However, the other methods can be selected using the \ref run() |
187 /// However, the other methods can be selected using the \ref run() |
185 /// function with the proper parameter. |
188 /// function with the proper parameter. |
186 enum Method { |
189 enum Method { |
187 /// Local push operations are used, i.e. flow is moved only on one |
190 /// Local push operations are used, i.e. flow is moved only on one |
446 /// and the required flow value. |
449 /// and the required flow value. |
447 /// If neither this function nor \ref supplyMap() is used before |
450 /// If neither this function nor \ref supplyMap() is used before |
448 /// calling \ref run(), the supply of each node will be set to zero. |
451 /// calling \ref run(), the supply of each node will be set to zero. |
449 /// |
452 /// |
450 /// Using this function has the same effect as using \ref supplyMap() |
453 /// Using this function has the same effect as using \ref supplyMap() |
451 /// with such a map in which \c k is assigned to \c s, \c -k is |
454 /// with a map in which \c k is assigned to \c s, \c -k is |
452 /// assigned to \c t and all other nodes have zero supply value. |
455 /// assigned to \c t and all other nodes have zero supply value. |
453 /// |
456 /// |
454 /// \param s The source node. |
457 /// \param s The source node. |
455 /// \param t The target node. |
458 /// \param t The target node. |
456 /// \param k The required amount of flow from node \c s to node \c t |
459 /// \param k The required amount of flow from node \c s to node \c t |