COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 268:f4eb1ae59b50

Last change on this file since 268:f4eb1ae59b50 was 268:f4eb1ae59b50, checked in by marci, 20 years ago

blocking flows

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