COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 269:07af3069c0b8

Last change on this file since 269:07af3069c0b8 was 269:07af3069c0b8, checked in by marci, 16 years ago

Working on-the-fly with wrappers

File size: 37.3 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_EDMONDS_KARP_H
3#define HUGO_EDMONDS_KARP_H
4
5#include <algorithm>
6#include <list>
7#include <iterator>
8
9#include <bfs_iterator.h>
10#include <invalid.h>
11
12namespace hugo {
13
14  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
15  class ResGraph {
16  public:
17    typedef typename Graph::Node Node;
18    typedef typename Graph::NodeIt NodeIt;
19  private:
20    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
21    const Graph& G;
22    FlowMap& flow;
23    const CapacityMap& capacity;
24  public:
25    ResGraph(const Graph& _G, FlowMap& _flow,
26             const CapacityMap& _capacity) :
27      G(_G), flow(_flow), capacity(_capacity) { }
28
29    class Edge;
30    class OutEdgeIt;
31    friend class Edge;
32    friend class OutEdgeIt;
33
34    class Edge {
35      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
36    protected:
37      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
38      OldSymEdgeIt sym;
39    public:
40      Edge() { }
41      //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
42      Number free() const {
43        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
44          return (resG->capacity.get(sym)-resG->flow.get(sym));
45        } else {
46          return (resG->flow.get(sym));
47        }
48      }
49      bool valid() const { return sym.valid(); }
50      void augment(Number a) const {
51        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
52          resG->flow.set(sym, resG->flow.get(sym)+a);
53          //resG->flow[sym]+=a;
54        } else {
55          resG->flow.set(sym, resG->flow.get(sym)-a);
56          //resG->flow[sym]-=a;
57        }
58      }
59    };
60
61    class OutEdgeIt : public Edge {
62      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
63    public:
64      OutEdgeIt() { }
65      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
66    private:
67      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
68        resG=&_resG;
69        sym=resG->G.template first<OldSymEdgeIt>(v);
70        while( sym.valid() && !(free()>0) ) { ++sym; }
71      }
72    public:
73      OutEdgeIt& operator++() {
74        ++sym;
75        while( sym.valid() && !(free()>0) ) { ++sym; }
76        return *this;
77      }
78    };
79
80    void /*getF*/first(OutEdgeIt& e, Node v) const {
81      e=OutEdgeIt(*this, v);
82    }
83    void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
84   
85    template< typename It >
86    It first() const {
87      It e;     
88      /*getF*/first(e);
89      return e;
90    }
91
92    template< typename It >
93    It first(Node v) const {
94      It e;
95      /*getF*/first(e, v);
96      return e;
97    }
98
99    Node tail(Edge e) const { return G.aNode(e.sym); }
100    Node head(Edge e) const { return G.bNode(e.sym); }
101
102    Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
103    Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
104
105    int id(Node v) const { return G.id(v); }
106
107    template <typename S>
108    class NodeMap {
109      typename Graph::NodeMap<S> node_map;
110    public:
111      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
112      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
113      void set(Node nit, S a) { node_map.set(nit, a); }
114      S get(Node nit) const { return node_map.get(nit); }
115      S& operator[](Node nit) { return node_map[nit]; }
116      const S& operator[](Node nit) const { return node_map[nit]; }
117    };
118
119  };
120
121
122  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
123  class ResGraph2 {
124  public:
125    typedef typename Graph::Node Node;
126    typedef typename Graph::NodeIt NodeIt;
127  private:
128    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
129    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
130    typedef typename Graph::InEdgeIt OldInEdgeIt;
131   
132    const Graph& G;
133    FlowMap& flow;
134    const CapacityMap& capacity;
135  public:
136    ResGraph2(const Graph& _G, FlowMap& _flow,
137             const CapacityMap& _capacity) :
138      G(_G), flow(_flow), capacity(_capacity) { }
139
140    class Edge;
141    class OutEdgeIt;
142    friend class Edge;
143    friend class OutEdgeIt;
144
145    class Edge {
146      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
147    protected:
148      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
149      //OldSymEdgeIt sym;
150      OldOutEdgeIt out;
151      OldInEdgeIt in;
152      bool out_or_in; //true, iff out
153    public:
154      Edge() : out_or_in(true) { }
155      Number free() const {
156        if (out_or_in) {
157          return (resG->capacity.get(out)-resG->flow.get(out));
158        } else {
159          return (resG->flow.get(in));
160        }
161      }
162      bool valid() const {
163        return out_or_in && out.valid() || in.valid(); }
164      void augment(Number a) const {
165        if (out_or_in) {
166          resG->flow.set(out, resG->flow.get(out)+a);
167        } else {
168          resG->flow.set(in, resG->flow.get(in)-a);
169        }
170      }
171    };
172
173    class OutEdgeIt : public Edge {
174      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
175    public:
176      OutEdgeIt() { }
177    private:
178      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
179        resG=&_resG;
180        out=resG->G.template first<OldOutEdgeIt>(v);
181        while( out.valid() && !(free()>0) ) { ++out; }
182        if (!out.valid()) {
183          out_or_in=0;
184          in=resG->G.template first<OldInEdgeIt>(v);
185          while( in.valid() && !(free()>0) ) { ++in; }
186        }
187      }
188    public:
189      OutEdgeIt& operator++() {
190        if (out_or_in) {
191          Node v=resG->G.aNode(out);
192          ++out;
193          while( out.valid() && !(free()>0) ) { ++out; }
194          if (!out.valid()) {
195            out_or_in=0;
196            in=resG->G.template first<OldInEdgeIt>(v);
197            while( in.valid() && !(free()>0) ) { ++in; }
198          }
199        } else {
200          ++in;
201          while( in.valid() && !(free()>0) ) { ++in; }
202        }
203        return *this;
204      }
205    };
206
207    void /*getF*/first(OutEdgeIt& e, Node v) const {
208      e=OutEdgeIt(*this, v);
209    }
210    void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
211   
212    template< typename It >
213    It first() const {
214      It e;
215      /*getF*/first(e);
216      return e;
217    }
218
219    template< typename It >
220    It first(Node v) const {
221      It e;
222      /*getF*/first(e, v);
223      return e;
224    }
225
226    Node tail(Edge e) const {
227      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
228    Node head(Edge e) const {
229      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
230
231    Node aNode(OutEdgeIt e) const {
232      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
233    Node bNode(OutEdgeIt e) const {
234      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
235
236    int id(Node v) const { return G.id(v); }
237
238    template <typename S>
239    class NodeMap {
240      typename Graph::NodeMap<S> node_map;
241    public:
242      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
243      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
244      void set(Node nit, S a) { node_map.set(nit, a); }
245      S get(Node nit) const { return node_map.get(nit); }
246    };
247  };
248
249
250  template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
251  class MaxFlow {
252  protected:
253    typedef GraphWrapper GW;
254    typedef typename GW::Node Node;
255    typedef typename GW::Edge Edge;
256    typedef typename GW::EdgeIt EdgeIt;
257    typedef typename GW::OutEdgeIt OutEdgeIt;
258    typedef typename GW::InEdgeIt InEdgeIt;
259    //const Graph* G;
260    GW gw;
261    Node s;
262    Node t;
263    FlowMap* flow;
264    const CapacityMap* capacity;
265    typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
266    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
267    typedef typename ResGW::Edge ResGWEdge;
268  public:
269
270    MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
271      gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
272
273    bool augmentOnShortestPath() {
274      ResGW res_graph(gw, *flow, *capacity);
275      bool _augment=false;
276     
277      typedef typename ResGW::NodeMap<bool> ReachedMap;
278      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
279      bfs.pushAndSetReached(s);
280       
281      typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
282      pred.set(s, INVALID);
283     
284      typename ResGW::NodeMap<Number> free(res_graph);
285       
286      //searching for augmenting path
287      while ( !bfs.finished() ) {
288        ResGWOutEdgeIt e=bfs;
289        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
290          Node v=res_graph.tail(e);
291          Node w=res_graph.head(e);
292          pred.set(w, e);
293          if (res_graph.valid(pred.get(v))) {
294            free.set(w, std::min(free.get(v), res_graph.resCap(e)));
295          } else {
296            free.set(w, res_graph.resCap(e));
297          }
298          if (res_graph.head(e)==t) { _augment=true; break; }
299        }
300       
301        ++bfs;
302      } //end of searching augmenting path
303
304      if (_augment) {
305        Node n=t;
306        Number augment_value=free.get(t);
307        while (res_graph.valid(pred.get(n))) {
308          ResGWEdge e=pred.get(n);
309          res_graph.augment(e, augment_value);
310          n=res_graph.tail(e);
311        }
312      }
313
314      return _augment;
315    }
316
317    template<typename MapGraphWrapper>
318    class DistanceMap {
319    protected:
320      MapGraphWrapper gw;
321      typename MapGraphWrapper::NodeMap<int> dist;
322    public:
323      DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
324      void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
325      int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
326      bool get(const typename MapGraphWrapper::Edge& e) const {
327        return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
328      }
329    };
330
331    template<typename MutableGraph> bool augmentOnBlockingFlow() {     
332      typedef MutableGraph MG;
333      bool _augment=false;
334
335      ResGW res_graph(gw, *flow, *capacity);
336
337      typedef typename ResGW::NodeMap<bool> ReachedMap;
338      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
339
340      bfs.pushAndSetReached(s);
341      //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
342      DistanceMap<ResGW> dist(res_graph);
343      while ( !bfs.finished() ) {
344        ResGWOutEdgeIt e=bfs;
345        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
346          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
347        }
348        ++bfs;
349      } //computing distances from s in the residual graph
350
351      MG F;
352      typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
353      FilterResGW filter_res_graph(res_graph, dist);
354      typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
355      for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
356        res_graph_to_F.set(n, F.addNode());
357      }
358
359      typename MG::Node sF=res_graph_to_F.get(s);
360      typename MG::Node tF=res_graph_to_F.get(t);
361      typename MG::EdgeMap<ResGWEdge> original_edge(F);
362      typename MG::EdgeMap<Number> residual_capacity(F);
363
364      //Making F to the graph containing the edges of the residual graph
365      //which are in some shortest paths
366      for(typename FilterResGW::EdgeIt e=filter_res_graph.template first<typename FilterResGW::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
367        //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
368          typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
369          original_edge.update();
370          original_edge.set(f, e);
371          residual_capacity.update();
372          residual_capacity.set(f, res_graph.resCap(e));
373          //}
374      }
375
376      bool __augment=true;
377
378      while (__augment) {
379        __augment=false;
380        //computing blocking flow with dfs
381        typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
382        DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
383        typename MG::NodeMap<typename MG::Edge> pred(F);
384        pred.set(sF, INVALID);
385        //invalid iterators for sources
386
387        typename MG::NodeMap<Number> free(F);
388
389        dfs.pushAndSetReached(sF);     
390        while (!dfs.finished()) {
391          ++dfs;
392          if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
393            if (dfs.isBNodeNewlyReached()) {
394              typename MG::Node v=F.aNode(dfs);
395              typename MG::Node w=F.bNode(dfs);
396              pred.set(w, dfs);
397              if (F.valid(pred.get(v))) {
398                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
399              } else {
400                free.set(w, residual_capacity.get(dfs));
401              }
402              if (w==tF) {
403                __augment=true;
404                _augment=true;
405                break;
406              }
407             
408            } else {
409              F.erase(/*typename MG::OutEdgeIt*/(dfs));
410            }
411          }
412        }
413
414        if (__augment) {
415          typename MG::Node n=tF;
416          Number augment_value=free.get(tF);
417          while (F.valid(pred.get(n))) {
418            typename MG::Edge e=pred.get(n);
419            res_graph.augment(original_edge.get(e), augment_value);
420            n=F.tail(e);
421            if (residual_capacity.get(e)==augment_value)
422              F.erase(e);
423            else
424              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
425          }
426        }
427       
428      }
429           
430      return _augment;
431    }
432
433    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
434      typedef MutableGraph MG;
435      bool _augment=false;
436
437      ResGW res_graph(gw, *flow, *capacity);
438
439      //bfs for distances on the residual graph
440      typedef typename ResGW::NodeMap<bool> ReachedMap;
441      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
442      bfs.pushAndSetReached(s);
443      typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
444
445      //F will contain the physical copy of the residual graph
446      //with the set of edges which are on shortest paths
447      MG F;
448      typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
449      for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
450        res_graph_to_F.set(n, F.addNode());
451      }
452
453      typename MG::Node sF=res_graph_to_F.get(s);
454      typename MG::Node tF=res_graph_to_F.get(t);
455      typename MG::EdgeMap<ResGWEdge> original_edge(F);
456      typename MG::EdgeMap<Number> residual_capacity(F);
457
458      while ( !bfs.finished() ) {
459        ResGWOutEdgeIt e=bfs;
460        if (res_graph.valid(e)) {
461          if (bfs.isBNodeNewlyReached()) {
462            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
463            typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
464            original_edge.update();
465            original_edge.set(f, e);
466            residual_capacity.update();
467            residual_capacity.set(f, res_graph.resCap(e));
468          } else {
469            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
470              typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
471              original_edge.update();
472              original_edge.set(f, e);
473              residual_capacity.update();
474              residual_capacity.set(f, res_graph.resCap(e));
475            }
476          }
477        }
478        ++bfs;
479      } //computing distances from s in the residual graph
480
481      bool __augment=true;
482
483      while (__augment) {
484        __augment=false;
485        //computing blocking flow with dfs
486        typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
487        DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
488        typename MG::NodeMap<typename MG::Edge> pred(F);
489        pred.set(sF, INVALID);
490        //invalid iterators for sources
491
492        typename MG::NodeMap<Number> free(F);
493
494        dfs.pushAndSetReached(sF);     
495        while (!dfs.finished()) {
496          ++dfs;
497          if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
498            if (dfs.isBNodeNewlyReached()) {
499              typename MG::Node v=F.aNode(dfs);
500              typename MG::Node w=F.bNode(dfs);
501              pred.set(w, dfs);
502              if (F.valid(pred.get(v))) {
503                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
504              } else {
505                free.set(w, residual_capacity.get(dfs));
506              }
507              if (w==tF) {
508                __augment=true;
509                _augment=true;
510                break;
511              }
512             
513            } else {
514              F.erase(/*typename MG::OutEdgeIt*/(dfs));
515            }
516          }
517        }
518
519        if (__augment) {
520          typename MG::Node n=tF;
521          Number augment_value=free.get(tF);
522          while (F.valid(pred.get(n))) {
523            typename MG::Edge e=pred.get(n);
524            res_graph.augment(original_edge.get(e), augment_value);
525            n=F.tail(e);
526            if (residual_capacity.get(e)==augment_value)
527              F.erase(e);
528            else
529              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
530          }
531        }
532       
533      }
534           
535      return _augment;
536    }
537
538    bool augmentOnBlockingFlow2() {
539      bool _augment=false;
540
541      ResGW res_graph(gw, *flow, *capacity);
542
543      typedef typename ResGW::NodeMap<bool> ReachedMap;
544      BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
545
546      bfs.pushAndSetReached(s);
547      DistanceMap<ResGW> dist(res_graph);
548      while ( !bfs.finished() ) {
549        ResGWOutEdgeIt e=bfs;
550        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
551          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
552        }
553        ++bfs;
554      } //computing distances from s in the residual graph
555
556      //Subgraph containing the edges on some shortest paths
557      typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
558      FilterResGW filter_res_graph(res_graph, dist);
559
560      //Subgraph, which is able to delete edges which are already
561      //met by the dfs
562      typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
563        first_out_edges(filter_res_graph);
564      typename FilterResGW::NodeIt v;
565      for(filter_res_graph.first(v); filter_res_graph.valid(v);
566          filter_res_graph.next(v))
567      {
568        typename FilterResGW::OutEdgeIt e;
569        filter_res_graph.first(e, v);
570        first_out_edges.set(v, e);
571      }
572      typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
573        NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
574      ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
575
576      bool __augment=true;
577
578      while (__augment) {
579
580        __augment=false;
581        //computing blocking flow with dfs
582        typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
583        DfsIterator5< ErasingResGW, BlockingReachedMap >
584          dfs(erasing_res_graph);
585        typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
586          pred(erasing_res_graph);
587        pred.set(s, INVALID);
588        //invalid iterators for sources
589
590        typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
591
592        dfs.pushAndSetReached(s);
593        while (!dfs.finished()) {
594          ++dfs;
595          if (erasing_res_graph.valid(
596                /*typename ErasingResGW::OutEdgeIt*/(dfs)))
597          {
598            if (dfs.isBNodeNewlyReached()) {
599         
600              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
601              typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
602
603              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
604              if (erasing_res_graph.valid(pred.get(v))) {
605                free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
606              } else {
607                free.set(w, res_graph.resCap(dfs));
608              }
609             
610              if (w==t) {
611                __augment=true;
612                _augment=true;
613                break;
614              }
615            } else {
616              erasing_res_graph.erase(dfs);
617            }
618          }
619        }       
620
621        if (__augment) {
622          typename ErasingResGW::Node n=t;
623          Number augment_value=free.get(n);
624          while (erasing_res_graph.valid(pred.get(n))) {
625            typename ErasingResGW::OutEdgeIt e=pred.get(n);
626            res_graph.augment(e, augment_value);
627            n=erasing_res_graph.tail(e);
628            if (res_graph.resCap(e)==0)
629              erasing_res_graph.erase(e);
630          }
631        }
632     
633      } //while (__augment)
634           
635      return _augment;
636    }
637
638//     bool augmentOnBlockingFlow2() {
639//       bool _augment=false;
640
641//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
642//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
643//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
644//       typedef typename EAugGraph::Edge EAugEdge;
645
646//       EAugGraph res_graph(*G, *flow, *capacity);
647
648//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
649//       BfsIterator5<
650//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
651//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
652//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
653     
654//       bfs.pushAndSetReached(s);
655
656//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
657//      NodeMap<int>& dist=res_graph.dist;
658
659//       while ( !bfs.finished() ) {
660//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
661//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
662//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
663//      }
664//      ++bfs; 
665//       } //computing distances from s in the residual graph
666
667//       bool __augment=true;
668
669//       while (__augment) {
670
671//      __augment=false;
672//      //computing blocking flow with dfs
673//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
674//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
675//        dfs(res_graph);
676//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
677//      pred.set(s, EAugEdge(INVALID));
678//      //invalid iterators for sources
679
680//      typename EAugGraph::NodeMap<Number> free(res_graph);
681
682//      dfs.pushAndSetReached(s);
683//      while (!dfs.finished()) {
684//        ++dfs;
685//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
686//          if (dfs.isBNodeNewlyReached()) {
687         
688//            typename EAugGraph::Node v=res_graph.aNode(dfs);
689//            typename EAugGraph::Node w=res_graph.bNode(dfs);
690
691//            pred.set(w, EAugOutEdgeIt(dfs));
692//            if (res_graph.valid(pred.get(v))) {
693//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
694//            } else {
695//              free.set(w, res_graph.free(dfs));
696//            }
697             
698//            if (w==t) {
699//              __augment=true;
700//              _augment=true;
701//              break;
702//            }
703//          } else {
704//            res_graph.erase(dfs);
705//          }
706//        }
707
708//      }
709
710//      if (__augment) {
711//        typename EAugGraph::Node n=t;
712//        Number augment_value=free.get(t);
713//        while (res_graph.valid(pred.get(n))) {
714//          EAugEdge e=pred.get(n);
715//          res_graph.augment(e, augment_value);
716//          n=res_graph.tail(e);
717//          if (res_graph.free(e)==0)
718//            res_graph.erase(e);
719//        }
720//      }
721     
722//       }
723           
724//       return _augment;
725//     }
726
727    void run() {
728      //int num_of_augmentations=0;
729      while (augmentOnShortestPath()) {
730        //while (augmentOnBlockingFlow<MutableGraph>()) {
731        //std::cout << ++num_of_augmentations << " ";
732        //std::cout<<std::endl;
733      }
734    }
735
736    template<typename MutableGraph> void run() {
737      //int num_of_augmentations=0;
738      //while (augmentOnShortestPath()) {
739        while (augmentOnBlockingFlow<MutableGraph>()) {
740        //std::cout << ++num_of_augmentations << " ";
741        //std::cout<<std::endl;
742      }
743    }
744
745    Number flowValue() {
746      Number a=0;
747      OutEdgeIt e;
748      for(gw.first(e, s); gw.valid(e); gw.next(e)) {
749        a+=flow->get(e);
750      }
751      return a;
752    }
753
754  };
755
756
757//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
758//   class MaxMatching {
759//   public:
760//     typedef typename Graph::Node Node;
761//     typedef typename Graph::NodeIt NodeIt;
762//     typedef typename Graph::Edge Edge;
763//     typedef typename Graph::EdgeIt EdgeIt;
764//     typedef typename Graph::OutEdgeIt OutEdgeIt;
765//     typedef typename Graph::InEdgeIt InEdgeIt;
766
767//     typedef typename Graph::NodeMap<bool> SMap;
768//     typedef typename Graph::NodeMap<bool> TMap;
769//   private:
770//     const Graph* G;
771//     SMap* S;
772//     TMap* T;
773//     //Node s;
774//     //Node t;
775//     FlowMap* flow;
776//     const CapacityMap* capacity;
777//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
778//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
779//     typedef typename AugGraph::Edge AugEdge;
780//     typename Graph::NodeMap<int> used; //0
781
782//   public:
783//     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
784//       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
785//     bool augmentOnShortestPath() {
786//       AugGraph res_graph(*G, *flow, *capacity);
787//       bool _augment=false;
788     
789//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
790//       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
791//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
792//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
793//      if ((S->get(s)) && (used.get(s)<1) ) {
794//        //Number u=0;
795//        //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
796//        //u+=flow->get(e);
797//        //if (u<1) {
798//          bfs.pushAndSetReached(s);
799//          pred.set(s, AugEdge(INVALID));
800//          //}
801//      }
802//       }
803     
804//       typename AugGraph::NodeMap<Number> free(res_graph);
805       
806//       Node n;
807//       //searching for augmenting path
808//       while ( !bfs.finished() ) {
809//      AugOutEdgeIt e=bfs;
810//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
811//        Node v=res_graph.tail(e);
812//        Node w=res_graph.head(e);
813//        pred.set(w, e);
814//        if (res_graph.valid(pred.get(v))) {
815//          free.set(w, std::min(free.get(v), res_graph.free(e)));
816//        } else {
817//          free.set(w, res_graph.free(e));
818//        }
819//        n=res_graph.head(e);
820//        if (T->get(n) && (used.get(n)<1) ) {
821//          //Number u=0;
822//          //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
823//          //u+=flow->get(f);
824//          //if (u<1) {
825//            _augment=true;
826//            break;
827//            //}
828//        }
829//      }
830       
831//      ++bfs;
832//       } //end of searching augmenting path
833
834//       if (_augment) {
835//      //Node n=t;
836//      used.set(n, 1); //mind2 vegen jav
837//      Number augment_value=free.get(n);
838//      while (res_graph.valid(pred.get(n))) {
839//        AugEdge e=pred.get(n);
840//        res_graph.augment(e, augment_value);
841//        n=res_graph.tail(e);
842//      }
843//      used.set(n, 1); //mind2 vegen jav
844//       }
845
846//       return _augment;
847//     }
848
849// //     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
850// //       bool _augment=false;
851
852// //       AugGraph res_graph(*G, *flow, *capacity);
853
854// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
855// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
856
857
858
859
860
861// //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
862// //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
863// //   if (S->get(s)) {
864// //     Number u=0;
865// //     for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
866// //       u+=flow->get(e);
867// //     if (u<1) {
868// //       bfs.pushAndSetReached(s);
869// //       //pred.set(s, AugEdge(INVALID));
870// //     }
871// //   }
872// //       }
873
874
875
876
877// //       //bfs.pushAndSetReached(s);
878// //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
879// //       while ( !bfs.finished() ) {
880// //   AugOutEdgeIt e=bfs;
881// //   if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
882// //     dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
883// //   }
884       
885// //   ++bfs;
886// //       } //computing distances from s in the residual graph
887
888// //       MutableGraph F;
889// //       typename AugGraph::NodeMap<typename MutableGraph::Node>
890// //   res_graph_to_F(res_graph);
891// //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
892// //   res_graph_to_F.set(n, F.addNode());
893// //       }
894     
895// //       typename MutableGraph::Node sF=res_graph_to_F.get(s);
896// //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
897
898// //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
899// //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
900
901// //       //Making F to the graph containing the edges of the residual graph
902// //       //which are in some shortest paths
903// //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
904// //   if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
905// //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
906// //     original_edge.update();
907// //     original_edge.set(f, e);
908// //     residual_capacity.update();
909// //     residual_capacity.set(f, res_graph.free(e));
910// //   }
911// //       }
912
913// //       bool __augment=true;
914
915// //       while (__augment) {
916// //   __augment=false;
917// //   //computing blocking flow with dfs
918// //   typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
919// //   DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
920// //   typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
921// //   pred.set(sF, typename MutableGraph::Edge(INVALID));
922// //   //invalid iterators for sources
923
924// //   typename MutableGraph::NodeMap<Number> free(F);
925
926// //   dfs.pushAndSetReached(sF);     
927// //   while (!dfs.finished()) {
928// //     ++dfs;
929// //     if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
930// //       if (dfs.isBNodeNewlyReached()) {
931// //         typename MutableGraph::Node v=F.aNode(dfs);
932// //         typename MutableGraph::Node w=F.bNode(dfs);
933// //         pred.set(w, dfs);
934// //         if (F.valid(pred.get(v))) {
935// //           free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
936// //         } else {
937// //           free.set(w, residual_capacity.get(dfs));
938// //         }
939// //         if (w==tF) {
940// //           __augment=true;
941// //           _augment=true;
942// //           break;
943// //         }
944             
945// //       } else {
946// //         F.erase(typename MutableGraph::OutEdgeIt(dfs));
947// //       }
948// //     }
949// //   }
950
951// //   if (__augment) {
952// //     typename MutableGraph::Node n=tF;
953// //     Number augment_value=free.get(tF);
954// //     while (F.valid(pred.get(n))) {
955// //       typename MutableGraph::Edge e=pred.get(n);
956// //       res_graph.augment(original_edge.get(e), augment_value);
957// //       n=F.tail(e);
958// //       if (residual_capacity.get(e)==augment_value)
959// //         F.erase(e);
960// //       else
961// //         residual_capacity.set(e, residual_capacity.get(e)-augment_value);
962// //     }
963// //   }
964       
965// //       }
966           
967// //       return _augment;
968// //     }
969//     bool augmentOnBlockingFlow2() {
970//       bool _augment=false;
971
972//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
973//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
974//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
975//       typedef typename EAugGraph::Edge EAugEdge;
976
977//       EAugGraph res_graph(*G, *flow, *capacity);
978
979//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
980//       BfsIterator5<
981//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
982//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
983//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
984
985
986//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
987//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
988//      if (S->get(s)) {
989//        Number u=0;
990//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
991//          u+=flow->get(e);
992//        if (u<1) {
993//          bfs.pushAndSetReached(s);
994//          //pred.set(s, AugEdge(INVALID));
995//        }
996//      }
997//       }
998
999     
1000//       //bfs.pushAndSetReached(s);
1001
1002//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1003//      NodeMap<int>& dist=res_graph.dist;
1004
1005//       while ( !bfs.finished() ) {
1006//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1007//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1008//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1009//      }
1010//      ++bfs; 
1011//       } //computing distances from s in the residual graph
1012
1013//       bool __augment=true;
1014
1015//       while (__augment) {
1016
1017//      __augment=false;
1018//      //computing blocking flow with dfs
1019//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1020//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1021//        dfs(res_graph);
1022//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1023//      //pred.set(s, EAugEdge(INVALID));
1024//      //invalid iterators for sources
1025
1026//      typename EAugGraph::NodeMap<Number> free(res_graph);
1027
1028
1029//      //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1030//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1031//      if (S->get(s)) {
1032//        Number u=0;
1033//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1034//          u+=flow->get(e);
1035//        if (u<1) {
1036//          dfs.pushAndSetReached(s);
1037//          //pred.set(s, AugEdge(INVALID));
1038//        }
1039//      }
1040//       }
1041
1042
1043
1044//       //dfs.pushAndSetReached(s);
1045//       typename EAugGraph::Node n;
1046//      while (!dfs.finished()) {
1047//        ++dfs;
1048//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1049//          if (dfs.isBNodeNewlyReached()) {
1050         
1051//            typename EAugGraph::Node v=res_graph.aNode(dfs);
1052//            typename EAugGraph::Node w=res_graph.bNode(dfs);
1053
1054//            pred.set(w, EAugOutEdgeIt(dfs));
1055//            if (res_graph.valid(pred.get(v))) {
1056//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1057//            } else {
1058//              free.set(w, res_graph.free(dfs));
1059//            }
1060             
1061//            n=w;
1062//            if (T->get(w)) {
1063//              Number u=0;
1064//              for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1065//                u+=flow->get(f);
1066//              if (u<1) {
1067//                __augment=true;
1068//                _augment=true;
1069//                break;
1070//              }
1071//            }
1072//          } else {
1073//            res_graph.erase(dfs);
1074//          }
1075//        }
1076
1077//      }
1078
1079//      if (__augment) {
1080//        // typename EAugGraph::Node n=t;
1081//        Number augment_value=free.get(n);
1082//        while (res_graph.valid(pred.get(n))) {
1083//          EAugEdge e=pred.get(n);
1084//          res_graph.augment(e, augment_value);
1085//          n=res_graph.tail(e);
1086//          if (res_graph.free(e)==0)
1087//            res_graph.erase(e);
1088//        }
1089//      }
1090     
1091//       }
1092           
1093//       return _augment;
1094//     }
1095//     void run() {
1096//       //int num_of_augmentations=0;
1097//       while (augmentOnShortestPath()) {
1098//      //while (augmentOnBlockingFlow<MutableGraph>()) {
1099//      //std::cout << ++num_of_augmentations << " ";
1100//      //std::cout<<std::endl;
1101//       }
1102//     }
1103// //     template<typename MutableGraph> void run() {
1104// //       //int num_of_augmentations=0;
1105// //       //while (augmentOnShortestPath()) {
1106// //   while (augmentOnBlockingFlow<MutableGraph>()) {
1107// //   //std::cout << ++num_of_augmentations << " ";
1108// //   //std::cout<<std::endl;
1109// //       }
1110// //     }
1111//     Number flowValue() {
1112//       Number a=0;
1113//       EdgeIt e;
1114//       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1115//      a+=flow->get(e);
1116//       }
1117//       return a;
1118//     }
1119//   };
1120
1121
1122
1123
1124
1125 
1126// //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1127// //   class MaxFlow2 {
1128// //   public:
1129// //     typedef typename Graph::Node Node;
1130// //     typedef typename Graph::Edge Edge;
1131// //     typedef typename Graph::EdgeIt EdgeIt;
1132// //     typedef typename Graph::OutEdgeIt OutEdgeIt;
1133// //     typedef typename Graph::InEdgeIt InEdgeIt;
1134// //   private:
1135// //     const Graph& G;
1136// //     std::list<Node>& S;
1137// //     std::list<Node>& T;
1138// //     FlowMap& flow;
1139// //     const CapacityMap& capacity;
1140// //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1141// //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1142// //     typedef typename AugGraph::Edge AugEdge;
1143// //     typename Graph::NodeMap<bool> SMap;
1144// //     typename Graph::NodeMap<bool> TMap;
1145// //   public:
1146// //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1147// //       for(typename std::list<Node>::const_iterator i=S.begin();
1148// //     i!=S.end(); ++i) {
1149// //   SMap.set(*i, true);
1150// //       }
1151// //       for (typename std::list<Node>::const_iterator i=T.begin();
1152// //      i!=T.end(); ++i) {
1153// //   TMap.set(*i, true);
1154// //       }
1155// //     }
1156// //     bool augment() {
1157// //       AugGraph res_graph(G, flow, capacity);
1158// //       bool _augment=false;
1159// //       Node reached_t_node;
1160     
1161// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
1162// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1163// //       for(typename std::list<Node>::const_iterator i=S.begin();
1164// //     i!=S.end(); ++i) {
1165// //   bfs.pushAndSetReached(*i);
1166// //       }
1167// //       //bfs.pushAndSetReached(s);
1168       
1169// //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1170// //       //filled up with invalid iterators
1171     
1172// //       typename AugGraph::NodeMap<Number> free(res_graph);
1173       
1174// //       //searching for augmenting path
1175// //       while ( !bfs.finished() ) {
1176// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1177// //   if (e.valid() && bfs.isBNodeNewlyReached()) {
1178// //     Node v=res_graph.tail(e);
1179// //     Node w=res_graph.head(e);
1180// //     pred.set(w, e);
1181// //     if (pred.get(v).valid()) {
1182// //       free.set(w, std::min(free.get(v), e.free()));
1183// //     } else {
1184// //       free.set(w, e.free());
1185// //     }
1186// //     if (TMap.get(res_graph.head(e))) {
1187// //       _augment=true;
1188// //       reached_t_node=res_graph.head(e);
1189// //       break;
1190// //     }
1191// //   }
1192       
1193// //   ++bfs;
1194// //       } //end of searching augmenting path
1195
1196// //       if (_augment) {
1197// //   Node n=reached_t_node;
1198// //   Number augment_value=free.get(reached_t_node);
1199// //   while (pred.get(n).valid()) {
1200// //     AugEdge e=pred.get(n);
1201// //     e.augment(augment_value);
1202// //     n=res_graph.tail(e);
1203// //   }
1204// //       }
1205
1206// //       return _augment;
1207// //     }
1208// //     void run() {
1209// //       while (augment()) { }
1210// //     }
1211// //     Number flowValue() {
1212// //       Number a=0;
1213// //       for(typename std::list<Node>::const_iterator i=S.begin();
1214// //     i!=S.end(); ++i) {
1215// //   for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1216// //     a+=flow.get(e);
1217// //   }
1218// //   for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1219// //     a-=flow.get(e);
1220// //   }
1221// //       }
1222// //       return a;
1223// //     }
1224// //   };
1225
1226
1227} // namespace hugo
1228
1229#endif //HUGO_EDMONDS_KARP_H
Note: See TracBrowser for help on using the repository browser.