lemon-0.x: src/work/marci/edmonds

     1 // -*- c++ -*-

     2 #ifndef HUGO_EDMONDS_KARP_H

     3 #define HUGO_EDMONDS_KARP_H

     5 #include <algorithm>

     6 #include <list>

     7 #include <iterator>

     9 #include <bfs_iterator.h>

    10 #include <invalid.h>

    11 #include <graph_wrapper.h>

    12 #include <maps.h>

    14 namespace hugo {

    16   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

    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     FlowMap& flow;

    25     const CapacityMap& capacity;

    26   public:

    27     ResGraph(const Graph& _G, FlowMap& _flow,

    28 	     const CapacityMap& _capacity) :

    29       G(_G), flow(_flow), capacity(_capacity) { }

    31     class Edge;

    32     class OutEdgeIt;

    33     friend class Edge;

    34     friend class OutEdgeIt;

    36     class Edge {

    37       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    38     protected:

    39       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;

    40       OldSymEdgeIt sym;

    41     public:

    42       Edge() { }

    43       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }

    44       Number free() const {

    45 	if (resG->G.aNode(sym)==resG->G.tail(sym)) {

    46 	  return (resG->capacity.get(sym)-resG->flow.get(sym));

    47 	} else {

    48 	  return (resG->flow.get(sym));

    49 	}

    50       }

    51       bool valid() const { return sym.valid(); }

    52       void augment(Number a) const {

    53 	if (resG->G.aNode(sym)==resG->G.tail(sym)) {

    54 	  resG->flow.set(sym, resG->flow.get(sym)+a);

    55 	  //resG->flow[sym]+=a;

    56 	} else {

    57 	  resG->flow.set(sym, resG->flow.get(sym)-a);

    58 	  //resG->flow[sym]-=a;

    59 	}

    60       }

    61     };

    63     class OutEdgeIt : public Edge {

    64       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;

    65     public:

    66       OutEdgeIt() { }

    67       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }

    68     private:

    69       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {

    70       	resG=&_resG;

    71 	sym=resG->G.template first<OldSymEdgeIt>(v);

    72 	while( sym.valid() && !(free()>0) ) { ++sym; }

    73       }

    74     public:

    75       OutEdgeIt& operator++() {

    76 	++sym;

    77 	while( sym.valid() && !(free()>0) ) { ++sym; }

    78 	return *this;

    79       }

    80     };

    82     void /*getF*/first(OutEdgeIt& e, Node v) const {

    83       e=OutEdgeIt(*this, v);

    84     }

    85     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

    87     template< typename It >

    88     It first() const {

    89       It e;

    90       /*getF*/first(e);

    91       return e;

    92     }

    94     template< typename It >

    95     It first(Node v) const {

    96       It e;

    97       /*getF*/first(e, v);

    98       return e;

    99     }

   101     Node tail(Edge e) const { return G.aNode(e.sym); }

   102     Node head(Edge e) const { return G.bNode(e.sym); }

   104     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }

   105     Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

   107     int id(Node v) const { return G.id(v); }

   109     template <typename S>

   110     class NodeMap {

   111       typename Graph::NodeMap<S> node_map;

   112     public:

   113       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

   114       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

   115       void set(Node nit, S a) { node_map.set(nit, a); }

   116       S get(Node nit) const { return node_map.get(nit); }

   117       S& operator[](Node nit) { return node_map[nit]; }

   118       const S& operator[](Node nit) const { return node_map[nit]; }

   119     };

   121   };

   124   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   125   class ResGraph2 {

   126   public:

   127     typedef typename Graph::Node Node;

   128     typedef typename Graph::NodeIt NodeIt;

   129   private:

   130     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

   131     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

   132     typedef typename Graph::InEdgeIt OldInEdgeIt;

   134     const Graph& G;

   135     FlowMap& flow;

   136     const CapacityMap& capacity;

   137   public:

   138     ResGraph2(const Graph& _G, FlowMap& _flow,

   139 	     const CapacityMap& _capacity) :

   140       G(_G), flow(_flow), capacity(_capacity) { }

   142     class Edge;

   143     class OutEdgeIt;

   144     friend class Edge;

   145     friend class OutEdgeIt;

   147     class Edge {

   148       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   149     protected:

   150       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;

   151       //OldSymEdgeIt sym;

   152       OldOutEdgeIt out;

   153       OldInEdgeIt in;

   154       bool out_or_in; //true, iff out

   155     public:

   156       Edge() : out_or_in(true) { }

   157       Number free() const {

   158 	if (out_or_in) {

   159 	  return (resG->capacity.get(out)-resG->flow.get(out));

   160 	} else {

   161 	  return (resG->flow.get(in));

   162 	}

   163       }

   164       bool valid() const {

   165 	return out_or_in && out.valid() || in.valid(); }

   166       void augment(Number a) const {

   167 	if (out_or_in) {

   168 	  resG->flow.set(out, resG->flow.get(out)+a);

   169 	} else {

   170 	  resG->flow.set(in, resG->flow.get(in)-a);

   171 	}

   172       }

   173     };

   175     class OutEdgeIt : public Edge {

   176       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

   177     public:

   178       OutEdgeIt() { }

   179     private:

   180       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {

   181       	resG=&_resG;

   182 	out=resG->G.template first<OldOutEdgeIt>(v);

   183 	while( out.valid() && !(free()>0) ) { ++out; }

   184 	if (!out.valid()) {

   185 	  out_or_in=0;

   186 	  in=resG->G.template first<OldInEdgeIt>(v);

   187 	  while( in.valid() && !(free()>0) ) { ++in; }

   188 	}

   189       }

   190     public:

   191       OutEdgeIt& operator++() {

   192 	if (out_or_in) {

   193 	  Node v=resG->G.aNode(out);

   194 	  ++out;

   195 	  while( out.valid() && !(free()>0) ) { ++out; }

   196 	  if (!out.valid()) {

   197 	    out_or_in=0;

   198 	    in=resG->G.template first<OldInEdgeIt>(v);

   199 	    while( in.valid() && !(free()>0) ) { ++in; }

   200 	  }

   201 	} else {

   202 	  ++in;

   203 	  while( in.valid() && !(free()>0) ) { ++in; }

   204 	}

   205 	return *this;

   206       }

   207     };

   209     void /*getF*/first(OutEdgeIt& e, Node v) const {

   210       e=OutEdgeIt(*this, v);

   211     }

   212     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }

   214     template< typename It >

   215     It first() const {

   216       It e;

   217       /*getF*/first(e);

   218       return e;

   219     }

   221     template< typename It >

   222     It first(Node v) const {

   223       It e;

   224       /*getF*/first(e, v);

   225       return e;

   226     }

   228     Node tail(Edge e) const {

   229       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }

   230     Node head(Edge e) const {

   231       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }

   233     Node aNode(OutEdgeIt e) const {

   234       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }

   235     Node bNode(OutEdgeIt e) const {

   236       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }

   238     int id(Node v) const { return G.id(v); }

   240     template <typename S>

   241     class NodeMap {

   242       typename Graph::NodeMap<S> node_map;

   243     public:

   244       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

   245       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

   246       void set(Node nit, S a) { node_map.set(nit, a); }

   247       S get(Node nit) const { return node_map.get(nit); }

   248     };

   249   };

   252   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   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     FlowMap* flow;

   264     const CapacityMap* capacity;

   265     typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;

   266     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;

   267     typedef typename ResGW::Edge ResGWEdge;

   268   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) { }

   273     bool augmentOnShortestPath() {

   274       ResGW res_graph(*g, *flow, *capacity);

   275       bool _augment=false;

   277       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);

   278       bfs.pushAndSetReached(s);

   280       typename ResGW::NodeMap<ResGWEdge> pred(res_graph);

   281       pred.set(s, INVALID);

   283       typename ResGW::NodeMap<Number> free(res_graph);

   285       //searching for augmenting path

   286       while ( !bfs.finished() ) {

   287 	ResGWOutEdgeIt e=bfs;

   288 	if (res_graph.valid(e) && 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[v])) {

   293 	    free.set(w, std::min(free[v], res_graph.resCap(e)));

   294 	  } else {

   295 	    free.set(w, res_graph.resCap(e));

   296 	  }

   297 	  if (res_graph.head(e)==t) { _augment=true; break; }

   298 	}

   300 	++bfs;

   301       } //end of searching augmenting path

   303       if (_augment) {

   304 	Node n=t;

   305 	Number augment_value=free[t];

   306 	while (res_graph.valid(pred[n])) {

   307 	  ResGWEdge e=pred[n];

   308 	  res_graph.augment(e, augment_value);

   309 	  n=res_graph.tail(e);

   310 	}

   311       }

   313       return _augment;

   314     }

   316     template<typename MapGraphWrapper>

   317     class DistanceMap {

   318     protected:

   319       const MapGraphWrapper* g;

   320       typename MapGraphWrapper::NodeMap<int> dist;

   321     public:

   322       DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }

   323       void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }

   324       int operator[](const typename MapGraphWrapper::Node& n)

   325 	{ return dist[n]; }

   326 //       int get(const typename MapGraphWrapper::Node& n) const {

   327 // 	return dist[n]; }

   328 //       bool get(const typename MapGraphWrapper::Edge& e) const {

   329 // 	return (dist.get(g->tail(e))<dist.get(g->head(e))); }

   330       bool operator[](const typename MapGraphWrapper::Edge& e) const {

   331 	return (dist[g->tail(e)]<dist[g->head(e)]);

   332       }

   333     };

   335     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   336       typedef MutableGraph MG;

   337       bool _augment=false;

   339       ResGW res_graph(*g, *flow, *capacity);

   341       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);

   343       bfs.pushAndSetReached(s);

   344       //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's

   345       DistanceMap<ResGW> dist(res_graph);

   346       while ( !bfs.finished() ) {

   347 	ResGWOutEdgeIt e=bfs;

   348 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   349 	  dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);

   350 	}

   351 	++bfs;

   352       } //computing distances from s in the residual graph

   354       MG F;

   355       ConstMap<typename ResGW::Node, bool> true_map(true);

   356       typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,

   357 	DistanceMap<ResGW> > FilterResGW;

   358       FilterResGW filter_res_graph(res_graph, true_map, dist);

   359       typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);

   360       {

   361 	typename ResGW::NodeIt n;

   362 	for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {

   363 	  res_graph_to_F.set(n, F.addNode());

   364 	}

   365       }

   367       typename MG::Node sF=res_graph_to_F[s];

   368       typename MG::Node tF=res_graph_to_F[t];

   369       typename MG::EdgeMap<ResGWEdge> original_edge(F);

   370       typename MG::EdgeMap<Number> residual_capacity(F);

   372       //Making F to the graph containing the edges of the residual graph

   373       //which are in some shortest paths

   374       {

   375 	typename FilterResGW::EdgeIt e;

   376 	for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {

   377 	  //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {

   378 	  typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[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.resCap(e));

   383 	  //}

   384 	}

   385       }

   387       bool __augment=true;

   389       while (__augment) {

   390 	__augment=false;

   391 	//computing blocking flow with dfs

   393 	DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);

   394 	typename MG::NodeMap<typename MG::Edge> pred(F);

   395 	pred.set(sF, INVALID);

   396 	//invalid iterators for sources

   398 	typename MG::NodeMap<Number> free(F);

   400 	dfs.pushAndSetReached(sF);

   401 	while (!dfs.finished()) {

   402 	  ++dfs;

   403 	  if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {

   404 	    if (dfs.isBNodeNewlyReached()) {

   405 	      typename MG::Node v=F.aNode(dfs);

   406 	      typename MG::Node w=F.bNode(dfs);

   407 	      pred.set(w, dfs);

   408 	      if (F.valid(pred[v])) {

   409 		free.set(w, std::min(free[v], residual_capacity[dfs]));

   410 	      } else {

   411 		free.set(w, residual_capacity[dfs]);

   412 	      }

   413 	      if (w==tF) {

   414 		__augment=true;

   415 		_augment=true;

   416 		break;

   417 	      }

   419 	    } else {

   420 	      F.erase(/*typename MG::OutEdgeIt*/(dfs));

   421 	    }

   422 	  }

   423 	}

   425 	if (__augment) {

   426 	  typename MG::Node n=tF;

   427 	  Number augment_value=free[tF];

   428 	  while (F.valid(pred[n])) {

   429 	    typename MG::Edge e=pred[n];

   430 	    res_graph.augment(original_edge[e], augment_value);

   431 	    n=F.tail(e);

   432 	    if (residual_capacity[e]==augment_value)

   433 	      F.erase(e);

   434 	    else

   435 	      residual_capacity.set(e, residual_capacity[e]-augment_value);

   436 	  }

   437 	}

   439       }

   441       return _augment;

   442     }

   444     template<typename MutableGraph> bool augmentOnBlockingFlow1() {

   445       typedef MutableGraph MG;

   446       bool _augment=false;

   448       ResGW res_graph(*g, *flow, *capacity);

   450       //bfs for distances on the residual graph

   451       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);

   452       bfs.pushAndSetReached(s);

   453       typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's

   455       //F will contain the physical copy of the residual graph

   456       //with the set of edges which are on shortest paths

   457       MG F;

   458       typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);

   459       {

   460 	typename ResGW::NodeIt n;

   461 	for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {

   462 	  res_graph_to_F.set(n, F.addNode());

   463 	}

   464       }

   466       typename MG::Node sF=res_graph_to_F[s];

   467       typename MG::Node tF=res_graph_to_F[t];

   468       typename MG::EdgeMap<ResGWEdge> original_edge(F);

   469       typename MG::EdgeMap<Number> residual_capacity(F);

   471       while ( !bfs.finished() ) {

   472 	ResGWOutEdgeIt e=bfs;

   473 	if (res_graph.valid(e)) {

   474 	  if (bfs.isBNodeNewlyReached()) {

   475 	    dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);

   476 	    typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);

   477 	    original_edge.update();

   478 	    original_edge.set(f, e);

   479 	    residual_capacity.update();

   480 	    residual_capacity.set(f, res_graph.resCap(e));

   481 	  } else {

   482 	    if (dist[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 	    }

   489 	  }

   490 	}

   491 	++bfs;

   492       } //computing distances from s in the residual graph

   494       bool __augment=true;

   496       while (__augment) {

   497 	__augment=false;

   498 	//computing blocking flow with dfs

   499 	DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);

   500 	typename MG::NodeMap<typename MG::Edge> pred(F);

   501 	pred.set(sF, INVALID);

   502 	//invalid iterators for sources

   504 	typename MG::NodeMap<Number> free(F);

   506 	dfs.pushAndSetReached(sF);

   507 	while (!dfs.finished()) {

   508 	  ++dfs;

   509 	  if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {

   510 	    if (dfs.isBNodeNewlyReached()) {

   511 	      typename MG::Node v=F.aNode(dfs);

   512 	      typename MG::Node w=F.bNode(dfs);

   513 	      pred.set(w, dfs);

   514 	      if (F.valid(pred[v])) {

   515 		free.set(w, std::min(free[v], residual_capacity[dfs]));

   516 	      } else {

   517 		free.set(w, residual_capacity[dfs]);

   518 	      }

   519 	      if (w==tF) {

   520 		__augment=true;

   521 		_augment=true;

   522 		break;

   523 	      }

   525 	    } else {

   526 	      F.erase(/*typename MG::OutEdgeIt*/(dfs));

   527 	    }

   528 	  }

   529 	}

   531 	if (__augment) {

   532 	  typename MG::Node n=tF;

   533 	  Number augment_value=free[tF];

   534 	  while (F.valid(pred[n])) {

   535 	    typename MG::Edge e=pred[n];

   536 	    res_graph.augment(original_edge[e], augment_value);

   537 	    n=F.tail(e);

   538 	    if (residual_capacity[e]==augment_value)

   539 	      F.erase(e);

   540 	    else

   541 	      residual_capacity.set(e, residual_capacity[e]-augment_value);

   542 	  }

   543 	}

   545       }

   547       return _augment;

   548     }

   550     bool augmentOnBlockingFlow2() {

   551       bool _augment=false;

   553       ResGW res_graph(*g, *flow, *capacity);

   555       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);

   557       bfs.pushAndSetReached(s);

   558       DistanceMap<ResGW> dist(res_graph);

   559       while ( !bfs.finished() ) {

   560  	ResGWOutEdgeIt e=bfs;

   561  	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   562  	  dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);

   563  	}

   564 	++bfs;

   565       } //computing distances from s in the residual graph

   567       //Subgraph containing the edges on some shortest paths

   568       ConstMap<typename ResGW::Node, bool> true_map(true);

   569       typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,

   570 	DistanceMap<ResGW> > FilterResGW;

   571       FilterResGW filter_res_graph(res_graph, true_map, dist);

   573       //Subgraph, which is able to delete edges which are already

   574       //met by the dfs

   575       typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>

   576  	first_out_edges(filter_res_graph);

   577       typename FilterResGW::NodeIt v;

   578       for(filter_res_graph.first(v); filter_res_graph.valid(v);

   579  	  filter_res_graph.next(v))

   580       {

   581  	typename FilterResGW::OutEdgeIt e;

   582  	filter_res_graph.first(e, v);

   583  	first_out_edges.set(v, e);

   584       }

   585       typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::

   586 	NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;

   587       ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);

   589       bool __augment=true;

   591       while (__augment) {

   593  	__augment=false;

   594   	//computing blocking flow with dfs

   595   	DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> >

   596   	  dfs(erasing_res_graph);

   597  	typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>

   598  	  pred(erasing_res_graph);

   599  	pred.set(s, INVALID);

   600   	//invalid iterators for sources

   602   	typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph);

   604  	dfs.pushAndSetReached(

   605 	  typename ErasingResGW::Node(

   606 	    typename FilterResGW::Node(

   607 	      typename ResGW::Node(s)

   608 	      )

   609 	    )

   610 	  );

   611  	while (!dfs.finished()) {

   612  	  ++dfs;

   613  	  if (erasing_res_graph.valid(

   614  		typename ErasingResGW::OutEdgeIt(dfs)))

   615  	  {

   616   	    if (dfs.isBNodeNewlyReached()) {

   618  	      typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);

   619  	      typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);

   621  	      pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));

   622  	      if (erasing_res_graph.valid(pred[v])) {

   623  		free1.set(w, std::min(free1[v], res_graph.resCap(

   624 				       typename ErasingResGW::OutEdgeIt(dfs))));

   625  	      } else {

   626  		free1.set(w, res_graph.resCap(

   627 			   typename ErasingResGW::OutEdgeIt(dfs)));

   628  	      }

   630  	      if (w==t) {

   631  		__augment=true;

   632  		_augment=true;

   633  		break;

   634  	      }

   635  	    } else {

   636  	      erasing_res_graph.erase(dfs);

   637 	    }

   638 	  }

   639 	}

   641   	if (__augment) {

   642    	  typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));

   643 // 	  typename ResGW::NodeMap<Number> a(res_graph);

   644 // 	  typename ResGW::Node b;

   645 // 	  Number j=a[b];

   646 // 	  typename FilterResGW::NodeMap<Number> a1(filter_res_graph);

   647 // 	  typename FilterResGW::Node b1;

   648 // 	  Number j1=a1[b1];

   649 // 	  typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);

   650 // 	  typename ErasingResGW::Node b2;

   651 // 	  Number j2=a2[b2];

   652  	  Number augment_value=free1[n];

   653  	  while (erasing_res_graph.valid(pred[n])) {

   654  	    typename ErasingResGW::OutEdgeIt e=pred[n];

   655  	    res_graph.augment(e, augment_value);

   656  	    n=erasing_res_graph.tail(e);

   657  	    if (res_graph.resCap(e)==0)

   658  	      erasing_res_graph.erase(e);

   659 	}

   660       }

   662       } //while (__augment)

   664       return _augment;

   665     }

   667     void run() {

   668       //int num_of_augmentations=0;

   669       while (augmentOnShortestPath()) {

   670 	//while (augmentOnBlockingFlow<MutableGraph>()) {

   671 	//std::cout << ++num_of_augmentations << " ";

   672 	//std::cout<<std::endl;

   673       }

   674     }

   676     template<typename MutableGraph> void run() {

   677       //int num_of_augmentations=0;

   678       //while (augmentOnShortestPath()) {

   679 	while (augmentOnBlockingFlow<MutableGraph>()) {

   680 	//std::cout << ++num_of_augmentations << " ";

   681 	//std::cout<<std::endl;

   682       }

   683     }

   685     Number flowValue() {

   686       Number a=0;

   687       OutEdgeIt e;

   688       for(g->first(e, s); g->valid(e); g->next(e)) {

   689 	a+=(*flow)[e];

   690       }

   691       return a;

   692     }

   694   };

   697 //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   698 //   class MaxMatching {

   699 //   public:

   700 //     typedef typename Graph::Node Node;

   701 //     typedef typename Graph::NodeIt NodeIt;

   702 //     typedef typename Graph::Edge Edge;

   703 //     typedef typename Graph::EdgeIt EdgeIt;

   704 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   705 //     typedef typename Graph::InEdgeIt InEdgeIt;

   707 //     typedef typename Graph::NodeMap<bool> SMap;

   708 //     typedef typename Graph::NodeMap<bool> TMap;

   709 //   private:

   710 //     const Graph* G;

   711 //     SMap* S;

   712 //     TMap* T;

   713 //     //Node s;

   714 //     //Node t;

   715 //     FlowMap* flow;

   716 //     const CapacityMap* capacity;

   717 //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

   718 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

   719 //     typedef typename AugGraph::Edge AugEdge;

   720 //     typename Graph::NodeMap<int> used; //0

   722 //   public:

   723 //     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :

   724 //       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }

   725 //     bool augmentOnShortestPath() {

   726 //       AugGraph res_graph(*G, *flow, *capacity);

   727 //       bool _augment=false;

   729 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   730 //       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);

   731 //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   732 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   733 // 	if ((S->get(s)) && (used.get(s)<1) ) {

   734 // 	  //Number u=0;

   735 // 	  //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   736 // 	  //u+=flow->get(e);

   737 // 	  //if (u<1) {

   738 // 	    bfs.pushAndSetReached(s);

   739 // 	    pred.set(s, AugEdge(INVALID));

   740 // 	    //}

   741 // 	}

   742 //       }

   744 //       typename AugGraph::NodeMap<Number> free(res_graph);

   746 //       Node n;

   747 //       //searching for augmenting path

   748 //       while ( !bfs.finished() ) {

   749 // 	AugOutEdgeIt e=bfs;

   750 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   751 // 	  Node v=res_graph.tail(e);

   752 // 	  Node w=res_graph.head(e);

   753 // 	  pred.set(w, e);

   754 // 	  if (res_graph.valid(pred.get(v))) {

   755 // 	    free.set(w, std::min(free.get(v), res_graph.free(e)));

   756 // 	  } else {

   757 // 	    free.set(w, res_graph.free(e));

   758 // 	  }

   759 // 	  n=res_graph.head(e);

   760 // 	  if (T->get(n) && (used.get(n)<1) ) {

   761 // 	    //Number u=0;

   762 // 	    //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))

   763 // 	    //u+=flow->get(f);

   764 // 	    //if (u<1) {

   765 // 	      _augment=true;

   766 // 	      break;

   767 // 	      //}

   768 // 	  }

   769 // 	}

   771 // 	++bfs;

   772 //       } //end of searching augmenting path

   774 //       if (_augment) {

   775 // 	//Node n=t;

   776 // 	used.set(n, 1); //mind2 vegen jav

   777 // 	Number augment_value=free.get(n);

   778 // 	while (res_graph.valid(pred.get(n))) {

   779 // 	  AugEdge e=pred.get(n);

   780 // 	  res_graph.augment(e, augment_value);

   781 // 	  n=res_graph.tail(e);

   782 // 	}

   783 // 	used.set(n, 1); //mind2 vegen jav

   784 //       }

   786 //       return _augment;

   787 //     }

   789 // //     template<typename MutableGraph> bool augmentOnBlockingFlow() {

   790 // //       bool _augment=false;

   792 // //       AugGraph res_graph(*G, *flow, *capacity);

   794 // //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

   795 // //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);

   801 // //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   802 // //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   803 // // 	if (S->get(s)) {

   804 // // 	  Number u=0;

   805 // // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   806 // // 	    u+=flow->get(e);

   807 // // 	  if (u<1) {

   808 // // 	    bfs.pushAndSetReached(s);

   809 // // 	    //pred.set(s, AugEdge(INVALID));

   810 // // 	  }

   811 // // 	}

   812 // //       }

   817 // //       //bfs.pushAndSetReached(s);

   818 // //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's

   819 // //       while ( !bfs.finished() ) {

   820 // // 	AugOutEdgeIt e=bfs;

   821 // // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   822 // // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   823 // // 	}

   825 // // 	++bfs;

   826 // //       } //computing distances from s in the residual graph

   828 // //       MutableGraph F;

   829 // //       typename AugGraph::NodeMap<typename MutableGraph::Node>

   830 // // 	res_graph_to_F(res_graph);

   831 // //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {

   832 // // 	res_graph_to_F.set(n, F.addNode());

   833 // //       }

   835 // //       typename MutableGraph::Node sF=res_graph_to_F.get(s);

   836 // //       typename MutableGraph::Node tF=res_graph_to_F.get(t);

   838 // //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);

   839 // //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);

   841 // //       //Making F to the graph containing the edges of the residual graph

   842 // //       //which are in some shortest paths

   843 // //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {

   844 // // 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {

   845 // // 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));

   846 // // 	  original_edge.update();

   847 // // 	  original_edge.set(f, e);

   848 // // 	  residual_capacity.update();

   849 // // 	  residual_capacity.set(f, res_graph.free(e));

   850 // // 	}

   851 // //       }

   853 // //       bool __augment=true;

   855 // //       while (__augment) {

   856 // // 	__augment=false;

   857 // // 	//computing blocking flow with dfs

   858 // // 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;

   859 // // 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);

   860 // // 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);

   861 // // 	pred.set(sF, typename MutableGraph::Edge(INVALID));

   862 // // 	//invalid iterators for sources

   864 // // 	typename MutableGraph::NodeMap<Number> free(F);

   866 // // 	dfs.pushAndSetReached(sF);

   867 // // 	while (!dfs.finished()) {

   868 // // 	  ++dfs;

   869 // // 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {

   870 // // 	    if (dfs.isBNodeNewlyReached()) {

   871 // // 	      typename MutableGraph::Node v=F.aNode(dfs);

   872 // // 	      typename MutableGraph::Node w=F.bNode(dfs);

   873 // // 	      pred.set(w, dfs);

   874 // // 	      if (F.valid(pred.get(v))) {

   875 // // 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));

   876 // // 	      } else {

   877 // // 		free.set(w, residual_capacity.get(dfs));

   878 // // 	      }

   879 // // 	      if (w==tF) {

   880 // // 		__augment=true;

   881 // // 		_augment=true;

   882 // // 		break;

   883 // // 	      }

   885 // // 	    } else {

   886 // // 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));

   887 // // 	    }

   888 // // 	  }

   889 // // 	}

   891 // // 	if (__augment) {

   892 // // 	  typename MutableGraph::Node n=tF;

   893 // // 	  Number augment_value=free.get(tF);

   894 // // 	  while (F.valid(pred.get(n))) {

   895 // // 	    typename MutableGraph::Edge e=pred.get(n);

   896 // // 	    res_graph.augment(original_edge.get(e), augment_value);

   897 // // 	    n=F.tail(e);

   898 // // 	    if (residual_capacity.get(e)==augment_value)

   899 // // 	      F.erase(e);

   900 // // 	    else

   901 // // 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);

   902 // // 	  }

   903 // // 	}

   905 // //       }

   907 // //       return _augment;

   908 // //     }

   909 //     bool augmentOnBlockingFlow2() {

   910 //       bool _augment=false;

   912 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;

   913 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;

   914 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;

   915 //       typedef typename EAugGraph::Edge EAugEdge;

   917 //       EAugGraph res_graph(*G, *flow, *capacity);

   919 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;

   920 //       BfsIterator5<

   921 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,

   922 // 	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/

   923 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);

   926 //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   927 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   928 // 	if (S->get(s)) {

   929 // 	  Number u=0;

   930 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   931 // 	    u+=flow->get(e);

   932 // 	  if (u<1) {

   933 // 	    bfs.pushAndSetReached(s);

   934 // 	    //pred.set(s, AugEdge(INVALID));

   935 // 	  }

   936 // 	}

   937 //       }

   940 //       //bfs.pushAndSetReached(s);

   942 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::

   943 // 	NodeMap<int>& dist=res_graph.dist;

   945 //       while ( !bfs.finished() ) {

   946 // 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;

   947 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {

   948 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);

   949 // 	}

   950 // 	++bfs;

   951 //       } //computing distances from s in the residual graph

   953 //       bool __augment=true;

   955 //       while (__augment) {

   957 // 	__augment=false;

   958 // 	//computing blocking flow with dfs

   959 // 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;

   960 // 	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >

   961 // 	  dfs(res_graph);

   962 // 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);

   963 // 	//pred.set(s, EAugEdge(INVALID));

   964 // 	//invalid iterators for sources

   966 // 	typename EAugGraph::NodeMap<Number> free(res_graph);

   969 // 	//typename AugGraph::NodeMap<AugEdge> pred(res_graph);

   970 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {

   971 // 	if (S->get(s)) {

   972 // 	  Number u=0;

   973 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))

   974 // 	    u+=flow->get(e);

   975 // 	  if (u<1) {

   976 // 	    dfs.pushAndSetReached(s);

   977 // 	    //pred.set(s, AugEdge(INVALID));

   978 // 	  }

   979 // 	}

   980 //       }

   984 //       //dfs.pushAndSetReached(s);

   985 //       typename EAugGraph::Node n;

   986 // 	while (!dfs.finished()) {

   987 // 	  ++dfs;

   988 // 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) {

   989 // 	    if (dfs.isBNodeNewlyReached()) {

   991 // 	      typename EAugGraph::Node v=res_graph.aNode(dfs);

   992 // 	      typename EAugGraph::Node w=res_graph.bNode(dfs);

   994 // 	      pred.set(w, EAugOutEdgeIt(dfs));

   995 // 	      if (res_graph.valid(pred.get(v))) {

   996 // 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));

   997 // 	      } else {

   998 // 		free.set(w, res_graph.free(dfs));

   999 // 	      }

  1001 // 	      n=w;

  1002 // 	      if (T->get(w)) {

  1003 // 		Number u=0;

  1004 // 		for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))

  1005 // 		  u+=flow->get(f);

  1006 // 		if (u<1) {

  1007 // 		  __augment=true;

  1008 // 		  _augment=true;

  1009 // 		  break;

  1010 // 		}

  1011 // 	      }

  1012 // 	    } else {

  1013 // 	      res_graph.erase(dfs);

  1014 // 	    }

  1015 // 	  }

  1017 // 	}

  1019 // 	if (__augment) {

  1020 // 	  // typename EAugGraph::Node n=t;

  1021 // 	  Number augment_value=free.get(n);

  1022 // 	  while (res_graph.valid(pred.get(n))) {

  1023 // 	    EAugEdge e=pred.get(n);

  1024 // 	    res_graph.augment(e, augment_value);

  1025 // 	    n=res_graph.tail(e);

  1026 // 	    if (res_graph.free(e)==0)

  1027 // 	      res_graph.erase(e);

  1028 // 	  }

  1029 // 	}

  1031 //       }

  1033 //       return _augment;

  1034 //     }

  1035 //     void run() {

  1036 //       //int num_of_augmentations=0;

  1037 //       while (augmentOnShortestPath()) {

  1038 // 	//while (augmentOnBlockingFlow<MutableGraph>()) {

  1039 // 	//std::cout << ++num_of_augmentations << " ";

  1040 // 	//std::cout<<std::endl;

  1041 //       }

  1042 //     }

  1043 // //     template<typename MutableGraph> void run() {

  1044 // //       //int num_of_augmentations=0;

  1045 // //       //while (augmentOnShortestPath()) {

  1046 // // 	while (augmentOnBlockingFlow<MutableGraph>()) {

  1047 // // 	//std::cout << ++num_of_augmentations << " ";

  1048 // // 	//std::cout<<std::endl;

  1049 // //       }

  1050 // //     }

  1051 //     Number flowValue() {

  1052 //       Number a=0;

  1053 //       EdgeIt e;

  1054 //       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {

  1055 // 	a+=flow->get(e);

  1056 //       }

  1057 //       return a;

  1058 //     }

  1059 //   };

  1066 // //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1067 // //   class MaxFlow2 {

  1068 // //   public:

  1069 // //     typedef typename Graph::Node Node;

  1070 // //     typedef typename Graph::Edge Edge;

  1071 // //     typedef typename Graph::EdgeIt EdgeIt;

  1072 // //     typedef typename Graph::OutEdgeIt OutEdgeIt;

  1073 // //     typedef typename Graph::InEdgeIt InEdgeIt;

  1074 // //   private:

  1075 // //     const Graph& G;

  1076 // //     std::list<Node>& S;

  1077 // //     std::list<Node>& T;

  1078 // //     FlowMap& flow;

  1079 // //     const CapacityMap& capacity;

  1080 // //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;

  1081 // //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

  1082 // //     typedef typename AugGraph::Edge AugEdge;

  1083 // //     typename Graph::NodeMap<bool> SMap;

  1084 // //     typename Graph::NodeMap<bool> TMap;

  1085 // //   public:

  1086 // //     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) {

  1087 // //       for(typename std::list<Node>::const_iterator i=S.begin();

  1088 // // 	  i!=S.end(); ++i) {

  1089 // // 	SMap.set(*i, true);

  1090 // //       }

  1091 // //       for (typename std::list<Node>::const_iterator i=T.begin();

  1092 // // 	   i!=T.end(); ++i) {

  1093 // // 	TMap.set(*i, true);

  1094 // //       }

  1095 // //     }

  1096 // //     bool augment() {

  1097 // //       AugGraph res_graph(G, flow, capacity);

  1098 // //       bool _augment=false;

  1099 // //       Node reached_t_node;

  1101 // //       typedef typename AugGraph::NodeMap<bool> ReachedMap;

  1102 // //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);

  1103 // //       for(typename std::list<Node>::const_iterator i=S.begin();

  1104 // // 	  i!=S.end(); ++i) {

  1105 // // 	bfs.pushAndSetReached(*i);

  1106 // //       }

  1107 // //       //bfs.pushAndSetReached(s);

  1109 // //       typename AugGraph::NodeMap<AugEdge> pred(res_graph);

  1110 // //       //filled up with invalid iterators

  1112 // //       typename AugGraph::NodeMap<Number> free(res_graph);

  1114 // //       //searching for augmenting path

  1115 // //       while ( !bfs.finished() ) {

  1116 // // 	AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);

  1117 // // 	if (e.valid() && bfs.isBNodeNewlyReached()) {

  1118 // // 	  Node v=res_graph.tail(e);

  1119 // // 	  Node w=res_graph.head(e);

  1120 // // 	  pred.set(w, e);

  1121 // // 	  if (pred.get(v).valid()) {

  1122 // // 	    free.set(w, std::min(free.get(v), e.free()));

  1123 // // 	  } else {

  1124 // // 	    free.set(w, e.free());

  1125 // // 	  }

  1126 // // 	  if (TMap.get(res_graph.head(e))) {

  1127 // // 	    _augment=true;

  1128 // // 	    reached_t_node=res_graph.head(e);

  1129 // // 	    break;

  1130 // // 	  }

  1131 // // 	}

  1133 // // 	++bfs;

  1134 // //       } //end of searching augmenting path

  1136 // //       if (_augment) {

  1137 // // 	Node n=reached_t_node;

  1138 // // 	Number augment_value=free.get(reached_t_node);

  1139 // // 	while (pred.get(n).valid()) {

  1140 // // 	  AugEdge e=pred.get(n);

  1141 // // 	  e.augment(augment_value);

  1142 // // 	  n=res_graph.tail(e);

  1143 // // 	}

  1144 // //       }

  1146 // //       return _augment;

  1147 // //     }

  1148 // //     void run() {

  1149 // //       while (augment()) { }

  1150 // //     }

  1151 // //     Number flowValue() {

  1152 // //       Number a=0;

  1153 // //       for(typename std::list<Node>::const_iterator i=S.begin();

  1154 // // 	  i!=S.end(); ++i) {

  1155 // // 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {

  1156 // // 	  a+=flow.get(e);

  1157 // // 	}

  1158 // // 	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {

  1159 // // 	  a-=flow.get(e);

  1160 // // 	}

  1161 // //       }

  1162 // //       return a;

  1163 // //     }

  1164 // //   };

  1167 } // namespace hugo

  1169 #endif //HUGO_EDMONDS_KARP_H

author	athos
	Wed, 14 Apr 2004 13:30:05 +0000
changeset 322	a42dacfd0e3e
parent 312	54e07057eb47
child 330	7ac0d4e8a31c
permissions	-rw-r--r--