14 namespace hugo { |
14 namespace hugo { |
15 |
15 |
16 /// \addtogroup flowalgs |
16 /// \addtogroup flowalgs |
17 /// @{ |
17 /// @{ |
18 |
18 |
19 ///Preflow algorithms class. |
19 ///%Preflow algorithms class. |
20 |
20 |
21 ///This class provides an implementation of the \e preflow \e |
21 ///This class provides an implementation of the \e preflow \e |
22 ///algorithm producing a flow of maximum value in a directed |
22 ///algorithm producing a flow of maximum value in a directed |
23 ///graph. The preflow algorithms are the fastest max flow algorithms |
23 ///graph. The preflow algorithms are the fastest max flow algorithms |
24 ///up-to-date. The \e source node, the \e target node, the \e |
24 ///up to now. The \e source node, the \e target node, the \e |
25 ///capacity of the edges and the \e starting \e flow value of the |
25 ///capacity of the edges and the \e starting \e flow value of the |
26 ///edges should be passed to the algorithm through the |
26 ///edges should be passed to the algorithm through the |
27 ///constructor. It is possible to change these quantities using the |
27 ///constructor. It is possible to change these quantities using the |
28 ///functions \ref setSource, \ref setTarget, \ref setCap and \ref |
28 ///functions \ref setSource, \ref setTarget, \ref setCap and \ref |
29 ///setFlow. |
29 ///setFlow. |
30 /// |
30 /// |
31 ///After running \c phase1 or \c preflow, the actual flow |
31 ///After running \ref phase1() or \ref preflow(), the actual flow |
32 ///value can be obtained by calling \ref flowValue(). The minimum |
32 ///value can be obtained by calling \ref flowValue(). The minimum |
33 ///value cut can be written into a \c node map of \c bools by |
33 ///value cut can be written into a <tt>bool</tt> node map by |
34 ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes |
34 ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes |
35 ///the inclusionwise minimum and maximum of the minimum value cuts, |
35 ///the inclusionwise minimum and maximum of the minimum value cuts, |
36 ///resp.) |
36 ///resp.) |
37 /// |
37 /// |
38 ///\param Graph The directed graph type the algorithm runs on. |
38 ///\param Graph The directed graph type the algorithm runs on. |
39 ///\param Num The number type of the capacities and the flow values. |
39 ///\param Num The number type of the capacities and the flow values. |
155 ///The preflow algorithm consists of two phases, this method runs the |
156 ///The preflow algorithm consists of two phases, this method runs the |
156 ///first phase. After the first phase the maximum flow value and a |
157 ///first phase. After the first phase the maximum flow value and a |
157 ///minimum value cut can already be computed, though a maximum flow |
158 ///minimum value cut can already be computed, though a maximum flow |
158 ///is not yet obtained. So after calling this method \ref flowValue |
159 ///is not yet obtained. So after calling this method \ref flowValue |
159 ///and \ref minCut gives proper results. |
160 ///and \ref minCut gives proper results. |
160 ///\warning: \ref minMinCut and \ref maxMinCut do not |
161 ///\warning \ref minMinCut and \ref maxMinCut do not |
161 ///give minimum value cuts unless calling \ref phase2. |
162 ///give minimum value cuts unless calling \ref phase2. |
162 ///\pre The starting flow must be |
163 ///\pre The starting flow must be |
163 /// - a constant zero flow if \c fp is \c ZERO_FLOW, |
164 /// - a constant zero flow if \c fp is \c ZERO_FLOW, |
164 /// - an arbitary flow if \c fp is \c GEN_FLOW, |
165 /// - an arbitary flow if \c fp is \c GEN_FLOW, |
165 /// - an arbitary preflow if \c fp is \c PRE_FLOW, |
166 /// - an arbitary preflow if \c fp is \c PRE_FLOW, |
176 ///The preflow algorithm consists of two phases, this method runs the |
177 ///The preflow algorithm consists of two phases, this method runs the |
177 ///first phase. After the first phase the maximum flow value and a |
178 ///first phase. After the first phase the maximum flow value and a |
178 ///minimum value cut can already be computed, though a maximum flow |
179 ///minimum value cut can already be computed, though a maximum flow |
179 ///is not yet obtained. So after calling this method \ref flowValue |
180 ///is not yet obtained. So after calling this method \ref flowValue |
180 ///and \ref actMinCut gives proper results. |
181 ///and \ref actMinCut gives proper results. |
181 ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not |
182 ///\warning \ref minCut, \ref minMinCut and \ref maxMinCut do not |
182 ///give minimum value cuts unless calling \ref phase2. |
183 ///give minimum value cuts unless calling \ref phase2. |
183 void phase1() |
184 void phase1() |
184 { |
185 { |
185 int heur0=(int)(H0*n); //time while running 'bound decrease' |
186 int heur0=(int)(H0*n); //time while running 'bound decrease' |
186 int heur1=(int)(H1*n); //time while running 'highest label' |
187 int heur1=(int)(H1*n); //time while running 'highest label' |