lemon/cost_scaling.h
changeset 1016 97975184f4aa
parent 938 a07b6b27fe69
child 1049 7bf489cf624e
child 1070 ee9bac10f58e
equal deleted inserted replaced
23:c134a8d8384f 24:ec27f2e73ddc
    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
   100   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
   101   /// implementations available in LEMON for this problem.
   101   /// implementations available in LEMON for solving this problem.
       
   102   /// (For more information, see \ref min_cost_flow_algs "the module page".)
   102   ///
   103   ///
   103   /// Most of the parameters of the problem (except for the digraph)
   104   /// Most of the parameters of the problem (except for the digraph)
   104   /// can be given using separate functions, and the algorithm can be
   105   /// can be given using separate functions, and the algorithm can be
   105   /// executed using the \ref run() function. If some parameters are not
   106   /// executed using the \ref run() function. If some parameters are not
   106   /// specified, then default values will be used.
   107   /// specified, then default values will be used.
   702     /// \pre \ref run() must be called before using this function.
   703     /// \pre \ref run() must be called before using this function.
   703     Value flow(const Arc& a) const {
   704     Value flow(const Arc& a) const {
   704       return _res_cap[_arc_idb[a]];
   705       return _res_cap[_arc_idb[a]];
   705     }
   706     }
   706 
   707 
   707     /// \brief Return the flow map (the primal solution).
   708     /// \brief Copy the flow values (the primal solution) into the
       
   709     /// given map.
   708     ///
   710     ///
   709     /// This function copies the flow value on each arc into the given
   711     /// This function copies the flow value on each arc into the given
   710     /// map. The \c Value type of the algorithm must be convertible to
   712     /// map. The \c Value type of the algorithm must be convertible to
   711     /// the \c Value type of the map.
   713     /// the \c Value type of the map.
   712     ///
   714     ///
   726     /// \pre \ref run() must be called before using this function.
   728     /// \pre \ref run() must be called before using this function.
   727     Cost potential(const Node& n) const {
   729     Cost potential(const Node& n) const {
   728       return static_cast<Cost>(_pi[_node_id[n]]);
   730       return static_cast<Cost>(_pi[_node_id[n]]);
   729     }
   731     }
   730 
   732 
   731     /// \brief Return the potential map (the dual solution).
   733     /// \brief Copy the potential values (the dual solution) into the
       
   734     /// given map.
   732     ///
   735     ///
   733     /// This function copies the potential (dual value) of each node
   736     /// This function copies the potential (dual value) of each node
   734     /// into the given map.
   737     /// into the given map.
   735     /// The \c Cost type of the algorithm must be convertible to the
   738     /// The \c Cost type of the algorithm must be convertible to the
   736     /// \c Value type of the map.
   739     /// \c Value type of the map.