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); |