Changeset 75:87623302a68f in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 02/16/04 12:29:48 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@98
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r69 r75 3 3 4 4 #include <algorithm> 5 #include <list> 6 #include <iterator> 5 7 6 8 #include <bfs_iterator.hh> … … 8 10 namespace marci { 9 11 10 template<typename Graph, typename T, typename FlowMap, typename CapacityMap>12 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 11 13 class ResGraph { 12 14 typedef typename Graph::NodeIt NodeIt; … … 27 29 28 30 class EdgeIt { 29 friend class ResGraph<Graph, T, FlowMap, CapacityMap>;31 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; 30 32 protected: 31 const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;33 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG; 32 34 OldSymEdgeIt sym; 33 35 public: 34 36 EdgeIt() { } 35 37 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } 36 Tfree() const {38 Number free() const { 37 39 if (resG>G.aNode(sym)==resG>G.tail(sym)) { 38 40 return (resG>capacity.get(sym)resG>flow.get(sym)); … … 42 44 } 43 45 bool valid() const { return sym.valid(); } 44 void augment( Ta) const {46 void augment(Number a) const { 45 47 if (resG>G.aNode(sym)==resG>G.tail(sym)) { 46 48 resG>flow.set(sym, resG>flow.get(sym)+a); 49 //resG>flow[sym]+=a; 47 50 } else { 48 51 resG>flow.set(sym, resG>flow.get(sym)a); 52 //resG>flow[sym]=a; 49 53 } 50 54 } … … 52 56 53 57 class OutEdgeIt : public EdgeIt { 54 friend class ResGraph<Graph, T, FlowMap, CapacityMap>;58 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; 55 59 public: 56 60 OutEdgeIt() { } 57 61 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } 58 62 private: 59 OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {63 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 60 64 resG=&_resG; 61 65 sym=resG>G.template first<OldSymEdgeIt>(v); … … 66 70 ++sym; 67 71 while( sym.valid() && !(free()>0) ) { ++sym; } 72 return *this; 73 } 74 }; 75 76 void getFirst(OutEdgeIt& e, NodeIt v) const { 77 e=OutEdgeIt(*this, v); 78 } 79 void getFirst(EachNodeIt& v) const { G.getFirst(v); } 80 81 template< typename It > 82 It first() const { 83 It e; 84 getFirst(e); 85 return e; 86 } 87 88 template< typename It > 89 It first(NodeIt v) const { 90 It e; 91 getFirst(e, v); 92 return e; 93 } 94 95 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } 96 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } 97 98 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } 99 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } 100 101 int id(NodeIt v) const { return G.id(v); } 102 103 template <typename S> 104 class NodeMap { 105 typename Graph::NodeMap<S> node_map; 106 public: 107 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } 108 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } 109 void set(NodeIt nit, S a) { node_map.set(nit, a); } 110 S get(NodeIt nit) const { return node_map.get(nit); } 111 S& operator[](NodeIt nit) { return node_map[nit]; } 112 const S& operator[](NodeIt nit) const { return node_map[nit]; } 113 }; 114 115 }; 116 117 118 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 119 class ResGraph2 { 120 typedef typename Graph::NodeIt NodeIt; 121 typedef typename Graph::EachNodeIt EachNodeIt; 122 //typedef typename Graph::SymEdgeIt OldSymEdgeIt; 123 typedef typename Graph::OutEdgeIt OldOutEdgeIt; 124 typedef typename Graph::InEdgeIt OldInEdgeIt; 125 126 const Graph& G; 127 FlowMap& flow; 128 const CapacityMap& capacity; 129 public: 130 ResGraph2(const Graph& _G, FlowMap& _flow, 131 const CapacityMap& _capacity) : 132 G(_G), flow(_flow), capacity(_capacity) { } 133 134 class EdgeIt; 135 class OutEdgeIt; 136 friend class EdgeIt; 137 friend class OutEdgeIt; 138 139 class EdgeIt { 140 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; 141 protected: 142 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG; 143 //OldSymEdgeIt sym; 144 OldOutEdgeIt out; 145 OldInEdgeIt in; 146 bool out_or_in; //1, iff out 147 public: 148 EdgeIt() : out_or_in(1) { } 149 Number free() const { 150 if (out_or_in) { 151 return (resG>capacity.get(out)resG>flow.get(out)); 152 } else { 153 return (resG>flow.get(in)); 154 } 155 } 156 bool valid() const { 157 return out_or_in && out.valid()  in.valid(); } 158 void augment(Number a) const { 159 if (out_or_in) { 160 resG>flow.set(out, resG>flow.get(out)+a); 161 } else { 162 resG>flow.set(in, resG>flow.get(in)a); 163 } 164 } 165 }; 166 167 class OutEdgeIt : public EdgeIt { 168 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; 169 public: 170 OutEdgeIt() { } 171 private: 172 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 173 resG=&_resG; 174 out=resG>G.template first<OldOutEdgeIt>(v); 175 while( out.valid() && !(free()>0) ) { ++out; } 176 if (!out.valid()) { 177 out_or_in=0; 178 in=resG>G.template first<OldInEdgeIt>(v); 179 while( in.valid() && !(free()>0) ) { ++in; } 180 } 181 } 182 public: 183 OutEdgeIt& operator++() { 184 if (out_or_in) { 185 NodeIt v=resG>G.aNode(out); 186 ++out; 187 while( out.valid() && !(free()>0) ) { ++out; } 188 if (!out.valid()) { 189 out_or_in=0; 190 in=resG>G.template first<OldInEdgeIt>(v); 191 while( in.valid() && !(free()>0) ) { ++in; } 192 } 193 } else { 194 ++in; 195 while( in.valid() && !(free()>0) ) { ++in; } 196 } 68 197 return *this; 69 198 } … … 89 218 } 90 219 91 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } 92 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } 93 94 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } 95 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } 220 NodeIt tail(EdgeIt e) const { 221 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 222 NodeIt head(EdgeIt e) const { 223 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 224 225 NodeIt aNode(OutEdgeIt e) const { 226 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 227 NodeIt bNode(OutEdgeIt e) const { 228 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 96 229 97 230 int id(NodeIt v) const { return G.id(v); } … … 101 234 typename Graph::NodeMap<S> node_map; 102 235 public: 103 NodeMap(const ResGraph <Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }104 NodeMap(const ResGraph <Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }236 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } 237 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } 105 238 void set(NodeIt nit, S a) { node_map.set(nit, a); } 106 239 S get(NodeIt nit) const { return node_map.get(nit); } 107 240 }; 108 109 241 }; 110 242 111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> 243 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 244 class ResGraph3 { 245 typedef typename Graph::NodeIt NodeIt; 246 typedef typename Graph::EachNodeIt EachNodeIt; 247 //typedef typename Graph::SymEdgeIt OldSymEdgeIt; 248 typedef typename Graph::OutEdgeIt OldOutEdgeIt; 249 typedef typename Graph::InEdgeIt OldInEdgeIt; 250 251 const Graph& G; 252 FlowMap& flow; 253 const CapacityMap& capacity; 254 public: 255 ResGraph3(const Graph& _G, FlowMap& _flow, 256 const CapacityMap& _capacity) : 257 G(_G), flow(_flow), capacity(_capacity) { } 258 259 class EdgeIt; 260 class OutEdgeIt; 261 friend class EdgeIt; 262 friend class OutEdgeIt; 263 264 class EdgeIt { 265 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>; 266 protected: 267 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG; 268 const Graph* G; 269 FlowMap* flow; 270 const CapacityMap* capacity; 271 //OldSymEdgeIt sym; 272 OldOutEdgeIt out; 273 OldInEdgeIt in; 274 bool out_or_in; //1, iff out 275 public: 276 EdgeIt() : out_or_in(1) { } 277 Number free() const { 278 if (out_or_in) { 279 return (/*resG>*/capacity>get(out)/*resG>*/flow>get(out)); 280 } else { 281 return (/*resG>*/flow>get(in)); 282 } 283 } 284 bool valid() const { 285 return out_or_in && out.valid()  in.valid(); } 286 void augment(Number a) const { 287 if (out_or_in) { 288 /*resG>*/flow>set(out, /*resG>*/flow>get(out)+a); 289 } else { 290 /*resG>*/flow>set(in, /*resG>*/flow>get(in)a); 291 } 292 } 293 }; 294 295 class OutEdgeIt : public EdgeIt { 296 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>; 297 public: 298 OutEdgeIt() { } 299 private: 300 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 301 G=&_G; 302 flow=&_flow; 303 capacity=&_capacity; 304 out=/*resG>*/G>template first<OldOutEdgeIt>(v); 305 while( out.valid() && !(free()>0) ) { ++out; } 306 if (!out.valid()) { 307 out_or_in=0; 308 in=/*resG>*/G>template first<OldInEdgeIt>(v); 309 while( in.valid() && !(free()>0) ) { ++in; } 310 } 311 } 312 public: 313 OutEdgeIt& operator++() { 314 if (out_or_in) { 315 NodeIt v=/*resG>*/G>aNode(out); 316 ++out; 317 while( out.valid() && !(free()>0) ) { ++out; } 318 if (!out.valid()) { 319 out_or_in=0; 320 in=/*resG>*/G>template first<OldInEdgeIt>(v); 321 while( in.valid() && !(free()>0) ) { ++in; } 322 } 323 } else { 324 ++in; 325 while( in.valid() && !(free()>0) ) { ++in; } 326 } 327 return *this; 328 } 329 }; 330 331 void getFirst(OutEdgeIt& e, NodeIt v) const { 332 e=OutEdgeIt(G, v, flow, capacity); 333 } 334 void getFirst(EachNodeIt& v) const { G.getFirst(v); } 335 336 template< typename It > 337 It first() const { 338 It e; 339 getFirst(e); 340 return e; 341 } 342 343 template< typename It > 344 It first(NodeIt v) const { 345 It e; 346 getFirst(e, v); 347 return e; 348 } 349 350 NodeIt tail(EdgeIt e) const { 351 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 352 NodeIt head(EdgeIt e) const { 353 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 354 355 NodeIt aNode(OutEdgeIt e) const { 356 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 357 NodeIt bNode(OutEdgeIt e) const { 358 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 359 360 int id(NodeIt v) const { return G.id(v); } 361 362 template <typename S> 363 class NodeMap { 364 typename Graph::NodeMap<S> node_map; 365 public: 366 NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } 367 NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } 368 void set(NodeIt nit, S a) { node_map.set(nit, a); } 369 S get(NodeIt nit) const { return node_map.get(nit); } 370 }; 371 372 }; 373 374 375 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 112 376 class MaxFlow { 113 377 typedef typename Graph::NodeIt NodeIt; … … 121 385 FlowMap& flow; 122 386 const CapacityMap& capacity; 123 typedef ResGraph <Graph, T, FlowMap, CapacityMap > AugGraph;387 typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph; 124 388 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 125 389 typedef typename AugGraph::EdgeIt AugEdgeIt; 390 391 //AugGraph res_graph; 392 //typedef typename AugGraph::NodeMap<bool> ReachedMap; 393 //typename AugGraph::NodeMap<AugEdgeIt> pred; 394 //typename AugGraph::NodeMap<int> free; 126 395 public: 127 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { } 396 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 397 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 398 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 399 { } 128 400 bool augment() { 129 401 AugGraph res_graph(G, flow, capacity); … … 131 403 132 404 typedef typename AugGraph::NodeMap<bool> ReachedMap; 133 BfsIterator 2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);405 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); 134 406 res_bfs.pushAndSetReached(s); 135 407 136 408 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 137 //filled with invalid iterators 409 //filled up with invalid iterators 410 //pred.set(s, AugEdgeIt()); 138 411 139 412 typename AugGraph::NodeMap<int> free(res_graph); … … 159 432 if (_augment) { 160 433 NodeIt n=t; 161 Taugment_value=free.get(t);434 Number augment_value=free.get(t); 162 435 while (pred.get(n).valid()) { 163 436 AugEdgeIt e=pred.get(n); … … 172 445 while (augment()) { } 173 446 } 174 TflowValue() {175 Ta=0;447 Number flowValue() { 448 Number a=0; 176 449 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { 177 450 a+=flow.get(i); … … 181 454 }; 182 455 456 457 /* 458 template <typename Graph> 459 class IteratorBoolNodeMap { 460 typedef typename Graph::NodeIt NodeIt; 461 typedef typename Graph::EachNodeIt EachNodeIt; 462 class BoolItem { 463 public: 464 bool value; 465 NodeIt prev; 466 NodeIt next; 467 BoolItem() : value(false), prev(), next() {} 468 }; 469 NodeIt first_true; 470 //NodeIt last_true; 471 NodeIt first_false; 472 //NodeIt last_false; 473 const Graph& G; 474 typename Graph::NodeMap<BoolItem> container; 475 public: 476 typedef bool ValueType; 477 typedef NodeIt KeyType; 478 IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { 479 //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) { 480 //BoolItem b=container.get(e); 481 //b.me=e; 482 //container.set(b); 483 //} 484 G.getFirst(first_false); 485 NodeIt e_prev; 486 for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) { 487 container[e].prev=e_prev; 488 if (e_prev.valid()) container[e_prev].next=e; 489 e_prev=e; 490 } 491 } 492 //NodeMap(const Graph& _G, T a) : 493 // G(_G), container(G.node_id, a) { } 494 //FIXME 495 void set(NodeIt nit, T a) { container[G.id(nit)]=a; } 496 T get(NodeIt nit) const { return container[G.id(nit)]; } 497 //void resize() { container.resize(G.node_id); } 498 //void resize(T a) { container.resize(G.node_id, a); } 499 }; 500 */ 501 502 503 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> 504 class MaxFlow2 { 505 typedef typename Graph::NodeIt NodeIt; 506 typedef typename Graph::EdgeIt EdgeIt; 507 typedef typename Graph::EachEdgeIt EachEdgeIt; 508 typedef typename Graph::OutEdgeIt OutEdgeIt; 509 typedef typename Graph::InEdgeIt InEdgeIt; 510 const Graph& G; 511 std::list<NodeIt>& S; 512 std::list<NodeIt>& T; 513 FlowMap& flow; 514 const CapacityMap& capacity; 515 typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph; 516 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 517 typedef typename AugGraph::EdgeIt AugEdgeIt; 518 typename Graph::NodeMap<bool> SMap; 519 typename Graph::NodeMap<bool> TMap; 520 public: 521 MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 522 for(typename std::list<NodeIt>::const_iterator i=S.begin(); 523 i!=S.end(); ++i) { 524 SMap.set(*i, true); 525 } 526 for (typename std::list<NodeIt>::const_iterator i=T.begin(); 527 i!=T.end(); ++i) { 528 TMap.set(*i, true); 529 } 530 } 531 bool augment() { 532 AugGraph res_graph(G, flow, capacity); 533 bool _augment=false; 534 NodeIt reached_t_node; 535 536 typedef typename AugGraph::NodeMap<bool> ReachedMap; 537 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); 538 for(typename std::list<NodeIt>::const_iterator i=S.begin(); 539 i!=S.end(); ++i) { 540 res_bfs.pushAndSetReached(*i); 541 } 542 //res_bfs.pushAndSetReached(s); 543 544 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 545 //filled up with invalid iterators 546 547 typename AugGraph::NodeMap<int> free(res_graph); 548 549 //searching for augmenting path 550 while ( !res_bfs.finished() ) { 551 AugOutEdgeIt e=AugOutEdgeIt(res_bfs); 552 if (e.valid() && res_bfs.isBNodeNewlyReached()) { 553 NodeIt v=res_graph.tail(e); 554 NodeIt w=res_graph.head(e); 555 pred.set(w, e); 556 if (pred.get(v).valid()) { 557 free.set(w, std::min(free.get(v), e.free())); 558 } else { 559 free.set(w, e.free()); 560 } 561 if (TMap.get(res_graph.head(e))) { 562 _augment=true; 563 reached_t_node=res_graph.head(e); 564 break; 565 } 566 } 567 568 ++res_bfs; 569 } //end of searching augmenting path 570 571 if (_augment) { 572 NodeIt n=reached_t_node; 573 Number augment_value=free.get(reached_t_node); 574 while (pred.get(n).valid()) { 575 AugEdgeIt e=pred.get(n); 576 e.augment(augment_value); 577 n=res_graph.tail(e); 578 } 579 } 580 581 return _augment; 582 } 583 void run() { 584 while (augment()) { } 585 } 586 Number flowValue() { 587 Number a=0; 588 for(typename std::list<NodeIt>::const_iterator i=S.begin(); 589 i!=S.end(); ++i) { 590 for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { 591 a+=flow.get(e); 592 } 593 for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { 594 a=flow.get(e); 595 } 596 } 597 return a; 598 } 599 }; 600 601 602 183 603 } // namespace marci 184 604
Note: See TracChangeset
for help on using the changeset viewer.