lemon/network_simplex.h
changeset 809 22bb98ca0101
parent 755 134852d7fb0a
parent 786 e20173729589
child 811 fe80a8145653
equal deleted inserted replaced
20:63eac285a825 22:03a38fee3dad
    48   /// It is one of the most efficient solution methods.
    48   /// It is one of the most efficient solution methods.
    49   ///
    49   ///
    50   /// In general this class is the fastest implementation available
    50   /// In general this class is the fastest implementation available
    51   /// in LEMON for the minimum cost flow problem.
    51   /// in LEMON for the minimum cost flow problem.
    52   /// Moreover it supports both directions of the supply/demand inequality
    52   /// Moreover it supports both directions of the supply/demand inequality
    53   /// constraints. For more information see \ref SupplyType.
    53   /// constraints. For more information, see \ref SupplyType.
    54   ///
    54   ///
    55   /// Most of the parameters of the problem (except for the digraph)
    55   /// Most of the parameters of the problem (except for the digraph)
    56   /// can be given using separate functions, and the algorithm can be
    56   /// can be given using separate functions, and the algorithm can be
    57   /// executed using the \ref run() function. If some parameters are not
    57   /// executed using the \ref run() function. If some parameters are not
    58   /// specified, then default values will be used.
    58   /// specified, then default values will be used.
    59   ///
    59   ///
    60   /// \tparam GR The digraph type the algorithm runs on.
    60   /// \tparam GR The digraph type the algorithm runs on.
    61   /// \tparam V The value type used for flow amounts, capacity bounds
    61   /// \tparam V The value type used for flow amounts, capacity bounds
    62   /// and supply values in the algorithm. By default it is \c int.
    62   /// and supply values in the algorithm. By default, it is \c int.
    63   /// \tparam C The value type used for costs and potentials in the
    63   /// \tparam C The value type used for costs and potentials in the
    64   /// algorithm. By default it is the same as \c V.
    64   /// algorithm. By default, it is the same as \c V.
    65   ///
    65   ///
    66   /// \warning Both value types must be signed and all input data must
    66   /// \warning Both value types must be signed and all input data must
    67   /// be integer.
    67   /// be integer.
    68   ///
    68   ///
    69   /// \note %NetworkSimplex provides five different pivot rule
    69   /// \note %NetworkSimplex provides five different pivot rule
    70   /// implementations, from which the most efficient one is used
    70   /// implementations, from which the most efficient one is used
    71   /// by default. For more information see \ref PivotRule.
    71   /// by default. For more information, see \ref PivotRule.
    72   template <typename GR, typename V = int, typename C = V>
    72   template <typename GR, typename V = int, typename C = V>
    73   class NetworkSimplex
    73   class NetworkSimplex
    74   {
    74   {
    75   public:
    75   public:
    76 
    76 
   122     /// the \ref run() function.
   122     /// the \ref run() function.
   123     ///
   123     ///
   124     /// \ref NetworkSimplex provides five different pivot rule
   124     /// \ref NetworkSimplex provides five different pivot rule
   125     /// implementations that significantly affect the running time
   125     /// implementations that significantly affect the running time
   126     /// of the algorithm.
   126     /// of the algorithm.
   127     /// By default \ref BLOCK_SEARCH "Block Search" is used, which
   127     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
   128     /// proved to be the most efficient and the most robust on various
   128     /// proved to be the most efficient and the most robust on various
   129     /// test inputs according to our benchmark tests.
   129     /// test inputs according to our benchmark tests.
   130     /// However another pivot rule can be selected using the \ref run()
   130     /// However, another pivot rule can be selected using the \ref run()
   131     /// function with the proper parameter.
   131     /// function with the proper parameter.
   132     enum PivotRule {
   132     enum PivotRule {
   133 
   133 
   134       /// The First Eligible pivot rule.
   134       /// The \e First \e Eligible pivot rule.
   135       /// The next eligible arc is selected in a wraparound fashion
   135       /// The next eligible arc is selected in a wraparound fashion
   136       /// in every iteration.
   136       /// in every iteration.
   137       FIRST_ELIGIBLE,
   137       FIRST_ELIGIBLE,
   138 
   138 
   139       /// The Best Eligible pivot rule.
   139       /// The \e Best \e Eligible pivot rule.
   140       /// The best eligible arc is selected in every iteration.
   140       /// The best eligible arc is selected in every iteration.
   141       BEST_ELIGIBLE,
   141       BEST_ELIGIBLE,
   142 
   142 
   143       /// The Block Search pivot rule.
   143       /// The \e Block \e Search pivot rule.
   144       /// A specified number of arcs are examined in every iteration
   144       /// A specified number of arcs are examined in every iteration
   145       /// in a wraparound fashion and the best eligible arc is selected
   145       /// in a wraparound fashion and the best eligible arc is selected
   146       /// from this block.
   146       /// from this block.
   147       BLOCK_SEARCH,
   147       BLOCK_SEARCH,
   148 
   148 
   149       /// The Candidate List pivot rule.
   149       /// The \e Candidate \e List pivot rule.
   150       /// In a major iteration a candidate list is built from eligible arcs
   150       /// In a major iteration a candidate list is built from eligible arcs
   151       /// in a wraparound fashion and in the following minor iterations
   151       /// in a wraparound fashion and in the following minor iterations
   152       /// the best eligible arc is selected from this list.
   152       /// the best eligible arc is selected from this list.
   153       CANDIDATE_LIST,
   153       CANDIDATE_LIST,
   154 
   154 
   155       /// The Altering Candidate List pivot rule.
   155       /// The \e Altering \e Candidate \e List pivot rule.
   156       /// It is a modified version of the Candidate List method.
   156       /// It is a modified version of the Candidate List method.
   157       /// It keeps only the several best eligible arcs from the former
   157       /// It keeps only the several best eligible arcs from the former
   158       /// candidate list and extends this list in every iteration.
   158       /// candidate list and extends this list in every iteration.
   159       ALTERING_LIST
   159       ALTERING_LIST
   160     };
   160     };
   810     ///
   810     ///
   811     /// This function sets the type of the supply/demand constraints.
   811     /// This function sets the type of the supply/demand constraints.
   812     /// If it is not used before calling \ref run(), the \ref GEQ supply
   812     /// If it is not used before calling \ref run(), the \ref GEQ supply
   813     /// type will be used.
   813     /// type will be used.
   814     ///
   814     ///
   815     /// For more information see \ref SupplyType.
   815     /// For more information, see \ref SupplyType.
   816     ///
   816     ///
   817     /// \return <tt>(*this)</tt>
   817     /// \return <tt>(*this)</tt>
   818     NetworkSimplex& supplyType(SupplyType supply_type) {
   818     NetworkSimplex& supplyType(SupplyType supply_type) {
   819       _stype = supply_type;
   819       _stype = supply_type;
   820       return *this;
   820       return *this;
   842     ///
   842     ///
   843     /// This function can be called more than once. All the parameters
   843     /// This function can be called more than once. All the parameters
   844     /// that have been given are kept for the next call, unless
   844     /// that have been given are kept for the next call, unless
   845     /// \ref reset() is called, thus only the modified parameters
   845     /// \ref reset() is called, thus only the modified parameters
   846     /// have to be set again. See \ref reset() for examples.
   846     /// have to be set again. See \ref reset() for examples.
   847     /// However the underlying digraph must not be modified after this
   847     /// However, the underlying digraph must not be modified after this
   848     /// class have been constructed, since it copies and extends the graph.
   848     /// class have been constructed, since it copies and extends the graph.
   849     ///
   849     ///
   850     /// \param pivot_rule The pivot rule that will be used during the
   850     /// \param pivot_rule The pivot rule that will be used during the
   851     /// algorithm. For more information see \ref PivotRule.
   851     /// algorithm. For more information, see \ref PivotRule.
   852     ///
   852     ///
   853     /// \return \c INFEASIBLE if no feasible flow exists,
   853     /// \return \c INFEASIBLE if no feasible flow exists,
   854     /// \n \c OPTIMAL if the problem has optimal solution
   854     /// \n \c OPTIMAL if the problem has optimal solution
   855     /// (i.e. it is feasible and bounded), and the algorithm has found
   855     /// (i.e. it is feasible and bounded), and the algorithm has found
   856     /// optimal flow and node potentials (primal and dual solutions),
   856     /// optimal flow and node potentials (primal and dual solutions),
   871     /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
   871     /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
   872     ///
   872     ///
   873     /// It is useful for multiple run() calls. If this function is not
   873     /// It is useful for multiple run() calls. If this function is not
   874     /// used, all the parameters given before are kept for the next
   874     /// used, all the parameters given before are kept for the next
   875     /// \ref run() call.
   875     /// \ref run() call.
   876     /// However the underlying digraph must not be modified after this
   876     /// However, the underlying digraph must not be modified after this
   877     /// class have been constructed, since it copies and extends the graph.
   877     /// class have been constructed, since it copies and extends the graph.
   878     ///
   878     ///
   879     /// For example,
   879     /// For example,
   880     /// \code
   880     /// \code
   881     ///   NetworkSimplex<ListDigraph> ns(graph);
   881     ///   NetworkSimplex<ListDigraph> ns(graph);