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

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

Location:

src/work/marci

Files:

• augmenting_flow.h (modified) (17 diffs)
• bfs_dfs.h (modified) (19 diffs)
• bfsit_vs_byhand.cc (modified) (2 diffs)
• graph_wrapper_time.cc (modified) (4 diffs)
• iterator_bfs_demo.cc (modified) (14 diffs)
• lg_vs_sg_vs_sg.cc (modified) (11 diffs)
• max_flow_demo.cc (modified) (3 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);

src/work/marci/bfs_dfs.h

@@ -28 +28 @@
   protected:
     typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     const Graph* graph;
@@ -33 +34 @@
     ReachedMap& reached;
     bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
+    Edge actual_edge;
     bool own_reached_map;
   public:
@@ -56 +57 @@
     /// and the first out-edge is processed.
     /// If the queue is not empty, then \c s is simply pushed.
-    void pushAndSetReached(Node s) { 
+    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 
       reached.set(s, true);
       if (bfs_queue.empty()) {
         bfs_queue.push(s);
-        graph->first(actual_edge, s);
+        actual_edge=OutEdgeIt(*graph, s);
+        //graph->first(actual_edge, s);
         if (actual_edge!=INVALID) { 
           Node w=graph->head(actual_edge);
@@ -74 +76 @@
         bfs_queue.push(s);
       }
+      return *this;
     }
     /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
@@ -80 +83 @@
     operator++() { 
       if (actual_edge!=INVALID) { 
-        ++actual_edge;
+        actual_edge=++OutEdgeIt(*graph, actual_edge);
+        //++actual_edge;
         if (actual_edge!=INVALID) {
           Node w=graph->head(actual_edge);
@@ -94 +98 @@
         bfs_queue.pop(); 
         if (!bfs_queue.empty()) {
-          graph->first(actual_edge, bfs_queue.front());
+          actual_edge=OutEdgeIt(*graph, bfs_queue.front());
+          //graph->first(actual_edge, bfs_queue.front());
           if (actual_edge!=INVALID) {
             Node w=graph->head(actual_edge);
@@ -114 +119 @@
     /// to an \c out-edge-iterator.
     ///\bug Edge have to be in HUGO 0.2
-    operator OutEdgeIt() const { return actual_edge; }
+    operator Edge() const { return actual_edge; }
     /// Returns if b-node has been reached just now.
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
@@ -120 +125 @@
     bool isANodeExamined() const { return actual_edge==INVALID; }
     /// Returns a-node of the actual edge, so does if the edge is invalid.
-    Node aNode() const { return bfs_queue.front(); }
+    Node tail() const { return bfs_queue.front(); }
     /// \pre The actual edge have to be valid.
-    Node bNode() const { return graph->bNode(actual_edge); }
+    Node head() const { return graph->head(actual_edge); }
     /// Guess what?
     /// \deprecated 
@@ -160 +165 @@
     /// in addition its pred is set to be \c INVALID, and dist to \c 0. 
     /// if \c s was marked previuosly, then it is simply pushed.
-    void push(Node s) { 
+    Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) { 
       if (this->reached[s]) {
         Parent::pushAndSetReached(s);
@@ -168 +173 @@
         dist.set(s, 0);
       }
+      return *this;
     }
     /// A bfs is processed from \c s.
-    void run(Node s) {
+    Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
       push(s);
       while (!this->finished()) this->operator++();
+      return *this;
     }
     /// Beside the bfs iteration, \c pred and \dist are saved in a 
@@ -180 +187 @@
       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
       {
-        pred.set(this->bNode(), this->actual_edge);
-        dist.set(this->bNode(), dist[this->aNode()]);
+        pred.set(this->head(), this->actual_edge);
+        dist.set(this->head(), dist[this->tail()]);
       }
       return *this;
@@ -202 +209 @@
   protected:
     typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     const Graph* graph;
     std::stack<OutEdgeIt> dfs_stack;
     bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
+    Edge actual_edge;
     Node actual_node;
     ReachedMap& reached;
@@ -225 +233 @@
     ~DfsIterator() { if (own_reached_map) delete &reached; }
     /// This method markes s reached and first out-edge is processed.
-    void pushAndSetReached(Node s) { 
+    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 
       actual_node=s;
       reached.set(s, true);
-      OutEdgeIt e;
-      graph->first(e, s);
+      OutEdgeIt e(*graph, s);
+      //graph->first(e, s);
       dfs_stack.push(e); 
+      return *this;
     }
     /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, 
@@ -237 +246 @@
     operator++() { 
       actual_edge=dfs_stack.top();
-      //actual_node=G.aNode(actual_edge);
       if (actual_edge!=INVALID/*.valid()*/) { 
         Node w=graph->head(actual_edge);
         actual_node=w;
         if (!reached[w]) {
-          OutEdgeIt e;
-          graph->first(e, w);
+          OutEdgeIt e(*graph, w);
+          //graph->first(e, w);
           dfs_stack.push(e);
           reached.set(w, true);
@@ -263 +271 @@
     /// to an \c out-edge-iterator.
     ///\bug Edge have to be in HUGO 0.2
-    operator OutEdgeIt() const { return actual_edge; }
+    operator Edge() const { return actual_edge; }
     /// Returns if b-node has been reached just now.
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
@@ -269 +277 @@
     bool isANodeExamined() const { return actual_edge==INVALID; }
     /// Returns a-node of the actual edge, so does if the edge is invalid.
-    Node aNode() const { return actual_node; /*FIXME*/}
+    Node tail() const { return actual_node; /*FIXME*/}
     /// Returns b-node of the actual edge. 
     /// \pre The actual edge have to be valid.
-    Node bNode() const { return graph->bNode(actual_edge); }
+    Node head() const { return graph->head(actual_edge); }
     /// Guess what?
     /// \deprecated
@@ -305 +313 @@
     /// in addition its pred is set to be \c INVALID. 
     /// if \c s was marked previuosly, then it is simply pushed.
-    void push(Node s) { 
+    Dfs<Graph, ReachedMap, PredMap>& push(Node s) { 
       if (this->reached[s]) {
         Parent::pushAndSetReached(s);
@@ -312 +320 @@
         pred.set(s, INVALID);
       }
+      return *this;
     }
     /// A bfs is processed from \c s.
-    void run(Node s) {
+    Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
       push(s);
       while (!this->finished()) this->operator++();
+      return *this;
     }
     /// Beside the dfs iteration, \c pred is saved in a 
@@ -324 +334 @@
       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
       {
-        pred.set(this->bNode(), this->actual_edge);
+        pred.set(this->head(), this->actual_edge);
       }
       return *this;

src/work/marci/bfsit_vs_byhand.cc

@@ -34 +34 @@
   cout << g.edgeNum() << endl;
 
-  Graph::NodeMap<OutEdgeIt> pred(g);
+  Graph::NodeMap<Edge> pred(g);
   cout << "iteration time of bfs written by hand..." << endl;
   Timer ts;
@@ -70 +70 @@
       ++bfs; 
       if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
-        pred.set(bfs.bNode(), bfs);
+        pred.set(bfs.head(), Graph::Edge(bfs));
     }
     std::cout << ts << std::endl;

src/work/marci/graph_wrapper_time.cc

@@ -1 +1 @@
 // -*- c++ -*-
+
+// Use a DIMACS max flow file as follows:
+// graph_wrapper_time dimacs_max_flow_file
 
 #include <iostream>
@@ -29 +32 @@
   Timer ts;
   ts.reset();
-  cout << g.nodeNum() << endl;
-  cout << g.edgeNum() << endl;
+
   typedef MaxFlow<Graph, int, FlowMap, FlowMap> MyMaxFlow;
   MyMaxFlow max_flow(g, s, t, cap, flow);
@@ -42 +44 @@
   typedef ListGraph Graph; 
   Graph g;
-//   cout << g.id(g.addNode()) << endl;
-//   cout << g.id(g.addNode()) << endl;
-//   cout << g.nodeNum() << endl;
   timeTest<Graph>(in, g);
   typedef GraphWrapper<Graph> Graph1;
   Graph1 g1(g);
-//   g1.clear();
-//   cout << g.id(g1.addNode()) << endl;
-//   cout << g.id(g1.addNode()) << endl;
-//   cout << g1.nodeNum() << endl;
-//   g1.clear();
   timeTest<Graph1>(in, g1);
   typedef GraphWrapper<Graph1> Graph2;
@@ -60 +54 @@
   Graph3 g3(g2);
   timeTest<Graph3>(in, g3);
-//   typedef GraphWrapper<Graph3> Graph4;
-//   Graph4 g4(g3);
-//   timeTest<Graph4>(in, g4);
-//   typedef GraphWrapper<Graph4> Graph5;
-//   Graph5 g5(g4);
-//   timeTest<Graph5>(in, g5);
-//   typedef GraphWrapper<Graph5> Graph6;
-//   Graph6 g6(g5);
-//   timeTest<Graph6>(in, g6);  
-//   typedef GraphWrapper<Graph6> Graph7;
-//   Graph7 g7(g6);
-//   timeTest<Graph7>(in, g7);
+  typedef GraphWrapper<Graph3> Graph4;
+  Graph4 g4(g3);
+  timeTest<Graph4>(in, g4);
+  typedef GraphWrapper<Graph4> Graph5;
+  Graph5 g5(g4);
+  timeTest<Graph5>(in, g5);
+  typedef GraphWrapper<Graph5> Graph6;
+  Graph6 g6(g5);
+  timeTest<Graph6>(in, g6);  
+  typedef GraphWrapper<Graph6> Graph7;
+  Graph7 g7(g6);
+  timeTest<Graph7>(in, g7);
 
   return 0;

src/work/marci/iterator_bfs_demo.cc

@@ -10 +10 @@
 
 using namespace hugo;
+
 using std::cout; 
 using std::endl;
@@ -73 +74 @@
   cout << "    \\-->    ------------->         "<< endl;
   
-//   typedef TrivGraphWrapper<const Graph> CGW;
-//   CGW gw(G);
-
-//   cout << "bfs and dfs demo on the directed graph" << endl;
-//   for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { 
-//     cout << n << ": ";
-//     cout << "out edges: ";
-//     for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 
-//       cout << e << " ";
-//     cout << "in edges: ";
-//     for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) 
-//       cout << e << " ";
-//     cout << endl;
-//   }
-
   {
     EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
@@ -108 +94 @@
     while (!bfs.finished()) {
       //cout << "edge: ";
-      if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
+      if (Graph::Edge(bfs)!=INVALID) {
         cout << edge_name[bfs] << /*endl*/", " << 
           node_name[G.tail(bfs)] << 
@@ -117 +103 @@
       } else { 
         cout << "invalid" << /*endl*/", " << 
-          node_name[bfs.aNode()] << 
+          node_name[bfs.tail()] << 
           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
           
@@ -142 +128 @@
       ++dfs;
       //cout << "edge: ";
-      if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
+      if (Graph::Edge(dfs)!=INVALID) {
         cout << edge_name[dfs] << /*endl*/", " << 
           node_name[G.tail(dfs)] << 
@@ -151 +137 @@
       } else { 
         cout << "invalid" << /*endl*/", " << 
-          node_name[dfs.aNode()] << 
+          node_name[dfs.tail()] << 
           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
           
@@ -184 +170 @@
     while (!bfs.finished()) {
       //cout << "edge: ";
-      if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
-        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
+      if (GW::Edge(bfs)!=INVALID) {
+        cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 
           node_name[gw.tail(bfs)] << 
           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
@@ -193 +179 @@
       } else { 
         cout << "invalid" << /*endl*/", " << 
-          node_name[bfs.aNode()] << 
+          node_name[bfs.tail()] << 
           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
           
@@ -218 +204 @@
       ++dfs;
       //cout << "edge: ";
-      if (GW::OutEdgeIt(dfs)!=INVALID) {
-        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
+      if (GW::Edge(dfs)!=INVALID) {
+        cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 
           node_name[gw.tail(dfs)] << 
           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
@@ -227 +213 @@
       } else { 
         cout << "invalid" << /*endl*/", " << 
-          node_name[dfs.aNode()] << 
+          node_name[dfs.tail()] << 
           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
           
@@ -347 +333 @@
     while (!bfs.finished()) {
       //cout << "edge: ";
-      if (GW::OutEdgeIt(bfs)!=INVALID) {
-        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
+      if (GW::Edge(bfs)!=INVALID) {
+        cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << 
           node_name[gw.tail(bfs)] << 
           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
@@ -356 +342 @@
       } else { 
         cout << "invalid" << /*endl*/", " << 
-          node_name[bfs.aNode()] << 
+          node_name[bfs.tail()] << 
           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
           
@@ -381 +367 @@
       ++dfs;
       //cout << "edge: ";
-      if (GW::OutEdgeIt(dfs)!=INVALID) {
-        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
+      if (GW::Edge(dfs)!=INVALID) {
+        cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << 
           node_name[gw.tail(dfs)] << 
           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
@@ -390 +376 @@
       } else { 
         cout << "invalid" << /*endl*/", " << 
-          node_name[dfs.aNode()] << 
+          node_name[dfs.tail()] << 
           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
           

src/work/marci/lg_vs_sg_vs_sg.cc

@@ -54 +54 @@
     {
       std::cout << "physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -76 +76 @@
     {
       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -87 +87 @@
     {
       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -122 +122 @@
     {
       std::cout << "preflow ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       max_flow_test.run();
@@ -131 +131 @@
     {
       std::cout << "physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -153 +153 @@
     {
       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -164 +164 @@
     {
       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -199 +199 @@
     {
       std::cout << "preflow ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       max_flow_test.run();
@@ -208 +208 @@
     {
       std::cout << "physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -230 +230 @@
     {
       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;
@@ -241 +241 @@
     {
       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
       ts.reset();
       int i=0;

src/work/marci/max_flow_demo.cc

@@ -1 +1 @@
 // -*- c++ -*-
+
+// Use a DIMACS max flow file as stdin.
+// max_flow_demo < dimacs_max_flow_file
+
+
 #include <iostream>
 #include <fstream>
@@ -15 +20 @@
 
 using namespace hugo;
-
-// Use a DIMACS max flow file as stdin.
-// max_flow_demo < dimacs_max_flow_file
 
 int main(int, char **) {
@@ -103 +105 @@
   }
 
-//   {
-//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
-//     ts.reset();
-//     int i=0;
-//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
-//     std::cout << "elapsed time: " << ts << std::endl;
-//     std::cout << "number of augmentation phases: " << i << std::endl; 
-//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
+  {
+    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+    ts.reset();
+    int i=0;
+    while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
 
-//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
-//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
-//      std::cout << "Slackness does not hold!" << std::endl;
-//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
-//      std::cout << "Slackness does not hold!" << std::endl;
-//     }
-//   }
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
+  }
 
   {