38 |
38 |
39 /// \brief Default traits class of CostScaling algorithm. |
39 /// \brief Default traits class of CostScaling algorithm. |
40 /// |
40 /// |
41 /// Default traits class of CostScaling algorithm. |
41 /// Default traits class of CostScaling algorithm. |
42 /// \tparam GR Digraph type. |
42 /// \tparam GR Digraph type. |
43 /// \tparam V The value type used for flow amounts, capacity bounds |
43 /// \tparam V The number type used for flow amounts, capacity bounds |
44 /// and supply values. By default it is \c int. |
44 /// and supply values. By default it is \c int. |
45 /// \tparam C The value type used for costs and potentials. |
45 /// \tparam C The number type used for costs and potentials. |
46 /// By default it is the same as \c V. |
46 /// By default it is the same as \c V. |
47 #ifdef DOXYGEN |
47 #ifdef DOXYGEN |
48 template <typename GR, typename V = int, typename C = V> |
48 template <typename GR, typename V = int, typename C = V> |
49 #else |
49 #else |
50 template < typename GR, typename V = int, typename C = V, |
50 template < typename GR, typename V = int, typename C = V, |
99 /// can be given using separate functions, and the algorithm can be |
99 /// can be given using separate functions, and the algorithm can be |
100 /// executed using the \ref run() function. If some parameters are not |
100 /// executed using the \ref run() function. If some parameters are not |
101 /// specified, then default values will be used. |
101 /// specified, then default values will be used. |
102 /// |
102 /// |
103 /// \tparam GR The digraph type the algorithm runs on. |
103 /// \tparam GR The digraph type the algorithm runs on. |
104 /// \tparam V The value type used for flow amounts, capacity bounds |
104 /// \tparam V The number type used for flow amounts, capacity bounds |
105 /// and supply values in the algorithm. By default it is \c int. |
105 /// and supply values in the algorithm. By default it is \c int. |
106 /// \tparam C The value type used for costs and potentials in the |
106 /// \tparam C The number type used for costs and potentials in the |
107 /// algorithm. By default it is the same as \c V. |
107 /// algorithm. By default it is the same as \c V. |
108 /// |
108 /// |
109 /// \warning Both value types must be signed and all input data must |
109 /// \warning Both number types must be signed and all input data must |
110 /// be integer. |
110 /// be integer. |
111 /// \warning This algorithm does not support negative costs for such |
111 /// \warning This algorithm does not support negative costs for such |
112 /// arcs that have infinite upper bound. |
112 /// arcs that have infinite upper bound. |
113 /// |
113 /// |
114 /// \note %CostScaling provides three different internal methods, |
114 /// \note %CostScaling provides three different internal methods, |
155 /// bounded), and the algorithm has found optimal flow and node |
155 /// bounded), and the algorithm has found optimal flow and node |
156 /// potentials (primal and dual solutions). |
156 /// potentials (primal and dual solutions). |
157 OPTIMAL, |
157 OPTIMAL, |
158 /// The digraph contains an arc of negative cost and infinite |
158 /// The digraph contains an arc of negative cost and infinite |
159 /// upper bound. It means that the objective function is unbounded |
159 /// upper bound. It means that the objective function is unbounded |
160 /// on that arc, however note that it could actually be bounded |
160 /// on that arc, however, note that it could actually be bounded |
161 /// over the feasible flows, but this algroithm cannot handle |
161 /// over the feasible flows, but this algroithm cannot handle |
162 /// these cases. |
162 /// these cases. |
163 UNBOUNDED |
163 UNBOUNDED |
164 }; |
164 }; |
165 |
165 |
323 _cost_map(_cost_vec), _pi_map(_pi), |
323 _cost_map(_cost_vec), _pi_map(_pi), |
324 INF(std::numeric_limits<Value>::has_infinity ? |
324 INF(std::numeric_limits<Value>::has_infinity ? |
325 std::numeric_limits<Value>::infinity() : |
325 std::numeric_limits<Value>::infinity() : |
326 std::numeric_limits<Value>::max()) |
326 std::numeric_limits<Value>::max()) |
327 { |
327 { |
328 // Check the value types |
328 // Check the number types |
329 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
329 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
330 "The flow type of CostScaling must be signed"); |
330 "The flow type of CostScaling must be signed"); |
331 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
331 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
332 "The cost type of CostScaling must be signed"); |
332 "The cost type of CostScaling must be signed"); |
333 |
333 |
431 /// \brief Set the upper bounds (capacities) on the arcs. |
431 /// \brief Set the upper bounds (capacities) on the arcs. |
432 /// |
432 /// |
433 /// This function sets the upper bounds (capacities) on the arcs. |
433 /// This function sets the upper bounds (capacities) on the arcs. |
434 /// If it is not used before calling \ref run(), the upper bounds |
434 /// If it is not used before calling \ref run(), the upper bounds |
435 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
435 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
436 /// unbounded from above on each arc). |
436 /// unbounded from above). |
437 /// |
437 /// |
438 /// \param map An arc map storing the upper bounds. |
438 /// \param map An arc map storing the upper bounds. |
439 /// Its \c Value type must be convertible to the \c Value type |
439 /// Its \c Value type must be convertible to the \c Value type |
440 /// of the algorithm. |
440 /// of the algorithm. |
441 /// |
441 /// |
547 /// \n \c OPTIMAL if the problem has optimal solution |
547 /// \n \c OPTIMAL if the problem has optimal solution |
548 /// (i.e. it is feasible and bounded), and the algorithm has found |
548 /// (i.e. it is feasible and bounded), and the algorithm has found |
549 /// optimal flow and node potentials (primal and dual solutions), |
549 /// optimal flow and node potentials (primal and dual solutions), |
550 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost |
550 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost |
551 /// and infinite upper bound. It means that the objective function |
551 /// and infinite upper bound. It means that the objective function |
552 /// is unbounded on that arc, however note that it could actually be |
552 /// is unbounded on that arc, however, note that it could actually be |
553 /// bounded over the feasible flows, but this algroithm cannot handle |
553 /// bounded over the feasible flows, but this algroithm cannot handle |
554 /// these cases. |
554 /// these cases. |
555 /// |
555 /// |
556 /// \see ProblemType, Method |
556 /// \see ProblemType, Method |
557 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { |
557 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { |
569 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). |
569 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). |
570 /// |
570 /// |
571 /// It is useful for multiple run() calls. If this function is not |
571 /// It is useful for multiple run() calls. If this function is not |
572 /// used, all the parameters given before are kept for the next |
572 /// used, all the parameters given before are kept for the next |
573 /// \ref run() call. |
573 /// \ref run() call. |
574 /// However the underlying digraph must not be modified after this |
574 /// However, the underlying digraph must not be modified after this |
575 /// class have been constructed, since it copies and extends the graph. |
575 /// class have been constructed, since it copies and extends the graph. |
576 /// |
576 /// |
577 /// For example, |
577 /// For example, |
578 /// \code |
578 /// \code |
579 /// CostScaling<ListDigraph> cs(graph); |
579 /// CostScaling<ListDigraph> cs(graph); |