43 ///constructor. It is possible to change these quantities using the |
43 ///constructor. It is possible to change these quantities using the |
44 ///functions \ref setSource, \ref setTarget, \ref setCap and \ref |
44 ///functions \ref setSource, \ref setTarget, \ref setCap and \ref |
45 ///setFlow. |
45 ///setFlow. |
46 /// |
46 /// |
47 ///After running \ref hugo::Preflow::phase1() "phase1()" |
47 ///After running \ref hugo::Preflow::phase1() "phase1()" |
48 ///or \ref hugo::Preflow::run() "run()", the actual flow |
48 ///or \ref hugo::Preflow::run() "run()", the maximal flow |
49 ///value can be obtained by calling \ref flowValue(). The minimum |
49 ///value can be obtained by calling \ref flowValue(). The minimum |
50 ///value cut can be written into a <tt>bool</tt> node map by |
50 ///value cut can be written into a <tt>bool</tt> node map by |
51 ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes |
51 ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes |
52 ///the inclusionwise minimum and maximum of the minimum value cuts, |
52 ///the inclusionwise minimum and maximum of the minimum value cuts, |
53 ///resp.) |
53 ///resp.) |
169 run(); |
169 run(); |
170 } |
170 } |
171 |
171 |
172 ///Runs the first phase of the preflow algorithm. |
172 ///Runs the first phase of the preflow algorithm. |
173 |
173 |
174 ///The preflow algorithm consists of two phases, this method runs the |
174 ///The preflow algorithm consists of two phases, this method runs |
175 ///first phase. After the first phase the maximum flow value and a |
175 ///the first phase. After the first phase the maximum flow value |
176 ///minimum value cut can already be computed, though a maximum flow |
176 ///and a minimum value cut can already be computed, though a |
177 ///is not yet obtained. So after calling this method \ref flowValue |
177 ///maximum flow is not yet obtained. So after calling this method |
178 ///and \ref minCut gives proper results. |
178 ///\ref flowValue returns the value of a maximum flow and \ref |
179 ///\warning \ref minMinCut and \ref maxMinCut do not |
179 ///minCut returns a minimum cut. |
180 ///give minimum value cuts unless calling \ref phase2. |
180 ///\warning \ref minMinCut and \ref maxMinCut do not give minimum |
181 ///\pre The starting flow must be |
181 ///value cuts unless calling \ref phase2. |
182 /// - a constant zero flow if \c fp is \c ZERO_FLOW, |
182 ///\pre The starting flow must be |
183 /// - an arbitary flow if \c fp is \c GEN_FLOW, |
183 ///- a constant zero flow if \c fp is \c ZERO_FLOW, |
184 /// - an arbitary preflow if \c fp is \c PRE_FLOW, |
184 ///- an arbitary flow if \c fp is \c GEN_FLOW, |
185 /// - any map if \c fp is NO_FLOW. |
185 ///- an arbitary preflow if \c fp is \c PRE_FLOW, |
|
186 ///- any map if \c fp is NO_FLOW. |
186 void phase1(FlowEnum fp) |
187 void phase1(FlowEnum fp) |
187 { |
188 { |
188 flow_prop=fp; |
189 flow_prop=fp; |
189 phase1(); |
190 phase1(); |
190 } |
191 } |
191 |
192 |
192 |
193 |
193 ///Runs the first phase of the preflow algorithm. |
194 ///Runs the first phase of the preflow algorithm. |
194 |
195 |
195 ///The preflow algorithm consists of two phases, this method runs the |
196 ///The preflow algorithm consists of two phases, this method runs |
196 ///first phase. After the first phase the maximum flow value and a |
197 ///the first phase. After the first phase the maximum flow value |
197 ///minimum value cut can already be computed, though a maximum flow |
198 ///and a minimum value cut can already be computed, though a |
198 ///is not yet obtained. So after calling this method \ref flowValue |
199 ///maximum flow is not yet obtained. So after calling this method |
199 ///and \ref MinCut() gives proper results. |
200 ///\ref flowValue returns the value of a maximum flow and \ref |
|
201 ///minCut returns a minimum cut. |
200 ///\warning \ref minCut(), \ref minMinCut() and \ref maxMinCut() do not |
202 ///\warning \ref minCut(), \ref minMinCut() and \ref maxMinCut() do not |
201 ///give minimum value cuts unless calling \ref phase2(). |
203 ///give minimum value cuts unless calling \ref phase2(). |
202 void phase1() |
204 void phase1() |
203 { |
205 { |
204 int heur0=(int)(H0*n); //time while running 'bound decrease' |
206 int heur0=(int)(H0*n); //time while running 'bound decrease' |
273 |
275 |
274 |
276 |
275 ///Runs the second phase of the preflow algorithm. |
277 ///Runs the second phase of the preflow algorithm. |
276 |
278 |
277 ///The preflow algorithm consists of two phases, this method runs |
279 ///The preflow algorithm consists of two phases, this method runs |
278 ///the second phase. After calling \ref phase1 and then |
280 ///the second phase. After calling \ref phase1 and then \ref |
279 ///\ref phase2 the methods \ref flowValue, \ref minCut, |
281 ///phase2, \ref flow contains a maximum flow, \ref flowValue |
280 ///\ref minMinCut and \ref maxMinCut give proper results. |
282 ///returns the value of a maximum flow, \ref minCut returns a |
281 ///\pre \ref phase1 must be called before. |
283 ///minimum cut, while the methods \ref minMinCut and \ref |
|
284 ///maxMinCut return the inclusionwise minimum and maximum cuts of |
|
285 ///minimum value, resp. \pre \ref phase1 must be called before. |
282 void phase2() |
286 void phase2() |
283 { |
287 { |
284 |
288 |
285 int k=n-2; //bound on the highest level under n containing a node |
289 int k=n-2; //bound on the highest level under n containing a node |
286 int b=k; //bound on the highest level under n of an active node |
290 int b=k; //bound on the highest level under n of an active node |