COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 266:4cec4981dfd1

Last change on this file since 266:4cec4981dfd1 was 266:4cec4981dfd1, checked in by marci, 20 years ago

GraphWrappers?, MapWrappers?

File size: 35.2 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(*G, *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//     bool augmentOnBlockingFlow2() {
539//       bool _augment=false;
540
541//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
542//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
543//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
544//       typedef typename EAugGraph::Edge EAugEdge;
545
546//       EAugGraph res_graph(*G, *flow, *capacity);
547
548//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
549//       BfsIterator5<
550//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
551//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
552//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
553     
554//       bfs.pushAndSetReached(s);
555
556//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
557//      NodeMap<int>& dist=res_graph.dist;
558
559//       while ( !bfs.finished() ) {
560//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
561//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
562//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
563//      }
564//      ++bfs; 
565//       } //computing distances from s in the residual graph
566
567//       bool __augment=true;
568
569//       while (__augment) {
570
571//      __augment=false;
572//      //computing blocking flow with dfs
573//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
574//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
575//        dfs(res_graph);
576//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
577//      pred.set(s, EAugEdge(INVALID));
578//      //invalid iterators for sources
579
580//      typename EAugGraph::NodeMap<Number> free(res_graph);
581
582//      dfs.pushAndSetReached(s);
583//      while (!dfs.finished()) {
584//        ++dfs;
585//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
586//          if (dfs.isBNodeNewlyReached()) {
587         
588//            typename EAugGraph::Node v=res_graph.aNode(dfs);
589//            typename EAugGraph::Node w=res_graph.bNode(dfs);
590
591//            pred.set(w, EAugOutEdgeIt(dfs));
592//            if (res_graph.valid(pred.get(v))) {
593//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
594//            } else {
595//              free.set(w, res_graph.free(dfs));
596//            }
597             
598//            if (w==t) {
599//              __augment=true;
600//              _augment=true;
601//              break;
602//            }
603//          } else {
604//            res_graph.erase(dfs);
605//          }
606//        }
607
608//      }
609
610//      if (__augment) {
611//        typename EAugGraph::Node n=t;
612//        Number augment_value=free.get(t);
613//        while (res_graph.valid(pred.get(n))) {
614//          EAugEdge e=pred.get(n);
615//          res_graph.augment(e, augment_value);
616//          n=res_graph.tail(e);
617//          if (res_graph.free(e)==0)
618//            res_graph.erase(e);
619//        }
620//      }
621     
622//       }
623           
624//       return _augment;
625//     }
626//     void run() {
627//       //int num_of_augmentations=0;
628//       while (augmentOnShortestPath()) {
629//      //while (augmentOnBlockingFlow<MutableGraph>()) {
630//      //std::cout << ++num_of_augmentations << " ";
631//      //std::cout<<std::endl;
632//       }
633//     }
634//     template<typename MutableGraph> void run() {
635//       //int num_of_augmentations=0;
636//       //while (augmentOnShortestPath()) {
637//      while (augmentOnBlockingFlow<MutableGraph>()) {
638//      //std::cout << ++num_of_augmentations << " ";
639//      //std::cout<<std::endl;
640//       }
641//     }
642    Number flowValue() {
643      Number a=0;
644      OutEdgeIt e;
645      for(gw.first(e, s); gw.valid(e); gw.next(e)) {
646        a+=flow->get(e);
647      }
648      return a;
649    }
650  };
651
652
653//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
654//   class MaxMatching {
655//   public:
656//     typedef typename Graph::Node Node;
657//     typedef typename Graph::NodeIt NodeIt;
658//     typedef typename Graph::Edge Edge;
659//     typedef typename Graph::EdgeIt EdgeIt;
660//     typedef typename Graph::OutEdgeIt OutEdgeIt;
661//     typedef typename Graph::InEdgeIt InEdgeIt;
662
663//     typedef typename Graph::NodeMap<bool> SMap;
664//     typedef typename Graph::NodeMap<bool> TMap;
665//   private:
666//     const Graph* G;
667//     SMap* S;
668//     TMap* T;
669//     //Node s;
670//     //Node t;
671//     FlowMap* flow;
672//     const CapacityMap* capacity;
673//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
674//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
675//     typedef typename AugGraph::Edge AugEdge;
676//     typename Graph::NodeMap<int> used; //0
677
678//   public:
679//     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
680//       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
681//     bool augmentOnShortestPath() {
682//       AugGraph res_graph(*G, *flow, *capacity);
683//       bool _augment=false;
684     
685//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
686//       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
687//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
688//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
689//      if ((S->get(s)) && (used.get(s)<1) ) {
690//        //Number u=0;
691//        //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
692//        //u+=flow->get(e);
693//        //if (u<1) {
694//          res_bfs.pushAndSetReached(s);
695//          pred.set(s, AugEdge(INVALID));
696//          //}
697//      }
698//       }
699     
700//       typename AugGraph::NodeMap<Number> free(res_graph);
701       
702//       Node n;
703//       //searching for augmenting path
704//       while ( !res_bfs.finished() ) {
705//      AugOutEdgeIt e=res_bfs;
706//      if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
707//        Node v=res_graph.tail(e);
708//        Node w=res_graph.head(e);
709//        pred.set(w, e);
710//        if (res_graph.valid(pred.get(v))) {
711//          free.set(w, std::min(free.get(v), res_graph.free(e)));
712//        } else {
713//          free.set(w, res_graph.free(e));
714//        }
715//        n=res_graph.head(e);
716//        if (T->get(n) && (used.get(n)<1) ) {
717//          //Number u=0;
718//          //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
719//          //u+=flow->get(f);
720//          //if (u<1) {
721//            _augment=true;
722//            break;
723//            //}
724//        }
725//      }
726       
727//      ++res_bfs;
728//       } //end of searching augmenting path
729
730//       if (_augment) {
731//      //Node n=t;
732//      used.set(n, 1); //mind2 vegen jav
733//      Number augment_value=free.get(n);
734//      while (res_graph.valid(pred.get(n))) {
735//        AugEdge e=pred.get(n);
736//        res_graph.augment(e, augment_value);
737//        n=res_graph.tail(e);
738//      }
739//      used.set(n, 1); //mind2 vegen jav
740//       }
741
742//       return _augment;
743//     }
744
745// //     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
746// //       bool _augment=false;
747
748// //       AugGraph res_graph(*G, *flow, *capacity);
749
750// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
751// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
752
753
754
755
756
757// //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
758// //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
759// //   if (S->get(s)) {
760// //     Number u=0;
761// //     for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
762// //       u+=flow->get(e);
763// //     if (u<1) {
764// //       res_bfs.pushAndSetReached(s);
765// //       //pred.set(s, AugEdge(INVALID));
766// //     }
767// //   }
768// //       }
769
770
771
772
773// //       //bfs.pushAndSetReached(s);
774// //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
775// //       while ( !bfs.finished() ) {
776// //   AugOutEdgeIt e=bfs;
777// //   if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
778// //     dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
779// //   }
780       
781// //   ++bfs;
782// //       } //computing distances from s in the residual graph
783
784// //       MutableGraph F;
785// //       typename AugGraph::NodeMap<typename MutableGraph::Node>
786// //   res_graph_to_F(res_graph);
787// //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
788// //   res_graph_to_F.set(n, F.addNode());
789// //       }
790     
791// //       typename MutableGraph::Node sF=res_graph_to_F.get(s);
792// //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
793
794// //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
795// //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
796
797// //       //Making F to the graph containing the edges of the residual graph
798// //       //which are in some shortest paths
799// //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
800// //   if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
801// //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
802// //     original_edge.update();
803// //     original_edge.set(f, e);
804// //     residual_capacity.update();
805// //     residual_capacity.set(f, res_graph.free(e));
806// //   }
807// //       }
808
809// //       bool __augment=true;
810
811// //       while (__augment) {
812// //   __augment=false;
813// //   //computing blocking flow with dfs
814// //   typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
815// //   DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
816// //   typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
817// //   pred.set(sF, typename MutableGraph::Edge(INVALID));
818// //   //invalid iterators for sources
819
820// //   typename MutableGraph::NodeMap<Number> free(F);
821
822// //   dfs.pushAndSetReached(sF);     
823// //   while (!dfs.finished()) {
824// //     ++dfs;
825// //     if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
826// //       if (dfs.isBNodeNewlyReached()) {
827// //         typename MutableGraph::Node v=F.aNode(dfs);
828// //         typename MutableGraph::Node w=F.bNode(dfs);
829// //         pred.set(w, dfs);
830// //         if (F.valid(pred.get(v))) {
831// //           free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
832// //         } else {
833// //           free.set(w, residual_capacity.get(dfs));
834// //         }
835// //         if (w==tF) {
836// //           __augment=true;
837// //           _augment=true;
838// //           break;
839// //         }
840             
841// //       } else {
842// //         F.erase(typename MutableGraph::OutEdgeIt(dfs));
843// //       }
844// //     }
845// //   }
846
847// //   if (__augment) {
848// //     typename MutableGraph::Node n=tF;
849// //     Number augment_value=free.get(tF);
850// //     while (F.valid(pred.get(n))) {
851// //       typename MutableGraph::Edge e=pred.get(n);
852// //       res_graph.augment(original_edge.get(e), augment_value);
853// //       n=F.tail(e);
854// //       if (residual_capacity.get(e)==augment_value)
855// //         F.erase(e);
856// //       else
857// //         residual_capacity.set(e, residual_capacity.get(e)-augment_value);
858// //     }
859// //   }
860       
861// //       }
862           
863// //       return _augment;
864// //     }
865//     bool augmentOnBlockingFlow2() {
866//       bool _augment=false;
867
868//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
869//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
870//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
871//       typedef typename EAugGraph::Edge EAugEdge;
872
873//       EAugGraph res_graph(*G, *flow, *capacity);
874
875//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
876//       BfsIterator5<
877//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
878//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
879//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
880
881
882//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
883//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
884//      if (S->get(s)) {
885//        Number u=0;
886//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
887//          u+=flow->get(e);
888//        if (u<1) {
889//          bfs.pushAndSetReached(s);
890//          //pred.set(s, AugEdge(INVALID));
891//        }
892//      }
893//       }
894
895     
896//       //bfs.pushAndSetReached(s);
897
898//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
899//      NodeMap<int>& dist=res_graph.dist;
900
901//       while ( !bfs.finished() ) {
902//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
903//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
904//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
905//      }
906//      ++bfs; 
907//       } //computing distances from s in the residual graph
908
909//       bool __augment=true;
910
911//       while (__augment) {
912
913//      __augment=false;
914//      //computing blocking flow with dfs
915//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
916//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
917//        dfs(res_graph);
918//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
919//      //pred.set(s, EAugEdge(INVALID));
920//      //invalid iterators for sources
921
922//      typename EAugGraph::NodeMap<Number> free(res_graph);
923
924
925//      //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
926//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
927//      if (S->get(s)) {
928//        Number u=0;
929//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
930//          u+=flow->get(e);
931//        if (u<1) {
932//          dfs.pushAndSetReached(s);
933//          //pred.set(s, AugEdge(INVALID));
934//        }
935//      }
936//       }
937
938
939
940//       //dfs.pushAndSetReached(s);
941//       typename EAugGraph::Node n;
942//      while (!dfs.finished()) {
943//        ++dfs;
944//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
945//          if (dfs.isBNodeNewlyReached()) {
946         
947//            typename EAugGraph::Node v=res_graph.aNode(dfs);
948//            typename EAugGraph::Node w=res_graph.bNode(dfs);
949
950//            pred.set(w, EAugOutEdgeIt(dfs));
951//            if (res_graph.valid(pred.get(v))) {
952//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
953//            } else {
954//              free.set(w, res_graph.free(dfs));
955//            }
956             
957//            n=w;
958//            if (T->get(w)) {
959//              Number u=0;
960//              for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
961//                u+=flow->get(f);
962//              if (u<1) {
963//                __augment=true;
964//                _augment=true;
965//                break;
966//              }
967//            }
968//          } else {
969//            res_graph.erase(dfs);
970//          }
971//        }
972
973//      }
974
975//      if (__augment) {
976//        // typename EAugGraph::Node n=t;
977//        Number augment_value=free.get(n);
978//        while (res_graph.valid(pred.get(n))) {
979//          EAugEdge e=pred.get(n);
980//          res_graph.augment(e, augment_value);
981//          n=res_graph.tail(e);
982//          if (res_graph.free(e)==0)
983//            res_graph.erase(e);
984//        }
985//      }
986     
987//       }
988           
989//       return _augment;
990//     }
991//     void run() {
992//       //int num_of_augmentations=0;
993//       while (augmentOnShortestPath()) {
994//      //while (augmentOnBlockingFlow<MutableGraph>()) {
995//      //std::cout << ++num_of_augmentations << " ";
996//      //std::cout<<std::endl;
997//       }
998//     }
999// //     template<typename MutableGraph> void run() {
1000// //       //int num_of_augmentations=0;
1001// //       //while (augmentOnShortestPath()) {
1002// //   while (augmentOnBlockingFlow<MutableGraph>()) {
1003// //   //std::cout << ++num_of_augmentations << " ";
1004// //   //std::cout<<std::endl;
1005// //       }
1006// //     }
1007//     Number flowValue() {
1008//       Number a=0;
1009//       EdgeIt e;
1010//       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1011//      a+=flow->get(e);
1012//       }
1013//       return a;
1014//     }
1015//   };
1016
1017
1018
1019
1020
1021 
1022// //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1023// //   class MaxFlow2 {
1024// //   public:
1025// //     typedef typename Graph::Node Node;
1026// //     typedef typename Graph::Edge Edge;
1027// //     typedef typename Graph::EdgeIt EdgeIt;
1028// //     typedef typename Graph::OutEdgeIt OutEdgeIt;
1029// //     typedef typename Graph::InEdgeIt InEdgeIt;
1030// //   private:
1031// //     const Graph& G;
1032// //     std::list<Node>& S;
1033// //     std::list<Node>& T;
1034// //     FlowMap& flow;
1035// //     const CapacityMap& capacity;
1036// //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1037// //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1038// //     typedef typename AugGraph::Edge AugEdge;
1039// //     typename Graph::NodeMap<bool> SMap;
1040// //     typename Graph::NodeMap<bool> TMap;
1041// //   public:
1042// //     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) {
1043// //       for(typename std::list<Node>::const_iterator i=S.begin();
1044// //     i!=S.end(); ++i) {
1045// //   SMap.set(*i, true);
1046// //       }
1047// //       for (typename std::list<Node>::const_iterator i=T.begin();
1048// //      i!=T.end(); ++i) {
1049// //   TMap.set(*i, true);
1050// //       }
1051// //     }
1052// //     bool augment() {
1053// //       AugGraph res_graph(G, flow, capacity);
1054// //       bool _augment=false;
1055// //       Node reached_t_node;
1056     
1057// //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
1058// //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1059// //       for(typename std::list<Node>::const_iterator i=S.begin();
1060// //     i!=S.end(); ++i) {
1061// //   res_bfs.pushAndSetReached(*i);
1062// //       }
1063// //       //res_bfs.pushAndSetReached(s);
1064       
1065// //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1066// //       //filled up with invalid iterators
1067     
1068// //       typename AugGraph::NodeMap<Number> free(res_graph);
1069       
1070// //       //searching for augmenting path
1071// //       while ( !res_bfs.finished() ) {
1072// //   AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1073// //   if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1074// //     Node v=res_graph.tail(e);
1075// //     Node w=res_graph.head(e);
1076// //     pred.set(w, e);
1077// //     if (pred.get(v).valid()) {
1078// //       free.set(w, std::min(free.get(v), e.free()));
1079// //     } else {
1080// //       free.set(w, e.free());
1081// //     }
1082// //     if (TMap.get(res_graph.head(e))) {
1083// //       _augment=true;
1084// //       reached_t_node=res_graph.head(e);
1085// //       break;
1086// //     }
1087// //   }
1088       
1089// //   ++res_bfs;
1090// //       } //end of searching augmenting path
1091
1092// //       if (_augment) {
1093// //   Node n=reached_t_node;
1094// //   Number augment_value=free.get(reached_t_node);
1095// //   while (pred.get(n).valid()) {
1096// //     AugEdge e=pred.get(n);
1097// //     e.augment(augment_value);
1098// //     n=res_graph.tail(e);
1099// //   }
1100// //       }
1101
1102// //       return _augment;
1103// //     }
1104// //     void run() {
1105// //       while (augment()) { }
1106// //     }
1107// //     Number flowValue() {
1108// //       Number a=0;
1109// //       for(typename std::list<Node>::const_iterator i=S.begin();
1110// //     i!=S.end(); ++i) {
1111// //   for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1112// //     a+=flow.get(e);
1113// //   }
1114// //   for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1115// //     a-=flow.get(e);
1116// //   }
1117// //       }
1118// //       return a;
1119// //     }
1120// //   };
1121
1122
1123} // namespace hugo
1124
1125#endif //HUGO_EDMONDS_KARP_H
Note: See TracBrowser for help on using the repository browser.