# HG changeset patch
# User marci
# Date 1079547506 0
# Node ID 5cec393baade5a08f921a6e0d37c14fdd461e8e4
# Parent  fff43d9c7110f3dc19b6d1cf0c797bc1f6e09b54
max cardinality bipartite matching demo, something to play with it

diff -r fff43d9c7110 -r 5cec393baade src/work/edmonds_karp.h
--- a/src/work/edmonds_karp.h	Wed Mar 17 17:04:41 2004 +0000
+++ b/src/work/edmonds_karp.h	Wed Mar 17 18:18:26 2004 +0000
@@ -551,10 +551,11 @@
     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     typedef typename AugGraph::Edge AugEdge;
+    typename Graph::NodeMap<int> used; //0
 
   public:
     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 
-      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
+      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
     bool augmentOnShortestPath() {
       AugGraph res_graph(*G, *flow, *capacity);
       bool _augment=false;
@@ -563,14 +564,14 @@
       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)) {
-	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) {
+	if ((S->get(s)) && (used.get(s)<1) ) {
+	  //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));
-	  }
+	    //}
 	}
       }
       
@@ -590,14 +591,14 @@
 	    free.set(w, res_graph.free(e)); 
 	  }
 	  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) {
+	  if (T->get(n) && (used.get(n)<1) ) { 
+	    //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; 
-	    }
+	      //}
 	  }
 	}
 	
@@ -606,12 +607,14 @@
 
       if (_augment) {
 	//Node n=t;
+	used.set(n, 1); //mind2 vegen jav
 	Number augment_value=free.get(n);
 	while (res_graph.valid(pred.get(n))) { 
 	  AugEdge e=pred.get(n);
 	  res_graph.augment(e, augment_value); 
 	  n=res_graph.tail(e);
 	}
+	used.set(n, 1); //mind2 vegen jav
       }
 
       return _augment;
diff -r fff43d9c7110 -r 5cec393baade src/work/marci/leda_graph_wrapper.h
--- a/src/work/marci/leda_graph_wrapper.h	Wed Mar 17 17:04:41 2004 +0000
+++ b/src/work/marci/leda_graph_wrapper.h	Wed Mar 17 18:18:26 2004 +0000
@@ -70,6 +70,7 @@
       //Node(const Node &) {} 
       bool operator==(Node n) const { return _n==n._n; } //FIXME
       bool operator!=(Node n) const { return _n!=n._n; } //FIXME
+      operator leda_node () { return _n; }
     };
     
     /// This iterator goes through each node.
@@ -100,7 +101,8 @@
       Edge(Invalid) : _e(0) {}
       //Edge(const Edge &) {} 
       bool operator==(Edge e) const { return _e==e._e; } //FIXME
-      bool operator!=(Edge e) const { return _e!=e._e; } //FIXME    
+      bool operator!=(Edge e) const { return _e!=e._e; } //FIXME 
+      operator leda_edge () { return _e; }
     };
     
     /// This iterator goes trought the outgoing edges of a certain graph.
diff -r fff43d9c7110 -r 5cec393baade src/work/marci/max_bipartite_matching_demo.cc
--- a/src/work/marci/max_bipartite_matching_demo.cc	Wed Mar 17 17:04:41 2004 +0000
+++ b/src/work/marci/max_bipartite_matching_demo.cc	Wed Mar 17 18:18:26 2004 +0000
@@ -91,12 +91,13 @@
 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
 //   G.addEdge(s_nodes[3], t_nodes[4-4]);
 
-
+  leda_list<leda_node> A;
+  leda_list<leda_node> B;
   Graph::NodeMap<bool> s_map(G); //false
   Graph::NodeMap<bool> t_map(G); //false
   
-  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);
+  for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; }
+  for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; }
 
 //   cout << "bfs and dfs iterator demo on the directed graph" << endl;
 //   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
@@ -112,7 +113,7 @@
 
 
   {
-    std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
+    std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
     Graph::EdgeMap<int> cap(G, 1);
 
@@ -144,51 +145,54 @@
     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);
+//   {
+//     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();
+//     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; 
-    }
+//     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 << "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 << "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);
 
+    leda_node_array<bool> NC(g);
+
     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_HK(g, A, B, NC, false);
     leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);