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, 17 years ago

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

File size: 25.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; //true, iff out
152    public:
153      EdgeIt() : out_or_in(true) { }
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 ResGraphWrapper {
250  public:
251    typedef typename Graph::NodeIt NodeIt;
252    typedef typename Graph::EachNodeIt EachNodeIt;
253  private:
254    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
255    typedef typename Graph::InEdgeIt OldInEdgeIt;
256    const Graph* G;
257    FlowMap* flow;
258    const CapacityMap* capacity;
259  public:
260    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
261             const CapacityMap& _capacity) :
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) { }
265    class EdgeIt;
266    class OutEdgeIt;
267    friend class EdgeIt;
268    friend class OutEdgeIt;
269
270    class EdgeIt {
271      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
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;
280      bool out_or_in; //true, iff out
281    public:
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) { }
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) { }
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      }
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      }
319    };
320
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
328    class OutEdgeIt : public EdgeIt {
329      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
330    public:
331      OutEdgeIt() { }
332    private:
333      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
334        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
335        G->getFirst(out, v);
336        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
337        if (!out.valid()) {
338          out_or_in=0;
339          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
340          G->getFirst(in, v);
341          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
342        }
343      }
344    public:
345      OutEdgeIt& operator++() {
346        if (out_or_in) {
347          NodeIt v=/*resG->*/G->aNode(out);
348          ++out;
349          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
350          if (!out.valid()) {
351            out_or_in=0;
352            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
353            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
354          }
355        } else {
356          ++in;
357          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
358        }
359        return *this;
360      }
361    };
362
363    class EachEdgeIt : public EdgeIt {
364      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
365      typename Graph::EachNodeIt v;
366    public:
367      EachEdgeIt() { }
368      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
369      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
370        out_or_in=true;
371        G->getFirst(v);
372        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
373        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
374        while (v.valid() && !out.valid()) {
375          ++v;
376          if (v.valid()) G->getFirst(out, v);
377          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
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();
383          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
384          while (v.valid() && !in.valid()) {
385            ++v;
386            if (v.valid()) G->getFirst(in, v);
387            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
388          }
389        }
390      }
391      EachEdgeIt& operator++() {
392        if (out_or_in) {
393          ++out;
394          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
395          while (v.valid() && !out.valid()) {
396            ++v;
397            if (v.valid()) G->getFirst(out, v);
398            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
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();
404            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
405            while (v.valid() && !in.valid()) {
406              ++v;
407              if (v.valid()) G->getFirst(in, v);
408              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
409            } 
410          }
411        } else {
412          ++in;
413          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
414          while (v.valid() && !in.valid()) {
415            ++v;
416            if (v.valid()) G->getFirst(in, v);
417            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
418          }
419        }
420        return *this;
421      }
422    };
423
424    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
425    void getFirst(OutEdgeIt& e, NodeIt v) const {
426      e=OutEdgeIt(*G, v, *flow, *capacity);
427    }
428    void getFirst(EachEdgeIt& e) const {
429      e=EachEdgeIt(*G, *flow, *capacity);
430    }
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      }
482   
483
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 {
499      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
500    NodeIt head(EdgeIt e) const {
501      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
502
503    NodeIt aNode(OutEdgeIt e) const {
504      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
505    NodeIt bNode(OutEdgeIt e) const {
506      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
507
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); }
513
514    template <typename T>
515    class NodeMap {
516      typename Graph::NodeMap<T> node_map;
517    public:
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) { }
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:
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) { }
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      }
542    };
543
544  };
545
546  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
547  class MaxFlow {
548  public:
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;
554
555  private:
556    const Graph* G;
557    NodeIt s;
558    NodeIt t;
559    FlowMap* flow;
560    const CapacityMap* capacity;
561    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
562    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
563    typedef typename AugGraph::EdgeIt AugEdgeIt;
564
565    //AugGraph res_graph;   
566    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
567    //typename AugGraph::NodeMap<AugEdgeIt> pred;
568    //typename AugGraph::NodeMap<Number> free;
569  public:
570    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
571      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
572      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
573      { }
574    bool augmentOnShortestPath() {
575      AugGraph res_graph(*G, *flow, *capacity);
576      bool _augment=false;
577     
578      typedef typename AugGraph::NodeMap<bool> ReachedMap;
579      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
580      res_bfs.pushAndSetReached(s);
581       
582      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
583      //filled up with invalid iterators
584      //pred.set(s, AugEdgeIt());
585     
586      typename AugGraph::NodeMap<Number> free(res_graph);
587       
588      //searching for augmenting path
589      while ( !res_bfs.finished() ) {
590        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
591        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
592          NodeIt v=res_graph.tail(e);
593          NodeIt w=res_graph.head(e);
594          pred.set(w, e);
595          if (res_graph.valid(pred.get(v))) {
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
605
606      if (_augment) {
607        NodeIt n=t;
608        Number augment_value=free.get(t);
609        while (res_graph.valid(pred.get(n))) {
610          AugEdgeIt e=pred.get(n);
611          e.augment(augment_value);
612          n=res_graph.tail(e);
613        }
614      }
615
616      return _augment;
617    }
618
619    template<typename MutableGraph> bool augmentOnBlockingFlow() {
620      bool _augment=false;
621
622      AugGraph res_graph(*G, *flow, *capacity);
623
624      typedef typename AugGraph::NodeMap<bool> ReachedMap;
625      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
626
627      bfs.pushAndSetReached(s);
628      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
629      while ( !bfs.finished() ) {
630        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
631        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
632          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
633        }
634       
635        ++bfs;
636      } //computing distances from s in the residual graph
637
638      MutableGraph F;
639      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
640      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
641        res_graph_to_F.set(n, F.addNode());
642      }
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);
648      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
649
650      //Making F to the graph containing the edges of the residual graph
651      //which are in some shortest paths
652      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
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);
657          residual_capacity.update();
658          residual_capacity.set(f, e.free());
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;
675          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
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);
683            if (F.valid(pred.get(v))) {
684              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
685            } else {
686              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
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;
714        }
715
716        if (__augment) {
717          typename MutableGraph::NodeIt n=tF;
718          Number augment_value=free.get(tF);
719          while (F.valid(pred.get(n))) {
720            typename MutableGraph::EdgeIt e=pred.get(n);
721            original_edge.get(e).augment(augment_value);
722            n=F.tail(e);
723            if (residual_capacity.get(e)==augment_value)
724              F.erase(e);
725            else
726              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
727          }
728        }
729     
730      }
731           
732      return _augment;
733    }
734    void run() {
735      //int num_of_augmentations=0;
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>()) {
746        //std::cout << ++num_of_augmentations << " ";
747        //std::cout<<std::endl;
748      }
749    }
750    Number flowValue() {
751      Number a=0;
752      OutEdgeIt e;
753      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
754        a+=flow->get(e);
755      }
756      return a;
757    }
758  };
759
760 
761  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
762  class MaxFlow2 {
763  public:
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;
769  private:
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     
807      typename AugGraph::NodeMap<Number> free(res_graph);
808       
809      //searching for augmenting path
810      while ( !res_bfs.finished() ) {
811        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
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
863} // namespace hugo
864
865#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.