Changeset 777:a82713ed19f3 in lemon-0.x for src/work/marci/augmenting_flow.h

Timestamp:

08/31/04 19:54:22 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

graph_wrapper.h is ready for hugo 0.2

File:

• src/work/marci/augmenting_flow.h (modified) (17 diffs)

src/work/marci/augmenting_flow.h

@@ -12 +12 @@
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
-#include <for_each_macros.h>
+//#include <for_each_macros.h>
 
 /// \file
@@ -1083 +1083 @@
     Num flowValue() const {
       Num a=0;
-      FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
-      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
+      for (InEdgeIt e(*g, t); e!=INVALID; ++e) a+=(*flow)[e];
+      for (OutEdgeIt e(*g, t); e!=INVALID; ++e) a-=(*flow)[e];
       return a;
       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
@@ -1122 +1122 @@
 
     //ReachedMap level(res_graph);
-    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+    for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     bfs.pushAndSetReached(s);
@@ -1133 +1133 @@
     //searching for augmenting path
     while ( !bfs.finished() ) {
-      ResGWOutEdgeIt e=bfs;
+      ResGWEdge e=bfs;
       if (e!=INVALID && bfs.isBNodeNewlyReached()) {
         Node v=res_graph.tail(e);
@@ -1170 +1170 @@
 
     if (status!=AFTER_FAST_AUGMENTING) {
-      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 
+      for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); 
       number_of_augmentations=1;
     } else {
@@ -1190 +1190 @@
     //searching for augmenting path
     while ( !bfs.finished() ) {
-      ResGWOutEdgeIt e=bfs;
+      ResGWEdge e=bfs;
       if (e!=INVALID && bfs.isBNodeNewlyReached()) {
         Node v=res_graph.tail(e);
@@ -1232 +1232 @@
     //bfs for distances on the residual graph
     //ReachedMap level(res_graph);
-    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+    for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     bfs.pushAndSetReached(s);
@@ -1256 +1256 @@
 
     while ( !bfs.finished() ) {
-      ResGWOutEdgeIt e=bfs;
+      ResGWEdge e=bfs;
       if (e!=INVALID) {
         if (bfs.isBNodeNewlyReached()) {
@@ -1297 +1297 @@
         if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
           if (dfs.isBNodeNewlyReached()) {
-            typename MG::Node v=F.aNode(dfs);
-            typename MG::Node w=F.bNode(dfs);
+            typename MG::Node v=F.tail(dfs);
+            typename MG::Node w=F.head(dfs);
             pred.set(w, dfs);
             if (pred[v]!=INVALID) {
@@ -1346 +1346 @@
 
     //ReachedMap level(res_graph);
-    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+    for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 
@@ -1352 +1352 @@
     DistanceMap<ResGW> dist(res_graph);
     while ( !bfs.finished() ) {
-      ResGWOutEdgeIt e=bfs;
+      ResGWEdge e=bfs;
       if (e!=INVALID && bfs.isBNodeNewlyReached()) {
         dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
@@ -1359 +1359 @@
     } //computing distances from s in the residual graph
 
-      //Subgraph containing the edges on some shortest paths
+    //Subgraph containing the edges on some shortest paths
     ConstMap<typename ResGW::Node, bool> true_map(true);
     typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
@@ -1367 +1367 @@
     //Subgraph, which is able to delete edges which are already
     //met by the dfs
-    typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
+    typename FilterResGW::template NodeMap<typename FilterResGW::Edge>
       first_out_edges(filter_res_graph);
     typename FilterResGW::NodeIt v;
     for(filter_res_graph.first(v); v!=INVALID; ++v)
       {
-        typename FilterResGW::OutEdgeIt e;
-        filter_res_graph.first(e, v);
-        first_out_edges.set(v, e);
+        typename FilterResGW::OutEdgeIt e;
+        filter_res_graph.first(e, v);
+        first_out_edges.set(v, e);
       }
     typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
-      template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
+      template NodeMap<typename FilterResGW::Edge> > ErasingResGW;
     ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
 
@@ -1390 +1390 @@
         dfs(erasing_res_graph);
       typename ErasingResGW::
-        template NodeMap<typename ErasingResGW::OutEdgeIt>
-        pred(erasing_res_graph);
+        template NodeMap<typename ErasingResGW::Edge> pred(erasing_res_graph);
       pred.set(s, INVALID);
       //invalid iterators for sources
@@ -1399 +1398 @@
 
       dfs.pushAndSetReached
-        ///\bug hugo 0.2
+        /// \bug hugo 0.2
         (typename ErasingResGW::Node
          (typename FilterResGW::Node
@@ -1406 +1405 @@
           )
          );
+        
       while (!dfs.finished()) {
         ++dfs;
-        if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
+        if (typename ErasingResGW::Edge(dfs)!=INVALID)
           {
             if (dfs.isBNodeNewlyReached()) {
 
-              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
-              typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
-
-              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
+              typename ErasingResGW::Node v=erasing_res_graph.tail(dfs);
+              typename ErasingResGW::Node w=erasing_res_graph.head(dfs);
+
+              pred.set(w, typename ErasingResGW::Edge(dfs));
               if (pred[v]!=INVALID) {
                 free1.set
                   (w, std::min(free1[v], res_graph.resCap
-                               (typename ErasingResGW::OutEdgeIt(dfs))));
+                               (typename ErasingResGW::Edge(dfs))));
               } else {
                 free1.set
                   (w, res_graph.resCap
-                   (typename ErasingResGW::OutEdgeIt(dfs)));
+                   (typename ErasingResGW::Edge(dfs)));
               }
 
@@ -1450 +1450 @@
         //        Num j2=a2[b2];
         Num augment_value=free1[n];
-        while (erasing_res_graph.valid(pred[n])) {
-          typename ErasingResGW::OutEdgeIt e=pred[n];
+        while (pred[n]!=INVALID) {
+          typename ErasingResGW::Edge e=pred[n];
           res_graph.augment(e, augment_value);
           n=erasing_res_graph.tail(e);