Changeset 197:fff43d9c7110 in lemon-0.x for src/work/marci/max_bipartite_matching_demo.cc

Timestamp:

03/17/04 18:04:41 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@274

Message:

.

File:

• src/work/marci/max_bipartite_matching_demo.cc (modified) (6 diffs)

src/work/marci/max_bipartite_matching_demo.cc

@@ -5 +5 @@
 #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>
@@ -37 +40 @@
 
 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;
@@ -59 +63 @@
   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]);
 
 
@@ -81 +96 @@
   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);
-  }
-
-  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;
-  }
+  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;
+//   }
 
 
@@ -108 +121 @@
 
     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;
@@ -133 +144 @@
     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;
+  }
+