33 |
33 |
34 /// \brief Default traits class of CapacityScaling algorithm. |
34 /// \brief Default traits class of CapacityScaling algorithm. |
35 /// |
35 /// |
36 /// Default traits class of CapacityScaling algorithm. |
36 /// Default traits class of CapacityScaling algorithm. |
37 /// \tparam GR Digraph type. |
37 /// \tparam GR Digraph type. |
38 /// \tparam V The value type used for flow amounts, capacity bounds |
38 /// \tparam V The number type used for flow amounts, capacity bounds |
39 /// and supply values. By default it is \c int. |
39 /// and supply values. By default it is \c int. |
40 /// \tparam C The value type used for costs and potentials. |
40 /// \tparam C The number type used for costs and potentials. |
41 /// By default it is the same as \c V. |
41 /// By default it is the same as \c V. |
42 template <typename GR, typename V = int, typename C = V> |
42 template <typename GR, typename V = int, typename C = V> |
43 struct CapacityScalingDefaultTraits |
43 struct CapacityScalingDefaultTraits |
44 { |
44 { |
45 /// The type of the digraph |
45 /// The type of the digraph |
73 /// can be given using separate functions, and the algorithm can be |
73 /// can be given using separate functions, and the algorithm can be |
74 /// executed using the \ref run() function. If some parameters are not |
74 /// executed using the \ref run() function. If some parameters are not |
75 /// specified, then default values will be used. |
75 /// specified, then default values will be used. |
76 /// |
76 /// |
77 /// \tparam GR The digraph type the algorithm runs on. |
77 /// \tparam GR The digraph type the algorithm runs on. |
78 /// \tparam V The value type used for flow amounts, capacity bounds |
78 /// \tparam V The number type used for flow amounts, capacity bounds |
79 /// and supply values in the algorithm. By default it is \c int. |
79 /// and supply values in the algorithm. By default it is \c int. |
80 /// \tparam C The value type used for costs and potentials in the |
80 /// \tparam C The number type used for costs and potentials in the |
81 /// algorithm. By default it is the same as \c V. |
81 /// algorithm. By default it is the same as \c V. |
82 /// |
82 /// |
83 /// \warning Both value types must be signed and all input data must |
83 /// \warning Both number types must be signed and all input data must |
84 /// be integer. |
84 /// be integer. |
85 /// \warning This algorithm does not support negative costs for such |
85 /// \warning This algorithm does not support negative costs for such |
86 /// arcs that have infinite upper bound. |
86 /// arcs that have infinite upper bound. |
87 #ifdef DOXYGEN |
87 #ifdef DOXYGEN |
88 template <typename GR, typename V, typename C, typename TR> |
88 template <typename GR, typename V, typename C, typename TR> |
120 /// bounded), and the algorithm has found optimal flow and node |
120 /// bounded), and the algorithm has found optimal flow and node |
121 /// potentials (primal and dual solutions). |
121 /// potentials (primal and dual solutions). |
122 OPTIMAL, |
122 OPTIMAL, |
123 /// The digraph contains an arc of negative cost and infinite |
123 /// The digraph contains an arc of negative cost and infinite |
124 /// upper bound. It means that the objective function is unbounded |
124 /// upper bound. It means that the objective function is unbounded |
125 /// on that arc, however note that it could actually be bounded |
125 /// on that arc, however, note that it could actually be bounded |
126 /// over the feasible flows, but this algroithm cannot handle |
126 /// over the feasible flows, but this algroithm cannot handle |
127 /// these cases. |
127 /// these cases. |
128 UNBOUNDED |
128 UNBOUNDED |
129 }; |
129 }; |
130 |
130 |
305 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), |
305 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), |
306 INF(std::numeric_limits<Value>::has_infinity ? |
306 INF(std::numeric_limits<Value>::has_infinity ? |
307 std::numeric_limits<Value>::infinity() : |
307 std::numeric_limits<Value>::infinity() : |
308 std::numeric_limits<Value>::max()) |
308 std::numeric_limits<Value>::max()) |
309 { |
309 { |
310 // Check the value types |
310 // Check the number types |
311 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
311 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
312 "The flow type of CapacityScaling must be signed"); |
312 "The flow type of CapacityScaling must be signed"); |
313 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
313 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
314 "The cost type of CapacityScaling must be signed"); |
314 "The cost type of CapacityScaling must be signed"); |
315 |
315 |
409 /// \brief Set the upper bounds (capacities) on the arcs. |
409 /// \brief Set the upper bounds (capacities) on the arcs. |
410 /// |
410 /// |
411 /// This function sets the upper bounds (capacities) on the arcs. |
411 /// This function sets the upper bounds (capacities) on the arcs. |
412 /// If it is not used before calling \ref run(), the upper bounds |
412 /// If it is not used before calling \ref run(), the upper bounds |
413 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
413 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
414 /// unbounded from above on each arc). |
414 /// unbounded from above). |
415 /// |
415 /// |
416 /// \param map An arc map storing the upper bounds. |
416 /// \param map An arc map storing the upper bounds. |
417 /// Its \c Value type must be convertible to the \c Value type |
417 /// Its \c Value type must be convertible to the \c Value type |
418 /// of the algorithm. |
418 /// of the algorithm. |
419 /// |
419 /// |
512 /// |
512 /// |
513 /// This function can be called more than once. All the parameters |
513 /// This function can be called more than once. All the parameters |
514 /// that have been given are kept for the next call, unless |
514 /// that have been given are kept for the next call, unless |
515 /// \ref reset() is called, thus only the modified parameters |
515 /// \ref reset() is called, thus only the modified parameters |
516 /// have to be set again. See \ref reset() for examples. |
516 /// have to be set again. See \ref reset() for examples. |
517 /// However the underlying digraph must not be modified after this |
517 /// However, the underlying digraph must not be modified after this |
518 /// class have been constructed, since it copies and extends the graph. |
518 /// class have been constructed, since it copies and extends the graph. |
519 /// |
519 /// |
520 /// \param factor The capacity scaling factor. It must be larger than |
520 /// \param factor The capacity scaling factor. It must be larger than |
521 /// one to use scaling. If it is less or equal to one, then scaling |
521 /// one to use scaling. If it is less or equal to one, then scaling |
522 /// will be disabled. |
522 /// will be disabled. |
525 /// \n \c OPTIMAL if the problem has optimal solution |
525 /// \n \c OPTIMAL if the problem has optimal solution |
526 /// (i.e. it is feasible and bounded), and the algorithm has found |
526 /// (i.e. it is feasible and bounded), and the algorithm has found |
527 /// optimal flow and node potentials (primal and dual solutions), |
527 /// optimal flow and node potentials (primal and dual solutions), |
528 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost |
528 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost |
529 /// and infinite upper bound. It means that the objective function |
529 /// and infinite upper bound. It means that the objective function |
530 /// is unbounded on that arc, however note that it could actually be |
530 /// is unbounded on that arc, however, note that it could actually be |
531 /// bounded over the feasible flows, but this algroithm cannot handle |
531 /// bounded over the feasible flows, but this algroithm cannot handle |
532 /// these cases. |
532 /// these cases. |
533 /// |
533 /// |
534 /// \see ProblemType |
534 /// \see ProblemType |
535 ProblemType run(int factor = 4) { |
535 ProblemType run(int factor = 4) { |