equal
deleted
inserted
replaced
67 /// \ref CapacityScaling implements the capacity scaling version |
67 /// \ref CapacityScaling implements the capacity scaling version |
68 /// of the successive shortest path algorithm for finding a |
68 /// of the successive shortest path algorithm for finding a |
69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, |
69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, |
70 /// \ref edmondskarp72theoretical. It is an efficient dual |
70 /// \ref edmondskarp72theoretical. It is an efficient dual |
71 /// solution method. |
71 /// solution method. |
|
72 /// |
|
73 /// This algorithm is typically slower than \ref CostScaling and |
|
74 /// \ref NetworkSimplex, but in special cases, it can be more |
|
75 /// efficient than them. |
|
76 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
72 /// |
77 /// |
73 /// Most of the parameters of the problem (except for the digraph) |
78 /// Most of the parameters of the problem (except for the digraph) |
74 /// can be given using separate functions, and the algorithm can be |
79 /// can be given using separate functions, and the algorithm can be |
75 /// executed using the \ref run() function. If some parameters are not |
80 /// executed using the \ref run() function. If some parameters are not |
76 /// specified, then default values will be used. |
81 /// specified, then default values will be used. |
674 /// \pre \ref run() must be called before using this function. |
679 /// \pre \ref run() must be called before using this function. |
675 Value flow(const Arc& a) const { |
680 Value flow(const Arc& a) const { |
676 return _res_cap[_arc_idb[a]]; |
681 return _res_cap[_arc_idb[a]]; |
677 } |
682 } |
678 |
683 |
679 /// \brief Return the flow map (the primal solution). |
684 /// \brief Copy the flow values (the primal solution) into the |
|
685 /// given map. |
680 /// |
686 /// |
681 /// This function copies the flow value on each arc into the given |
687 /// This function copies the flow value on each arc into the given |
682 /// map. The \c Value type of the algorithm must be convertible to |
688 /// map. The \c Value type of the algorithm must be convertible to |
683 /// the \c Value type of the map. |
689 /// the \c Value type of the map. |
684 /// |
690 /// |
698 /// \pre \ref run() must be called before using this function. |
704 /// \pre \ref run() must be called before using this function. |
699 Cost potential(const Node& n) const { |
705 Cost potential(const Node& n) const { |
700 return _pi[_node_id[n]]; |
706 return _pi[_node_id[n]]; |
701 } |
707 } |
702 |
708 |
703 /// \brief Return the potential map (the dual solution). |
709 /// \brief Copy the potential values (the dual solution) into the |
|
710 /// given map. |
704 /// |
711 /// |
705 /// This function copies the potential (dual value) of each node |
712 /// This function copies the potential (dual value) of each node |
706 /// into the given map. |
713 /// into the given map. |
707 /// The \c Cost type of the algorithm must be convertible to the |
714 /// The \c Cost type of the algorithm must be convertible to the |
708 /// \c Value type of the map. |
715 /// \c Value type of the map. |