lemon/capacity_scaling.h
changeset 1011 9a6c9d4ee77b
parent 985 eb12ad2789fc
parent 1003 16f55008c863
child 1049 7bf489cf624e
child 1070 ee9bac10f58e
equal deleted inserted replaced
18:cea0b59ede18 20:083ca195a82d
    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.