COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 137:6364b07f8cd4

Last change on this file since 137:6364b07f8cd4 was 137:6364b07f8cd4, checked in by marci, 17 years ago

ResGraph3::EdgeMap?<T>

File size: 24.5 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 T>
456    class NodeMap {
457      typename Graph::NodeMap<T> 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, T a) : node_map(_G.G, a) { }
461      void set(NodeIt nit, T a) { node_map.set(nit, a); }
462      T get(NodeIt nit) const { return node_map.get(nit); }
463    };
464
465    template <typename T>
466    class EdgeMap {
467      typename Graph::EdgeMap<T> forward_map, backward_map;
468    public:
469      EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }
470      EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.G, a), backward_map(_G.G, a) { }
471      void set(EdgeIt e, T a) {
472        if (e.out_or_in)
473          forward_map.set(e.out, a);
474        else
475          backward_map.set(e.in, a);
476      }
477      T get(EdgeIt e) {
478        if (e.out_or_in)
479          return forward_map.get(e.out);
480        else
481          return backward_map.get(e.in);
482      }
483    };
484
485  };
486
487  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
488  class MaxFlow {
489  public:
490    typedef typename Graph::NodeIt NodeIt;
491    typedef typename Graph::EdgeIt EdgeIt;
492    typedef typename Graph::EachEdgeIt EachEdgeIt;
493    typedef typename Graph::OutEdgeIt OutEdgeIt;
494    typedef typename Graph::InEdgeIt InEdgeIt;
495
496  private:
497    const Graph& G;
498    NodeIt s;
499    NodeIt t;
500    FlowMap& flow;
501    const CapacityMap& capacity;
502    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
503    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
504    typedef typename AugGraph::EdgeIt AugEdgeIt;
505
506    //AugGraph res_graph;   
507    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
508    //typename AugGraph::NodeMap<AugEdgeIt> pred;
509    //typename AugGraph::NodeMap<Number> free;
510  public:
511    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
512      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
513      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
514      { }
515    bool augmentOnShortestPath() {
516      AugGraph res_graph(G, flow, capacity);
517      bool _augment=false;
518     
519      typedef typename AugGraph::NodeMap<bool> ReachedMap;
520      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
521      res_bfs.pushAndSetReached(s);
522       
523      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
524      //filled up with invalid iterators
525      //pred.set(s, AugEdgeIt());
526     
527      typename AugGraph::NodeMap<Number> free(res_graph);
528       
529      //searching for augmenting path
530      while ( !res_bfs.finished() ) {
531        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
532        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
533          NodeIt v=res_graph.tail(e);
534          NodeIt w=res_graph.head(e);
535          pred.set(w, e);
536          if (pred.get(v).valid()) {
537            free.set(w, std::min(free.get(v), e.free()));
538          } else {
539            free.set(w, e.free());
540          }
541          if (res_graph.head(e)==t) { _augment=true; break; }
542        }
543       
544        ++res_bfs;
545      } //end of searching augmenting path
546
547      if (_augment) {
548        NodeIt n=t;
549        Number augment_value=free.get(t);
550        while (pred.get(n).valid()) {
551          AugEdgeIt e=pred.get(n);
552          e.augment(augment_value);
553          n=res_graph.tail(e);
554        }
555      }
556
557      return _augment;
558    }
559    template<typename MutableGraph> bool augmentOnBlockingFlow() {
560      bool _augment=false;
561
562      AugGraph res_graph(G, flow, capacity);
563
564      typedef typename AugGraph::NodeMap<bool> ReachedMap;
565      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
566
567      bfs.pushAndSetReached(s);
568      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
569      while ( !bfs.finished() ) {
570        AugOutEdgeIt e=AugOutEdgeIt(bfs);
571        if (e.valid() && bfs.isBNodeNewlyReached()) {
572          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
573        }
574       
575        ++bfs;
576      } //computing distances from s in the residual graph
577
578      MutableGraph F;
579      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
580      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
581        res_graph_to_F.set(n, F.addNode());
582      }
583     
584      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
585      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
586
587      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
588      typename MutableGraph::EdgeMap<Number> free_on_edge(F);
589
590      //Making F to the graph containing the edges of the residual graph
591      //which are in some shortest paths
592      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
593        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
594          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
595          original_edge.update();
596          original_edge.set(f, e);
597          free_on_edge.update();
598          free_on_edge.set(f, e.free());
599        }
600      }
601
602      bool __augment=true;
603
604      while (__augment) {
605        __augment=false;
606        //computing blocking flow with dfs
607        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
608        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
609        typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
610        typename MutableGraph::NodeMap<Number> free(F);
611
612        dfs.pushAndSetReached(sF);     
613        while (!dfs.finished()) {
614          ++dfs;
615          if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
616            //std::cout << "OutEdgeIt: " << dfs;
617            //std::cout << " aNode: " << F.aNode(dfs);
618            //std::cout << " bNode: " << F.bNode(dfs) << " ";
619         
620            typename MutableGraph::NodeIt v=F.aNode(dfs);
621            typename MutableGraph::NodeIt w=F.bNode(dfs);
622            pred.set(w, dfs);
623            if (pred.get(v).valid()) {
624              free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
625            } else {
626              free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
627            }
628            if (w==tF) {
629              //std::cout << "AUGMENTATION"<<std::endl;
630              __augment=true;
631              _augment=true;
632              break;
633            }
634          } else {
635            //std::cout << "OutEdgeIt: " << "invalid";
636            //std::cout << " aNode: " << dfs.aNode();
637            //std::cout << " bNode: " << "invalid" << " ";
638          }
639          if (dfs.isBNodeNewlyReached()) {
640            //std::cout << "bNodeIsNewlyReached ";
641          } else {
642            //std::cout << "bNodeIsNotNewlyReached ";
643            if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
644              //std::cout << "DELETE ";
645              F.erase(typename MutableGraph::OutEdgeIt(dfs));
646            }
647          }
648          //if (dfs.isANodeExamined()) {
649            //std::cout << "aNodeIsExamined ";
650            //} else {
651            //std::cout << "aNodeIsNotExamined ";
652            //}
653          //std::cout<<std::endl;
654        }
655
656        if (__augment) {
657          typename MutableGraph::NodeIt n=tF;
658          Number augment_value=free.get(tF);
659          while (pred.get(n).valid()) {
660            typename MutableGraph::EdgeIt e=pred.get(n);
661            original_edge.get(e).augment(augment_value);
662            n=F.tail(e);
663            if (free_on_edge.get(e)==augment_value)
664              F.erase(e);
665            else
666              free_on_edge.set(e, free_on_edge.get(e)-augment_value);
667          }
668        }
669     
670      }
671           
672      return _augment;
673    }
674    void run() {
675      //int num_of_augmentations=0;
676      while (augmentOnShortestPath()) {
677        //while (augmentOnBlockingFlow<MutableGraph>()) {
678        //std::cout << ++num_of_augmentations << " ";
679        //std::cout<<std::endl;
680      }
681    }
682    template<typename MutableGraph> void run() {
683      //int num_of_augmentations=0;
684      //while (augmentOnShortestPath()) {
685        while (augmentOnBlockingFlow<MutableGraph>()) {
686        //std::cout << ++num_of_augmentations << " ";
687        //std::cout<<std::endl;
688      }
689    }
690    Number flowValue() {
691      Number a=0;
692      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
693        a+=flow.get(i);
694      }
695      return a;
696    }
697  };
698
699
700/*
701  template <typename Graph>
702  class IteratorBoolNodeMap {
703    typedef typename Graph::NodeIt NodeIt;
704    typedef typename Graph::EachNodeIt EachNodeIt;
705    class BoolItem {
706    public:
707      bool value;
708      NodeIt prev;
709      NodeIt next;
710      BoolItem() : value(false), prev(), next() {}
711    };
712    NodeIt first_true;
713    //NodeIt last_true;
714    NodeIt first_false;
715    //NodeIt last_false;
716    const Graph& G;
717    typename Graph::NodeMap<BoolItem> container;
718  public:
719    typedef bool ValueType;
720    typedef NodeIt KeyType;
721    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
722      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
723      //BoolItem b=container.get(e);
724      //b.me=e;
725      //container.set(b);
726      //}
727      G.getFirst(first_false);
728      NodeIt e_prev;
729      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
730        container[e].prev=e_prev;
731        if (e_prev.valid()) container[e_prev].next=e;
732        e_prev=e;
733      }
734    }
735    //NodeMap(const Graph& _G, T a) :
736    //  G(_G), container(G.node_id, a) { }
737    //FIXME
738    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
739    T get(NodeIt nit) const { return container[G.id(nit)]; }
740    //void update() { container.resize(G.node_id); }
741    //void update(T a) { container.resize(G.node_id, a); }
742  };
743*/
744
745 
746  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
747  class MaxFlow2 {
748  public:
749    typedef typename Graph::NodeIt NodeIt;
750    typedef typename Graph::EdgeIt EdgeIt;
751    typedef typename Graph::EachEdgeIt EachEdgeIt;
752    typedef typename Graph::OutEdgeIt OutEdgeIt;
753    typedef typename Graph::InEdgeIt InEdgeIt;
754  private:
755    const Graph& G;
756    std::list<NodeIt>& S;
757    std::list<NodeIt>& T;
758    FlowMap& flow;
759    const CapacityMap& capacity;
760    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
761    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
762    typedef typename AugGraph::EdgeIt AugEdgeIt;
763    typename Graph::NodeMap<bool> SMap;
764    typename Graph::NodeMap<bool> TMap;
765  public:
766    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) {
767      for(typename std::list<NodeIt>::const_iterator i=S.begin();
768          i!=S.end(); ++i) {
769        SMap.set(*i, true);
770      }
771      for (typename std::list<NodeIt>::const_iterator i=T.begin();
772           i!=T.end(); ++i) {
773        TMap.set(*i, true);
774      }
775    }
776    bool augment() {
777      AugGraph res_graph(G, flow, capacity);
778      bool _augment=false;
779      NodeIt reached_t_node;
780     
781      typedef typename AugGraph::NodeMap<bool> ReachedMap;
782      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
783      for(typename std::list<NodeIt>::const_iterator i=S.begin();
784          i!=S.end(); ++i) {
785        res_bfs.pushAndSetReached(*i);
786      }
787      //res_bfs.pushAndSetReached(s);
788       
789      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
790      //filled up with invalid iterators
791     
792      typename AugGraph::NodeMap<Number> free(res_graph);
793       
794      //searching for augmenting path
795      while ( !res_bfs.finished() ) {
796        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
797        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
798          NodeIt v=res_graph.tail(e);
799          NodeIt w=res_graph.head(e);
800          pred.set(w, e);
801          if (pred.get(v).valid()) {
802            free.set(w, std::min(free.get(v), e.free()));
803          } else {
804            free.set(w, e.free());
805          }
806          if (TMap.get(res_graph.head(e))) {
807            _augment=true;
808            reached_t_node=res_graph.head(e);
809            break;
810          }
811        }
812       
813        ++res_bfs;
814      } //end of searching augmenting path
815
816      if (_augment) {
817        NodeIt n=reached_t_node;
818        Number augment_value=free.get(reached_t_node);
819        while (pred.get(n).valid()) {
820          AugEdgeIt e=pred.get(n);
821          e.augment(augment_value);
822          n=res_graph.tail(e);
823        }
824      }
825
826      return _augment;
827    }
828    void run() {
829      while (augment()) { }
830    }
831    Number flowValue() {
832      Number a=0;
833      for(typename std::list<NodeIt>::const_iterator i=S.begin();
834          i!=S.end(); ++i) {
835        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
836          a+=flow.get(e);
837        }
838        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
839          a-=flow.get(e);
840        }
841      }
842      return a;
843    }
844  };
845
846
847
848} // namespace hugo
849
850#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.