# HG changeset patch
# User marci
# Date 1079543081 0
# Node ID fff43d9c7110f3dc19b6d1cf0c797bc1f6e09b54
# Parent  8a9b9360463e641694e5c22418301ccf420e2e08
.

diff -r 8a9b9360463e -r fff43d9c7110 src/work/edmonds_karp.h
--- a/src/work/edmonds_karp.h	Wed Mar 17 16:10:33 2004 +0000
+++ b/src/work/edmonds_karp.h	Wed Mar 17 17:04:41 2004 +0000
@@ -564,10 +564,10 @@
       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
 	if (S->get(s)) {
-	  Number f=0;
+	  Number u=0;
 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
-	    f+=flow->get(e);
-	  if (f<1) {
+	    u+=flow->get(e);
+	  if (u<1) {
 	    res_bfs.pushAndSetReached(s);
 	    pred.set(s, AugEdge(INVALID));
 	  }
@@ -589,10 +589,15 @@
 	  } else {
 	    free.set(w, res_graph.free(e)); 
 	  }
-	  if (T->get(res_graph.head(e))) { 
-	    n=res_graph.head(e);
-	    _augment=true; 
-	    break; 
+	  n=res_graph.head(e);
+	  if (T->get(n)) { 
+	    Number u=0;
+	    for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
+	      u+=flow->get(f);
+	    if (u<1) {
+	      _augment=true; 
+	      break; 
+	    }
 	  }
 	}
 	
@@ -620,7 +625,27 @@
 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
 //       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
 
-//       bfs.pushAndSetReached(s);
+
+
+
+
+//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
+//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
+// 	if (S->get(s)) {
+// 	  Number u=0;
+// 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
+// 	    u+=flow->get(e);
+// 	  if (u<1) {
+// 	    res_bfs.pushAndSetReached(s);
+// 	    //pred.set(s, AugEdge(INVALID));
+// 	  }
+// 	}
+//       }
+
+
+
+
+//       //bfs.pushAndSetReached(s);
 //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
 //       while ( !bfs.finished() ) { 
 // 	AugOutEdgeIt e=bfs;
@@ -712,94 +737,132 @@
             
 //       return _augment;
 //     }
-//     bool augmentOnBlockingFlow2() {
-//       bool _augment=false;
+    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;
+      //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);
+      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);
+      //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);
+
+
+      //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
+      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
+	if (S->get(s)) {
+	  Number u=0;
+	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
+	    u+=flow->get(e);
+	  if (u<1) {
+	    bfs.pushAndSetReached(s);
+	    //pred.set(s, AugEdge(INVALID));
+	  }
+	}
+      }
+
       
-//       bfs.pushAndSetReached(s);
+      //bfs.pushAndSetReached(s);
 
-//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
-// 	NodeMap<int>& dist=res_graph.dist;
+      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
+      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;
+      bool __augment=true;
 
-//       while (__augment) {
+      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
+	__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, INVALID); 
+	//pred.set(s, EAugEdge(INVALID));
+	//invalid iterators for sources
 
-// 	typename EAugGraph::NodeMap<Number> free(res_graph);
+	typename EAugGraph::NodeMap<Number> free(res_graph);
 
