COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.h @ 265:bf7aea53635a

Last change on this file since 265:bf7aea53635a was 265:bf7aea53635a, checked in by marci, 17 years ago

GraphWrappers?

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