COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 133:0631992fe7a1

Last change on this file since 133:0631992fe7a1 was 133:0631992fe7a1, checked in by marci, 17 years ago

Dinits blocking flow added to edmonds_karp_demo.hh.

File size: 23.7 KB
Line 
1#ifndef EDMONDS_KARP_HH
2#define EDMONDS_KARP_HH
3
4#include <algorithm>
5#include <list>
6#include <iterator>
7
8#include <bfs_iterator.hh>
9//#include <time_measure.h>
10
11namespace hugo {
12
13  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
14  class ResGraph {
15  public:
16    typedef typename Graph::NodeIt NodeIt;
17    typedef typename Graph::EachNodeIt EachNodeIt;
18  private:
19    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
20    const Graph& G;
21    FlowMap& flow;
22    const CapacityMap& capacity;
23  public:
24    ResGraph(const Graph& _G, FlowMap& _flow,
25             const CapacityMap& _capacity) :
26      G(_G), flow(_flow), capacity(_capacity) { }
27
28    class EdgeIt;
29    class OutEdgeIt;
30    friend class EdgeIt;
31    friend class OutEdgeIt;
32
33    class EdgeIt {
34      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
35    protected:
36      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
37      OldSymEdgeIt sym;
38    public:
39      EdgeIt() { }
40      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
41      Number free() const {
42        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
43          return (resG->capacity.get(sym)-resG->flow.get(sym));
44        } else {
45          return (resG->flow.get(sym));
46        }
47      }
48      bool valid() const { return sym.valid(); }
49      void augment(Number a) const {
50        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
51          resG->flow.set(sym, resG->flow.get(sym)+a);
52          //resG->flow[sym]+=a;
53        } else {
54          resG->flow.set(sym, resG->flow.get(sym)-a);
55          //resG->flow[sym]-=a;
56        }
57      }
58    };
59
60    class OutEdgeIt : public EdgeIt {
61      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
62    public:
63      OutEdgeIt() { }
64      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
65    private:
66      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
67        resG=&_resG;
68        sym=resG->G.template first<OldSymEdgeIt>(v);
69        while( sym.valid() && !(free()>0) ) { ++sym; }
70      }
71    public:
72      OutEdgeIt& operator++() {
73        ++sym;
74        while( sym.valid() && !(free()>0) ) { ++sym; }
75        return *this;
76      }
77    };
78
79    void getFirst(OutEdgeIt& e, NodeIt v) const {
80      e=OutEdgeIt(*this, v);
81    }
82    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
83   
84    template< typename It >
85    It first() const {
86      It e;     
87      getFirst(e);
88      return e;
89    }
90
91    template< typename It >
92    It first(NodeIt v) const {
93      It e;
94      getFirst(e, v);
95      return e;
96    }
97
98    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
99    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
100
101    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
102    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
103
104    int id(NodeIt v) const { return G.id(v); }
105
106    template <typename S>
107    class NodeMap {
108      typename Graph::NodeMap<S> node_map;
109    public:
110      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
111      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
112      void set(NodeIt nit, S a) { node_map.set(nit, a); }
113      S get(NodeIt nit) const { return node_map.get(nit); }
114      S& operator[](NodeIt nit) { return node_map[nit]; }
115      const S& operator[](NodeIt nit) const { return node_map[nit]; }
116    };
117
118  };
119
120
121  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
122  class ResGraph2 {
123  public:
124    typedef typename Graph::NodeIt NodeIt;
125    typedef typename Graph::EachNodeIt EachNodeIt;
126  private:
127    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
128    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
129    typedef typename Graph::InEdgeIt OldInEdgeIt;
130   
131    const Graph& G;
132    FlowMap& flow;
133    const CapacityMap& capacity;
134  public:
135    ResGraph2(const Graph& _G, FlowMap& _flow,
136             const CapacityMap& _capacity) :
137      G(_G), flow(_flow), capacity(_capacity) { }
138
139    class EdgeIt;
140    class OutEdgeIt;
141    friend class EdgeIt;
142    friend class OutEdgeIt;
143
144    class EdgeIt {
145      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
146    protected:
147      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
148      //OldSymEdgeIt sym;
149      OldOutEdgeIt out;
150      OldInEdgeIt in;
151      bool out_or_in; //1, iff out
152    public:
153      EdgeIt() : out_or_in(1) { }
154      Number free() const {
155        if (out_or_in) {
156          return (resG->capacity.get(out)-resG->flow.get(out));
157        } else {
158          return (resG->flow.get(in));
159        }
160      }
161      bool valid() const {
162        return out_or_in && out.valid() || in.valid(); }
163      void augment(Number a) const {
164        if (out_or_in) {
165          resG->flow.set(out, resG->flow.get(out)+a);
166        } else {
167          resG->flow.set(in, resG->flow.get(in)-a);
168        }
169      }
170    };
171
172    class OutEdgeIt : public EdgeIt {
173      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
174    public:
175      OutEdgeIt() { }
176    private:
177      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
178        resG=&_resG;
179        out=resG->G.template first<OldOutEdgeIt>(v);
180        while( out.valid() && !(free()>0) ) { ++out; }
181        if (!out.valid()) {
182          out_or_in=0;
183          in=resG->G.template first<OldInEdgeIt>(v);
184          while( in.valid() && !(free()>0) ) { ++in; }
185        }
186      }
187    public:
188      OutEdgeIt& operator++() {
189        if (out_or_in) {
190          NodeIt v=resG->G.aNode(out);
191          ++out;
192          while( out.valid() && !(free()>0) ) { ++out; }
193          if (!out.valid()) {
194            out_or_in=0;
195            in=resG->G.template first<OldInEdgeIt>(v);
196            while( in.valid() && !(free()>0) ) { ++in; }
197          }
198        } else {
199          ++in;
200          while( in.valid() && !(free()>0) ) { ++in; }
201        }
202        return *this;
203      }
204    };
205
206    void getFirst(OutEdgeIt& e, NodeIt v) const {
207      e=OutEdgeIt(*this, v);
208    }
209    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
210   
211    template< typename It >
212    It first() const {
213      It e;
214      getFirst(e);
215      return e;
216    }
217
218    template< typename It >
219    It first(NodeIt v) const {
220      It e;
221      getFirst(e, v);
222      return e;
223    }
224
225    NodeIt tail(EdgeIt e) const {
226      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
227    NodeIt head(EdgeIt e) const {
228      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
229
230    NodeIt aNode(OutEdgeIt e) const {
231      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
232    NodeIt bNode(OutEdgeIt e) const {
233      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
234
235    int id(NodeIt v) const { return G.id(v); }
236
237    template <typename S>
238    class NodeMap {
239      typename Graph::NodeMap<S> node_map;
240    public:
241      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
242      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
243      void set(NodeIt nit, S a) { node_map.set(nit, a); }
244      S get(NodeIt nit) const { return node_map.get(nit); }
245    };
246  };
247
248  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
249  class ResGraph3 {
250  public:
251    typedef typename Graph::NodeIt NodeIt;
252    typedef typename Graph::EachNodeIt EachNodeIt;
253
254  private:
255    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
256    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
257    typedef typename Graph::InEdgeIt OldInEdgeIt;
258    const Graph& G;
259    FlowMap& flow;
260    const CapacityMap& capacity;
261  public:
262    ResGraph3(const Graph& _G, FlowMap& _flow,
263             const CapacityMap& _capacity) :
264      G(_G), flow(_flow), capacity(_capacity) { }
265
266    class EdgeIt;
267    class OutEdgeIt;
268    friend class EdgeIt;
269    friend class OutEdgeIt;
270
271    class EdgeIt {
272      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
273    protected:
274      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
275      const Graph* G;
276      FlowMap* flow;
277      const CapacityMap* capacity;
278      //OldSymEdgeIt sym;
279      OldOutEdgeIt out;
280      OldInEdgeIt in;
281      bool out_or_in; //1, iff out
282    public:
283      EdgeIt() : out_or_in(1) { }
284      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
285      Number free() const {
286        if (out_or_in) {
287          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
288        } else {
289          return (/*resG->*/flow->get(in));
290        }
291      }
292      bool valid() const {
293        return out_or_in && out.valid() || in.valid(); }
294      void augment(Number a) const {
295        if (out_or_in) {
296          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
297        } else {
298          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
299        }
300      }
301      void print() {
302        if (out_or_in) {
303          std::cout << "out ";
304          if (out.valid())
305            std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
306          else
307            std::cout << "invalid";
308        }
309        else {
310          std::cout << "in ";
311          if (in.valid())
312            std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
313          else
314            std::cout << "invalid";
315        }
316        std::cout << std::endl;
317      }
318    };
319
320    class OutEdgeIt : public EdgeIt {
321      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
322    public:
323      OutEdgeIt() { }
324    private:
325      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
326        G=&_G;
327        flow=&_flow;
328        capacity=&_capacity;
329        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
330        G->getFirst(out, v);
331        while( out.valid() && !(free()>0) ) { ++out; }
332        if (!out.valid()) {
333          out_or_in=0;
334          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
335          G->getFirst(in, v);
336          while( in.valid() && !(free()>0) ) { ++in; }
337        }
338      }
339    public:
340      OutEdgeIt& operator++() {
341        if (out_or_in) {
342          NodeIt v=/*resG->*/G->aNode(out);
343          ++out;
344          while( out.valid() && !(free()>0) ) { ++out; }
345          if (!out.valid()) {
346            out_or_in=0;
347            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
348            while( in.valid() && !(free()>0) ) { ++in; }
349          }
350        } else {
351          ++in;
352          while( in.valid() && !(free()>0) ) { ++in; }
353        }
354        return *this;
355      }
356    };
357
358    class EachEdgeIt : public EdgeIt {
359      typename Graph::EachNodeIt v;
360    public:
361      EachEdgeIt() { }
362      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
363      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
364        G=&_G;
365        flow=&_flow;
366        capacity=&_capacity;
367        out_or_in=1;
368        G->getFirst(v);
369        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
370        while (out.valid() && !(free()>0) ) { ++out; }
371        while (v.valid() && !out.valid()) {
372          ++v;
373          if (v.valid()) G->getFirst(out, v);
374          while (out.valid() && !(free()>0) ) { ++out; }
375        }
376        if (!out.valid()) {
377          out_or_in=0;
378          G->getFirst(v);
379          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
380          while (in.valid() && !(free()>0) ) { ++in; }
381          while (v.valid() && !in.valid()) {
382            ++v;
383            if (v.valid()) G->getFirst(in, v);
384            while (in.valid() && !(free()>0) ) { ++in; }
385          }
386        }
387      }
388      EachEdgeIt& operator++() {
389        if (out_or_in) {
390          ++out;
391          while (out.valid() && !(free()>0) ) { ++out; }
392          while (v.valid() && !out.valid()) {
393            ++v;
394            if (v.valid()) G->getFirst(out, v);
395            while (out.valid() && !(free()>0) ) { ++out; }
396          }
397          if (!out.valid()) {
398            out_or_in=0;
399            G->getFirst(v);
400            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
401            while (in.valid() && !(free()>0) ) { ++in; }
402            while (v.valid() && !in.valid()) {
403              ++v;
404              if (v.valid()) G->getFirst(in, v);
405              while (in.valid() && !(free()>0) ) { ++in; }
406            } 
407          }
408        } else {
409          ++in;
410          while (in.valid() && !(free()>0) ) { ++in; }
411          while (v.valid() && !in.valid()) {
412            ++v;
413            if (v.valid()) G->getFirst(in, v);
414            while (in.valid() && !(free()>0) ) { ++in; }
415          }
416        }
417        return *this;
418      }
419    };
420
421    void getFirst(OutEdgeIt& e, NodeIt v) const {
422      e=OutEdgeIt(G, v, flow, capacity);
423    }
424    void getFirst(EachEdgeIt& e) const {
425      e=EachEdgeIt(G, flow, capacity);
426    }
427    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
428   
429    template< typename It >
430    It first() const {
431      It e;
432      getFirst(e);
433      return e;
434    }
435
436    template< typename It >
437    It first(NodeIt v) const {
438      It e;
439      getFirst(e, v);
440      return e;
441    }
442
443    NodeIt tail(EdgeIt e) const {
444      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
445    NodeIt head(EdgeIt e) const {
446      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
447
448    NodeIt aNode(OutEdgeIt e) const {
449      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
450    NodeIt bNode(OutEdgeIt e) const {
451      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
452
453    int id(NodeIt v) const { return G.id(v); }
454
455    template <typename S>
456    class NodeMap {
457      typename Graph::NodeMap<S> node_map;
458    public:
459      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
460      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
461      void set(NodeIt nit, S a) { node_map.set(nit, a); }
462      S get(NodeIt nit) const { return node_map.get(nit); }
463    };
464
465  };
466
467
468  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
469  class MaxFlow {
470  public:
471    typedef typename Graph::NodeIt NodeIt;
472    typedef typename Graph::EdgeIt EdgeIt;
473    typedef typename Graph::EachEdgeIt EachEdgeIt;
474    typedef typename Graph::OutEdgeIt OutEdgeIt;
475    typedef typename Graph::InEdgeIt InEdgeIt;
476
477  private:
478    const Graph& G;
479    NodeIt s;
480    NodeIt t;
481    FlowMap& flow;
482    const CapacityMap& capacity;
483    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
484    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
485    typedef typename AugGraph::EdgeIt AugEdgeIt;
486
487    //AugGraph res_graph;   
488    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
489    //typename AugGraph::NodeMap<AugEdgeIt> pred;
490    //typename AugGraph::NodeMap<Number> free;
491  public:
492    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
493      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
494      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
495      { }
496    bool augmentOnShortestPath() {
497      AugGraph res_graph(G, flow, capacity);
498      bool _augment=false;
499     
500      typedef typename AugGraph::NodeMap<bool> ReachedMap;
501      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
502      res_bfs.pushAndSetReached(s);
503       
504      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
505      //filled up with invalid iterators
506      //pred.set(s, AugEdgeIt());
507     
508      typename AugGraph::NodeMap<Number> free(res_graph);
509       
510      //searching for augmenting path
511      while ( !res_bfs.finished() ) {
512        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
513        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
514          NodeIt v=res_graph.tail(e);
515          NodeIt w=res_graph.head(e);
516          pred.set(w, e);
517          if (pred.get(v).valid()) {
518            free.set(w, std::min(free.get(v), e.free()));
519          } else {
520            free.set(w, e.free());
521          }
522          if (res_graph.head(e)==t) { _augment=true; break; }
523        }
524       
525        ++res_bfs;
526      } //end of searching augmenting path
527
528      if (_augment) {
529        NodeIt n=t;
530        Number augment_value=free.get(t);
531        while (pred.get(n).valid()) {
532          AugEdgeIt e=pred.get(n);
533          e.augment(augment_value);
534          n=res_graph.tail(e);
535        }
536      }
537
538      return _augment;
539    }
540    template<typename MutableGraph> bool augmentOnBlockingFlow() {
541      bool _augment=false;
542
543      AugGraph res_graph(G, flow, capacity);
544
545      typedef typename AugGraph::NodeMap<bool> ReachedMap;
546      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
547
548      bfs.pushAndSetReached(s);
549      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
550      while ( !bfs.finished() ) {
551        AugOutEdgeIt e=AugOutEdgeIt(bfs);
552        if (e.valid() && bfs.isBNodeNewlyReached()) {
553          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
554        }
555       
556        ++bfs;
557      } //computing distances from s in the residual graph
558
559      MutableGraph F;
560      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
561      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
562        res_graph_to_F.set(n, F.addNode());
563      }
564     
565      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
566      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
567
568      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
569      typename MutableGraph::EdgeMap<Number> free_on_edge(F);
570
571      //Making F to the graph containing the edges of the residual graph
572      //which are in some shortest paths
573      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
574        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
575          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
576          original_edge.update();
577          original_edge.set(f, e);
578          free_on_edge.update();
579          free_on_edge.set(f, e.free());
580        }
581      }
582
583      bool __augment=true;
584
585      while (__augment) {
586        __augment=false;
587        //computing blocking flow with dfs
588        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
589        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
590        typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
591        typename MutableGraph::NodeMap<Number> free(F);
592
593        dfs.pushAndSetReached(sF);     
594        while (!dfs.finished()) {
595          ++dfs;
596          if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
597            //std::cout << "OutEdgeIt: " << dfs;
598            //std::cout << " aNode: " << F.aNode(dfs);
599            //std::cout << " bNode: " << F.bNode(dfs) << " ";
600         
601            typename MutableGraph::NodeIt v=F.aNode(dfs);
602            typename MutableGraph::NodeIt w=F.bNode(dfs);
603            pred.set(w, dfs);
604            if (pred.get(v).valid()) {
605              free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
606            } else {
607              free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
608            }
609            if (w==tF) {
610              //std::cout << "AUGMENTATION"<<std::endl;
611              __augment=true;
612              _augment=true;
613              break;
614            }
615          } else {
616            //std::cout << "OutEdgeIt: " << "invalid";
617            //std::cout << " aNode: " << dfs.aNode();
618            //std::cout << " bNode: " << "invalid" << " ";
619          }
620          if (dfs.isBNodeNewlyReached()) {
621            //std::cout << "bNodeIsNewlyReached ";
622          } else {
623            //std::cout << "bNodeIsNotNewlyReached ";
624            if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
625              //std::cout << "DELETE ";
626              F.erase(typename MutableGraph::OutEdgeIt(dfs));
627            }
628          }
629          //if (dfs.isANodeExamined()) {
630            //std::cout << "aNodeIsExamined ";
631            //} else {
632            //std::cout << "aNodeIsNotExamined ";
633            //}
634          //std::cout<<std::endl;
635        }
636
637        if (__augment) {
638          typename MutableGraph::NodeIt n=tF;
639          Number augment_value=free.get(tF);
640          while (pred.get(n).valid()) {
641            typename MutableGraph::EdgeIt e=pred.get(n);
642            original_edge.get(e).augment(augment_value);
643            n=F.tail(e);
644            F.erase(e);
645          }
646        }
647
648      }
649           
650      return _augment;
651    }
652    void run() {
653      //int num_of_augmentations=0;
654      while (augmentOnShortestPath()) {
655        //while (augmentOnBlockingFlow<MutableGraph>()) {
656        //std::cout << ++num_of_augmentations << " ";
657        //std::cout<<std::endl;
658      }
659    }
660    template<typename MutableGraph> void run() {
661      //int num_of_augmentations=0;
662      //while (augmentOnShortestPath()) {
663        while (augmentOnBlockingFlow<MutableGraph>()) {
664        //std::cout << ++num_of_augmentations << " ";
665        //std::cout<<std::endl;
666      }
667    }
668    Number flowValue() {
669      Number a=0;
670      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
671        a+=flow.get(i);
672      }
673      return a;
674    }
675  };
676
677
678/*
679  template <typename Graph>
680  class IteratorBoolNodeMap {
681    typedef typename Graph::NodeIt NodeIt;
682    typedef typename Graph::EachNodeIt EachNodeIt;
683    class BoolItem {
684    public:
685      bool value;
686      NodeIt prev;
687      NodeIt next;
688      BoolItem() : value(false), prev(), next() {}
689    };
690    NodeIt first_true;
691    //NodeIt last_true;
692    NodeIt first_false;
693    //NodeIt last_false;
694    const Graph& G;
695    typename Graph::NodeMap<BoolItem> container;
696  public:
697    typedef bool ValueType;
698    typedef NodeIt KeyType;
699    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
700      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
701      //BoolItem b=container.get(e);
702      //b.me=e;
703      //container.set(b);
704      //}
705      G.getFirst(first_false);
706      NodeIt e_prev;
707      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
708        container[e].prev=e_prev;
709        if (e_prev.valid()) container[e_prev].next=e;
710        e_prev=e;
711      }
712    }
713    //NodeMap(const Graph& _G, T a) :
714    //  G(_G), container(G.node_id, a) { }
715    //FIXME
716    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
717    T get(NodeIt nit) const { return container[G.id(nit)]; }
718    //void update() { container.resize(G.node_id); }
719    //void update(T a) { container.resize(G.node_id, a); }
720  };
721*/
722
723 
724  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
725  class MaxFlow2 {
726  public:
727    typedef typename Graph::NodeIt NodeIt;
728    typedef typename Graph::EdgeIt EdgeIt;
729    typedef typename Graph::EachEdgeIt EachEdgeIt;
730    typedef typename Graph::OutEdgeIt OutEdgeIt;
731    typedef typename Graph::InEdgeIt InEdgeIt;
732  private:
733    const Graph& G;
734    std::list<NodeIt>& S;
735    std::list<NodeIt>& T;
736    FlowMap& flow;
737    const CapacityMap& capacity;
738    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
739    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
740    typedef typename AugGraph::EdgeIt AugEdgeIt;
741    typename Graph::NodeMap<bool> SMap;
742    typename Graph::NodeMap<bool> TMap;
743  public:
744    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) {
745      for(typename std::list<NodeIt>::const_iterator i=S.begin();
746          i!=S.end(); ++i) {
747        SMap.set(*i, true);
748      }
749      for (typename std::list<NodeIt>::const_iterator i=T.begin();
750           i!=T.end(); ++i) {
751        TMap.set(*i, true);
752      }
753    }
754    bool augment() {
755      AugGraph res_graph(G, flow, capacity);
756      bool _augment=false;
757      NodeIt reached_t_node;
758     
759      typedef typename AugGraph::NodeMap<bool> ReachedMap;
760      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
761      for(typename std::list<NodeIt>::const_iterator i=S.begin();
762          i!=S.end(); ++i) {
763        res_bfs.pushAndSetReached(*i);
764      }
765      //res_bfs.pushAndSetReached(s);
766       
767      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
768      //filled up with invalid iterators
769     
770      typename AugGraph::NodeMap<Number> free(res_graph);
771       
772      //searching for augmenting path
773      while ( !res_bfs.finished() ) {
774        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
775        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
776          NodeIt v=res_graph.tail(e);
777          NodeIt w=res_graph.head(e);
778          pred.set(w, e);
779          if (pred.get(v).valid()) {
780            free.set(w, std::min(free.get(v), e.free()));
781          } else {
782            free.set(w, e.free());
783          }
784          if (TMap.get(res_graph.head(e))) {
785            _augment=true;
786            reached_t_node=res_graph.head(e);
787            break;
788          }
789        }
790       
791        ++res_bfs;
792      } //end of searching augmenting path
793
794      if (_augment) {
795        NodeIt n=reached_t_node;
796        Number augment_value=free.get(reached_t_node);
797        while (pred.get(n).valid()) {
798          AugEdgeIt e=pred.get(n);
799          e.augment(augment_value);
800          n=res_graph.tail(e);
801        }
802      }
803
804      return _augment;
805    }
806    void run() {
807      while (augment()) { }
808    }
809    Number flowValue() {
810      Number a=0;
811      for(typename std::list<NodeIt>::const_iterator i=S.begin();
812          i!=S.end(); ++i) {
813        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
814          a+=flow.get(e);
815        }
816        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
817          a-=flow.get(e);
818        }
819      }
820      return a;
821    }
822  };
823
824
825
826} // namespace hugo
827
828#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.