Changeset 97:a5127ecb2914 in lemon-0.x
- Timestamp:
- 02/18/04 15:42:38 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@126
- Location:
- src/work/jacint
- Files:
-
- 2 edited
-
preflow_push_hl.h (modified) (10 diffs)
-
preflow_push_max_flow.h (modified) (8 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/preflow_push_hl.h
r88 r97 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)). 6 running time O(n^2\sqrt(m)), and with the 'empty level' heuristic. 7 8 'A' is a parameter for the empty_level heuristic 7 9 8 10 Member functions: … … 16 18 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 17 19 18 Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x 19 20 Graph::NodeMap<bool> mincut() : returns a 21 characteristic vector of a minimum cut. (An empty level 22 in the algorithm gives a minimum cut.) 20 FlowMap allflow() : returns the fixed maximum flow x 21 22 void mincut(CutMap& M) : sets M to the characteristic vector of a 23 minimum cut. M should be a map of bools initialized to false. 24 25 void min_mincut(CutMap& M) : sets M to the characteristic vector of the 26 minimum min cut. M should be a map of bools initialized to false. 27 28 void max_mincut(CutMap& M) : sets M to the characteristic vector of the 29 maximum min cut. M should be a map of bools initialized to false. 30 23 31 */ 24 32 … … 30 38 #include <vector> 31 39 #include <stack> 32 33 #include <reverse_bfs.h> 40 #include <queue> 34 41 35 42 namespace marci { 36 43 37 template <typename Graph, typename T> 44 template <typename Graph, typename T, 45 typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 46 typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> > 38 47 class preflow_push_hl { 39 48 … … 47 56 NodeIt s; 48 57 NodeIt t; 49 typename Graph::EdgeMap<T>flow;50 typename Graph::EdgeMap<T> capacity;58 FlowMap flow; 59 CapMap& capacity; 51 60 T value; 52 typename Graph::NodeMap<bool> mincutvector; 53 61 54 62 public: 55 63 56 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, 57 typename Graph::EdgeMap<T>& _capacity) : 58 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 59 mincutvector(_G, true) { } 60 61 62 /* 63 The run() function runs the highest label preflow-push, 64 running time: O(n^2\sqrt(m)) 65 */ 64 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : 65 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } 66 67 68 69 66 70 void run() { 67 71 68 std::cout<<"A is "<<A<<" ";69 70 typename Graph::NodeMap<int> level(G);71 typename Graph::NodeMap<T> excess(G);72 73 72 int n=G.nodeNum(); 74 73 int b=n-2; 75 74 /* 76 75 b is a bound on the highest level of an active node. 77 In the beginning it is at most n-2.78 76 */ 79 77 80 std::vector<int> numb(n); //The number of nodes on level i < n. 78 IntMap level(G,n); 79 TMap excess(G); 80 81 std::vector<int> numb(n); 82 /* 83 The number of nodes on level i < n. It is 84 initialized to n+1, because of the reverse_bfs-part. 85 */ 86 81 87 std::vector<std::stack<NodeIt> > stack(2*n-1); 82 88 //Stack of the active nodes in level i. … … 84 90 85 91 /*Reverse_bfs from t, to find the starting level.*/ 86 reverse_bfs<Graph> bfs(G, t); 87 bfs.run(); 88 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 89 { 90 int dist=bfs.dist(v); 91 level.set(v, dist); 92 ++numb[dist]; 93 } 94 92 level.set(t,0); 93 std::queue<NodeIt> bfs_queue; 94 bfs_queue.push(t); 95 96 while (!bfs_queue.empty()) { 97 98 NodeIt v=bfs_queue.front(); 99 bfs_queue.pop(); 100 int l=level.get(v)+1; 101 102 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 103 NodeIt w=G.tail(e); 104 if ( level.get(w) == n ) { 105 bfs_queue.push(w); 106 ++numb[l]; 107 level.set(w, l); 108 } 109 } 110 } 111 95 112 level.set(s,n); 113 96 114 97 115 … … 99 117 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 100 118 { 101 if ( capacity.get(e) > 0 ) { 102 NodeIt w=G.head(e); 103 if ( w!=s ) { 104 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 105 flow.set(e, capacity.get(e)); 106 excess.set(w, excess.get(w)+capacity.get(e)); 107 } 108 } 109 } 110 119 if ( capacity.get(e) == 0 ) continue; 120 NodeIt w=G.head(e); 121 if ( w!=s ) { 122 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 123 flow.set(e, capacity.get(e)); 124 excess.set(w, excess.get(w)+capacity.get(e)); 125 } 126 } 127 111 128 /* 112 129 End of preprocessing … … 114 131 115 132 116 117 133 /* 118 134 Push/relabel on the highest level active nodes. 119 135 */ 120 121 136 /*While there exists an active node.*/ 122 137 while (b) { 123 124 /*We decrease the bound if there is no active node of level b.*/ 125 if (stack[b].empty()) { 138 if ( stack[b].empty() ) { 126 139 --b; 127 } else { 128 129 NodeIt w=stack[b].top(); //w is a highest label active node. 130 stack[b].pop(); 131 132 int newlevel=2*n-2; //In newlevel we bound the next level of w. 133 140 continue; 141 } 142 143 NodeIt w=stack[b].top(); //w is a highest label active node. 144 stack[b].pop(); 145 int lev=level.get(w); 146 int exc=excess.get(w); 147 int newlevel=2*n-2; //In newlevel we bound the next level of w. 148 149 // if ( level.get(w) < n ) { //Nem tudom ez mukodik-e 134 150 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { 135 151 136 if ( flow.get(e) < capacity.get(e) ) { 137 /*e is an edge of the residual graph */ 138 139 NodeIt v=G.head(e); /*e is the edge wv.*/ 140 141 if( level.get(w) == level.get(v)+1 ) { 142 /*Push is allowed now*/ 143 144 if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v); 145 /*v becomes active.*/ 146 147 if ( capacity.get(e)-flow.get(e) > excess.get(w) ) { 148 /*A nonsaturating push.*/ 149 150 flow.set(e, flow.get(e)+excess.get(w)); 151 excess.set(v, excess.get(v)+excess.get(w)); 152 excess.set(w,0); 153 break; 154 155 } else { 156 /*A saturating push.*/ 157 158 excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e)); 159 excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e)); 160 flow.set(e, capacity.get(e)); 161 if ( excess.get(w)==0 ) break; 162 /*If w is not active any more, then we go on to the next node.*/ 163 164 } 165 } else { 166 newlevel = newlevel < level.get(v) ? newlevel : level.get(v); 152 if ( flow.get(e) == capacity.get(e) ) continue; 153 NodeIt v=G.head(e); 154 //e=wv 155 156 if( lev > level.get(v) ) { 157 /*Push is allowed now*/ 158 159 if ( excess.get(v)==0 && v != s && v !=t ) 160 stack[level.get(v)].push(v); 161 /*v becomes active.*/ 162 163 int cap=capacity.get(e); 164 int flo=flow.get(e); 165 int remcap=cap-flo; 166 167 if ( remcap >= exc ) { 168 /*A nonsaturating push.*/ 169 170 flow.set(e, flo+exc); 171 excess.set(v, excess.get(v)+exc); 172 exc=0; 173 break; 174 175 } else { 176 /*A saturating push.*/ 177 178 flow.set(e, cap ); 179 excess.set(v, excess.get(v)+remcap); 180 exc-=remcap; 167 181 } 168 169 } //if the out edge wv is in the res graph 170 182 } else if ( newlevel > level.get(v) ) newlevel = level.get(v); 183 171 184 } //for out edges wv 185 186 187 if ( exc > 0 ) { 188 for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 189 190 if( flow.get(e) == 0 ) continue; 191 NodeIt v=G.tail(e); 192 //e=vw 193 194 if( lev > level.get(v) ) { 195 /*Push is allowed now*/ 196 197 if ( excess.get(v)==0 && v != s && v !=t) 198 stack[level.get(v)].push(v); 199 /*v becomes active.*/ 200 201 int flo=flow.get(e); 202 203 if ( flo >= exc ) { 204 /*A nonsaturating push.*/ 205 206 flow.set(e, flo-exc); 207 excess.set(v, excess.get(v)+exc); 208 exc=0; 209 break; 210 } else { 211 /*A saturating push.*/ 212 213 excess.set(v, excess.get(v)+flo); 214 exc-=flo; 215 flow.set(e,0); 216 } 217 } else if ( newlevel > level.get(v) ) newlevel = level.get(v); 218 219 } //for in edges vw 172 220 173 174 if ( excess.get(w) > 0 ) { 175 176 for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 177 NodeIt v=G.tail(e); /*e is the edge vw.*/ 178 179 if( flow.get(e) > 0 ) { 180 /*e is an edge of the residual graph */ 181 182 if( level.get(w)==level.get(v)+1 ) { 183 /*Push is allowed now*/ 184 185 if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 186 /*v becomes active.*/ 187 188 if ( flow.get(e) > excess.get(w) ) { 189 /*A nonsaturating push.*/ 190 191 flow.set(e, flow.get(e)-excess.get(w)); 192 excess.set(v, excess.get(v)+excess.get(w)); 193 excess.set(w,0); 194 break; 195 } else { 196 /*A saturating push.*/ 197 198 excess.set(v, excess.get(v)+flow.get(e)); 199 excess.set(w, excess.get(w)-flow.get(e)); 200 flow.set(e,0); 201 if ( excess.get(w)==0 ) break; 202 } 203 } else { 204 newlevel = newlevel < level.get(v) ? newlevel : level.get(v); 205 } 206 207 } //if in edge vw is in the res graph 208 209 } //for in edges vw 210 211 } // if w still has excess after the out edge for cycle 212 213 214 /* 215 Relabel 216 */ 221 } // if w still has excess after the out edge for cycle 222 223 excess.set(w, exc); 224 225 226 227 228 /* 229 Relabel 230 */ 231 232 if ( exc > 0 ) { 233 //now 'lev' is the old level of w 234 level.set(w,++newlevel); 217 235 218 if ( excess.get(w) > 0 ) { 219 220 int oldlevel=level.get(w); 221 level.set(w,++newlevel); 222 223 if ( oldlevel < n ) { 224 --numb[oldlevel]; 225 226 if ( !numb[oldlevel] && oldlevel < A*n ) { //If the level of w gets empty. 227 228 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 229 if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n); 230 } 231 for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0; 232 if ( newlevel < n ) newlevel=n; 233 } else { 234 if ( newlevel < n ) ++numb[newlevel]; 236 if ( lev < n ) { 237 --numb[lev]; 238 239 if ( !numb[lev] && lev < A*n ) { //If the level of w gets empty. 240 241 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 242 if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); 235 243 } 244 for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 245 if ( newlevel < n ) newlevel=n; 236 246 } else { 237 if ( newlevel < n ) ++numb[newlevel];247 if ( newlevel < n ) ++numb[newlevel]; 238 248 } 239 240 stack[newlevel].push(w); 241 b=newlevel; 242 243 } 244 245 } // if stack[b] is nonempty 246 249 } 250 251 stack[newlevel].push(w); 252 b=newlevel; 253 254 } 255 247 256 } // while(b) 248 249 257 258 250 259 value = excess.get(t); 251 260 /*Max flow value.*/ … … 272 281 */ 273 282 274 T flowonedge( EdgeIt e) {283 T flowonedge(const EdgeIt e) { 275 284 return flow.get(e); 276 285 } … … 282 291 */ 283 292 284 typename Graph::EdgeMap<T>allflow() {293 FlowMap allflow() { 285 294 return flow; 286 295 } … … 288 297 289 298 290 /* 291 Returns a minimum cut by using a reverse bfs from t in the residual graph. 299 300 /* 301 Returns the minimum min cut, by a bfs from s in the residual graph. 292 302 */ 293 303 294 typename Graph::NodeMap<bool> mincut() { 304 template<typename CutMap> 305 void mincut(CutMap& M) { 295 306 296 307 std::queue<NodeIt> queue; 297 308 298 mincutvector.set(t,false);299 queue.push( t);309 M.set(s,true); 310 queue.push(s); 300 311 301 312 while (!queue.empty()) { 302 313 NodeIt w=queue.front(); 303 314 queue.pop(); 315 316 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 317 NodeIt v=G.head(e); 318 if (!M.get(v) && flow.get(e) < capacity.get(e) ) { 319 queue.push(v); 320 M.set(v, true); 321 } 322 } 304 323 305 324 for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) { 306 325 NodeIt v=G.tail(e); 307 if ( mincutvector.get(v) && flow.get(e) < capacity.get(e)) {326 if (!M.get(v) && flow.get(e) > 0 ) { 308 327 queue.push(v); 309 mincutvector.set(v, false); 310 } 311 } // for 328 M.set(v, true); 329 } 330 } 331 332 } 333 } 334 335 336 337 /* 338 Returns the maximum min cut, by a reverse bfs 339 from t in the residual graph. 340 */ 341 342 template<typename CutMap> 343 void max_mincut(CutMap& M) { 344 345 std::queue<NodeIt> queue; 346 347 M.set(t,true); 348 queue.push(t); 349 350 while (!queue.empty()) { 351 NodeIt w=queue.front(); 352 queue.pop(); 353 354 for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) { 355 NodeIt v=G.tail(e); 356 if (!M.get(v) && flow.get(e) < capacity.get(e) ) { 357 queue.push(v); 358 M.set(v, true); 359 } 360 } 312 361 313 362 for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) { 314 363 NodeIt v=G.head(e); 315 if ( mincutvector.get(v) && flow.get(e) > 0 ) {364 if (!M.get(v) && flow.get(e) > 0 ) { 316 365 queue.push(v); 317 mincutvector.set(v, false); 318 } 319 } // for 320 366 M.set(v, true); 367 } 368 } 321 369 } 322 370 323 return mincutvector; 324 325 } 371 for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) { 372 M.set(v, !M.get(v)); 373 } 374 375 } 376 377 378 379 template<typename CutMap> 380 void min_mincut(CutMap& M) { 381 mincut(M); 382 } 383 384 385 326 386 }; 327 387 }//namespace marci -
src/work/jacint/preflow_push_max_flow.h
r85 r97 1 // -*- C++ -*- 1 2 /* 2 3 preflow_push_max_flow_h … … 16 17 T maxflow() : returns the value of a maximum flow 17 18 18 NodeMap<bool> mincut(): returns a 19 characteristic vector of a minimum cut. 19 void mincut(CutMap& M) : sets M to the characteristic vector of a 20 minimum cut. M should be a map of bools initialized to false. 21 20 22 */ 21 23 22 24 #ifndef PREFLOW_PUSH_MAX_FLOW_H 23 25 #define PREFLOW_PUSH_MAX_FLOW_H 26 27 #define A 1 24 28 25 29 #include <algorithm> … … 32 36 namespace marci { 33 37 34 template <typename Graph, typename T> 38 template <typename Graph, typename T, 39 typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 40 typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> > 35 41 class preflow_push_max_flow { 36 42 … … 43 49 NodeIt s; 44 50 NodeIt t; 45 typename Graph::EdgeMap<T>& capacity; 46 T value; 47 typename Graph::NodeMap<bool> mincutvector; 48 49 50 51 IntMap level; 52 CapMap& capacity; 53 int empty_level; //an empty level in the end of run() 54 T value; 55 51 56 public: 52 53 preflow_push_max_flow ( Graph& _G, NodeIt _s, NodeIt _t, 54 typename Graph::EdgeMap<T>& _capacity) : 55 G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { } 57 58 preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : 59 G(_G), s(_s), t(_t), level(_G), capacity(_capacity) { } 56 60 57 61 … … 63 67 void run() { 64 68 65 typename Graph::EdgeMap<T> flow(G, 0); 66 typename Graph::NodeMap<int> level(G); 67 typename Graph::NodeMap<T> excess(G); 68 69 int n=G.nodeNum(); 69 int n=G.nodeNum(); 70 70 int b=n-2; 71 71 /* 72 b is a bound on the highest level of an active Node. 73 In the beginning it is at most n-2. 74 */ 75 76 std::vector<int> numb(n); //The number of Nodes on level i < n. 77 std::vector<std::stack<NodeIt> > stack(2*n-1); 78 //Stack of the active Nodes in level i. 72 b is a bound on the highest level of an active node. 73 */ 74 75 IntMap level(G,n); 76 TMap excess(G); 77 FlowMap flow(G,0); 78 79 std::vector<int> numb(n); 80 /* 81 The number of nodes on level i < n. It is 82 initialized to n+1, because of the reverse_bfs-part. 83 */ 84 85 std::vector<std::stack<NodeIt> > stack(n); 86 //Stack of the active nodes in level i. 87 79 88 80 89 /*Reverse_bfs from t, to find the starting level.*/ 81 reverse_bfs<Graph> bfs(G, t); 82 bfs.run(); 83 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 84 { 85 int dist=bfs.dist(v); 86 level.set(v, dist); 87 ++numb[dist]; 90 level.set(t,0); 91 std::queue<NodeIt> bfs_queue; 92 bfs_queue.push(t); 93 94 while (!bfs_queue.empty()) { 95 96 NodeIt v=bfs_queue.front(); 97 bfs_queue.pop(); 98 int l=level.get(v)+1; 99 100 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 101 NodeIt w=G.tail(e); 102 if ( level.get(w) == n ) { 103 bfs_queue.push(w); 104 ++numb[l]; 105 level.set(w, l); 106 } 88 107 } 89 108 } 109 90 110 level.set(s,n); 91 111 92 /* Starting flow. It is everywhere 0 at the moment. */ 112 113 114 /* Starting flow. It is everywhere 0 at the moment. */ 93 115 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 94 116 { 95 if ( capacity.get(e) > 0 ) { 96 NodeIt w=G.head(e); 117 if ( capacity.get(e) == 0 ) continue; 118 NodeIt w=G.head(e); 119 if ( level.get(w) < n ) { 120 if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 97 121 flow.set(e, capacity.get(e)); 98 stack[level.get(w)].push(w);99 122 excess.set(w, excess.get(w)+capacity.get(e)); 100 123 } 101 124 } 102 125 103 126 /* 104 127 End of preprocessing … … 106 129 107 130 108 109 131 /* 110 Push/relabel on the highest level active Nodes. 111 */ 112 113 /*While there exists an active Node.*/ 132 Push/relabel on the highest level active nodes. 133 */ 134 /*While there exists an active node.*/ 114 135 while (b) { 115 116 /*We decrease the bound if there is no active node of level b.*/ 117 if (stack[b].empty()) { 136 if ( stack[b].empty() ) { 118 137 --b; 119 } else { 120 121 NodeIt w=stack[b].top(); //w is the highest label active Node. 122 stack[b].pop(); //We delete w from the stack. 123 124 int newlevel=2*n-2; //In newlevel we maintain the next level of w. 125 138 continue; 139 } 140 141 NodeIt w=stack[b].top(); //w is a highest label active node. 142 stack[b].pop(); 143 int lev=level.get(w); 144 int exc=excess.get(w); 145 int newlevel=2*n-2; //In newlevel we bound the next level of w. 146 147 // if ( level.get(w) < n ) { //Nem tudom ez mukodik-e 126 148 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) { 127 NodeIt v=G.head(e); 128 /*e is the Edge wv.*/ 129 130 if (flow.get(e)<capacity.get(e)) { 131 /*e is an Edge of the residual graph */ 132 133 if(level.get(w)==level.get(v)+1) { 134 /*Push is allowed now*/ 135 136 if (capacity.get(e)-flow.get(e) > excess.get(w)) { 137 /*A nonsaturating push.*/ 138 139 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 140 /*v becomes active.*/ 141 142 flow.set(e, flow.get(e)+excess.get(w)); 143 excess.set(v, excess.get(v)+excess.get(w)); 144 excess.set(w,0); 145 //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl; 146 break; 147 } else { 148 /*A saturating push.*/ 149 150 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 151 /*v becomes active.*/ 152 153 excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e)); 154 excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e)); 155 flow.set(e, capacity.get(e)); 156 //std::cout << w <<" " << v <<" elore elen sat pump " << std::endl; 157 if (excess.get(w)==0) break; 158 /*If w is not active any more, then we go on to the next Node.*/ 159 160 } // if (capacity.get(e)-flow.get(e) > excess.get(w)) 161 } // if (level.get(w)==level.get(v)+1) 162 163 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} 164 165 } //if (flow.get(e)<capacity.get(e)) 166 167 } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e) 149 150 if ( flow.get(e) == capacity.get(e) ) continue; 151 NodeIt v=G.head(e); 152 //e=wv 153 154 if( lev > level.get(v) ) { 155 /*Push is allowed now*/ 156 157 if ( excess.get(v)==0 && v != s && v !=t ) 158 stack[level.get(v)].push(v); 159 /*v becomes active.*/ 160 161 int cap=capacity.get(e); 162 int flo=flow.get(e); 163 int remcap=cap-flo; 164 165 if ( remcap >= exc ) { 166 /*A nonsaturating push.*/ 167 168 flow.set(e, flo+exc); 169 excess.set(v, excess.get(v)+exc); 170 exc=0; 171 break; 172 173 } else { 174 /*A saturating push.*/ 175 176 flow.set(e, cap ); 177 excess.set(v, excess.get(v)+remcap); 178 exc-=remcap; 179 } 180 } else if ( newlevel > level.get(v) ) newlevel = level.get(v); 181 182 } //for out edges wv 183 184 185 if ( exc > 0 ) { 186 for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 187 188 if( flow.get(e) == 0 ) continue; 189 NodeIt v=G.tail(e); 190 //e=vw 191 192 if( lev > level.get(v) ) { 193 /*Push is allowed now*/ 194 195 if ( excess.get(v)==0 && v != s && v !=t) 196 stack[level.get(v)].push(v); 197 /*v becomes active.*/ 198 199 int flo=flow.get(e); 200 201 if ( flo >= exc ) { 202 /*A nonsaturating push.*/ 203 204 flow.set(e, flo-exc); 205 excess.set(v, excess.get(v)+exc); 206 exc=0; 207 break; 208 } else { 209 /*A saturating push.*/ 210 211 excess.set(v, excess.get(v)+flo); 212 exc-=flo; 213 flow.set(e,0); 214 } 215 } else if ( newlevel > level.get(v) ) newlevel = level.get(v); 216 217 } //for in edges vw 168 218 169 170 171 for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) { 172 NodeIt v=G.tail(e); 173 /*e is the Edge vw.*/ 174 175 if (excess.get(w)==0) break; 176 /*It may happen, that w became inactive in the first 'for' cycle.*/ 177 178 if(flow.get(e)>0) { 179 /*e is an Edge of the residual graph */ 180 181 if(level.get(w)==level.get(v)+1) { 182 /*Push is allowed now*/ 183 184 if (flow.get(e) > excess.get(w)) { 185 /*A nonsaturating push.*/ 186 187 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 188 /*v becomes active.*/ 189 190 flow.set(e, flow.get(e)-excess.get(w)); 191 excess.set(v, excess.get(v)+excess.get(w)); 192 excess.set(w,0); 193 //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl; 194 break; 195 } else { 196 /*A saturating push.*/ 197 198 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 199 /*v becomes active.*/ 200 201 flow.set(e,0); 202 excess.set(v, excess.get(v)+flow.get(e)); 203 excess.set(w, excess.get(w)-flow.get(e)); 204 //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl; 205 if (excess.get(w)==0) { break;} 206 } //if (flow.get(e) > excess.get(v)) 207 } //if(level.get(w)==level.get(v)+1) 208 209 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} 210 //std::cout << "Leveldecrease of Node " << w << " to " << newlevel << std::endl; 211 212 } //if (flow.get(e)>0) 213 214 } //for in-Edge 215 216 217 218 219 /* 220 Relabel 221 */ 222 if (excess.get(w)>0) { 223 /*Now newlevel <= n*/ 224 225 int l=level.get(w); //l is the old level of w. 226 --numb[l]; 227 228 if (newlevel == n) { 229 level.set(w,n); 230 231 } else { 232 233 if (numb[l]) { 234 /*If the level of w remains nonempty.*/ 235 236 level.set(w,++newlevel); 237 ++numb[newlevel]; 238 stack[newlevel].push(w); 239 b=newlevel; 240 } else { 241 /*If the level of w gets empty.*/ 242 243 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 244 if (level.get(v) >= l ) { 245 level.set(v,n); 246 } 247 } 248 249 for (int i=l+1 ; i!=n ; ++i) numb[i]=0; 250 } //if (numb[l]) 251 252 } // if (newlevel = n) 253 254 } // if (excess.get(w)>0) 255 256 257 } //else 258 219 } // if w still has excess after the out edge for cycle 220 221 excess.set(w, exc); 222 223 224 /* 225 Relabel 226 */ 227 228 if ( exc > 0 ) { 229 //now 'lev' is the old level of w 230 level.set(w,++newlevel); 231 --numb[lev]; 232 233 if ( !numb[lev] && lev < A*n ) { //If the level of w gets empty. 234 235 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) { 236 if (level.get(v) > lev ) level.set(v,n); 237 } 238 for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 239 if ( newlevel < n ) newlevel=n; 240 } else if ( newlevel < n ) { 241 ++numb[newlevel]; 242 stack[newlevel].push(w); 243 b=newlevel; 244 } 245 } 246 247 248 259 249 } //while(b) 260 250 … … 263 253 264 254 265 266 /* 267 We find an empty level, e. The Nodes above this level give 268 a minimum cut. 269 */ 270 271 int e=1; 272 273 while(e) { 274 if(numb[e]) ++e; 255 /* 256 We count empty_level. The nodes above this level is a mincut. 257 */ 258 while(true) { 259 if(numb[empty_level]) ++empty_level; 275 260 else break; 276 261 } 277 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) { 278 if (level.get(v) > e) mincutvector.set(v, true); 279 } 280 281 262 282 263 } // void run() 283 264 … … 296 277 /* 297 278 Returns a minimum cut. 298 */ 299 300 typename Graph::NodeMap<bool> mincut() { 301 return mincutvector; 279 */ 280 template<typename CutMap> 281 void mincut(CutMap& M) { 282 283 for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) { 284 if ( level.get(v) > empty_level ) M.set(v, true); 285 } 302 286 } 303 287 304 288 305 289 };
Note: See TracChangeset
for help on using the changeset viewer.
