equal
deleted
inserted
replaced
120 }; |
120 }; |
121 |
121 |
122 enum StatusEnum { |
122 enum StatusEnum { |
123 AFTER_NOTHING, |
123 AFTER_NOTHING, |
124 AFTER_AUGMENTING, |
124 AFTER_AUGMENTING, |
|
125 AFTER_FAST_AUGMENTING, |
125 AFTER_PRE_FLOW_PHASE_1, |
126 AFTER_PRE_FLOW_PHASE_1, |
126 AFTER_PRE_FLOW_PHASE_2 |
127 AFTER_PRE_FLOW_PHASE_2 |
127 }; |
128 }; |
128 |
129 |
129 /// Don not needle this flag only if necessary. |
130 /// Don not needle this flag only if necessary. |
263 /// for MinCut computation |
264 /// for MinCut computation |
264 template<typename _CutMap> |
265 template<typename _CutMap> |
265 void actMinCut(_CutMap& M) const { |
266 void actMinCut(_CutMap& M) const { |
266 NodeIt v; |
267 NodeIt v; |
267 switch (status) { |
268 switch (status) { |
268 case AFTER_PRE_FLOW_PHASE_1: |
269 case AFTER_PRE_FLOW_PHASE_1: |
269 for(g->first(v); g->valid(v); g->next(v)) { |
270 for(g->first(v); g->valid(v); g->next(v)) { |
270 if (level[v] < n) { |
271 if (level[v] < n) { |
271 M.set(v, false); |
272 M.set(v, false); |
272 } else { |
273 } else { |
273 M.set(v, true); |
274 M.set(v, true); |
274 } |
275 } |
275 } |
276 } |
276 break; |
277 break; |
277 case AFTER_PRE_FLOW_PHASE_2: |
278 case AFTER_PRE_FLOW_PHASE_2: |
278 case AFTER_NOTHING: |
279 case AFTER_NOTHING: |
279 minMinCut(M); |
280 minMinCut(M); |
280 break; |
281 break; |
281 case AFTER_AUGMENTING: |
282 case AFTER_AUGMENTING: |
282 for(g->first(v); g->valid(v); g->next(v)) { |
283 for(g->first(v); g->valid(v); g->next(v)) { |
283 if (level[v]) { |
284 if (level[v]) { |
|
285 M.set(v, true); |
|
286 } else { |
|
287 M.set(v, false); |
|
288 } |
|
289 } |
|
290 break; |
|
291 case AFTER_FAST_AUGMENTING: |
|
292 for(g->first(v); g->valid(v); g->next(v)) { |
|
293 if (level[v]==number_of_augmentations) { |
284 M.set(v, true); |
294 M.set(v, true); |
285 } else { |
295 } else { |
286 M.set(v, false); |
296 M.set(v, false); |
287 } |
297 } |
288 } |
298 } |
942 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2() |
952 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2() |
943 { |
953 { |
944 ResGW res_graph(*g, *capacity, *flow); |
954 ResGW res_graph(*g, *capacity, *flow); |
945 bool _augment=false; |
955 bool _augment=false; |
946 |
956 |
947 if (status!=AFTER_AUGMENTING) { |
957 if (status!=AFTER_FAST_AUGMENTING) { |
948 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 3*n); |
958 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); |
949 number_of_augmentations=3*n+1; |
959 number_of_augmentations=1; |
950 } else { |
960 } else { |
951 ++number_of_augmentations; |
961 ++number_of_augmentations; |
952 } |
962 } |
953 TrickyReachedMap<ReachedMap> |
963 TrickyReachedMap<ReachedMap> |
954 tricky_reached_map(level, number_of_augmentations); |
964 tricky_reached_map(level, number_of_augmentations); |
989 res_graph.augment(e, augment_value); |
999 res_graph.augment(e, augment_value); |
990 n=res_graph.tail(e); |
1000 n=res_graph.tail(e); |
991 } |
1001 } |
992 } |
1002 } |
993 |
1003 |
994 status=AFTER_AUGMENTING; |
1004 status=AFTER_FAST_AUGMENTING; |
995 return _augment; |
1005 return _augment; |
996 } |
1006 } |
997 |
1007 |
998 |
1008 |
999 template <typename Graph, typename Num, typename CapMap, typename FlowMap> |
1009 template <typename Graph, typename Num, typename CapMap, typename FlowMap> |