-// 	dfs.pushAndSetReached(s);
-// 	while (!dfs.finished()) {
-// 	  ++dfs;
-// 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
-// 	    if (dfs.isBNodeNewlyReached()) {
+
+	//typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
+      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
+	if (S->get(s)) {
+	  Number u=0;
+	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
+	    u+=flow->get(e);
+	  if (u<1) {
+	    dfs.pushAndSetReached(s);
+	    //pred.set(s, AugEdge(INVALID));
+	  }
+	}
+      }
+
+
+
+      //dfs.pushAndSetReached(s);
+      typename EAugGraph::Node n;
+	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);
+	      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);
-// 	    }
-// 	  } 
+	      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)); 
+	      }
+	     
+	      n=w;
+	      if (T->get(w)) {
+		Number u=0;
+		for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
+		  u+=flow->get(f);
+		if (u<1) {
+		  __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);
-// 	  }
-// 	}
+	if (__augment) {
+	  // typename EAugGraph::Node n=t;
+	  Number augment_value=free.get(n);
+	  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;
-//     }
+      return _augment;
+    }
     void run() {
       //int num_of_augmentations=0;
       while (augmentOnShortestPath()) { 
diff -r 8a9b9360463e -r fff43d9c7110 src/work/marci/max_bipartite_matching_demo.cc
--- a/src/work/marci/max_bipartite_matching_demo.cc	Wed Mar 17 16:10:33 2004 +0000
+++ b/src/work/marci/max_bipartite_matching_demo.cc	Wed Mar 17 17:04:41 2004 +0000
@@ -4,8 +4,11 @@
 #include <vector>
 #include <cstdlib>
 
-//#include <LEDA/graph.h>
-//#include <leda_graph_wrapper.h>
+#include <LEDA/graph.h>
+#include <LEDA/mcb_matching.h>
+#include <LEDA/list.h>
+
+#include <leda_graph_wrapper.h>
 #include <list_graph.h>
 #include <dimacs.h>
 #include <time_measure.h>
@@ -36,14 +39,15 @@
 using namespace hugo;
 
 using std::cout; 
+using std::cin; 
 using std::endl;
 
 int main() {
-//   leda::graph g;
-//   typedef LedaGraphWrapper<leda::graph> Graph;
-//   Graph G(g);
-  typedef ListGraph Graph;
-  Graph G;
+   leda::graph g;
+   typedef LedaGraphWrapper<leda::graph> Graph;
+   Graph G(g);
+//  typedef ListGraph Graph;
+//  Graph G;
 
   typedef Graph::Node Node;
   typedef Graph::NodeIt NodeIt;  
@@ -58,44 +62,53 @@
   std::vector<Node> s_nodes;
   std::vector<Node> t_nodes;
 
-  for(int i=0; i<4; ++i) {
+  int a;
+  cout << "number of nodes in the first color class=";
+  cin >> a; 
+  int b;
+  cout << "number of nodes in the second color class=";
+  cin >> b; 
+  int m;
+  cout << "number of edges=";
+  cin >> m; 
+  
+
+  for(int i=0; i<a; ++i) {
     s_nodes.push_back(G.addNode());
   }
-  for(int i=0; i<4; ++i) {
+  for(int i=0; i<a; ++i) {
     t_nodes.push_back(G.addNode());
   }
   random_init();
-  for(int i=0; i<6; ++i) {
-    G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
+  for(int i=0; i<m; ++i) {
+    G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
   }
   
+//   G.addEdge(s_nodes[1], t_nodes[5-4]);
+//   G.addEdge(s_nodes[1], t_nodes[5-4]);
+//   G.addEdge(s_nodes[1], t_nodes[4-4]);
+//   G.addEdge(s_nodes[1], t_nodes[4-4]);
 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
-//   G.addEdge(s_nodes[2], t_nodes[7-4]);
-//   G.addEdge(s_nodes[2], t_nodes[4-4]);
-//   G.addEdge(s_nodes[3], t_nodes[6-4]);
-//   G.addEdge(s_nodes[3], t_nodes[5-4]);
-//   G.addEdge(s_nodes[3], t_nodes[5-4]);
+//   G.addEdge(s_nodes[3], t_nodes[4-4]);
 
 
   Graph::NodeMap<bool> s_map(G); //false
   Graph::NodeMap<bool> t_map(G); //false
   
-  for(int i=0; i<4; ++i) {
-    s_map.set(s_nodes[i], true);
-    t_map.set(t_nodes[i], true);
-  }
+  for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true);
+  for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true);
 
-  cout << "bfs and dfs iterator demo on the directed graph" << endl;
-  for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
-    cout << G.id(n) << ": ";
-    cout << "out edges: ";
-    for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
-      cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
-    cout << "in edges: ";
-    for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
-      cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
-    cout << endl;
-  }
+//   cout << "bfs and dfs iterator demo on the directed graph" << endl;
+//   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
+//     cout << G.id(n) << ": ";
+//     cout << "out edges: ";
+//     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
+//       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
+//     cout << "in edges: ";
+//     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
+//       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
+//     cout << endl;
+//   }
 
 
   {
@@ -107,31 +120,95 @@
     ts.reset();
 
     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
-    //max_flow_test.augmentWithBlockingFlow<Graph>();
     int i=0;
     while (max_flow_test.augmentOnShortestPath()) { 
-//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//     }
-//     std::cout<<std::endl;
+//       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//       std::cout<<std::endl;
       ++i; 
     }
 
-    std::cout << "maximum matching: "<< std::endl;
-    for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
-      if (flow.get(e))
-	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
-    std::cout<<std::endl;
-    std::cout << "edges which are not in this maximum matching: "<< std::endl;
-    for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
-      if (!flow.get(e))
-	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
-    std::cout<<std::endl;
+//     std::cout << "maximum matching: "<< std::endl;
+//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+//       if (flow.get(e))
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//     std::cout<<std::endl;
+//     std::cout << "edges which are not in this maximum matching: "<< std::endl;
+//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+//       if (!flow.get(e))
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//     std::cout<<std::endl;
     
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
+
+  {
+    std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
+    Graph::EdgeMap<int> flow(G); //0 flow
+    Graph::EdgeMap<int> cap(G, 1);
+
+    Timer ts;
+    ts.reset();
+
+    MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
+    int i=0;
+    while (max_flow_test.augmentOnBlockingFlow2()) { 
+//       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//       std::cout<<std::endl;
+      ++i; 
+    }
+
+//     std::cout << "maximum matching: "<< std::endl;
+//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+//       if (flow.get(e))
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//     std::cout<<std::endl;
+//     std::cout << "edges which are not in this maximum matching: "<< std::endl;
+//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+//       if (!flow.get(e))
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//     std::cout<<std::endl;
+    
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
+
+  {
+    std::cout << "max bipartite matching (LEDA)..." << std::endl;
+    //Graph::EdgeMap<int> flow(G); //0 flow
+    //Graph::EdgeMap<int> cap(G, 1);
+
+    Timer ts;
+    ts.reset();
+
+    //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
+    //int i=0;
+    //while (max_flow_test.augmentOnShortestPath()) { ++i; }
+
+    leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);    
+    
+
+//     std::cout << "maximum matching: "<< std::endl;
+//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+//       if (flow.get(e))
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//     std::cout<<std::endl;
+//     std::cout << "edges which are not in this maximum matching: "<< std::endl;
+//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
+//       if (!flow.get(e))
+// 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
+//     std::cout<<std::endl;
+    
+    
+    std::cout << "elapsed time: " << ts << std::endl;
+    //std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< l.size() << std::endl;
+  }
+  
   
 
   return 0;