COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/edmonds_karp.h @ 393:4535f78639e2

Last change on this file since 393:4535f78639e2 was 389:770cc1f4861f, checked in by marci, 20 years ago

modifications for better compatibility with gcc 3.4.0

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