COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp.h @ 330:7ac0d4e8a31c

Last change on this file since 330:7ac0d4e8a31c was 330:7ac0d4e8a31c, checked in by marci, 20 years ago

In the resgraphwrapper interface, and in the constructor,
the order of FlowMap? and CapacityMap? is changed.

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