COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 147:f3f1d7a4a8d3

Last change on this file since 147:f3f1d7a4a8d3 was 141:a17d2a6462ee, checked in by marci, 20 years ago

.

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