COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 210:6bc65a8a99c6

Last change on this file since 210:6bc65a8a99c6 was 206:47f62d789fe7, checked in by marci, 20 years ago

.

File size: 32.7 KB
Line 
1// -*- c++ -*-
2#ifndef EDMONDS_KARP_H
3#define 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 Graph, typename Number, typename FlowMap, typename CapacityMap>
251  class MaxFlow {
252  public:
253    typedef typename Graph::Node Node;
254    typedef typename Graph::Edge Edge;
255    typedef typename Graph::EdgeIt EdgeIt;
256    typedef typename Graph::OutEdgeIt OutEdgeIt;
257    typedef typename Graph::InEdgeIt InEdgeIt;
258
259  private:
260    const Graph* G;
261    Node s;
262    Node t;
263    FlowMap* flow;
264    const CapacityMap* capacity;
265    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
266    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
267    typedef typename AugGraph::Edge AugEdge;
268
269  public:
270    MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
271      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
272    bool augmentOnShortestPath() {
273      AugGraph res_graph(*G, *flow, *capacity);
274      bool _augment=false;
275     
276      typedef typename AugGraph::NodeMap<bool> ReachedMap;
277      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
278      res_bfs.pushAndSetReached(s);
279       
280      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
281      pred.set(s, AugEdge(INVALID));
282     
283      typename AugGraph::NodeMap<Number> free(res_graph);
284       
285      //searching for augmenting path
286      while ( !res_bfs.finished() ) {
287        AugOutEdgeIt e=res_bfs;
288        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
289          Node v=res_graph.tail(e);
290          Node w=res_graph.head(e);
291          pred.set(w, e);
292          if (res_graph.valid(pred.get(v))) {
293            free.set(w, std::min(free.get(v), res_graph.free(e)));
294          } else {
295            free.set(w, res_graph.free(e));
296          }
297          if (res_graph.head(e)==t) { _augment=true; break; }
298        }
299       
300        ++res_bfs;
301      } //end of searching augmenting path
302
303      if (_augment) {
304        Node n=t;
305        Number augment_value=free.get(t);
306        while (res_graph.valid(pred.get(n))) {
307          AugEdge e=pred.get(n);
308          res_graph.augment(e, augment_value);
309          n=res_graph.tail(e);
310        }
311      }
312
313      return _augment;
314    }
315
316    template<typename MutableGraph> bool augmentOnBlockingFlow() {     
317      bool _augment=false;
318
319      AugGraph res_graph(*G, *flow, *capacity);
320
321      typedef typename AugGraph::NodeMap<bool> ReachedMap;
322      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
323
324      bfs.pushAndSetReached(s);
325      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
326      while ( !bfs.finished() ) {
327        AugOutEdgeIt e=bfs;
328        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
329          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
330        }
331       
332        ++bfs;
333      } //computing distances from s in the residual graph
334
335      MutableGraph F;
336      typename AugGraph::NodeMap<typename MutableGraph::Node>
337        res_graph_to_F(res_graph);
338      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
339        res_graph_to_F.set(n, F.addNode());
340      }
341     
342      typename MutableGraph::Node sF=res_graph_to_F.get(s);
343      typename MutableGraph::Node tF=res_graph_to_F.get(t);
344
345      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
346      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
347
348      //Making F to the graph containing the edges of the residual graph
349      //which are in some shortest paths
350      for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
351        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
352          typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
353          original_edge.update();
354          original_edge.set(f, e);
355          residual_capacity.update();
356          residual_capacity.set(f, res_graph.free(e));
357        }
358      }
359
360      bool __augment=true;
361
362      while (__augment) {
363        __augment=false;
364        //computing blocking flow with dfs
365        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
366        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
367        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
368        pred.set(sF, typename MutableGraph::Edge(INVALID));
369        //invalid iterators for sources
370
371        typename MutableGraph::NodeMap<Number> free(F);
372
373        dfs.pushAndSetReached(sF);     
374        while (!dfs.finished()) {
375          ++dfs;
376          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
377            if (dfs.isBNodeNewlyReached()) {
378              typename MutableGraph::Node v=F.aNode(dfs);
379              typename MutableGraph::Node w=F.bNode(dfs);
380              pred.set(w, dfs);
381              if (F.valid(pred.get(v))) {
382                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
383              } else {
384                free.set(w, residual_capacity.get(dfs));
385              }
386              if (w==tF) {
387                __augment=true;
388                _augment=true;
389                break;
390              }
391             
392            } else {
393              F.erase(typename MutableGraph::OutEdgeIt(dfs));
394            }
395          }
396        }
397
398        if (__augment) {
399          typename MutableGraph::Node n=tF;
400          Number augment_value=free.get(tF);
401          while (F.valid(pred.get(n))) {
402            typename MutableGraph::Edge e=pred.get(n);
403            res_graph.augment(original_edge.get(e), augment_value);
404            n=F.tail(e);
405            if (residual_capacity.get(e)==augment_value)
406              F.erase(e);
407            else
408              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
409          }
410        }
411       
412      }
413           
414      return _augment;
415    }
416    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
417      bool _augment=false;
418
419      AugGraph res_graph(*G, *flow, *capacity);
420
421      //bfs for distances on the residual graph
422      typedef typename AugGraph::NodeMap<bool> ReachedMap;
423      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
424      bfs.pushAndSetReached(s);
425      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
426
427      //F will contain the physical copy of the residual graph
428      //with the set of edges which areon shortest paths
429      MutableGraph F;
430      typename AugGraph::NodeMap<typename MutableGraph::Node>
431        res_graph_to_F(res_graph);
432      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
433        res_graph_to_F.set(n, F.addNode());
434      }
435      typename MutableGraph::Node sF=res_graph_to_F.get(s);
436      typename MutableGraph::Node tF=res_graph_to_F.get(t);
437      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
438      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
439
440      while ( !bfs.finished() ) {
441        AugOutEdgeIt e=bfs;
442        if (res_graph.valid(e)) {
443          if (bfs.isBNodeNewlyReached()) {
444            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
445            typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
446            original_edge.update();
447            original_edge.set(f, e);
448            residual_capacity.update();
449            residual_capacity.set(f, res_graph.free(e));
450          } else {
451            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
452              typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
453              original_edge.update();
454              original_edge.set(f, e);
455              residual_capacity.update();
456              residual_capacity.set(f, res_graph.free(e));
457            }
458          }
459        }
460        ++bfs;
461      } //computing distances from s in the residual graph
462
463      bool __augment=true;
464
465      while (__augment) {
466        __augment=false;
467        //computing blocking flow with dfs
468        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
469        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
470        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
471        pred.set(sF, typename MutableGraph::Edge(INVALID));
472        //invalid iterators for sources
473
474        typename MutableGraph::NodeMap<Number> free(F);
475
476        dfs.pushAndSetReached(sF);     
477        while (!dfs.finished()) {
478          ++dfs;
479          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
480            if (dfs.isBNodeNewlyReached()) {
481              typename MutableGraph::Node v=F.aNode(dfs);
482              typename MutableGraph::Node w=F.bNode(dfs);
483              pred.set(w, dfs);
484              if (F.valid(pred.get(v))) {
485                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
486              } else {
487                free.set(w, residual_capacity.get(dfs));
488              }
489              if (w==tF) {
490                __augment=true;
491                _augment=true;
492                break;
493              }
494             
495            } else {
496              F.erase(typename MutableGraph::OutEdgeIt(dfs));
497            }
498          }
499        }
500
501        if (__augment) {
502          typename MutableGraph::Node n=tF;
503          Number augment_value=free.get(tF);
504          while (F.valid(pred.get(n))) {
505            typename MutableGraph::Edge e=pred.get(n);
506            res_graph.augment(original_edge.get(e), augment_value);
507            n=F.tail(e);
508            if (residual_capacity.get(e)==augment_value)
509              F.erase(e);
510            else
511              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
512          }
513        }
514       
515      }
516           
517      return _augment;
518    }
519    bool augmentOnBlockingFlow2() {
520      bool _augment=false;
521
522      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
523      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
524      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
525      typedef typename EAugGraph::Edge EAugEdge;
526
527      EAugGraph res_graph(*G, *flow, *capacity);
528
529      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
530      BfsIterator4<
531        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
532        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
533        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
534     
535      bfs.pushAndSetReached(s);
536
537      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
538        NodeMap<int>& dist=res_graph.dist;
539
540      while ( !bfs.finished() ) {
541        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
542        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
543          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
544        }
545        ++bfs; 
546      } //computing distances from s in the residual graph
547
548      bool __augment=true;
549
550      while (__augment) {
551
552        __augment=false;
553        //computing blocking flow with dfs
554        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
555        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
556          dfs(res_graph);
557        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
558        pred.set(s, EAugEdge(INVALID));
559        //invalid iterators for sources
560
561        typename EAugGraph::NodeMap<Number> free(res_graph);
562
563        dfs.pushAndSetReached(s);
564        while (!dfs.finished()) {
565          ++dfs;
566          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
567            if (dfs.isBNodeNewlyReached()) {
568         
569              typename EAugGraph::Node v=res_graph.aNode(dfs);
570              typename EAugGraph::Node w=res_graph.bNode(dfs);
571
572              pred.set(w, EAugOutEdgeIt(dfs));
573              if (res_graph.valid(pred.get(v))) {
574                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
575              } else {
576                free.set(w, res_graph.free(dfs));
577              }
578             
579              if (w==t) {
580                __augment=true;
581                _augment=true;
582                break;
583              }
584            } else {
585              res_graph.erase(dfs);
586            }
587          }
588
589        }
590
591        if (__augment) {
592          typename EAugGraph::Node n=t;
593          Number augment_value=free.get(t);
594          while (res_graph.valid(pred.get(n))) {
595            EAugEdge e=pred.get(n);
596            res_graph.augment(e, augment_value);
597            n=res_graph.tail(e);
598            if (res_graph.free(e)==0)
599              res_graph.erase(e);
600          }
601        }
602     
603      }
604           
605      return _augment;
606    }
607    void run() {
608      //int num_of_augmentations=0;
609      while (augmentOnShortestPath()) {
610        //while (augmentOnBlockingFlow<MutableGraph>()) {
611        //std::cout << ++num_of_augmentations << " ";
612        //std::cout<<std::endl;
613      }
614    }
615    template<typename MutableGraph> void run() {
616      //int num_of_augmentations=0;
617      //while (augmentOnShortestPath()) {
618        while (augmentOnBlockingFlow<MutableGraph>()) {
619        //std::cout << ++num_of_augmentations << " ";
620        //std::cout<<std::endl;
621      }
622    }
623    Number flowValue() {
624      Number a=0;
625      OutEdgeIt e;
626      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
627        a+=flow->get(e);
628      }
629      return a;
630    }
631  };
632
633
634  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
635  class MaxMatching {
636  public:
637    typedef typename Graph::Node Node;
638    typedef typename Graph::NodeIt NodeIt;
639    typedef typename Graph::Edge Edge;
640    typedef typename Graph::EdgeIt EdgeIt;
641    typedef typename Graph::OutEdgeIt OutEdgeIt;
642    typedef typename Graph::InEdgeIt InEdgeIt;
643
644    typedef typename Graph::NodeMap<bool> SMap;
645    typedef typename Graph::NodeMap<bool> TMap;
646  private:
647    const Graph* G;
648    SMap* S;
649    TMap* T;
650    //Node s;
651    //Node t;
652    FlowMap* flow;
653    const CapacityMap* capacity;
654    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
655    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
656    typedef typename AugGraph::Edge AugEdge;
657    typename Graph::NodeMap<int> used; //0
658
659  public:
660    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
661      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
662    bool augmentOnShortestPath() {
663      AugGraph res_graph(*G, *flow, *capacity);
664      bool _augment=false;
665     
666      typedef typename AugGraph::NodeMap<bool> ReachedMap;
667      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
668      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
669      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
670        if ((S->get(s)) && (used.get(s)<1) ) {
671          //Number u=0;
672          //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
673          //u+=flow->get(e);
674          //if (u<1) {
675            res_bfs.pushAndSetReached(s);
676            pred.set(s, AugEdge(INVALID));
677            //}
678        }
679      }
680     
681      typename AugGraph::NodeMap<Number> free(res_graph);
682       
683      Node n;
684      //searching for augmenting path
685      while ( !res_bfs.finished() ) {
686        AugOutEdgeIt e=res_bfs;
687        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
688          Node v=res_graph.tail(e);
689          Node w=res_graph.head(e);
690          pred.set(w, e);
691          if (res_graph.valid(pred.get(v))) {
692            free.set(w, std::min(free.get(v), res_graph.free(e)));
693          } else {
694            free.set(w, res_graph.free(e));
695          }
696          n=res_graph.head(e);
697          if (T->get(n) && (used.get(n)<1) ) {
698            //Number u=0;
699            //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
700            //u+=flow->get(f);
701            //if (u<1) {
702              _augment=true;
703              break;
704              //}
705          }
706        }
707       
708        ++res_bfs;
709      } //end of searching augmenting path
710
711      if (_augment) {
712        //Node n=t;
713        used.set(n, 1); //mind2 vegen jav
714        Number augment_value=free.get(n);
715        while (res_graph.valid(pred.get(n))) {
716          AugEdge e=pred.get(n);
717          res_graph.augment(e, augment_value);
718          n=res_graph.tail(e);
719        }
720        used.set(n, 1); //mind2 vegen jav
721      }
722
723      return _augment;
724    }
725
726//     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
727//       bool _augment=false;
728
729//       AugGraph res_graph(*G, *flow, *capacity);
730
731//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
732//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
733
734
735
736
737
738//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
739//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
740//      if (S->get(s)) {
741//        Number u=0;
742//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
743//          u+=flow->get(e);
744//        if (u<1) {
745//          res_bfs.pushAndSetReached(s);
746//          //pred.set(s, AugEdge(INVALID));
747//        }
748//      }
749//       }
750
751
752
753
754//       //bfs.pushAndSetReached(s);
755//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
756//       while ( !bfs.finished() ) {
757//      AugOutEdgeIt e=bfs;
758//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
759//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
760//      }
761       
762//      ++bfs;
763//       } //computing distances from s in the residual graph
764
765//       MutableGraph F;
766//       typename AugGraph::NodeMap<typename MutableGraph::Node>
767//      res_graph_to_F(res_graph);
768//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
769//      res_graph_to_F.set(n, F.addNode());
770//       }
771     
772//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
773//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
774
775//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
776//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
777
778//       //Making F to the graph containing the edges of the residual graph
779//       //which are in some shortest paths
780//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
781//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
782//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
783//        original_edge.update();
784//        original_edge.set(f, e);
785//        residual_capacity.update();
786//        residual_capacity.set(f, res_graph.free(e));
787//      }
788//       }
789
790//       bool __augment=true;
791
792//       while (__augment) {
793//      __augment=false;
794//      //computing blocking flow with dfs
795//      typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
796//      DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
797//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
798//      pred.set(sF, typename MutableGraph::Edge(INVALID));
799//      //invalid iterators for sources
800
801//      typename MutableGraph::NodeMap<Number> free(F);
802
803//      dfs.pushAndSetReached(sF);     
804//      while (!dfs.finished()) {
805//        ++dfs;
806//        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
807//          if (dfs.isBNodeNewlyReached()) {
808//            typename MutableGraph::Node v=F.aNode(dfs);
809//            typename MutableGraph::Node w=F.bNode(dfs);
810//            pred.set(w, dfs);
811//            if (F.valid(pred.get(v))) {
812//              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
813//            } else {
814//              free.set(w, residual_capacity.get(dfs));
815//            }
816//            if (w==tF) {
817//              __augment=true;
818//              _augment=true;
819//              break;
820//            }
821             
822//          } else {
823//            F.erase(typename MutableGraph::OutEdgeIt(dfs));
824//          }
825//        }
826//      }
827
828//      if (__augment) {
829//        typename MutableGraph::Node n=tF;
830//        Number augment_value=free.get(tF);
831//        while (F.valid(pred.get(n))) {
832//          typename MutableGraph::Edge e=pred.get(n);
833//          res_graph.augment(original_edge.get(e), augment_value);
834//          n=F.tail(e);
835//          if (residual_capacity.get(e)==augment_value)
836//            F.erase(e);
837//          else
838//            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
839//        }
840//      }
841       
842//       }
843           
844//       return _augment;
845//     }
846    bool augmentOnBlockingFlow2() {
847      bool _augment=false;
848
849      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
850      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
851      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
852      typedef typename EAugGraph::Edge EAugEdge;
853
854      EAugGraph res_graph(*G, *flow, *capacity);
855
856      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
857      BfsIterator4<
858        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
859        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
860        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
861
862
863      //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
864      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
865        if (S->get(s)) {
866          Number u=0;
867          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
868            u+=flow->get(e);
869          if (u<1) {
870            bfs.pushAndSetReached(s);
871            //pred.set(s, AugEdge(INVALID));
872          }
873        }
874      }
875
876     
877      //bfs.pushAndSetReached(s);
878
879      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
880        NodeMap<int>& dist=res_graph.dist;
881
882      while ( !bfs.finished() ) {
883        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
884        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
885          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
886        }
887        ++bfs; 
888      } //computing distances from s in the residual graph
889
890      bool __augment=true;
891
892      while (__augment) {
893
894        __augment=false;
895        //computing blocking flow with dfs
896        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
897        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
898          dfs(res_graph);
899        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
900        //pred.set(s, EAugEdge(INVALID));
901        //invalid iterators for sources
902
903        typename EAugGraph::NodeMap<Number> free(res_graph);
904
905
906        //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
907      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
908        if (S->get(s)) {
909          Number u=0;
910          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
911            u+=flow->get(e);
912          if (u<1) {
913            dfs.pushAndSetReached(s);
914            //pred.set(s, AugEdge(INVALID));
915          }
916        }
917      }
918
919
920
921      //dfs.pushAndSetReached(s);
922      typename EAugGraph::Node n;
923        while (!dfs.finished()) {
924          ++dfs;
925          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
926            if (dfs.isBNodeNewlyReached()) {
927         
928              typename EAugGraph::Node v=res_graph.aNode(dfs);
929              typename EAugGraph::Node w=res_graph.bNode(dfs);
930
931              pred.set(w, EAugOutEdgeIt(dfs));
932              if (res_graph.valid(pred.get(v))) {
933                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
934              } else {
935                free.set(w, res_graph.free(dfs));
936              }
937             
938              n=w;
939              if (T->get(w)) {
940                Number u=0;
941                for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
942                  u+=flow->get(f);
943                if (u<1) {
944                  __augment=true;
945                  _augment=true;
946                  break;
947                }
948              }
949            } else {
950              res_graph.erase(dfs);
951            }
952          }
953
954        }
955
956        if (__augment) {
957          // typename EAugGraph::Node n=t;
958          Number augment_value=free.get(n);
959          while (res_graph.valid(pred.get(n))) {
960            EAugEdge e=pred.get(n);
961            res_graph.augment(e, augment_value);
962            n=res_graph.tail(e);
963            if (res_graph.free(e)==0)
964              res_graph.erase(e);
965          }
966        }
967     
968      }
969           
970      return _augment;
971    }
972    void run() {
973      //int num_of_augmentations=0;
974      while (augmentOnShortestPath()) {
975        //while (augmentOnBlockingFlow<MutableGraph>()) {
976        //std::cout << ++num_of_augmentations << " ";
977        //std::cout<<std::endl;
978      }
979    }
980//     template<typename MutableGraph> void run() {
981//       //int num_of_augmentations=0;
982//       //while (augmentOnShortestPath()) {
983//      while (augmentOnBlockingFlow<MutableGraph>()) {
984//      //std::cout << ++num_of_augmentations << " ";
985//      //std::cout<<std::endl;
986//       }
987//     }
988    Number flowValue() {
989      Number a=0;
990      EdgeIt e;
991      for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
992        a+=flow->get(e);
993      }
994      return a;
995    }
996  };
997
998
999
1000
1001
1002 
1003//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1004//   class MaxFlow2 {
1005//   public:
1006//     typedef typename Graph::Node Node;
1007//     typedef typename Graph::Edge Edge;
1008//     typedef typename Graph::EdgeIt EdgeIt;
1009//     typedef typename Graph::OutEdgeIt OutEdgeIt;
1010//     typedef typename Graph::InEdgeIt InEdgeIt;
1011//   private:
1012//     const Graph& G;
1013//     std::list<Node>& S;
1014//     std::list<Node>& T;
1015//     FlowMap& flow;
1016//     const CapacityMap& capacity;
1017//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1018//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1019//     typedef typename AugGraph::Edge AugEdge;
1020//     typename Graph::NodeMap<bool> SMap;
1021//     typename Graph::NodeMap<bool> TMap;
1022//   public:
1023//     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) {
1024//       for(typename std::list<Node>::const_iterator i=S.begin();
1025//        i!=S.end(); ++i) {
1026//      SMap.set(*i, true);
1027//       }
1028//       for (typename std::list<Node>::const_iterator i=T.begin();
1029//         i!=T.end(); ++i) {
1030//      TMap.set(*i, true);
1031//       }
1032//     }
1033//     bool augment() {
1034//       AugGraph res_graph(G, flow, capacity);
1035//       bool _augment=false;
1036//       Node reached_t_node;
1037     
1038//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
1039//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1040//       for(typename std::list<Node>::const_iterator i=S.begin();
1041//        i!=S.end(); ++i) {
1042//      res_bfs.pushAndSetReached(*i);
1043//       }
1044//       //res_bfs.pushAndSetReached(s);
1045       
1046//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1047//       //filled up with invalid iterators
1048     
1049//       typename AugGraph::NodeMap<Number> free(res_graph);
1050       
1051//       //searching for augmenting path
1052//       while ( !res_bfs.finished() ) {
1053//      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1054//      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1055//        Node v=res_graph.tail(e);
1056//        Node w=res_graph.head(e);
1057//        pred.set(w, e);
1058//        if (pred.get(v).valid()) {
1059//          free.set(w, std::min(free.get(v), e.free()));
1060//        } else {
1061//          free.set(w, e.free());
1062//        }
1063//        if (TMap.get(res_graph.head(e))) {
1064//          _augment=true;
1065//          reached_t_node=res_graph.head(e);
1066//          break;
1067//        }
1068//      }
1069       
1070//      ++res_bfs;
1071//       } //end of searching augmenting path
1072
1073//       if (_augment) {
1074//      Node n=reached_t_node;
1075//      Number augment_value=free.get(reached_t_node);
1076//      while (pred.get(n).valid()) {
1077//        AugEdge e=pred.get(n);
1078//        e.augment(augment_value);
1079//        n=res_graph.tail(e);
1080//      }
1081//       }
1082
1083//       return _augment;
1084//     }
1085//     void run() {
1086//       while (augment()) { }
1087//     }
1088//     Number flowValue() {
1089//       Number a=0;
1090//       for(typename std::list<Node>::const_iterator i=S.begin();
1091//        i!=S.end(); ++i) {
1092//      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1093//        a+=flow.get(e);
1094//      }
1095//      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1096//        a-=flow.get(e);
1097//      }
1098//       }
1099//       return a;
1100//     }
1101//   };
1102
1103
1104
1105} // namespace hugo
1106
1107#endif //EDMONDS_KARP_H
Note: See TracBrowser for help on using the repository browser.