Changeset 466:cd40ecf4d2a9 in lemon0.x
 Timestamp:
 04/29/04 12:16:46 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@617
 Location:
 src/work
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.h
r465 r466 60 60 typedef typename std::vector<Node> VecNode; 61 61 62 const Graph & G;62 const Graph* g; 63 63 Node s; 64 64 Node t; … … 80 80 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 81 81 FlowMap& _flow) : 82 G(_G), s(_s), t(_t), capacity(&_capacity),82 g(&_G), s(_s), t(_t), capacity(&_capacity), 83 83 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} 84 84 … … 110 110 VecStack active(n); 111 111 112 NNMap left( G,INVALID);113 NNMap right( G,INVALID);112 NNMap left(*g, INVALID); 113 NNMap right(*g, INVALID); 114 114 VecNode level_list(n,INVALID); 115 115 //List of the nodes in level i<n, set to n. 116 116 117 117 NodeIt v; 118 for( G.first(v); G.valid(v); G.next(v)) level.set(v,n);118 for(g>first(v); g>valid(v); g>next(v)) level.set(v,n); 119 119 //setting each node to level n 120 120 … … 124 124 //counting the excess 125 125 NodeIt v; 126 for( G.first(v); G.valid(v); G.next(v)) {126 for(g>first(v); g>valid(v); g>next(v)) { 127 127 T exc=0; 128 128 129 129 InEdgeIt e; 130 for( G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];130 for(g>first(e,v); g>valid(e); g>next(e)) exc+=(*flow)[e]; 131 131 OutEdgeIt f; 132 for( G.first(f,v); G.valid(f); G.next(f)) exc=(*flow)[f];132 for(g>first(f,v); g>valid(f); g>next(f)) exc=(*flow)[f]; 133 133 134 134 excess.set(v,exc); … … 146 146 147 147 InEdgeIt e; 148 for( G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];148 for(g>first(e,t); g>valid(e); g>next(e)) exc+=(*flow)[e]; 149 149 OutEdgeIt f; 150 for( G.first(f,t); G.valid(f); G.next(f)) exc=(*flow)[f];150 for(g>first(f,t); g>valid(f); g>next(f)) exc=(*flow)[f]; 151 151 152 152 excess.set(t,exc); … … 217 217 218 218 InEdgeIt e; 219 for( G.first(e,v); G.valid(e); G.next(e)) {219 for(g>first(e,v); g>valid(e); g>next(e)) { 220 220 if ( (*capacity)[e] == (*flow)[e] ) continue; 221 Node u= G.tail(e);221 Node u=g>tail(e); 222 222 if ( level[u] >= n ) { 223 223 bfs_queue.push(u); … … 228 228 229 229 OutEdgeIt f; 230 for( G.first(f,v); G.valid(f); G.next(f)) {230 for(g>first(f,v); g>valid(f); g>next(f)) { 231 231 if ( 0 == (*flow)[f] ) continue; 232 Node u= G.head(f);232 Node u=g>head(f); 233 233 if ( level[u] >= n ) { 234 234 bfs_queue.push(u); … … 270 270 void actMinCut(_CutMap& M) { 271 271 NodeIt v; 272 for(G.first(v); G.valid(v); G.next(v)) 273 if ( level[v] < n ) M.set(v,false); 274 else M.set(v,true); 272 for(g>first(v); g>valid(v); g>next(v)) 273 if ( level[v] < n ) { 274 M.set(v,false); 275 } else { 276 M.set(v,true); 277 } 275 278 } 276 279 … … 293 296 294 297 OutEdgeIt e; 295 for( G.first(e,w) ; G.valid(e); G.next(e)) {296 Node v= G.head(e);298 for(g>first(e,w) ; g>valid(e); g>next(e)) { 299 Node v=g>head(e); 297 300 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 298 301 queue.push(v); … … 302 305 303 306 InEdgeIt f; 304 for( G.first(f,w) ; G.valid(f); G.next(f)) {305 Node v= G.tail(f);307 for(g>first(f,w) ; g>valid(f); g>next(f)) { 308 Node v=g>tail(f); 306 309 if (!M[v] && (*flow)[f] > 0 ) { 307 310 queue.push(v); … … 323 326 324 327 NodeIt v; 325 for( G.first(v) ; G.valid(v); G.next(v)) {328 for(g>first(v) ; g>valid(v); g>next(v)) { 326 329 M.set(v, true); 327 330 } … … 338 341 339 342 InEdgeIt e; 340 for( G.first(e,w) ; G.valid(e); G.next(e)) {341 Node v= G.tail(e);343 for(g>first(e,w) ; g>valid(e); g>next(e)) { 344 Node v=g>tail(e); 342 345 if (M[v] && (*flow)[e] < (*capacity)[e] ) { 343 346 queue.push(v); … … 347 350 348 351 OutEdgeIt f; 349 for( G.first(f,w) ; G.valid(f); G.next(f)) {350 Node v= G.head(f);352 for(g>first(f,w) ; g>valid(f); g>next(f)) { 353 Node v=g>head(f); 351 354 if (M[v] && (*flow)[f] > 0 ) { 352 355 queue.push(v); … … 386 389 387 390 OutEdgeIt e; 388 for( G.first(e,w); G.valid(e); G.next(e)) {391 for(g>first(e,w); g>valid(e); g>next(e)) { 389 392 390 393 if ( (*flow)[e] == (*capacity)[e] ) continue; 391 Node v= G.head(e);394 Node v=g>head(e); 392 395 393 396 if( lev > level[v] ) { //Push is allowed now … … 419 422 if ( exc > 0 ) { 420 423 InEdgeIt e; 421 for( G.first(e,w); G.valid(e); G.next(e)) {424 for(g>first(e,w); g>valid(e); g>next(e)) { 422 425 423 426 if( (*flow)[e] == 0 ) continue; 424 Node v= G.tail(e);427 Node v=g>tail(e); 425 428 426 429 if( lev > level[v] ) { //Push is allowed now … … 475 478 476 479 InEdgeIt e; 477 for( G.first(e,v); G.valid(e); G.next(e)) {478 Node w= G.tail(e);480 for(g>first(e,v); g>valid(e); g>next(e)) { 481 Node w=g>tail(e); 479 482 if ( level[w] == n && w != s ) { 480 483 bfs_queue.push(w); 481 484 Node first=level_list[l]; 482 if ( G.valid(first) ) left.set(first,w);485 if ( g>valid(first) ) left.set(first,w); 483 486 right.set(w,first); 484 487 level_list[l]=w; … … 490 493 //the starting flow 491 494 OutEdgeIt e; 492 for( G.first(e,s); G.valid(e); G.next(e))495 for(g>first(e,s); g>valid(e); g>next(e)) 493 496 { 494 497 T c=(*capacity)[e]; 495 498 if ( c == 0 ) continue; 496 Node w= G.head(e);499 Node w=g>head(e); 497 500 if ( level[w] < n ) { 498 501 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 519 522 520 523 InEdgeIt e; 521 for( G.first(e,v); G.valid(e); G.next(e)) {524 for(g>first(e,v); g>valid(e); g>next(e)) { 522 525 if ( (*capacity)[e] == (*flow)[e] ) continue; 523 Node w= G.tail(e);526 Node w=g>tail(e); 524 527 if ( level[w] == n && w != s ) { 525 528 bfs_queue.push(w); 526 529 Node first=level_list[l]; 527 if ( G.valid(first) ) left.set(first,w);530 if ( g>valid(first) ) left.set(first,w); 528 531 right.set(w,first); 529 532 level_list[l]=w; … … 533 536 534 537 OutEdgeIt f; 535 for( G.first(f,v); G.valid(f); G.next(f)) {538 for(g>first(f,v); g>valid(f); g>next(f)) { 536 539 if ( 0 == (*flow)[f] ) continue; 537 Node w= G.head(f);540 Node w=g>head(f); 538 541 if ( level[w] == n && w != s ) { 539 542 bfs_queue.push(w); 540 543 Node first=level_list[l]; 541 if ( G.valid(first) ) left.set(first,w);544 if ( g>valid(first) ) left.set(first,w); 542 545 right.set(w,first); 543 546 level_list[l]=w; … … 550 553 //the starting flow 551 554 OutEdgeIt e; 552 for( G.first(e,s); G.valid(e); G.next(e))555 for(g>first(e,s); g>valid(e); g>next(e)) 553 556 { 554 557 T rem=(*capacity)[e](*flow)[e]; 555 558 if ( rem == 0 ) continue; 556 Node w= G.head(e);559 Node w=g>head(e); 557 560 if ( level[w] < n ) { 558 561 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 563 566 564 567 InEdgeIt f; 565 for( G.first(f,s); G.valid(f); G.next(f))568 for(g>first(f,s); g>valid(f); g>next(f)) 566 569 { 567 570 if ( (*flow)[f] == 0 ) continue; 568 Node w= G.tail(f);571 Node w=g>tail(f); 569 572 if ( level[w] < n ) { 570 573 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 590 593 591 594 //unlacing starts 592 if ( G.valid(right_n) ) {593 if ( G.valid(left_n) ) {595 if ( g>valid(right_n) ) { 596 if ( g>valid(left_n) ) { 594 597 right.set(left_n, right_n); 595 598 left.set(right_n, left_n); … … 599 602 } 600 603 } else { 601 if ( G.valid(left_n) ) {604 if ( g>valid(left_n) ) { 602 605 right.set(left_n, INVALID); 603 606 } else { … … 607 610 //unlacing ends 608 611 609 if ( ! G.valid(level_list[lev]) ) {612 if ( !g>valid(level_list[lev]) ) { 610 613 611 614 //gapping starts 612 615 for (int i=lev; i!=k ; ) { 613 616 Node v=level_list[++i]; 614 while ( G.valid(v) ) {617 while ( g>valid(v) ) { 615 618 level.set(v,n); 616 619 v=right[v]; … … 638 641 if ( k < newlevel ) ++k; //now k=newlevel 639 642 Node first=level_list[newlevel]; 640 if ( G.valid(first) ) left.set(first,w);643 if ( g>valid(first) ) left.set(first,w); 641 644 right.set(w,first); 642 645 left.set(w,INVALID); 
src/work/marci/edmonds_karp.h
r409 r466 11 11 #include <graph_wrapper.h> 12 12 #include <maps.h> 13 #include <for_each_macros.h> 13 14 14 15 namespace hugo { 15 16 // template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>17 // class ResGraph {18 // public:19 // typedef typename Graph::Node Node;20 // typedef typename Graph::NodeIt NodeIt;21 // private:22 // typedef typename Graph::SymEdgeIt OldSymEdgeIt;23 // const Graph& G;24 // const CapacityMap& capacity;25 // FlowMap& flow;26 // public:27 // ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :28 // G(_G), capacity(_capacity), flow(_flow) { }29 30 // class Edge;31 // class OutEdgeIt;32 // friend class Edge;33 // friend class OutEdgeIt;34 35 // class Edge {36 // friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;37 // protected:38 // const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;39 // OldSymEdgeIt sym;40 // public:41 // Edge() { }42 // //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }43 // Number free() const {44 // if (resG>G.aNode(sym)==resG>G.tail(sym)) {45 // return (resG>capacity.get(sym)resG>flow.get(sym));46 // } else {47 // return (resG>flow.get(sym));48 // }49 // }50 // bool valid() const { return sym.valid(); }51 // void augment(Number a) const {52 // if (resG>G.aNode(sym)==resG>G.tail(sym)) {53 // resG>flow.set(sym, resG>flow.get(sym)+a);54 // //resG>flow[sym]+=a;55 // } else {56 // resG>flow.set(sym, resG>flow.get(sym)a);57 // //resG>flow[sym]=a;58 // }59 // }60 // };61 62 // class OutEdgeIt : public Edge {63 // friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;64 // public:65 // OutEdgeIt() { }66 // //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }67 // private:68 // OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {69 // resG=&_resG;70 // sym=resG>G.template first<OldSymEdgeIt>(v);71 // while( sym.valid() && !(free()>0) ) { ++sym; }72 // }73 // public:74 // OutEdgeIt& operator++() {75 // ++sym;76 // while( sym.valid() && !(free()>0) ) { ++sym; }77 // return *this;78 // }79 // };80 81 // void /*getF*/first(OutEdgeIt& e, Node v) const {82 // e=OutEdgeIt(*this, v);83 // }84 // void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }85 86 // template< typename It >87 // It first() const {88 // It e;89 // /*getF*/first(e);90 // return e;91 // }92 93 // template< typename It >94 // It first(Node v) const {95 // It e;96 // /*getF*/first(e, v);97 // return e;98 // }99 100 // Node tail(Edge e) const { return G.aNode(e.sym); }101 // Node head(Edge e) const { return G.bNode(e.sym); }102 103 // Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }104 // Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }105 106 // int id(Node v) const { return G.id(v); }107 108 // template <typename S>109 // class NodeMap {110 // typename Graph::NodeMap<S> node_map;111 // public:112 // NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }113 // NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }114 // void set(Node nit, S a) { node_map.set(nit, a); }115 // S get(Node nit) const { return node_map.get(nit); }116 // S& operator[](Node nit) { return node_map[nit]; }117 // const S& operator[](Node nit) const { return node_map[nit]; }118 // };119 120 // };121 122 123 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>124 // class ResGraph2 {125 // public:126 // typedef typename Graph::Node Node;127 // typedef typename Graph::NodeIt NodeIt;128 // private:129 // //typedef typename Graph::SymEdgeIt OldSymEdgeIt;130 // typedef typename Graph::OutEdgeIt OldOutEdgeIt;131 // typedef typename Graph::InEdgeIt OldInEdgeIt;132 133 // const Graph& G;134 // FlowMap& flow;135 // const CapacityMap& capacity;136 // public:137 // ResGraph2(const Graph& _G, FlowMap& _flow,138 // const CapacityMap& _capacity) :139 // G(_G), flow(_flow), capacity(_capacity) { }140 141 // class Edge;142 // class OutEdgeIt;143 // friend class Edge;144 // friend class OutEdgeIt;145 146 // class Edge {147 // friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;148 // protected:149 // const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;150 // //OldSymEdgeIt sym;151 // OldOutEdgeIt out;152 // OldInEdgeIt in;153 // bool out_or_in; //true, iff out154 // public:155 // Edge() : out_or_in(true) { }156 // Number free() const {157 // if (out_or_in) {158 // return (resG>capacity.get(out)resG>flow.get(out));159 // } else {160 // return (resG>flow.get(in));161 // }162 // }163 // bool valid() const {164 // return out_or_in && out.valid()  in.valid(); }165 // void augment(Number a) const {166 // if (out_or_in) {167 // resG>flow.set(out, resG>flow.get(out)+a);168 // } else {169 // resG>flow.set(in, resG>flow.get(in)a);170 // }171 // }172 // };173 174 // class OutEdgeIt : public Edge {175 // friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;176 // public:177 // OutEdgeIt() { }178 // private:179 // OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {180 // resG=&_resG;181 // out=resG>G.template first<OldOutEdgeIt>(v);182 // while( out.valid() && !(free()>0) ) { ++out; }183 // if (!out.valid()) {184 // out_or_in=0;185 // in=resG>G.template first<OldInEdgeIt>(v);186 // while( in.valid() && !(free()>0) ) { ++in; }187 // }188 // }189 // public:190 // OutEdgeIt& operator++() {191 // if (out_or_in) {192 // Node v=resG>G.aNode(out);193 // ++out;194 // while( out.valid() && !(free()>0) ) { ++out; }195 // if (!out.valid()) {196 // out_or_in=0;197 // in=resG>G.template first<OldInEdgeIt>(v);198 // while( in.valid() && !(free()>0) ) { ++in; }199 // }200 // } else {201 // ++in;202 // while( in.valid() && !(free()>0) ) { ++in; }203 // }204 // return *this;205 // }206 // };207 208 // void /*getF*/first(OutEdgeIt& e, Node v) const {209 // e=OutEdgeIt(*this, v);210 // }211 // void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }212 213 // template< typename It >214 // It first() const {215 // It e;216 // /*getF*/first(e);217 // return e;218 // }219 220 // template< typename It >221 // It first(Node v) const {222 // It e;223 // /*getF*/first(e, v);224 // return e;225 // }226 227 // Node tail(Edge e) const {228 // return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }229 // Node head(Edge e) const {230 // return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }231 232 // Node aNode(OutEdgeIt e) const {233 // return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }234 // Node bNode(OutEdgeIt e) const {235 // return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }236 237 // int id(Node v) const { return G.id(v); }238 239 // template <typename S>240 // class NodeMap {241 // typename Graph::NodeMap<S> node_map;242 // public:243 // NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }244 // NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }245 // void set(Node nit, S a) { node_map.set(nit, a); }246 // S get(Node nit) const { return node_map.get(nit); }247 // };248 // };249 250 16 251 17 template <typename Graph, typename Number, … … 266 32 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 267 33 typedef typename ResGW::Edge ResGWEdge; 34 //typedef typename ResGW::template NodeMap<bool> ReachedMap; 35 typedef typename Graph::template NodeMap<bool> ReachedMap; 36 ReachedMap level; 37 //reached is called level because of compatibility with preflow 268 38 public: 269 39 270 40 MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity, 271 41 FlowMap& _flow) : 272 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }42 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { } 273 43 274 44 bool augmentOnShortestPath() { … … 276 46 bool _augment=false; 277 47 278 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 279 bfs(res_graph); 48 //ReachedMap level(res_graph); 49 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 50 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 280 51 bfs.pushAndSetReached(s); 281 52 … … 343 114 ResGW res_graph(*g, *capacity, *flow); 344 115 345 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 346 bfs(res_graph); 116 //ReachedMap level(res_graph); 117 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 118 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 347 119 348 120 bfs.pushAndSetReached(s); … … 455 227 456 228 //bfs for distances on the residual graph 457 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 458 bfs(res_graph); 229 //ReachedMap level(res_graph); 230 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 231 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 459 232 bfs.pushAndSetReached(s); 460 233 typename ResGW::template NodeMap<int> … … 561 334 562 335 ResGW res_graph(*g, *capacity, *flow); 563 564 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 565 bfs(res_graph); 336 337 //ReachedMap level(res_graph); 338 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 339 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); 566 340 567 341 bfs.pushAndSetReached(s);
Note: See TracChangeset
for help on using the changeset viewer.