Changeset 109:fc5982b39e10 in lemon-0.x for src
- Timestamp:
- 02/21/04 22:01:22 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@144
- Location:
- src/work/jacint
- Files:
-
- 12 added
- 4 deleted
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/preflow_hl2.h
r105 r109 4 4 by jacint. 5 5 Runs the highest label variant of the preflow push algorithm with 6 running time O(n^2\sqrt(m)), with the 'empty level' and with the 7 heuristic that the bound b on the active nodes is not increased 8 only when b=0, when we put b=2*n-2. 9 10 'A' is a parameter for the empty_level heuristic 11 12 Member functions: 13 14 void run() : runs the algorithm 15 16 The following functions should be used after run() was already run. 17 18 T maxflow() : returns the value of a maximum flow 19 20 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 21 22 FlowMap allflow() : returns the fixed maximum flow x 23 24 void mincut(CutMap& M) : sets M to the characteristic vector of a 6 running time O(n^2\sqrt(m)). 7 8 Heuristics: 9 10 gap: we iterate through the nodes for finding the nodes above 11 the gap and under level n. So it is quite slow. 12 numb: we maintain the number of nodes in level i. 13 highest label 14 15 'A' is a parameter for the gap, we only upgrade the nodes to level n, 16 if the gap is under A*n. 17 18 The constructor runs the algorithm. 19 20 Members: 21 22 T maxFlow() : returns the value of a maximum flow 23 24 T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 25 26 FlowMap Flow() : returns the fixed maximum flow x 27 28 void minCut(CutMap& M) : sets M to the characteristic vector of a 25 29 minimum cut. M should be a map of bools initialized to false. 26 30 27 void min _mincut(CutMap& M) : sets M to the characteristic vector of the31 void minMinCut(CutMap& M) : sets M to the characteristic vector of the 28 32 minimum min cut. M should be a map of bools initialized to false. 29 33 30 void max _mincut(CutMap& M) : sets M to the characteristic vector of the34 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 31 35 maximum min cut. M should be a map of bools initialized to false. 32 36 … … 36 40 #define PREFLOW_HL2_H 37 41 38 #define A 142 #define A .9 39 43 40 44 #include <vector> … … 45 49 46 50 template <typename Graph, typename T, 47 typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>,48 typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >51 typename FlowMap=typename Graph::EdgeMap<T>, 52 typename CapMap=typename Graph::EdgeMap<T> > 49 53 class preflow_hl2 { 50 54 … … 65 69 66 70 preflow_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : 67 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } 68 69 70 void run() { 71 72 bool no_end=true; 71 G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 72 73 73 int n=G.nodeNum(); 74 74 int b=n-2; 75 75 /* 76 76 b is a bound on the highest level of an active node. 77 In the beginning it is at most n-2.78 77 */ 79 78 80 IntMaplevel(G,n);81 TMapexcess(G);82 79 typename Graph::NodeMap<int> level(G,n); 80 typename Graph::NodeMap<T> excess(G); 81 83 82 std::vector<int> numb(n); 84 83 /* … … 111 110 } 112 111 } 113 112 114 113 level.set(s,n); 115 114 … … 128 127 } 129 128 } 130 129 131 130 /* 132 131 End of preprocessing … … 134 133 135 134 136 137 135 /* 138 136 Push/relabel on the highest level active nodes. 139 */ 137 */ 140 138 /*While there exists an active node.*/ 141 139 while (b) { 142 if ( stack[b].empty() ) { 143 if ( b==1 ) { 144 if ( !no_end ) break; 145 else { 146 b=2*n-2; 147 no_end=false; 148 } 149 } 140 if ( stack[b].empty() ) { 150 141 --b; 151 } else { 152 153 no_end=true; 154 155 NodeIt w=stack[b].top(); //w is a highest label active node. 156 stack[b].pop(); 157 int lev=level.get(w); 158 int exc=excess.get(w); 159 int newlevel=2*n; //In newlevel we bound the next level of w. 160 161 // if ( level.get(w) < n ) { //Nem tudom ez mukodik-e 142 continue; 143 } 144 145 NodeIt w=stack[b].top(); 146 stack[b].pop(); 147 int lev=level.get(w); 148 T exc=excess.get(w); 149 int newlevel=2*n; //In newlevel we bound the next level of w. 150 162 151 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { 163 152 … … 173 162 /*v becomes active.*/ 174 163 175 intcap=capacity.get(e);176 intflo=flow.get(e);177 intremcap=cap-flo;164 T cap=capacity.get(e); 165 T flo=flow.get(e); 166 T remcap=cap-flo; 178 167 179 168 if ( remcap >= exc ) { … … 211 200 /*v becomes active.*/ 212 201 213 intflo=flow.get(e);202 T flo=flow.get(e); 214 203 215 204 if ( flo >= exc ) { … … 232 221 233 222 } // if w still has excess after the out edge for cycle 234 235 excess.set(w, exc); 223 224 excess.set(w, exc); 225 226 227 228 229 /* 230 Relabel 231 */ 232 233 if ( exc > 0 ) { 234 //now 'lev' is the old level of w 235 level.set(w,++newlevel); 236 236 237 238 /* 239 Relabel 240 */ 237 if ( lev < n ) { 238 --numb[lev]; 239 240 if ( !numb[lev] && lev < A*n ) { //If the level of w gets empty. 241 242 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 243 if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 244 } 245 for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 246 if ( newlevel < n ) newlevel=n; 247 } else { 248 if ( newlevel < n ) ++numb[newlevel]; 249 } 250 } 241 251 242 if ( exc > 0 ) { 243 //now 'lev' is the old level of w 244 level.set(w,++newlevel); 245 246 if ( lev < n ) { 247 --numb[lev]; 248 249 if ( !numb[lev] && lev < A*n ) { //If the level of w gets empty. 250 251 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 252 if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 253 } 254 for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 255 if ( newlevel < n ) newlevel=n; 256 } else { 257 if ( newlevel < n ) ++numb[newlevel]; 258 } 259 } 260 261 stack[newlevel].push(w); 262 263 } 264 265 } // if stack[b] is nonempty 266 252 stack[newlevel].push(w); 253 b=newlevel; 254 255 } 256 267 257 } // while(b) 268 269 258 259 270 260 value = excess.get(t); 271 261 /*Max flow value.*/ … … 282 272 */ 283 273 284 T max flow() {274 T maxFlow() { 285 275 return value; 286 276 } … … 289 279 290 280 /* 291 For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 281 For the maximum flow x found by the algorithm, 282 it returns the flow value on edge e, i.e. x(e). 292 283 */ 293 284 294 T flow onedge(EdgeIt e) {285 T flowOnEdge(const EdgeIt e) { 295 286 return flow.get(e); 296 287 } … … 302 293 */ 303 294 304 FlowMap allflow() {295 FlowMap Flow() { 305 296 return flow; 306 297 } … … 314 305 315 306 template<typename CutMap> 316 void min cut(CutMap& M) {307 void minCut(CutMap& M) { 317 308 318 309 std::queue<NodeIt> queue; … … 324 315 NodeIt w=queue.front(); 325 316 queue.pop(); 326 317 327 318 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 328 319 NodeIt v=G.head(e); … … 339 330 M.set(v, true); 340 331 } 341 } 332 } 342 333 343 334 } 344 345 335 } 346 336 … … 353 343 354 344 template<typename CutMap> 355 void max _mincut(CutMap& M) {345 void maxMinCut(CutMap& M) { 356 346 357 347 std::queue<NodeIt> queue; … … 390 380 391 381 template<typename CutMap> 392 void min _mincut(CutMap& M) {393 min cut(M);382 void minMinCut(CutMap& M) { 383 minCut(M); 394 384 } 395 385 … … 397 387 398 388 }; 399 }//namespace hugo389 }//namespace marci 400 390 #endif 401 391 -
src/work/jacint/preflow_hl3.h
r105 r109 3 3 preflow_hl3.h 4 4 by jacint. 5 Runs the highest label variant of the preflow push algorithm with 6 running time O(n^2\sqrt(m)), with the felszippantos 'empty level' 7 and with the two-phase heuristic: if there is no active node of 8 level at most n, then we go into phase 1, do a bfs 9 from s, and flow the excess back to s. 10 11 In phase 1 we shift everything downwards by n. 12 13 'A' is a parameter for the empty_level heuristic 14 15 Member functions: 16 17 void run() : runs the algorithm 18 19 The following functions should be used after run() was already run. 20 21 T maxflow() : returns the value of a maximum flow 22 23 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 24 25 FlowMap allflow() : returns the fixed maximum flow x 26 27 void mincut(CutMap& M) : sets M to the characteristic vector of a 5 6 Heuristics: 7 8 suck gap : if there is a gap, then we put all 9 nodes reachable from the relabelled node to level n 10 2 phase 11 highest label 12 13 The constructor runs the algorithm. 14 15 Members: 16 17 T maxFlow() : returns the value of a maximum flow 18 19 T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 20 21 FlowMap Flow() : returns the fixed maximum flow x 22 23 void minCut(CutMap& M) : sets M to the characteristic vector of a 28 24 minimum cut. M should be a map of bools initialized to false. 29 25 30 void min _mincut(CutMap& M) : sets M to the characteristic vector of the26 void minMinCut(CutMap& M) : sets M to the characteristic vector of the 31 27 minimum min cut. M should be a map of bools initialized to false. 32 28 33 void max _mincut(CutMap& M) : sets M to the characteristic vector of the29 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 34 30 maximum min cut. M should be a map of bools initialized to false. 35 31 … … 38 34 #ifndef PREFLOW_HL3_H 39 35 #define PREFLOW_HL3_H 40 41 #define A 142 36 43 37 #include <vector> … … 45 39 #include <queue> 46 40 41 #include <time_measure.h> //for test 42 47 43 namespace hugo { 48 44 49 45 template <typename Graph, typename T, 50 typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>,51 typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >46 typename FlowMap=typename Graph::EdgeMap<T>, 47 typename CapMap=typename Graph::EdgeMap<T> > 52 48 class preflow_hl3 { 53 49 … … 67 63 public: 68 64 65 double time; //for test 66 69 67 preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : 70 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } 71 72 73 void run() { 74 68 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { 69 75 70 bool phase=0; 76 71 int n=G.nodeNum(); … … 81 76 */ 82 77 83 IntMaplevel(G,n);84 TMapexcess(G);78 typename Graph::NodeMap<int> level(G,n); 79 typename Graph::NodeMap<T> excess(G); 85 80 86 81 std::vector<int> numb(n); … … 149 144 if ( phase ) break; 150 145 phase=1; 151 146 time=currTime(); 147 152 148 level.set(s,0); 153 149 … … 188 184 else { 189 185 190 NodeIt w=stack[b].top(); //w is a highest label active node.186 NodeIt w=stack[b].top(); 191 187 stack[b].pop(); 192 188 int lev=level.get(w); 193 intexc=excess.get(w);194 int newlevel=n; //In newlevel we boundthe next level of w.189 T exc=excess.get(w); 190 int newlevel=n; //bound on the next level of w. 195 191 196 192 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { … … 207 203 /*v becomes active.*/ 208 204 209 intcap=capacity.get(e);210 intflo=flow.get(e);211 intremcap=cap-flo;205 T cap=capacity.get(e); 206 T flo=flow.get(e); 207 T remcap=cap-flo; 212 208 213 209 if ( remcap >= exc ) { … … 245 241 /*v becomes active.*/ 246 242 247 intflo=flow.get(e);243 T flo=flow.get(e); 248 244 249 245 if ( flo >= exc ) { … … 350 346 */ 351 347 352 T max flow() {348 T maxFlow() { 353 349 return value; 354 350 } … … 357 353 358 354 /* 359 For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 355 For the maximum flow x found by the algorithm, 356 it returns the flow value on edge e, i.e. x(e). 360 357 */ 361 358 362 T flow onedge(EdgeIt e) {359 T flowOnEdge(EdgeIt e) { 363 360 return flow.get(e); 364 361 } … … 370 367 */ 371 368 372 FlowMap allflow() {369 FlowMap Flow() { 373 370 return flow; 374 371 } … … 382 379 383 380 template<typename CutMap> 384 void min cut(CutMap& M) {381 void minCut(CutMap& M) { 385 382 386 383 std::queue<NodeIt> queue; … … 421 418 422 419 template<typename CutMap> 423 void max _mincut(CutMap& M) {420 void maxMinCut(CutMap& M) { 424 421 425 422 std::queue<NodeIt> queue; … … 458 455 459 456 template<typename CutMap> 460 void min _mincut(CutMap& M) {461 min cut(M);457 void minMinCut(CutMap& M) { 458 minCut(M); 462 459 } 463 460 … … 465 462 466 463 }; 467 }//namespace hugo464 }//namespace 468 465 #endif 469 466 -
src/work/jacint/preflow_hl4.h
r105 r109 1 1 // -*- C++ -*- 2 2 /* 3 preflow_h l4.h3 preflow_h5.h 4 4 by jacint. 5 Runs the two phase highest label preflow push algorithm. In phase 0 6 we maintain in a list the nodes in level i < n, and we maintain a 7 bound k on the max level i < n containing a node, so we can do 8 the gap heuristic fast. Phase 1 is the same. (The algorithm is the 9 same as preflow.hl3, the only diff is that here we use the gap 10 heuristic with the list of the nodes on level i, and not a bfs form the 11 upgraded node.) 12 13 In phase 1 we shift everything downwards by n. 14 15 Member functions: 16 17 void run() : runs the algorithm 18 19 The following functions should be used after run() was already run. 20 21 T maxflow() : returns the value of a maximum flow 22 23 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 24 25 FlowMap allflow() : returns a maximum flow 26 27 void allflow(FlowMap& _flow ) : returns a maximum flow 28 29 void mincut(CutMap& M) : sets M to the characteristic vector of a 30 minimum cut. M should be a map of bools initialized to false. 31 32 void min _mincut(CutMap& M) : sets M to the characteristic vector of the5 Heuristics: 6 2 phase 7 gap 8 list 'level_list' on the nodes on level i implemented by hand 9 highest label 10 relevel: in phase 0, after BFS*n relabels, it runs a reverse 11 bfs from t in the res graph to relevel the nodes reachable from t. 12 BFS is initialized to 20 13 14 Due to the last heuristic, this algorithm is quite fast on very 15 sparse graphs, but relatively bad on even the dense graphs. 16 17 'NodeMap<bool> cut' is a member, in this way we can count it fast, after 18 the algorithm was run. 19 20 The constructor runs the algorithm. 21 22 Members: 23 24 T maxFlow() : returns the value of a maximum flow 25 26 T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 27 28 FlowMap Flow() : returns the fixed maximum flow x 29 30 void Flow(FlowMap& _flow ) : returns the fixed maximum flow x 31 32 void minMinCut(CutMap& M) : sets M to the characteristic vector of the 33 33 minimum min cut. M should be a map of bools initialized to false. 34 34 35 void max _mincut(CutMap& M) : sets M to the characteristic vector of the35 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 36 36 maximum min cut. M should be a map of bools initialized to false. 37 38 void minCut(CutMap& M) : fast function, sets M to the characteristic 39 vector of a minimum cut. 40 41 Different member from the other preflow_hl-s (here we have a member 42 'NodeMap<bool> cut'). 43 44 CutMap minCut() : fast function, giving the characteristic 45 vector of a minimum cut. 46 37 47 38 48 */ … … 41 51 #define PREFLOW_HL4_H 42 52 53 #define BFS 20 54 43 55 #include <vector> 44 #include <stack>45 56 #include <queue> 57 58 #include <time_measure.h> //for test 46 59 47 60 namespace hugo { … … 49 62 template <typename Graph, typename T, 50 63 typename FlowMap=typename Graph::EdgeMap<T>, 64 typename CutMap=typename Graph::NodeMap<bool>, 51 65 typename CapMap=typename Graph::EdgeMap<T> > 52 66 class preflow_hl4 { … … 63 77 FlowMap flow; 64 78 CapMap& capacity; 79 CutMap cut; 65 80 T value; 66 81 67 82 public: 68 83 84 double time; 85 69 86 preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : 70 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } 71 72 73 void run() { 74 75 bool phase=0; 87 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 88 cut(G, false) { 89 90 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd 76 91 int n=G.nodeNum(); 92 int relabel=0; 93 int heur=(int)BFS*n; 77 94 int k=n-2; 78 95 int b=k; … … 84 101 typename Graph::NodeMap<int> level(G,n); 85 102 typename Graph::NodeMap<T> excess(G); 86 std::vector<std::stack<NodeIt> > stack(n); 103 104 std::vector<NodeIt> active(n); 105 typename Graph::NodeMap<NodeIt> next(G); 87 106 //Stack of the active nodes in level i < n. 88 107 //We use it in both phases. … … 108 127 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 109 128 NodeIt w=G.tail(e); 110 if ( level.get(w) == n ) {129 if ( level.get(w) == n && w !=s ) { 111 130 bfs_queue.push(w); 112 131 NodeIt first=level_list[l]; … … 129 148 NodeIt w=G.head(e); 130 149 if ( level.get(w) < n ) { 131 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 150 if ( excess.get(w) == 0 && w!=t ) { 151 next.set(w,active[level.get(w)]); 152 active[level.get(w)]=w; 153 } 132 154 flow.set(e, c); 133 155 excess.set(w, excess.get(w)+c); … … 152 174 */ 153 175 phase=1; 176 177 //Now have a min cut. 178 for( EachNodeIt v=G.template first<EachNodeIt>(); 179 v.valid(); ++v) 180 if (level.get(v) >= n ) cut.set(v,true); 181 182 time=currTime(); 154 183 level.set(s,0); 155 184 std::queue<NodeIt> bfs_queue; … … 168 197 bfs_queue.push(u); 169 198 level.set(u, l); 170 if ( excess.get(u) > 0 ) stack[l].push(u); 199 if ( excess.get(u) > 0 ) { 200 next.set(u,active[l]); 201 active[l]=u; 202 } 171 203 } 172 204 } … … 178 210 bfs_queue.push(u); 179 211 level.set(u, l); 180 if ( excess.get(u) > 0 ) stack[l].push(u); 212 if ( excess.get(u) > 0 ) { 213 next.set(u,active[l]); 214 active[l]=u; 215 } 181 216 } 182 217 } … … 186 221 187 222 188 if ( stack[b].empty()) --b;223 if ( active[b] == 0 ) --b; 189 224 else { 190 225 191 NodeIt w= stack[b].top(); //w is a highest label active node.192 stack[b].pop();226 NodeIt w=active[b]; 227 active[b]=next.get(w); 193 228 int lev=level.get(w); 194 229 T exc=excess.get(w); 195 int newlevel=n; // In newlevel we boundthe next level of w.230 int newlevel=n; //bound on the next level of w. 196 231 197 232 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { … … 204 239 /*Push is allowed now*/ 205 240 206 if ( excess.get(v)==0 && v!=t && v!=s ) 207 stack[level.get(v)].push(v); 208 /*v becomes active.*/ 241 if ( excess.get(v)==0 && v!=t && v!=s ) { 242 int lev_v=level.get(v); 243 next.set(v,active[lev_v]); 244 active[lev_v]=v; 245 } 209 246 210 247 T cap=capacity.get(e); … … 244 281 /*Push is allowed now*/ 245 282 246 if ( excess.get(v)==0 && v!=t && v!=s ) 247 stack[level.get(v)].push(v); 248 /*v becomes active.*/ 283 if ( excess.get(v)==0 && v!=t && v!=s ) { 284 int lev_v=level.get(v); 285 next.set(v,active[lev_v]); 286 active[lev_v]=v; 287 } 249 288 250 289 T flo=flow.get(e); … … 282 321 if ( phase ) { 283 322 level.set(w,++newlevel); 284 stack[newlevel].push(w); 323 next.set(w,active[newlevel]); 324 active[newlevel]=w; 285 325 b=newlevel; 286 326 } else { … … 304 344 } 305 345 } 346 //unlacing ends 306 347 307 348 … … 329 370 330 371 level.set(w,++newlevel); 331 stack[newlevel].push(w); 372 next.set(w,active[newlevel]); 373 active[newlevel]=w; 332 374 b=newlevel; 333 375 if ( k < newlevel ) ++k; … … 339 381 } 340 382 } 383 384 ++relabel; 385 if ( relabel >= heur ) { 386 relabel=0; 387 b=n-2; 388 k=b; 389 390 for ( int i=1; i!=n; ++i ) { 391 active[i]=0; 392 level_list[i]=0; 393 } 394 395 //bfs from t in the res graph to relevel the nodes 396 for( EachNodeIt v=G.template first<EachNodeIt>(); 397 v.valid(); ++v) level.set(v,n); 398 399 level.set(t,0); 400 std::queue<NodeIt> bfs_queue; 401 bfs_queue.push(t); 402 403 while (!bfs_queue.empty()) { 404 405 NodeIt v=bfs_queue.front(); 406 bfs_queue.pop(); 407 int l=level.get(v)+1; 408 409 for(InEdgeIt e=G.template first<InEdgeIt>(v); 410 e.valid(); ++e) { 411 if ( capacity.get(e) == flow.get(e) ) continue; 412 NodeIt u=G.tail(e); 413 if ( level.get(u) == n ) { 414 bfs_queue.push(u); 415 level.set(u, l); 416 if ( excess.get(u) > 0 ) { 417 next.set(u,active[l]); 418 active[l]=u; 419 } 420 NodeIt first=level_list[l]; 421 if ( first != 0 ) left.set(first,w); 422 right.set(w,first); 423 left.set(w,0); 424 level_list[l]=w; 425 } 426 } 427 428 429 for(OutEdgeIt e=G.template first<OutEdgeIt>(v); 430 e.valid(); ++e) { 431 if ( 0 == flow.get(e) ) continue; 432 NodeIt u=G.head(e); 433 if ( level.get(u) == n ) { 434 bfs_queue.push(u); 435 level.set(u, l); 436 if ( excess.get(u) > 0 ) { 437 next.set(u,active[l]); 438 active[l]=u; 439 } 440 NodeIt first=level_list[l]; 441 if ( first != 0 ) left.set(first,w); 442 right.set(w,first); 443 left.set(w,0); 444 level_list[l]=w; 445 } 446 } 447 } 448 449 level.set(s,n); 450 } 451 341 452 } //phase 0 342 453 } // if ( exc > 0 ) 343 454 344 455 345 456 } // if stack[b] is nonempty … … 362 473 */ 363 474 364 T max flow() {475 T maxFlow() { 365 476 return value; 366 477 } … … 372 483 */ 373 484 374 T flow onedge(EdgeIt e) {485 T flowOnEdge(EdgeIt e) { 375 486 return flow.get(e); 376 487 } … … 378 489 379 490 380 FlowMap allflow() {491 FlowMap Flow() { 381 492 return flow; 382 493 } … … 384 495 385 496 386 void allflow(FlowMap& _flow ) {497 void Flow(FlowMap& _flow ) { 387 498 for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) 388 499 _flow.set(v,flow.get(v)); … … 395 506 */ 396 507 397 template<typename CutMap>398 void min cut(CutMap& M) {508 template<typename _CutMap> 509 void minMinCut(_CutMap& M) { 399 510 400 511 std::queue<NodeIt> queue; … … 434 545 */ 435 546 436 template<typename CutMap>437 void max _mincut(CutMap& M) {547 template<typename _CutMap> 548 void maxMinCut(_CutMap& M) { 438 549 439 550 std::queue<NodeIt> queue; … … 470 581 471 582 472 473 template<typename CutMap> 474 void min_mincut(CutMap& M) { 475 mincut(M); 476 } 477 583 template<typename _CutMap> 584 void minCut(_CutMap& M) { 585 for( EachNodeIt v=G.template first<EachNodeIt>(); 586 v.valid(); ++v) 587 M.set(v, cut.get(v)); 588 } 589 590 591 CutMap minCut() { 592 return cut; 593 } 478 594 479 595 480 596 }; 481 }//namespace hugo597 }//namespace marci 482 598 #endif 483 599
Note: See TracChangeset
for help on using the changeset viewer.