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

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

Files:

• hugo/graph_wrapper.h (modified) (5 diffs)
• work/marci/augmenting_flow.h (modified) (17 diffs)
• work/marci/bfs_dfs.h (modified) (19 diffs)
• work/marci/bfsit_vs_byhand.cc (modified) (2 diffs)
• work/marci/graph_wrapper_time.cc (modified) (4 diffs)
• work/marci/iterator_bfs_demo.cc (modified) (14 diffs)
• work/marci/lg_vs_sg_vs_sg.cc (modified) (11 diffs)
• work/marci/max_flow_demo.cc (modified) (3 diffs)

src/hugo/graph_wrapper.h

@@ -182 +182 @@
         Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
       EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
-        Edge(w), gw(&_gw) { }
+        Edge(e), gw(&_gw) { }
       EdgeIt& operator++() { 
         *(static_cast<Edge*>(this))=
@@ -429 +429 @@
       OutEdgeIt(Invalid i) : Edge(i) { }
       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 
-        Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
+        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
              const Edge& e) : 
@@ -451 +451 @@
       InEdgeIt(Invalid i) : Edge(i) { }
       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 
-        Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
+        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
              const Edge& e) : 
@@ -2041 +2041 @@
 //     };
     typedef typename GraphWrapper<Graph>::Edge Edge;
-    class OutEdgeIt { 
+    class OutEdgeIt : public Edge { 
       friend class GraphWrapper<Graph>;
       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
-      typename Graph::OutEdgeIt e;
+      const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
     public:
       OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
-                const Node& _n) : 
-        e((*_G.first_out_edges)[_n]) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
-      typename Graph::InEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
-               const Node& _n) : 
-        e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
+      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
+      OutEdgeIt(Invalid i) : Edge(i) { }
+      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, 
+                const Node& n) : 
+        Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
+      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, 
+                const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      OutEdgeIt& operator++() { 
+        *(static_cast<Edge*>(this))=
+          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+        return *this; 
+      }
+    };
+//     class InEdgeIt { 
+//       friend class GraphWrapper<Graph>;
+//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
+// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
+//       typename Graph::InEdgeIt e;
+//     public:
+//       InEdgeIt() { }
+//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
+//       InEdgeIt(const Invalid& i) : e(i) { }
+//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
+//             const Node& _n) : 
+//      e(*(_G.graph), typename Graph::Node(_n)) { }
+//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
+//     };       
     //typedef typename Graph::SymEdgeIt SymEdgeIt;
-    class EdgeIt { 
-      friend class GraphWrapper<Graph>;
-      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//      typedef typename Graph::EdgeIt GraphEdgeIt;
-      typename Graph::EdgeIt e;
-    public:
-      EdgeIt() { }
-      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
-      EdgeIt(const Invalid& i) : e(i) { }
-      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
-        e(*(_G.graph)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
+//     class EdgeIt { 
+//       friend class GraphWrapper<Graph>;
+//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
+// //      typedef typename Graph::EdgeIt GraphEdgeIt;
+//       typename Graph::EdgeIt e;
+//     public:
+//       EdgeIt() { }
+//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
+//       EdgeIt(const Invalid& i) : e(i) { }
+//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
+//      e(*(_G.graph)) { }
+//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
+//     };
 
     using GraphWrapper<Graph>::first;
@@ -2091 +2097 @@
       i=OutEdgeIt(*this, p); return i;
     }
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this); return i;
-    }
-
-    using GraphWrapper<Graph>::next;
-//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
-    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
-    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
+//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
+//       i=InEdgeIt(*this, p); return i;
+//     }
+//     EdgeIt& first(EdgeIt& i) const { 
+//       i=EdgeIt(*this); return i;
+//     }
+
+//     using GraphWrapper<Graph>::next;
+// //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
+//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
+//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
+//     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
     
-    Node aNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-
-    void erase(const OutEdgeIt& e) const {
-      OutEdgeIt f=e;
-      this->next(f);
-      first_out_edges->set(this->tail(e), f.e);
+//     Node aNode(const OutEdgeIt& e) const { 
+//       return Node(this->graph->aNode(e.e)); }
+//     Node aNode(const InEdgeIt& e) const { 
+//       return Node(this->graph->aNode(e.e)); }
+//     Node bNode(const OutEdgeIt& e) const { 
+//       return Node(this->graph->bNode(e.e)); }
+//     Node bNode(const InEdgeIt& e) const { 
+//       return Node(this->graph->bNode(e.e)); }
+
+    void erase(const Edge& e) const {
+      Node n=tail(e);
+      typename Graph::OutEdgeIt f(*graph, n);
+      ++f;
+      first_out_edges->set(n, f);
     }
   };

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;
+    }
+  }
 
   {