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

 1 added
 4 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r64 r75 4 4 #include <queue> 5 5 #include <stack> 6 #include <utility> 7 #include <graph_wrapper.h> 6 8 7 9 namespace marci { … … 467 469 }; 468 470 471 472 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 473 class BfsIterator3 { 474 typedef typename Graph::NodeIt NodeIt; 475 const Graph& G; 476 std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue; 477 ReachedMap reached; 478 bool b_node_newly_reached; 479 OutEdgeIt actual_edge; 480 public: 481 BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { } 482 void pushAndSetReached(NodeIt s) { 483 reached.set(s, true); 484 if (bfs_queue.empty()) { 485 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); 486 actual_edge=bfs_queue.front().second; 487 if (actual_edge.valid()) { 488 NodeIt w=G.bNode(actual_edge); 489 if (!reached.get(w)) { 490 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); 491 reached.set(w, true); 492 b_node_newly_reached=true; 493 } else { 494 b_node_newly_reached=false; 495 } 496 } //else { 497 //} 498 } else { 499 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); 500 } 501 } 502 BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 503 operator++() { 504 if (bfs_queue.front().second.valid()) { 505 ++(bfs_queue.front().second); 506 actual_edge=bfs_queue.front().second; 507 if (actual_edge.valid()) { 508 NodeIt w=G.bNode(actual_edge); 509 if (!reached.get(w)) { 510 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); 511 reached.set(w, true); 512 b_node_newly_reached=true; 513 } else { 514 b_node_newly_reached=false; 515 } 516 } 517 } else { 518 bfs_queue.pop(); 519 if (!bfs_queue.empty()) { 520 actual_edge=bfs_queue.front().second; 521 if (actual_edge.valid()) { 522 NodeIt w=G.bNode(actual_edge); 523 if (!reached.get(w)) { 524 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); 525 reached.set(w, true); 526 b_node_newly_reached=true; 527 } else { 528 b_node_newly_reached=false; 529 } 530 } 531 } 532 } 533 return *this; 534 } 535 bool finished() const { return bfs_queue.empty(); } 536 operator OutEdgeIt () const { return actual_edge; } 537 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 538 bool isANodeExamined() const { return !(actual_edge.valid()); } 539 NodeIt aNode() const { return bfs_queue.front().first; } 540 NodeIt bNode() const { return G.bNode(actual_edge); } 541 const ReachedMap& getReachedMap() const { return reached; } 542 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } 543 }; 544 545 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 546 class BfsIterator4 { 547 typedef typename Graph::NodeIt NodeIt; 548 const Graph& G; 549 std::queue<NodeIt> bfs_queue; 550 ReachedMap reached; 551 bool b_node_newly_reached; 552 OutEdgeIt actual_edge; 553 public: 554 BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { } 555 void pushAndSetReached(NodeIt s) { 556 reached.set(s, true); 557 if (bfs_queue.empty()) { 558 bfs_queue.push(s); 559 G.getFirst(actual_edge, s); 560 if (actual_edge.valid()) { 561 NodeIt w=G.bNode(actual_edge); 562 if (!reached.get(w)) { 563 bfs_queue.push(w); 564 reached.set(w, true); 565 b_node_newly_reached=true; 566 } else { 567 b_node_newly_reached=false; 568 } 569 } 570 } else { 571 bfs_queue.push(s); 572 } 573 } 574 BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 575 operator++() { 576 if (actual_edge.valid()) { 577 ++actual_edge; 578 if (actual_edge.valid()) { 579 NodeIt w=G.bNode(actual_edge); 580 if (!reached.get(w)) { 581 bfs_queue.push(w); 582 reached.set(w, true); 583 b_node_newly_reached=true; 584 } else { 585 b_node_newly_reached=false; 586 } 587 } 588 } else { 589 bfs_queue.pop(); 590 if (!bfs_queue.empty()) { 591 G.getFirst(actual_edge, bfs_queue.front()); 592 if (actual_edge.valid()) { 593 NodeIt w=G.bNode(actual_edge); 594 if (!reached.get(w)) { 595 bfs_queue.push(w); 596 reached.set(w, true); 597 b_node_newly_reached=true; 598 } else { 599 b_node_newly_reached=false; 600 } 601 } 602 } 603 } 604 return *this; 605 } 606 bool finished() const { return bfs_queue.empty(); } 607 operator OutEdgeIt () const { return actual_edge; } 608 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 609 bool isANodeExamined() const { return !(actual_edge.valid()); } 610 NodeIt aNode() const { return bfs_queue.front(); } 611 NodeIt bNode() const { return G.bNode(actual_edge); } 612 const ReachedMap& getReachedMap() const { return reached; } 613 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 614 }; 615 616 617 template <typename GraphWrapper, typename ReachedMap> 618 class BfsIterator5 { 619 typedef typename GraphWrapper::NodeIt NodeIt; 620 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 621 GraphWrapper gw; 622 std::queue<NodeIt> bfs_queue; 623 ReachedMap reached; 624 bool b_node_newly_reached; 625 OutEdgeIt actual_edge; 626 public: 627 BfsIterator5(GraphWrapper _gw) : 628 gw(_gw), reached(_gw.getGraph()) { } 629 void pushAndSetReached(NodeIt s) { 630 reached.set(s, true); 631 if (bfs_queue.empty()) { 632 bfs_queue.push(s); 633 gw.getFirst(actual_edge, s); 634 if (actual_edge.valid()) { 635 NodeIt w=gw.bNode(actual_edge); 636 if (!reached.get(w)) { 637 bfs_queue.push(w); 638 reached.set(w, true); 639 b_node_newly_reached=true; 640 } else { 641 b_node_newly_reached=false; 642 } 643 } 644 } else { 645 bfs_queue.push(s); 646 } 647 } 648 BfsIterator5<GraphWrapper, ReachedMap>& 649 operator++() { 650 if (actual_edge.valid()) { 651 ++actual_edge; 652 if (actual_edge.valid()) { 653 NodeIt w=gw.bNode(actual_edge); 654 if (!reached.get(w)) { 655 bfs_queue.push(w); 656 reached.set(w, true); 657 b_node_newly_reached=true; 658 } else { 659 b_node_newly_reached=false; 660 } 661 } 662 } else { 663 bfs_queue.pop(); 664 if (!bfs_queue.empty()) { 665 gw.getFirst(actual_edge, bfs_queue.front()); 666 if (actual_edge.valid()) { 667 NodeIt w=gw.bNode(actual_edge); 668 if (!reached.get(w)) { 669 bfs_queue.push(w); 670 reached.set(w, true); 671 b_node_newly_reached=true; 672 } else { 673 b_node_newly_reached=false; 674 } 675 } 676 } 677 } 678 return *this; 679 } 680 bool finished() const { return bfs_queue.empty(); } 681 operator OutEdgeIt () const { return actual_edge; } 682 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 683 bool isANodeExamined() const { return !(actual_edge.valid()); } 684 NodeIt aNode() const { return bfs_queue.front(); } 685 NodeIt bNode() const { return gw.bNode(actual_edge); } 686 const ReachedMap& getReachedMap() const { return reached; } 687 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 688 }; 689 690 691 469 692 } // namespace marci 470 693 
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 
src/work/list_graph.hh
r69 r75 45 45 NodeMap(const ListGraph& _G, T a) : 46 46 G(_G), container(G.node_id, a) { } 47 void set(NodeIt nit, T a) { container[G.id(nit)]=a; } 48 T get(NodeIt nit) const { return container[G.id(nit)]; } 47 void set(NodeIt n, T a) { container[/*G.id(n)*/n.node>id]=a; } 48 T get(NodeIt n) const { return container[/*G.id(n)*/n.node>id]; } 49 T& operator[](NodeIt n) { return container[/*G.id(n)*/n.node>id]; } 50 const T& operator[](NodeIt n) const { return container[/*G.id(n)*/n.node>id]; } 49 51 void resize() { container.resize(G.node_id); } 50 52 void resize(T a) { container.resize(G.node_id, a); } … … 61 63 EdgeMap(const ListGraph& _G, T a) : 62 64 G(_G), container(G.edge_id, a) { } 63 void set(EdgeIt eit, T a) { container[G.id(eit)]=a; } 64 T get(EdgeIt eit) const { return container[G.id(eit)]; } 65 void set(EdgeIt e, T a) { container[/*G.id(e)*/e.edge>id]=a; } 66 T get(EdgeIt e) const { return container[/*G.id(e)*/e.edge>id]; } 67 T& operator[](EdgeIt e) { return container[/*G.id(e)*/e.edge>id]; } 68 const T& operator[](EdgeIt e) const { return container[/*G.id(e)*/e.edge>id]; } 65 69 void resize() { container.resize(G.edge_id); } 66 70 void resize(T a) { container.resize(G.edge_id, a); } … … 77 81 class node_item { 78 82 friend class ListGraph; 83 template <typename T> friend class NodeMap; 84 79 85 friend class NodeIt; 80 86 friend class EachNodeIt; … … 100 106 class edge_item { 101 107 friend class ListGraph; 108 template <typename T> friend class EdgeMap; 109 102 110 friend class NodeIt; 103 111 friend class EachNodeIt; … … 255 263 /* for experimental purpose */ 256 264 257 void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); } 258 void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); } 259 void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); } 260 void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); } 261 void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); } 265 EachNodeIt& getFirst(EachNodeIt& v) const { 266 v=EachNodeIt(*this); return v; } 267 EachEdgeIt& getFirst(EachEdgeIt& e) const { 268 e=EachEdgeIt(*this); return e; } 269 OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 270 e=OutEdgeIt(v); return e; } 271 InEdgeIt& getFirst(InEdgeIt& e, NodeIt v) const { 272 e=InEdgeIt(v); return e; } 273 SymEdgeIt& getFirst(SymEdgeIt& e, NodeIt v) const { 274 e=SymEdgeIt(v); return e; } 262 275 //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); } 263 276 //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); } … … 334 347 class NodeIt { 335 348 friend class ListGraph; 349 template <typename T> friend class NodeMap; 336 350 337 351 friend class EdgeIt; … … 368 382 class EdgeIt { 369 383 friend class ListGraph; 384 template <typename T> friend class EdgeMap; 370 385 371 386 friend class NodeIt; … … 414 429 class OutEdgeIt : public EdgeIt { 415 430 friend class ListGraph; 416 node_item* v;417 protected: 418 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v>_first_out_edge; }419 public: 420 OutEdgeIt() : EdgeIt() , v(0){ }421 OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v>_first_out_edge; }431 //node_item* v; 432 protected: 433 OutEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node>_first_out_edge; } 434 public: 435 OutEdgeIt() : EdgeIt()/*, v(0)*/ { } 436 OutEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node>_first_out_edge; } 422 437 OutEdgeIt& operator++() { edge=edge>_next_out; return *this; } 423 438 protected: 424 NodeIt aNode() const { return NodeIt(v); } 425 NodeIt bNode() const { 426 return (edge>_tail==v) ? NodeIt(edge>_head) : NodeIt(edge>_tail); } 439 NodeIt aNode() const { return NodeIt(edge>_tail); } 440 NodeIt bNode() const { return NodeIt(edge>_head); } 427 441 }; 428 442 429 443 class InEdgeIt : public EdgeIt { 430 444 friend class ListGraph; 431 node_item* v;432 protected: 433 InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v>_first_in_edge; }434 public: 435 InEdgeIt() : EdgeIt() , v(0){ }436 InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v>_first_in_edge; }445 //node_item* v; 446 protected: 447 InEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node>_first_in_edge; } 448 public: 449 InEdgeIt() : EdgeIt()/*, v(0)*/ { } 450 InEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node>_first_in_edge; } 437 451 InEdgeIt& operator++() { edge=edge>_next_in; return *this; } 438 452 protected: 439 NodeIt aNode() const { return NodeIt(v); } 440 NodeIt bNode() const { 441 return (edge>_tail==v) ? NodeIt(edge>_head) : NodeIt(edge>_tail); } 453 NodeIt aNode() const { return NodeIt(edge>_head); } 454 NodeIt bNode() const { return NodeIt(edge>_tail); } 442 455 }; 443 456 … … 445 458 friend class ListGraph; 446 459 bool out_or_in; //1 iff out, 0 iff in 447 node_item* v;448 protected: 449 SymEdgeIt(const NodeIt& _v) : v(_v.node){460 //node_item* v; 461 protected: 462 SymEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { 450 463 out_or_in=1; 451 edge= v>_first_out_edge;452 if (!edge) { edge= v>_first_in_edge; out_or_in=0; }464 edge=_v.node>_first_out_edge; 465 if (!edge) { edge=_v.node>_first_in_edge; out_or_in=0; } 453 466 } 454 467 public: 455 SymEdgeIt() : EdgeIt() , v(0){ }456 SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node){468 SymEdgeIt() : EdgeIt() /*, v(0)*/ { } 469 SymEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { 457 470 out_or_in=1; 458 edge= v>_first_out_edge;459 if (!edge) { edge= v>_first_in_edge; out_or_in=0; }471 edge=_v.node>_first_out_edge; 472 if (!edge) { edge=_v.node>_first_in_edge; out_or_in=0; } 460 473 } 461 474 SymEdgeIt& operator++() { 462 475 if (out_or_in) { 476 node_item* v=edge>_tail; 463 477 edge=edge>_next_out; 464 478 if (!edge) { out_or_in=0; edge=v>_first_in_edge; } … … 469 483 } 470 484 protected: 471 NodeIt aNode() const { return NodeIt(v); } 485 NodeIt aNode() const { 486 return (out_or_in) ? NodeIt(edge>_tail) : NodeIt(edge>_head); } 472 487 NodeIt bNode() const { 473 return ( edge>_tail==v) ? NodeIt(edge>_head) : NodeIt(edge>_tail); }488 return (out_or_in) ? NodeIt(edge>_head) : NodeIt(edge>_tail); } 474 489 }; 475 490 
src/work/marci_graph_demo.cc
r69 r75 95 95 } 96 96 std::cout << std::endl; 97 97 /* 98 98 std::cout << "bfs from the first node" << std::endl; 99 99 bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>()); … … 109 109 } 110 110 std::cout<<std::endl; 111 111 */ 112 112 113 113 std::cout << "augmenting path flow algorithm test..." << std::endl; … … 174 174 //flowG.setTail(v3_t, v2); 175 175 //flowG.setHead(v3_t, s); 176 176 /* 177 177 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 178 178 std::cout << node_name.get(i) << ": "; … … 189 189 std::cout << node_name.get(flowG.tail(e)) << ""<< cap.get(e) << ">" << node_name.get(flowG.head(e)) << " "; 190 190 } 191 191 */ 192 192 /* 193 193 while (flowG.first<EachEdgeIt>().valid()) { … … 220 220 */ 221 221 222 std::cout << std::endl; 223 //std::cout << "meg jo" << std::flush; 224 225 ListGraph::EdgeMap<int> flow(flowG, 0); 226 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap); 227 max_flow_test.run(); 228 229 std::cout << "maximum flow: "<< std::endl; 230 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 231 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 232 } 233 std::cout<<std::endl; 234 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 222 //std::cout << std::endl; 223 224 225 { 226 ListGraph::EdgeMap<int> flow(flowG, 0); 227 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap); 228 max_flow_test.run(); 229 230 std::cout << "maximum flow: "<< std::endl; 231 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 232 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 233 } 234 std::cout<<std::endl; 235 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 236 } 237 238 { 239 std::list<NodeIt> S; 240 S.push_back(s); S.push_back(v3); 241 std::list<NodeIt> T; 242 T.push_back(t); 243 244 ListGraph::EdgeMap<int> flow(flowG, 0); 245 MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap); 246 max_flow_test.run(); 247 248 std::cout << "maximum flow: "<< std::endl; 249 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 250 std::cout<<"("<<flowG.tail(e)<< ""<<flow.get(e)<<">"<<flowG.head(e)<<") "; 251 } 252 std::cout<<std::endl; 253 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 254 } 235 255 236 256 return 0;
Note: See TracChangeset
for help on using the changeset viewer.