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