COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 182:c59e450712d8

Last change on this file since 182:c59e450712d8 was 175:ebccffe4d47b, checked in by marci, 20 years ago

correcting implicit typenames

File size: 21.3 KB
Line 
1// -*- c++ -*-
2#ifndef EDMONDS_KARP_H
3#define EDMONDS_KARP_H
4
5#include <algorithm>
6#include <list>
7#include <iterator>
8
9#include <bfs_iterator.h>
10#include <invalid.h>
11
12namespace hugo {
13
14  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
15  class ResGraph {
16  public:
17    typedef typename Graph::Node Node;
18    typedef typename Graph::NodeIt NodeIt;
19  private:
20    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
21    const Graph& G;
22    FlowMap& flow;
23    const CapacityMap& capacity;
24  public:
25    ResGraph(const Graph& _G, FlowMap& _flow,
26             const CapacityMap& _capacity) :
27      G(_G), flow(_flow), capacity(_capacity) { }
28
29    class Edge;
30    class OutEdgeIt;
31    friend class Edge;
32    friend class OutEdgeIt;
33
34    class Edge {
35      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
36    protected:
37      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
38      OldSymEdgeIt sym;
39    public:
40      Edge() { }
41      //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
42      Number free() const {
43        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
44          return (resG->capacity.get(sym)-resG->flow.get(sym));
45        } else {
46          return (resG->flow.get(sym));
47        }
48      }
49      bool valid() const { return sym.valid(); }
50      void augment(Number a) const {
51        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
52          resG->flow.set(sym, resG->flow.get(sym)+a);
53          //resG->flow[sym]+=a;
54        } else {
55          resG->flow.set(sym, resG->flow.get(sym)-a);
56          //resG->flow[sym]-=a;
57        }
58      }
59    };
60
61    class OutEdgeIt : public Edge {
62      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
63    public:
64      OutEdgeIt() { }
65      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
66    private:
67      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
68        resG=&_resG;
69        sym=resG->G.template first<OldSymEdgeIt>(v);
70        while( sym.valid() && !(free()>0) ) { ++sym; }
71      }
72    public:
73      OutEdgeIt& operator++() {
74        ++sym;
75        while( sym.valid() && !(free()>0) ) { ++sym; }
76        return *this;
77      }
78    };
79
80    void /*getF*/first(OutEdgeIt& e, Node v) const {
81      e=OutEdgeIt(*this, v);
82    }
83    void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
84   
85    template< typename It >
86    It first() const {
87      It e;     
88      /*getF*/first(e);
89      return e;
90    }
91
92    template< typename It >
93    It first(Node v) const {
94      It e;
95      /*getF*/first(e, v);
96      return e;
97    }
98
99    Node tail(Edge e) const { return G.aNode(e.sym); }
100    Node head(Edge e) const { return G.bNode(e.sym); }
101
102    Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
103    Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
104
105    int id(Node v) const { return G.id(v); }
106
107    template <typename S>
108    class NodeMap {
109      typename Graph::NodeMap<S> node_map;
110    public:
111      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
112      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
113      void set(Node nit, S a) { node_map.set(nit, a); }
114      S get(Node nit) const { return node_map.get(nit); }
115      S& operator[](Node nit) { return node_map[nit]; }
116      const S& operator[](Node nit) const { return node_map[nit]; }
117    };
118
119  };
120
121
122  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
123  class ResGraph2 {
124  public:
125    typedef typename Graph::Node Node;
126    typedef typename Graph::NodeIt NodeIt;
127  private:
128    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
129    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
130    typedef typename Graph::InEdgeIt OldInEdgeIt;
131   
132    const Graph& G;
133    FlowMap& flow;
134    const CapacityMap& capacity;
135  public:
136    ResGraph2(const Graph& _G, FlowMap& _flow,
137             const CapacityMap& _capacity) :
138      G(_G), flow(_flow), capacity(_capacity) { }
139
140    class Edge;
141    class OutEdgeIt;
142    friend class Edge;
143    friend class OutEdgeIt;
144
145    class Edge {
146      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
147    protected:
148      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
149      //OldSymEdgeIt sym;
150      OldOutEdgeIt out;
151      OldInEdgeIt in;
152      bool out_or_in; //true, iff out
153    public:
154      Edge() : out_or_in(true) { }
155      Number free() const {
156        if (out_or_in) {
157          return (resG->capacity.get(out)-resG->flow.get(out));
158        } else {
159          return (resG->flow.get(in));
160        }
161      }
162      bool valid() const {
163        return out_or_in && out.valid() || in.valid(); }
164      void augment(Number a) const {
165        if (out_or_in) {
166          resG->flow.set(out, resG->flow.get(out)+a);
167        } else {
168          resG->flow.set(in, resG->flow.get(in)-a);
169        }
170      }
171    };
172
173    class OutEdgeIt : public Edge {
174      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
175    public:
176      OutEdgeIt() { }
177    private:
178      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
179        resG=&_resG;
180        out=resG->G.template first<OldOutEdgeIt>(v);
181        while( out.valid() && !(free()>0) ) { ++out; }
182        if (!out.valid()) {
183          out_or_in=0;
184          in=resG->G.template first<OldInEdgeIt>(v);
185          while( in.valid() && !(free()>0) ) { ++in; }
186        }
187      }
188    public:
189      OutEdgeIt& operator++() {
190        if (out_or_in) {
191          Node v=resG->G.aNode(out);
192          ++out;
193          while( out.valid() && !(free()>0) ) { ++out; }
194          if (!out.valid()) {
195            out_or_in=0;
196            in=resG->G.template first<OldInEdgeIt>(v);
197            while( in.valid() && !(free()>0) ) { ++in; }
198          }
199        } else {
200          ++in;
201          while( in.valid() && !(free()>0) ) { ++in; }
202        }
203        return *this;
204      }
205    };
206
207    void /*getF*/first(OutEdgeIt& e, Node v) const {
208      e=OutEdgeIt(*this, v);
209    }
210    void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
211   
212    template< typename It >
213    It first() const {
214      It e;
215      /*getF*/first(e);
216      return e;
217    }
218
219    template< typename It >
220    It first(Node v) const {
221      It e;
222      /*getF*/first(e, v);
223      return e;
224    }
225
226    Node tail(Edge e) const {
227      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
228    Node head(Edge e) const {
229      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
230
231    Node aNode(OutEdgeIt e) const {
232      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
233    Node bNode(OutEdgeIt e) const {
234      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
235
236    int id(Node v) const { return G.id(v); }
237
238    template <typename S>
239    class NodeMap {
240      typename Graph::NodeMap<S> node_map;
241    public:
242      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
243      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
244      void set(Node nit, S a) { node_map.set(nit, a); }
245      S get(Node nit) const { return node_map.get(nit); }
246    };
247  };
248
249
250  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
251  class MaxFlow {
252  public:
253    typedef typename Graph::Node Node;
254    typedef typename Graph::Edge Edge;
255    typedef typename Graph::EdgeIt EdgeIt;
256    typedef typename Graph::OutEdgeIt OutEdgeIt;
257    typedef typename Graph::InEdgeIt InEdgeIt;
258
259  private:
260    const Graph* G;
261    Node s;
262    Node t;
263    FlowMap* flow;
264    const CapacityMap* capacity;
265    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
266    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
267    typedef typename AugGraph::Edge AugEdge;
268
269    //AugGraph res_graph;   
270    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
271    //typename AugGraph::NodeMap<AugEdge> pred;
272    //typename AugGraph::NodeMap<Number> free;
273  public:
274    MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
275      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
276      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
277      { }
278    bool augmentOnShortestPath() {
279      AugGraph res_graph(*G, *flow, *capacity);
280      bool _augment=false;
281     
282      typedef typename AugGraph::NodeMap<bool> ReachedMap;
283      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
284      res_bfs.pushAndSetReached(s);
285       
286      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
287      pred.set(s, AugEdge(INVALID));
288     
289      typename AugGraph::NodeMap<Number> free(res_graph);
290       
291      //searching for augmenting path
292      while ( !res_bfs.finished() ) {
293        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
294        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
295          Node v=res_graph.tail(e);
296          Node w=res_graph.head(e);
297          pred.set(w, e);
298          if (res_graph.valid(pred.get(v))) {
299            free.set(w, std::min(free.get(v), res_graph.free(e)));
300          } else {
301            free.set(w, res_graph.free(e));
302          }
303          if (res_graph.head(e)==t) { _augment=true; break; }
304        }
305       
306        ++res_bfs;
307      } //end of searching augmenting path
308
309      if (_augment) {
310        Node n=t;
311        Number augment_value=free.get(t);
312        while (res_graph.valid(pred.get(n))) {
313          AugEdge e=pred.get(n);
314          res_graph.augment(e, augment_value);
315          //e.augment(augment_value);
316          n=res_graph.tail(e);
317        }
318      }
319
320      return _augment;
321    }
322
323    template<typename MutableGraph> bool augmentOnBlockingFlow() {
324     
325//       std::cout << "number of nodes: " << G->nodeNum() << std::endl;
326//       typename Graph::NodeIt n;
327//       G->first(n);
328//       for( ; G->valid(n); G->next(n)) {
329//      std::cout << G->id(n) << std::endl;
330//       }
331//       std::cout << "meg elek 1";
332
333//       for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) {
334//      std::cout << G->id(n) << std::endl;
335//       }
336//       std::cout << "meg elek 2";
337     
338      bool _augment=false;
339
340      AugGraph res_graph(*G, *flow, *capacity);
341
342      typedef typename AugGraph::NodeMap<bool> ReachedMap;
343      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
344
345      bfs.pushAndSetReached(s);
346      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
347      while ( !bfs.finished() ) {
348        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
349        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
350          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
351        }
352       
353        ++bfs;
354      } //computing distances from s in the residual graph
355
356//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
357//      std::cout << res_graph.id(n) << std::endl;
358//       }
359//       std::cout << "meg elek";
360
361      MutableGraph F;
362      typename AugGraph::NodeMap<typename MutableGraph::Node>
363        res_graph_to_F(res_graph);
364      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
365        res_graph_to_F.set(n, F.addNode());
366      }
367     
368      typename MutableGraph::Node sF=res_graph_to_F.get(s);
369      typename MutableGraph::Node tF=res_graph_to_F.get(t);
370
371      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
372      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
373
374      //Making F to the graph containing the edges of the residual graph
375      //which are in some shortest paths
376      for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
377        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
378          typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
379          original_edge.update();
380          original_edge.set(f, e);
381          residual_capacity.update();
382          residual_capacity.set(f, res_graph.free(e));
383        }
384      }
385
386//       for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {
387//      std::cout << F.id(n) << std::endl;
388//       }
389
390      bool __augment=true;
391
392      while (__augment) {
393        __augment=false;
394        //computing blocking flow with dfs
395        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
396        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
397        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
398        pred.set(sF, typename MutableGraph::Edge(INVALID));
399        //invalid iterators for sources
400
401        typename MutableGraph::NodeMap<Number> free(F);
402
403        dfs.pushAndSetReached(sF);     
404        while (!dfs.finished()) {
405          ++dfs;
406          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
407            if (dfs.isBNodeNewlyReached()) {
408//            std::cout << "OutEdgeIt: " << dfs;
409//            std::cout << " aNode: " << F.aNode(dfs);
410//            std::cout << " bNode: " << F.bNode(dfs) << " ";
411         
412              typename MutableGraph::Node v=F.aNode(dfs);
413              typename MutableGraph::Node w=F.bNode(dfs);
414              pred.set(w, dfs);
415              if (F.valid(pred.get(v))) {
416                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
417              } else {
418                free.set(w, residual_capacity.get(dfs));
419              }
420              if (w==tF) {
421                //std::cout << "AUGMENTATION"<<std::endl;
422                __augment=true;
423                _augment=true;
424                break;
425              }
426             
427            } else {
428              F.erase(typename MutableGraph::OutEdgeIt(dfs));
429            }
430          }
431        }
432
433        if (__augment) {
434          typename MutableGraph::Node n=tF;
435          Number augment_value=free.get(tF);
436          while (F.valid(pred.get(n))) {
437            typename MutableGraph::Edge e=pred.get(n);
438            res_graph.augment(original_edge.get(e), augment_value);
439            //original_edge.get(e).augment(augment_value);
440            n=F.tail(e);
441            if (residual_capacity.get(e)==augment_value)
442              F.erase(e);
443            else
444              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
445          }
446        }
447       
448      }
449           
450      return _augment;
451    }
452    bool augmentOnBlockingFlow2() {
453      bool _augment=false;
454
455      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
456      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
457      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
458      typedef typename EAugGraph::Edge EAugEdge;
459
460      EAugGraph res_graph(*G, *flow, *capacity);
461
462      //std::cout << "meg jo1" << std::endl;
463
464      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
465      BfsIterator4<
466        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
467        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
468        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
469     
470      //std::cout << "meg jo2" << std::endl;
471
472      bfs.pushAndSetReached(s);
473      //std::cout << "meg jo2.5" << std::endl;
474
475      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
476      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
477        NodeMap<int>& dist=res_graph.dist;
478      //std::cout << "meg jo2.6" << std::endl;
479
480      while ( !bfs.finished() ) {
481        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
482//      EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
483        //if (res_graph.valid(e)) {
484        //    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
485        //}
486        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
487          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
488        }
489       
490        ++bfs; 
491      } //computing distances from s in the residual graph
492
493
494      //std::cout << "meg jo3" << std::endl;
495
496//       typedef typename EAugGraph::NodeIt EAugNodeIt;
497//       for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
498//      std::cout << "dist: " << dist.get(n) << std::endl;
499//       }
500
501      bool __augment=true;
502
503      while (__augment) {
504//      std::cout << "new iteration"<< std::endl;
505
506        __augment=false;
507        //computing blocking flow with dfs
508        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
509        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
510          dfs(res_graph);
511        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
512        pred.set(s, EAugEdge(INVALID));
513        //invalid iterators for sources
514
515        typename EAugGraph::NodeMap<Number> free(res_graph);
516
517        dfs.pushAndSetReached(s);
518        while (!dfs.finished()) {
519          ++dfs;
520          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
521            if (dfs.isBNodeNewlyReached()) {
522//            std::cout << "OutEdgeIt: " << dfs;
523//            std::cout << " aNode: " << res_graph.aNode(dfs);
524//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
525//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
526         
527              typename EAugGraph::Node v=res_graph.aNode(dfs);
528              typename EAugGraph::Node w=res_graph.bNode(dfs);
529
530              pred.set(w, EAugOutEdgeIt(dfs));
531
532              //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
533              if (res_graph.valid(pred.get(v))) {
534                free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
535              } else {
536                free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
537              }
538             
539              if (w==t) {
540//              std::cout << "t is reached, AUGMENTATION"<<std::endl;
541                __augment=true;
542                _augment=true;
543                break;
544              }
545            } else {
546//            std::cout << "<<DELETE ";
547//            std::cout << " aNode: " << res_graph.aNode(dfs);
548//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
549//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
550//            std::cout << "DELETE>> ";
551
552              res_graph.erase(dfs);
553            }
554          }
555
556        }
557
558        if (__augment) {
559          typename EAugGraph::Node n=t;
560          Number augment_value=free.get(t);
561//        std::cout << "av:" << augment_value << std::endl;
562          while (res_graph.valid(pred.get(n))) {
563            EAugEdge e=pred.get(n);
564            res_graph.augment(e, augment_value);
565            //e.augment(augment_value);
566            n=res_graph.tail(e);
567            if (res_graph.free(e)==0)
568              res_graph.erase(e);
569          }
570        }
571     
572      }
573           
574      return _augment;
575    }
576    void run() {
577      //int num_of_augmentations=0;
578      while (augmentOnShortestPath()) {
579        //while (augmentOnBlockingFlow<MutableGraph>()) {
580        //std::cout << ++num_of_augmentations << " ";
581        //std::cout<<std::endl;
582      }
583    }
584    template<typename MutableGraph> void run() {
585      //int num_of_augmentations=0;
586      //while (augmentOnShortestPath()) {
587        while (augmentOnBlockingFlow<MutableGraph>()) {
588        //std::cout << ++num_of_augmentations << " ";
589        //std::cout<<std::endl;
590      }
591    }
592    Number flowValue() {
593      Number a=0;
594      OutEdgeIt e;
595      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
596        a+=flow->get(e);
597      }
598      return a;
599    }
600  };
601
602 
603//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
604//   class MaxFlow2 {
605//   public:
606//     typedef typename Graph::Node Node;
607//     typedef typename Graph::Edge Edge;
608//     typedef typename Graph::EdgeIt EdgeIt;
609//     typedef typename Graph::OutEdgeIt OutEdgeIt;
610//     typedef typename Graph::InEdgeIt InEdgeIt;
611//   private:
612//     const Graph& G;
613//     std::list<Node>& S;
614//     std::list<Node>& T;
615//     FlowMap& flow;
616//     const CapacityMap& capacity;
617//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
618//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
619//     typedef typename AugGraph::Edge AugEdge;
620//     typename Graph::NodeMap<bool> SMap;
621//     typename Graph::NodeMap<bool> TMap;
622//   public:
623//     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) {
624//       for(typename std::list<Node>::const_iterator i=S.begin();
625//        i!=S.end(); ++i) {
626//      SMap.set(*i, true);
627//       }
628//       for (typename std::list<Node>::const_iterator i=T.begin();
629//         i!=T.end(); ++i) {
630//      TMap.set(*i, true);
631//       }
632//     }
633//     bool augment() {
634//       AugGraph res_graph(G, flow, capacity);
635//       bool _augment=false;
636//       Node reached_t_node;
637     
638//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
639//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
640//       for(typename std::list<Node>::const_iterator i=S.begin();
641//        i!=S.end(); ++i) {
642//      res_bfs.pushAndSetReached(*i);
643//       }
644//       //res_bfs.pushAndSetReached(s);
645       
646//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
647//       //filled up with invalid iterators
648     
649//       typename AugGraph::NodeMap<Number> free(res_graph);
650       
651//       //searching for augmenting path
652//       while ( !res_bfs.finished() ) {
653//      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
654//      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
655//        Node v=res_graph.tail(e);
656//        Node w=res_graph.head(e);
657//        pred.set(w, e);
658//        if (pred.get(v).valid()) {
659//          free.set(w, std::min(free.get(v), e.free()));
660//        } else {
661//          free.set(w, e.free());
662//        }
663//        if (TMap.get(res_graph.head(e))) {
664//          _augment=true;
665//          reached_t_node=res_graph.head(e);
666//          break;
667//        }
668//      }
669       
670//      ++res_bfs;
671//       } //end of searching augmenting path
672
673//       if (_augment) {
674//      Node n=reached_t_node;
675//      Number augment_value=free.get(reached_t_node);
676//      while (pred.get(n).valid()) {
677//        AugEdge e=pred.get(n);
678//        e.augment(augment_value);
679//        n=res_graph.tail(e);
680//      }
681//       }
682
683//       return _augment;
684//     }
685//     void run() {
686//       while (augment()) { }
687//     }
688//     Number flowValue() {
689//       Number a=0;
690//       for(typename std::list<Node>::const_iterator i=S.begin();
691//        i!=S.end(); ++i) {
692//      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
693//        a+=flow.get(e);
694//      }
695//      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
696//        a-=flow.get(e);
697//      }
698//       }
699//       return a;
700//     }
701//   };
702
703
704
705} // namespace hugo
706
707#endif //EDMONDS_KARP_H
Note: See TracBrowser for help on using the repository browser.