Changeset 372:e6a156fc186d in lemon-0.x for src/work/jacint/preflow.h
- Timestamp:
- 04/22/04 16:11:28 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@502
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/preflow.h
r330 r372 1 1 // -*- C++ -*- 2 3 //run gyorsan tudna adni a minmincutot a 2 fazis elejen , ne vegyuk be konstruktorba egy cutmapet? 4 //constzero jo igy? 5 6 //majd marci megmondja betegyem-e bfs-t meg resgraphot 7 2 8 /* 3 9 Heuristics: … … 13 19 Constructors: 14 20 15 Preflow(Graph, Node, Node, CapMap, FlowMap) 21 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if 22 FlowMap is not constant zero, and should be true if it is 16 23 17 24 Members: … … 30 37 a min cut. M should be a map of bools initialized to false. 31 38 39 FIXME reset 40 32 41 */ 33 42 … … 45 54 template <typename Graph, typename T, 46 55 typename CapMap=typename Graph::EdgeMap<T>, 47 56 typename FlowMap=typename Graph::EdgeMap<T> > 48 57 class Preflow { 49 58 … … 60 69 FlowMap& flow; 61 70 T value; 71 bool constzero; 62 72 63 73 public: 64 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 65 FlowMap& _flow ) : 66 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {} 67 74 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, 75 FlowMap& _flow, bool _constzero ) : 76 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {} 77 78 68 79 void run() { 80 81 value=0; //for the subsequent runs 69 82 70 83 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd … … 90 103 typename Graph::NodeMap<T> excess(G); 91 104 92 std::vector<Node> active(n ,INVALID);105 std::vector<Node> active(n-1,INVALID); 93 106 typename Graph::NodeMap<Node> next(G,INVALID); 94 107 //Stack of the active nodes in level i < n. … … 102 115 */ 103 116 104 /*Reverse_bfs from t, to find the starting level.*/ 105 level.set(t,0);106 std::queue<Node> bfs_queue;107 bfs_queue.push(t); 108 109 while (!bfs_queue.empty()) { 110 111 Node v=bfs_queue.front();112 bfs_queue.pop();113 int l=level[v]+1;114 115 InEdgeIt e;116 for(G.first(e,v); G.valid(e); G.next(e)) {117 Node w=G.tail(e);118 if ( level[w] == n && w != s ) {119 bfs_queue.push(w);120 Node first=level_list[l];121 if ( G.valid(first) ) left.set(first,w);122 right.set(w,first);123 level_list[l]=w;124 level.set(w, l);125 }126 }127 } 128 129 level.set(s,n); 130 131 132 /* Starting flow. It is everywhere 0 at the moment. */ 133 134 117 118 if ( constzero ) { 119 120 /*Reverse_bfs from t, to find the starting level.*/ 121 level.set(t,0); 122 std::queue<Node> bfs_queue; 123 bfs_queue.push(t); 124 125 while (!bfs_queue.empty()) { 126 127 Node v=bfs_queue.front(); 128 bfs_queue.pop(); 129 int l=level[v]+1; 130 131 InEdgeIt e; 132 for(G.first(e,v); G.valid(e); G.next(e)) { 133 Node w=G.tail(e); 134 if ( level[w] == n && w != s ) { 135 bfs_queue.push(w); 136 Node first=level_list[l]; 137 if ( G.valid(first) ) left.set(first,w); 138 right.set(w,first); 139 level_list[l]=w; 140 level.set(w, l); 141 } 142 } 143 } 144 145 //the starting flow 146 OutEdgeIt e; 147 for(G.first(e,s); G.valid(e); G.next(e)) 135 148 { 136 149 T c=capacity[e]; … … 146 159 } 147 160 } 161 } 162 else 163 { 164 165 /* 166 Reverse_bfs from t in the residual graph, 167 to find the starting level. 168 */ 169 level.set(t,0); 170 std::queue<Node> bfs_queue; 171 bfs_queue.push(t); 172 173 while (!bfs_queue.empty()) { 174 175 Node v=bfs_queue.front(); 176 bfs_queue.pop(); 177 int l=level[v]+1; 178 179 InEdgeIt e; 180 for(G.first(e,v); G.valid(e); G.next(e)) { 181 if ( capacity[e] == flow[e] ) continue; 182 Node w=G.tail(e); 183 if ( level[w] == n && w != s ) { 184 bfs_queue.push(w); 185 Node first=level_list[l]; 186 if ( G.valid(first) ) left.set(first,w); 187 right.set(w,first); 188 level_list[l]=w; 189 level.set(w, l); 190 } 191 } 192 193 OutEdgeIt f; 194 for(G.first(f,v); G.valid(f); G.next(f)) { 195 if ( 0 == flow[f] ) continue; 196 Node w=G.head(f); 197 if ( level[w] == n && w != s ) { 198 bfs_queue.push(w); 199 Node first=level_list[l]; 200 if ( G.valid(first) ) left.set(first,w); 201 right.set(w,first); 202 level_list[l]=w; 203 level.set(w, l); 204 } 205 } 206 } 207 208 209 /* 210 Counting the excess 211 */ 212 NodeIt v; 213 for(G.first(v); G.valid(v); G.next(v)) { 214 T exc=0; 215 216 InEdgeIt e; 217 for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e]; 218 OutEdgeIt f; 219 for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e]; 220 221 excess.set(v,exc); 222 223 //putting the active nodes into the stack 224 int lev=level[v]; 225 if ( exc > 0 && lev < n ) { 226 next.set(v,active[lev]); 227 active[lev]=v; 228 } 229 } 230 231 232 //the starting flow 233 OutEdgeIt e; 234 for(G.first(e,s); G.valid(e); G.next(e)) 235 { 236 T rem=capacity[e]-flow[e]; 237 if ( rem == 0 ) continue; 238 Node w=G.head(e); 239 if ( level[w] < n ) { 240 if ( excess[w] == 0 && w!=t ) { 241 next.set(w,active[level[w]]); 242 active[level[w]]=w; 243 } 244 flow.set(e, capacity[e]); 245 excess.set(w, excess[w]+rem); 246 } 247 } 248 249 InEdgeIt f; 250 for(G.first(f,s); G.valid(f); G.next(f)) 251 { 252 if ( flow[f] == 0 ) continue; 253 Node w=G.head(f); 254 if ( level[w] < n ) { 255 if ( excess[w] == 0 && w!=t ) { 256 next.set(w,active[level[w]]); 257 active[level[w]]=w; 258 } 259 excess.set(w, excess[w]+flow[f]); 260 flow.set(f, 0); 261 } 262 } 263 } 264 265 266 148 267 149 268 /* … … 339 458 //unlacing ends 340 459 341 //gapping starts342 460 if ( !G.valid(level_list[lev]) ) { 343 461 462 //gapping starts 344 463 for (int i=lev; i!=k ; ) { 345 464 Node v=level_list[++i]; … … 356 475 k=b; 357 476 //gapping ends 477 358 478 } else { 359 479 … … 364 484 active[newlevel]=w; 365 485 if ( what_heur ) b=newlevel; 366 if ( k < newlevel ) ++k; 486 if ( k < newlevel ) ++k; //now k=newlevel 367 487 Node first=level_list[newlevel]; 368 488 if ( G.valid(first) ) left.set(first,w); … … 519 639 } 520 640 641 642 void reset_target (Node _t) {t=_t;} 643 void reset_source (Node _s) {s=_s;} 644 645 template<typename _CapMap> 646 void reset_cap (_CapMap _cap) {capacity=_cap;} 647 648 template<typename _FlowMap> 649 void reset_cap (_FlowMap _flow, bool _constzero) { 650 flow=_flow; 651 constzero=_constzero; 652 } 653 654 521 655 522 656 };
Note: See TracChangeset
for help on using the changeset viewer.