lemon/cycle_canceling.h
changeset 1011 9a6c9d4ee77b
parent 922 9312d6c89d02
child 1013 f6f6896a4724
equal deleted inserted replaced
11:e21af7af4032 12:a716379ddfea
    46   ///
    46   ///
    47   /// \ref CycleCanceling implements three different cycle-canceling
    47   /// \ref CycleCanceling implements three different cycle-canceling
    48   /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    48   /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    49   /// \ref amo93networkflows, \ref klein67primal,
    49   /// \ref amo93networkflows, \ref klein67primal,
    50   /// \ref goldberg89cyclecanceling.
    50   /// \ref goldberg89cyclecanceling.
    51   /// The most efficent one (both theoretically and practically)
    51   /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    52   /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
    52   /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    53   /// thus it is the default method.
    53   /// It runs in strongly polynomial time, but in practice, it is typically
    54   /// It is strongly polynomial, but in practice, it is typically much
    54   /// orders of magnitude slower than the scaling algorithms and
    55   /// slower than the scaling algorithms and NetworkSimplex.
    55   /// \ref NetworkSimplex.
       
    56   /// (For more information, see \ref min_cost_flow_algs "the module page".)
    56   ///
    57   ///
    57   /// Most of the parameters of the problem (except for the digraph)
    58   /// Most of the parameters of the problem (except for the digraph)
    58   /// can be given using separate functions, and the algorithm can be
    59   /// can be given using separate functions, and the algorithm can be
    59   /// executed using the \ref run() function. If some parameters are not
    60   /// executed using the \ref run() function. If some parameters are not
    60   /// specified, then default values will be used.
    61   /// specified, then default values will be used.
   114     ///
   115     ///
   115     /// Enum type containing constants for selecting the used method
   116     /// Enum type containing constants for selecting the used method
   116     /// for the \ref run() function.
   117     /// for the \ref run() function.
   117     ///
   118     ///
   118     /// \ref CycleCanceling provides three different cycle-canceling
   119     /// \ref CycleCanceling provides three different cycle-canceling
   119     /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
   120     /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
   120     /// is used, which is by far the most efficient and the most robust.
   121     /// is used, which is by far the most efficient and the most robust.
   121     /// However, the other methods can be selected using the \ref run()
   122     /// However, the other methods can be selected using the \ref run()
   122     /// function with the proper parameter.
   123     /// function with the proper parameter.
   123     enum Method {
   124     enum Method {
   124       /// A simple cycle-canceling method, which uses the
   125       /// A simple cycle-canceling method, which uses the
   125       /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
   126       /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
   126       /// number for detecting negative cycles in the residual network.
   127       /// cycles in the residual network.
       
   128       /// The number of Bellman-Ford iterations is bounded by a successively
       
   129       /// increased limit.
   127       SIMPLE_CYCLE_CANCELING,
   130       SIMPLE_CYCLE_CANCELING,
   128       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
   131       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
   129       /// well-known strongly polynomial method
   132       /// well-known strongly polynomial method
   130       /// \ref goldberg89cyclecanceling. It improves along a
   133       /// \ref goldberg89cyclecanceling. It improves along a
   131       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
   134       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
   132       /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
   135       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
   133       MINIMUM_MEAN_CYCLE_CANCELING,
   136       MINIMUM_MEAN_CYCLE_CANCELING,
   134       /// The "Cancel And Tighten" algorithm, which can be viewed as an
   137       /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
   135       /// improved version of the previous method
   138       /// improved version of the previous method
   136       /// \ref goldberg89cyclecanceling.
   139       /// \ref goldberg89cyclecanceling.
   137       /// It is faster both in theory and in practice, its running time
   140       /// It is faster both in theory and in practice, its running time
   138       /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
   141       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
   139       CANCEL_AND_TIGHTEN
   142       CANCEL_AND_TIGHTEN
   140     };
   143     };
   141 
   144 
   142   private:
   145   private:
   143 
   146 
   608     /// \pre \ref run() must be called before using this function.
   611     /// \pre \ref run() must be called before using this function.
   609     Value flow(const Arc& a) const {
   612     Value flow(const Arc& a) const {
   610       return _res_cap[_arc_idb[a]];
   613       return _res_cap[_arc_idb[a]];
   611     }
   614     }
   612 
   615 
   613     /// \brief Return the flow map (the primal solution).
   616     /// \brief Copy the flow values (the primal solution) into the
       
   617     /// given map.
   614     ///
   618     ///
   615     /// This function copies the flow value on each arc into the given
   619     /// This function copies the flow value on each arc into the given
   616     /// map. The \c Value type of the algorithm must be convertible to
   620     /// map. The \c Value type of the algorithm must be convertible to
   617     /// the \c Value type of the map.
   621     /// the \c Value type of the map.
   618     ///
   622     ///
   632     /// \pre \ref run() must be called before using this function.
   636     /// \pre \ref run() must be called before using this function.
   633     Cost potential(const Node& n) const {
   637     Cost potential(const Node& n) const {
   634       return static_cast<Cost>(_pi[_node_id[n]]);
   638       return static_cast<Cost>(_pi[_node_id[n]]);
   635     }
   639     }
   636 
   640 
   637     /// \brief Return the potential map (the dual solution).
   641     /// \brief Copy the potential values (the dual solution) into the
       
   642     /// given map.
   638     ///
   643     ///
   639     /// This function copies the potential (dual value) of each node
   644     /// This function copies the potential (dual value) of each node
   640     /// into the given map.
   645     /// into the given map.
   641     /// The \c Cost type of the algorithm must be convertible to the
   646     /// The \c Cost type of the algorithm must be convertible to the
   642     /// \c Value type of the map.
   647     /// \c Value type of the map.
   952         // Rebuild the residual network
   957         // Rebuild the residual network
   953         buildResidualNetwork();
   958         buildResidualNetwork();
   954       }
   959       }
   955     }
   960     }
   956 
   961 
   957     // Execute the "Cancel And Tighten" method
   962     // Execute the "Cancel-and-Tighten" method
   958     void startCancelAndTighten() {
   963     void startCancelAndTighten() {
   959       // Constants for the min mean cycle computations
   964       // Constants for the min mean cycle computations
   960       const double LIMIT_FACTOR = 1.0;
   965       const double LIMIT_FACTOR = 1.0;
   961       const int MIN_LIMIT = 5;
   966       const int MIN_LIMIT = 5;
   962 
   967