Changeset 198:5cec393baade in lemon-0.x for src/work/edmonds_karp.h

Timestamp:

03/17/04 19:18:26 (20 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

File:

• src/work/edmonds_karp.h (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
       }