COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp.h @ 311:6635b11938fe

Last change on this file since 311:6635b11938fe was 311:6635b11938fe, checked in by marci, 17 years ago

gw

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