Changeset 198:5cec393baade in lemon-0.x

Timestamp:

03/17/04 19:18:26 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

max cardinality bipartite matching demo, something to play with it

Location:

src/work

Files:

• edmonds_karp.h (modified) (5 diffs)
• marci/leda_graph_wrapper.h (modified) (2 diffs)
• marci/max_bipartite_matching_demo.cc (modified) (5 diffs)

src/work/edmonds_karp.h

@@ -552 +552 @@
     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);
@@ -564 +565 @@
       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));
-          }
+            //}
         }
       }
@@ -591 +592 @@
           }
           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; 
-            }
+              //}
           }
         }
@@ -607 +608 @@
       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))) { 
@@ -613 +615 @@
           n=res_graph.tail(e);
         }
+        used.set(n, 1); //mind2 vegen jav
       }
 

src/work/marci/leda_graph_wrapper.h

@@ -71 +71 @@
       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; }
     };
     
@@ -101 +102 @@
       //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; }
     };
     

src/work/marci/max_bipartite_matching_demo.cc

@@ -92 +92 @@
 //   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;
@@ -113 +114 @@
 
   {
-    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);
@@ -145 +146 @@
   }
 
-  {
-    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 << "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;
+//   }
 
   {
@@ -183 +184 @@
     //Graph::EdgeMap<int> cap(G, 1);
 
+    leda_node_array<bool> NC(g);
+
     Timer ts;
     ts.reset();
@@ -189 +192 @@
     //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);