Changeset 93:25ab81446a07 in lemon-0.x for src/work/alpar/f_ed_ka.h

Timestamp:

02/17/04 15:04:46 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

It is working...

File:

• src/work/alpar/f_ed_ka.h (modified) (5 diffs)

src/work/alpar/f_ed_ka.h

@@ -20 +20 @@
                                       typename Graph::EachNodeIt t)
   { 
+    typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::EachNodeIt EachNodeIt;
     typedef typename Graph::EdgeIt EdgeIt;
@@ -30 +31 @@
     T aug_val;
 
-    for(EachEdgeIt e(G);G.valid(e);G.next(e))
+    for(EachEdgeIt e(G);G.valid(e);G.goNext(e))
       f.set(e,0);
     
-    std::queue<EachNodeIt> bfs_queue;
+    std::queue<NodeIt> bfs_queue;
     typename Graph::NodeMap<int> visited(G); //0: unvisited,
                                              //1: reached by a forward edge
@@ -44 +45 @@
   augment:
     
-    for(EachNodeIt n(G);G.valid(n);G.next(n))
+    for(EachNodeIt n(G);G.valid(n);G.goNext(n))
       visited.set(n,0);
     
@@ -56 +57 @@
     while(!bfs_queue.empty() && !visited.get(t))
       {
-        EachNodeIt n(bfs_queue.front());
-        for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
+        NodeIt n(bfs_queue.front());
+        bfs_queue.pop();
+        for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e))
           if(f.get(e)<c.get(e) &&   //FIXME: <
              !visited.get(G.bNode(e))) 
             {
-              tree.set(G.bNode(e),e);
-              visited.set(G.bNode(e),1);
+              NodeIt nn(G.bNode(e)); //It improves nothing
+              tree.set(nn,e);
+              visited.set(nn,1);
+              bfs_queue.push(nn);
             }
-        for(InEdgeIt e(G,n);G.valid(e);G.next(e))
+        for(InEdgeIt e(G,n);G.valid(e);G.goNext(e))
           if(f.get(e)>0 &&   //FIXME: >
              !visited.get(G.bNode(e))) 
             {
-              tree.set(G.bNode(e),e);
-              visited.set(G.bNode(e),2);
+              NodeIt nn(G.bNode(e));
+              tree.set(nn,e);
+              visited.set(nn,2);
+              bfs_queue.push(nn);
             }
       }
@@ -82 +88 @@
     while(gn!=s) if(visited.get(gn)==1)
       {
-        //FIXME: nonstandars. gcc extension!
+        //FIXME: nonstandard gcc extension!
         aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
         gn=G.tail(tree.get(gn));
       }
     else {
-      //FIXME: nonstandars. gcc extension!
+      //FIXME: nonstandard gcc extension!
       aug_val <?= f.get(tree.get(gn));
       gn=G.head(tree.get(gn));