COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp.h @ 409:7ab7f083760a

Last change on this file since 409:7ab7f083760a was 409:7ab7f083760a, checked in by marci, 17 years ago

stGraphWrapper is almost working

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