diff -r 100770da4336 -r 84c19824322a src/work/edmonds_karp.h
--- a/src/work/edmonds_karp.h	Wed Mar 17 14:50:01 2004 +0000
+++ b/src/work/edmonds_karp.h	Wed Mar 17 15:01:04 2004 +0000
@@ -527,6 +527,306 @@
     }
   };
 
+
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class MaxMatching {
+  public:
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+
+    typedef typename Graph::NodeMap<bool> SMap;
+    typedef typename Graph::NodeMap<bool> TMap;
+  private:
+    const Graph* G;
+    SMap* S;
+    TMap* T;
+    //Node s;
+    //Node t;
+    FlowMap* flow;
+    const CapacityMap* capacity;
+    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
+    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
+    typedef typename AugGraph::Edge AugEdge;
+
+  public:
+    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 
+      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
+    bool augmentOnShortestPath() {
+      AugGraph res_graph(*G, *flow, *capacity);
+      bool _augment=false;
+      
+      typedef typename AugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
+      typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
+      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
+	Number f=0;
+	for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e))
+	  f+=flow->get(e);
+	if (f<1) {
+	  res_bfs.pushAndSetReached(s);
+	  pred.set(s, AugEdge(INVALID));
+	}
+      }
+      
+      typename AugGraph::NodeMap<Number> free(res_graph);
+	
+      Node n;
+      //searching for augmenting path
+      while ( !res_bfs.finished() ) { 
+	AugOutEdgeIt e=res_bfs;
+	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
+	  Node v=res_graph.tail(e);
+	  Node w=res_graph.head(e);
+	  pred.set(w, e);
+	  if (res_graph.valid(pred.get(v))) {
+	    free.set(w, std::min(free.get(v), res_graph.free(e)));
+	  } else {
+	    free.set(w, res_graph.free(e)); 
+	  }
+	  if (TMap(res_graph.head(e))) { 
+	    n=res_graph.head(e);
+	    _augment=true; 
+	    break; 
+	  }
+	}
+	
+	++res_bfs;
+      } //end of searching augmenting path
+
+      if (_augment) {
+	//Node n=t;
+	Number augment_value=free.get(t);
+	while (res_graph.valid(pred.get(n))) { 
+	  AugEdge e=pred.get(n);
+	  res_graph.augment(e, augment_value); 
+	  n=res_graph.tail(e);
+	}
+      }
+
+      return _augment;
+    }
+
+//     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
+//       bool _augment=false;
+
+//       AugGraph res_graph(*G, *flow, *capacity);
+
+//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
+//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
+
+//       bfs.pushAndSetReached(s);
+//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+//       while ( !bfs.finished() ) { 
+// 	AugOutEdgeIt e=bfs;
+// 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+// 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+// 	}
+	
+// 	++bfs;
+//       } //computing distances from s in the residual graph
+
+//       MutableGraph F;
+//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
+// 	res_graph_to_F(res_graph);
+//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+// 	res_graph_to_F.set(n, F.addNode());
+//       }
+      
+//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
+//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
+
+//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
+//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
+
+//       //Making F to the graph containing the edges of the residual graph 
+//       //which are in some shortest paths
+//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
+// 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
+// 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+// 	  original_edge.update();
+// 	  original_edge.set(f, e);
+// 	  residual_capacity.update();
+// 	  residual_capacity.set(f, res_graph.free(e));
+// 	} 
+//       }
+
+//       bool __augment=true;
+
+//       while (__augment) {
+// 	__augment=false;
+// 	//computing blocking flow with dfs
+// 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
+// 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
+// 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
+// 	pred.set(sF, typename MutableGraph::Edge(INVALID));
+// 	//invalid iterators for sources
+
+// 	typename MutableGraph::NodeMap<Number> free(F);
+
+// 	dfs.pushAndSetReached(sF);      
+// 	while (!dfs.finished()) {
+// 	  ++dfs;
+// 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
+// 	    if (dfs.isBNodeNewlyReached()) {
+// 	      typename MutableGraph::Node v=F.aNode(dfs);
+// 	      typename MutableGraph::Node w=F.bNode(dfs);
+// 	      pred.set(w, dfs);
+// 	      if (F.valid(pred.get(v))) {
+// 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+// 	      } else {
+// 		free.set(w, residual_capacity.get(dfs)); 
+// 	      }
+// 	      if (w==tF) { 
+// 		__augment=true; 
+// 		_augment=true;
+// 		break; 
+// 	      }
+	      
+// 	    } else {
+// 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
+// 	    }
+// 	  } 
+// 	}
+
+// 	if (__augment) {
+// 	  typename MutableGraph::Node n=tF;
+// 	  Number augment_value=free.get(tF);
+// 	  while (F.valid(pred.get(n))) { 
+// 	    typename MutableGraph::Edge e=pred.get(n);
+// 	    res_graph.augment(original_edge.get(e), augment_value); 
+// 	    n=F.tail(e);
+// 	    if (residual_capacity.get(e)==augment_value) 
+// 	      F.erase(e); 
+// 	    else 
+// 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+// 	  }
+// 	}
+	
+//       }
+            
+//       return _augment;
+//     }
+//     bool augmentOnBlockingFlow2() {
+//       bool _augment=false;
+
+//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
+//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
+//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
+//       typedef typename EAugGraph::Edge EAugEdge;
+
+//       EAugGraph res_graph(*G, *flow, *capacity);
+
+//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
+//       BfsIterator4< 
+// 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
+// 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
+// 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
+      
+//       bfs.pushAndSetReached(s);
+
+//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
+// 	NodeMap<int>& dist=res_graph.dist;
+
+//       while ( !bfs.finished() ) {
+// 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
+// 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+// 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+// 	}
+// 	++bfs;	
+//       } //computing distances from s in the residual graph
+
+//       bool __augment=true;
+
+//       while (__augment) {
+
+// 	__augment=false;
+// 	//computing blocking flow with dfs
+// 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
+// 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
+// 	  dfs(res_graph);
+// 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 
+// 	pred.set(s, EAugEdge(INVALID));
+// 	//invalid iterators for sources
+
+// 	typename EAugGraph::NodeMap<Number> free(res_graph);
+
+// 	dfs.pushAndSetReached(s);
+// 	while (!dfs.finished()) {
+// 	  ++dfs;
+// 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
+// 	    if (dfs.isBNodeNewlyReached()) {
+	  
+// 	      typename EAugGraph::Node v=res_graph.aNode(dfs);
+// 	      typename EAugGraph::Node w=res_graph.bNode(dfs);
+
+// 	      pred.set(w, EAugOutEdgeIt(dfs));
+// 	      if (res_graph.valid(pred.get(v))) {
+// 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));
+// 	      } else {
+// 		free.set(w, res_graph.free(dfs)); 
+// 	      }
+	      
+// 	      if (w==t) { 
+// 		__augment=true; 
+// 		_augment=true;
+// 		break; 
+// 	      }
+// 	    } else {
+// 	      res_graph.erase(dfs);
+// 	    }
+// 	  } 
+
+// 	}
+
+// 	if (__augment) {
+// 	  typename EAugGraph::Node n=t;
+// 	  Number augment_value=free.get(t);
+// 	  while (res_graph.valid(pred.get(n))) { 
+// 	    EAugEdge e=pred.get(n);
+// 	    res_graph.augment(e, augment_value);
+// 	    n=res_graph.tail(e);
+// 	    if (res_graph.free(e)==0)
+// 	      res_graph.erase(e);
+// 	  }
+// 	}
+      
+//       }
+            
+//       return _augment;
+//     }
+    void run() {
+      //int num_of_augmentations=0;
+      while (augmentOnShortestPath()) { 
+	//while (augmentOnBlockingFlow<MutableGraph>()) { 
+	//std::cout << ++num_of_augmentations << " ";
+	//std::cout<<std::endl;
+      } 
+    }
+    template<typename MutableGraph> void run() {
+      //int num_of_augmentations=0;
+      //while (augmentOnShortestPath()) { 
+	while (augmentOnBlockingFlow<MutableGraph>()) { 
+	//std::cout << ++num_of_augmentations << " ";
+	//std::cout<<std::endl;
+      } 
+    }
+    Number flowValue() { 
+      Number a=0;
+      OutEdgeIt e;
+      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
+	a+=flow->get(e);
+      }
+      return a;
+    }
+  };
+
+
+
+
+
   
 //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
 //   class MaxFlow2 {