COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 148:004fdf703abb

Last change on this file since 148:004fdf703abb was 148:004fdf703abb, checked in by marci, 20 years ago

G.next(...), G.valid(...), ...

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