Changeset 647:19dd325da0e8 in lemon0.x for src/work/jacint/max_flow.h
 Timestamp:
 05/19/04 18:09:38 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@847
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/max_flow.h
r640 r647 26 26 ///maximum value in a directed graph. The \e source node, the \e 27 27 ///target node, the \e capacity of the edges and the \e starting \e 28 ///flow value of the edges canbe passed to the algorithm through the28 ///flow value of the edges should be passed to the algorithm through the 29 29 ///constructor. It is possible to change these quantities using the 30 30 ///functions \ref resetSource, \ref resetTarget, \ref resetCap and 31 31 ///\ref resetFlow. Before any subsequent runs of any algorithm of 32 ///the class \ref resetFlow should be called , otherwise it will33 ///start from a maximum flow. 34 ///After running an algorithm of the class, the maximum value of a35 /// valuecan be obtained by calling \ref flowValue(). The minimum32 ///the class \ref resetFlow should be called. 33 34 ///After running an algorithm of the class, the actual flow value 35 ///can be obtained by calling \ref flowValue(). The minimum 36 36 ///value cut can be written into a \c node map of \c bools by 37 37 ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes … … 40 40 ///\param Graph The directed graph type the algorithm runs on. 41 41 ///\param Num The number type of the capacities and the flow values. 42 ///\param CapMap The type of the capacity map.43 ///\param FlowMap The type of the flow map.42 ///\param CapMap The capacity map type. 43 ///\param FlowMap The flow map type. 44 44 ///\author Marton Makai, Jacint Szabo 45 45 template <typename Graph, typename Num, … … 112 112 /// \c NO_FLOW: indicates an unspecified edge map. \ref flow will be 113 113 ///set to the constant zero flow in the beginning of the algorithm in this case. 114 enum flowEnum{114 enum FlowEnum{ 115 115 ZERO_FLOW, 116 116 GEN_FLOW, … … 119 119 }; 120 120 121 enum StatusEnum { 122 AFTER_NOTHING, 123 AFTER_AUGMENTING, 124 AFTER_PRE_FLOW_PHASE_1, 125 AFTER_PRE_FLOW_PHASE_2 126 }; 127 128 /// Don not needle this flag only if necessary. 129 StatusEnum status; 130 int number_of_augmentations; 131 132 133 template<typename IntMap> 134 class TrickyReachedMap { 135 protected: 136 IntMap* map; 137 int* number_of_augmentations; 138 public: 139 TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : 140 map(&_map), number_of_augmentations(&_number_of_augmentations) { } 141 void set(const Node& n, bool b) { 142 map>set(n, *number_of_augmentations); 143 } 144 bool operator[](const Node& n) const { 145 return (*map)[n]==*number_of_augmentations; 146 } 147 }; 148 121 149 MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 122 150 FlowMap& _flow) : 123 151 g(&_G), s(_s), t(_t), capacity(&_capacity), 124 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} 152 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), 153 status(AFTER_NOTHING), number_of_augmentations(0) { } 125 154 126 155 ///Runs a maximum flow algorithm. … … 133 162 ///  an arbitary preflow if \c fe is \c PRE_FLOW, 134 163 ///  any map if \c fe is NO_FLOW. 135 void run( flowEnum fe=ZERO_FLOW) {164 void run(FlowEnum fe=ZERO_FLOW) { 136 165 preflow(fe); 137 166 } 138 167 139 168 140 169 ///Runs a preflow algorithm. 141 170 … … 147 176 ///  an arbitary preflow if \c fe is \c PRE_FLOW, 148 177 ///  any map if \c fe is NO_FLOW. 149 void preflow( flowEnum fe) {178 void preflow(FlowEnum fe) { 150 179 preflowPhase1(fe); 151 180 preflowPhase2(); … … 174 203 ///  an arbitary preflow if \c fe is \c PRE_FLOW, 175 204 ///  any map if \c fe is NO_FLOW. 176 void preflowPhase1( flowEnum fe);205 void preflowPhase1(FlowEnum fe); 177 206 178 207 ///Runs the second phase of the preflow algorithm. … … 190 219 /// The return value shows if the augmentation was succesful. 191 220 bool augmentOnShortestPath(); 221 bool augmentOnShortestPath2(); 192 222 193 223 /// Starting from a flow, this method searches for an augmenting blocking … … 208 238 /// overflow of the target node \ref t. 209 239 /// It can be called already after running \ref preflowPhase1. 210 Num flowValue() {240 Num flowValue() const { 211 241 Num a=0; 212 242 FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e]; … … 229 259 /// for MinCut computation 230 260 template<typename _CutMap> 231 void actMinCut(_CutMap& M) {261 void actMinCut(_CutMap& M) const { 232 262 NodeIt v; 233 for(g>first(v); g>valid(v); g>next(v)) { 234 if ( level[v] < n ) { 235 M.set(v,false); 236 } else { 237 M.set(v,true); 238 } 263 switch (status) { 264 case AFTER_PRE_FLOW_PHASE_1: 265 for(g>first(v); g>valid(v); g>next(v)) { 266 if (level[v] < n) { 267 M.set(v, false); 268 } else { 269 M.set(v, true); 270 } 271 } 272 break; 273 case AFTER_PRE_FLOW_PHASE_2: 274 case AFTER_NOTHING: 275 minMinCut(M); 276 break; 277 case AFTER_AUGMENTING: 278 for(g>first(v); g>valid(v); g>next(v)) { 279 if (level[v]) { 280 M.set(v, true); 281 } else { 282 M.set(v, false); 283 } 284 } 285 break; 239 286 } 240 287 } … … 248 295 ///\pre \c flow must be a maximum flow. 249 296 template<typename _CutMap> 250 void minMinCut(_CutMap& M) { 251 297 void minMinCut(_CutMap& M) const { 252 298 std::queue<Node> queue; 253 299 … … 287 333 ///\pre \c flow must be a maximum flow. 288 334 template<typename _CutMap> 289 void maxMinCut(_CutMap& M) {335 void maxMinCut(_CutMap& M) const { 290 336 291 337 NodeIt v; … … 329 375 ///\pre \c flow must be a maximum flow. 330 376 template<typename CutMap> 331 void minCut(CutMap& M) { minMinCut(M); }377 void minCut(CutMap& M) const { minMinCut(M); } 332 378 333 379 ///Resets the source node to \c _s. … … 335 381 ///Resets the source node to \c _s. 336 382 /// 337 void resetSource(Node _s) { s=_s; }383 void resetSource(Node _s) { s=_s; status=AFTER_NOTHING; } 338 384 339 385 ///Resets the target node to \c _t. … … 341 387 ///Resets the target node to \c _t. 342 388 /// 343 void resetTarget(Node _t) { t=_t; }389 void resetTarget(Node _t) { t=_t; status=AFTER_NOTHING; } 344 390 345 391 /// Resets the edge map of the capacities to _cap. … … 347 393 /// Resets the edge map of the capacities to _cap. 348 394 /// 349 void resetCap(const CapMap& _cap) { capacity=&_cap; }395 void resetCap(const CapMap& _cap) { capacity=&_cap; status=AFTER_NOTHING; } 350 396 351 397 /// Resets the edge map of the flows to _flow. … … 353 399 /// Resets the edge map of the flows to _flow. 354 400 /// 355 void resetFlow(FlowMap& _flow) { flow=&_flow; }401 void resetFlow(FlowMap& _flow) { flow=&_flow; status=AFTER_NOTHING; } 356 402 357 403 … … 435 481 436 482 437 void preflowPreproc( flowEnum fe, VecStack& active,483 void preflowPreproc(FlowEnum fe, VecStack& active, 438 484 VecNode& level_list, NNMap& left, NNMap& right) 439 485 { … … 639 685 dist.set(n, a); 640 686 } 641 int operator[](const typename MapGraphWrapper::Node& n) 642 { return dist[n]; } 687 int operator[](const typename MapGraphWrapper::Node& n) const { 688 return dist[n]; 689 } 643 690 // int get(const typename MapGraphWrapper::Node& n) const { 644 691 // return dist[n]; } … … 654 701 655 702 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 656 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe)703 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1(FlowEnum fe) 657 704 { 658 705 … … 767 814 } 768 815 } 816 817 status=AFTER_PRE_FLOW_PHASE_1; 769 818 } 770 819 … … 831 880 } // if stack[b] is nonempty 832 881 } // while(true) 882 883 status=AFTER_PRE_FLOW_PHASE_2; 833 884 } 834 885 … … 879 930 } 880 931 932 status=AFTER_AUGMENTING; 881 933 return _augment; 882 934 } 883 935 884 936 885 886 887 937 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 938 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2() 939 { 940 ResGW res_graph(*g, *capacity, *flow); 941 bool _augment=false; 942 943 if (status!=AFTER_AUGMENTING) { 944 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 1); 945 number_of_augmentations=0; 946 } else { 947 ++number_of_augmentations; 948 } 949 TrickyReachedMap<ReachedMap> 950 tricky_reached_map(level, number_of_augmentations); 951 //ReachedMap level(res_graph); 952 // FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 953 BfsIterator<ResGW, TrickyReachedMap<ReachedMap> > 954 bfs(res_graph, tricky_reached_map); 955 bfs.pushAndSetReached(s); 956 957 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 958 pred.set(s, INVALID); 959 960 typename ResGW::template NodeMap<Num> free(res_graph); 961 962 //searching for augmenting path 963 while ( !bfs.finished() ) { 964 ResGWOutEdgeIt e=bfs; 965 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 966 Node v=res_graph.tail(e); 967 Node w=res_graph.head(e); 968 pred.set(w, e); 969 if (res_graph.valid(pred[v])) { 970 free.set(w, std::min(free[v], res_graph.resCap(e))); 971 } else { 972 free.set(w, res_graph.resCap(e)); 973 } 974 if (res_graph.head(e)==t) { _augment=true; break; } 975 } 976 977 ++bfs; 978 } //end of searching augmenting path 979 980 if (_augment) { 981 Node n=t; 982 Num augment_value=free[t]; 983 while (res_graph.valid(pred[n])) { 984 ResGWEdge e=pred[n]; 985 res_graph.augment(e, augment_value); 986 n=res_graph.tail(e); 987 } 988 } 989 990 status=AFTER_AUGMENTING; 991 return _augment; 992 } 888 993 889 994 … … 1000 1105 } 1001 1106 1107 status=AFTER_AUGMENTING; 1002 1108 return _augment; 1003 1109 } … … 1130 1236 } //while (__augment) 1131 1237 1238 status=AFTER_AUGMENTING; 1132 1239 return _augment; 1133 1240 }
Note: See TracChangeset
for help on using the changeset viewer.