# HG changeset patch
# User marci
# Date 1081252834 0
# Node ID 6635b11938feeaaa570143bd714dbd3990c78f3d
# Parent  76c005b15354e551e651f6f8d5e78a8b66bed2e1
gw

diff -r 76c005b15354 -r 6635b11938fe src/work/jacint/makefile
--- a/src/work/jacint/makefile	Mon Apr 05 18:24:37 2004 +0000
+++ b/src/work/jacint/makefile	Tue Apr 06 12:00:34 2004 +0000
@@ -1,23 +1,29 @@
 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
 CXX2 = g++-2.95
-CXXFLAGS = -W -Wall -ansi -pedantic -O3 -I. -I.. -I../marci -I../alpar -I../../include  
+CXX=$(CXX3)
+CC=$(CXX)
+INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} 
+CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS) 
 LEDAROOT ?= /ledasrc/LEDA-4.1
 
-BINARIES = dijkstra prim preflow
+BINARIES = preflow #dijkstra prim
 
 all: $(BINARIES)
 
+.depend dep depend:
+	-$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
+
 makefile: .depend
 sinclude .depend
 
-preflow: 
-	$(CXX3) $(CXXFLAGS)  -o preflow preflow.cc 
-
-dijkstra: 
-	$(CXX3) $(CXXFLAGS)  -o dijkstra dijkstra.cc
-
-prim: 
-	$(CXX3) $(CXXFLAGS)  -o prim prim.cc
+#preflow: 
+#	$(CXX3) $(CXXFLAGS)  -o preflow preflow.cc 
+#
+#dijkstra: 
+#	$(CXX3) $(CXXFLAGS)  -o dijkstra dijkstra.cc
+#
+#prim: 
+#	$(CXX3) $(CXXFLAGS)  -o prim prim.cc
 
 clean:
 	$(RM) *.o $(BINARIES) .depend
diff -r 76c005b15354 -r 6635b11938fe src/work/marci/edmonds_karp.h
--- a/src/work/marci/edmonds_karp.h	Mon Apr 05 18:24:37 2004 +0000
+++ b/src/work/marci/edmonds_karp.h	Tue Apr 06 12:00:34 2004 +0000
@@ -9,6 +9,7 @@
 #include <bfs_iterator.h>
 #include <invalid.h>
 #include <graph_wrapper.h>
+#include <maps.h>
 
 namespace hugo {
 
@@ -353,8 +354,10 @@
       } //computing distances from s in the residual graph
 
       MG F;
-      typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
-      FilterResGW filter_res_graph(res_graph, dist);
+      ConstMap<typename ResGW::Node, bool> true_map(true);
+      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 
+	DistanceMap<ResGW> > FilterResGW;
+      FilterResGW filter_res_graph(res_graph, true_map, dist);
       typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
       {
 	typename ResGW::NodeIt n;
@@ -567,8 +570,10 @@
       } //computing distances from s in the residual graph
 
       //Subgraph containing the edges on some shortest paths
-      typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
-      FilterResGW filter_res_graph(res_graph, dist);
+      ConstMap<typename ResGW::Node, bool> true_map(true);
+      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 
+	DistanceMap<ResGW> > FilterResGW;
+      FilterResGW filter_res_graph(res_graph, true_map, dist);
 
       //Subgraph, which is able to delete edges which are already 
       //met by the dfs
@@ -591,16 +596,16 @@
       while (__augment) {
 
  	__augment=false;
- 	//computing blocking flow with dfs
+  	//computing blocking flow with dfs
 	typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
- 	DfsIterator5< ErasingResGW, BlockingReachedMap > 
- 	  dfs(erasing_res_graph);
+  	DfsIterator5< ErasingResGW, BlockingReachedMap > 
+  	  dfs(erasing_res_graph);
  	typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> 
  	  pred(erasing_res_graph); 
  	pred.set(s, INVALID);
- 	//invalid iterators for sources
+  	//invalid iterators for sources
 
- 	typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
+  	typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
 
  	dfs.pushAndSetReached(s);
  	while (!dfs.finished()) {
@@ -608,7 +613,7 @@
  	  if (erasing_res_graph.valid(
  		/*typename ErasingResGW::OutEdgeIt*/(dfs))) 
  	  { 
- 	    if (dfs.isBNodeNewlyReached()) {
+  	    if (dfs.isBNodeNewlyReached()) {
 	  
  	      typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
  	      typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
@@ -625,14 +630,14 @@
  		_augment=true;
  		break; 
  	      }
-	    } else {
-	      erasing_res_graph.erase(dfs);
+ 	    } else {
+ 	      erasing_res_graph.erase(dfs);
 	    }
 	  }
 	}	
 
- 	if (__augment) {
- 	  typename ErasingResGW::Node n=t;
+  	if (__augment) {
+  	  typename ErasingResGW::Node n=t;
  	  Number augment_value=free[n];
  	  while (erasing_res_graph.valid(pred[n])) { 
  	    typename ErasingResGW::OutEdgeIt e=pred[n];
@@ -640,8 +645,8 @@
  	    n=erasing_res_graph.tail(e);
  	    if (res_graph.resCap(e)==0)
  	      erasing_res_graph.erase(e);
- 	  }
- 	}
+	}
+      }
       
       } //while (__augment) 
             
diff -r 76c005b15354 -r 6635b11938fe src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc	Mon Apr 05 18:24:37 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc	Tue Apr 06 12:00:34 2004 +0000
@@ -8,11 +8,7 @@
 #include <edmonds_karp.h>
 #include <time_measure.h>
 //#include <graph_wrapper.h>
-
-class CM {
-public:
-  template<typename T> int get(T) const {return 1;}
-};
+#include <preflow.h>
 
 using namespace hugo;
 
@@ -88,9 +84,37 @@
 //   //cgw.erase(csw);
 //   std::cout << "p2:" << cgw.nodeNum() << std::endl;
 
+  {
+    std::cout << "preflow ..." << std::endl;
+    Graph::EdgeMap<int> flow(G); //0 flow
+
+    Timer ts;
+    ts.reset();
+
+    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+      max_flow_test(G, s, t, cap, flow);
+    max_flow_test.run();
+//    int i=0;
+//    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
+//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+//      ++i; 
+//    }
+
+//   std::cout << "maximum flow: "<< std::endl;
+//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
+//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//   }
+//   std::cout<<std::endl;
+    std::cout << "elapsed time: " << ts << std::endl;
+//    std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
 
   {
-    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
+    std::cout << "physical blocking flow augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
     Timer ts;
@@ -118,7 +142,7 @@
   }
 
   {
-    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
+    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
     Timer ts;
@@ -146,7 +170,7 @@
   }
 
   {
-    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
+    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
     Timer ts;
@@ -174,7 +198,7 @@
   }
 
   {
-    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
+    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
     Timer ts;
diff -r 76c005b15354 -r 6635b11938fe src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Mon Apr 05 18:24:37 2004 +0000
+++ b/src/work/marci/graph_wrapper.h	Tue Apr 06 12:00:34 2004 +0000
@@ -12,6 +12,7 @@
     Graph* graph;
   
   public:
+//    typedef Graph BaseGraph;
     typedef Graph ParentGraph;
 
 //     TrivGraphWrapper() : graph(0) { }
@@ -24,9 +25,13 @@
     public:
       NodeIt() { }
       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
+//      NodeIt(const typename BaseGraph::NodeIt& n) : Graph::NodeIt(n) { }
       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
       NodeIt(const TrivGraphWrapper<Graph>& _G) : 
 	Graph::NodeIt(*(_G.graph)) { }
+//      operator typename BaseGraph::NodeIt() { 
+//	return typename BaseGraph::NodeIt(this->Graph::NodeIt);
+//      }
     };
     typedef typename Graph::Edge Edge;
     class OutEdgeIt : public Graph::OutEdgeIt { 
@@ -59,10 +64,6 @@
       i=NodeIt(*this);
       return i;
     }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this);
-      return i;
-    }
 //     template<typename I> I& first(I& i) const { 
 //       i=I(*this);
 //       return i;
@@ -75,6 +76,10 @@
       i=InEdgeIt(*this, p);
       return i;
     }
+    EdgeIt& first(EdgeIt& i) const { 
+      i=EdgeIt(*this);
+      return i;
+    }
 //     template<typename I, typename P> I& first(I& i, const P& p) const { 
 //       i=I(*this, p);
 //       return i;
@@ -82,7 +87,11 @@
     
 //    template<typename I> I getNext(const I& i) const { 
 //      return graph->getNext(i); }
-    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
+//    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
+    NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
+    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
+    InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
+    EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
 
     template< typename It > It first() const { 
       It e; this->first(e); return e; }
@@ -157,6 +166,7 @@
     Graph* graph;
   
   public:
+    typedef Graph BaseGraph;
     typedef Graph ParentGraph;
 
 //     GraphWrapper() : graph(0) { }
@@ -204,10 +214,6 @@
       i=NodeIt(*this);
       return i;
     }
-    EdgeIt& first(EdgeIt& i) const { 
-      i=EdgeIt(*this);
-      return i;
-    }
 //     template<typename I> I& first(I& i) const {       
 //       i=I(*this);
 //       return i;
@@ -220,6 +226,10 @@
       i=InEdgeIt(*this, p);
       return i;
     }
+    EdgeIt& first(EdgeIt& i) const { 
+      i=EdgeIt(*this);
+      return i;
+    }
 //     template<typename I, typename P> I& first(I& i, const P& p) const { 
 //       i=I(*this, p);
 //       return i; 
@@ -227,7 +237,11 @@
     
 //    template<typename I> I getNext(const I& i) const { 
 //      return gw.getNext(i); }
-    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
+//    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
+    NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
+    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
+    InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
+    EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }    
 
     template< typename It > It first() const { 
       It e; this->first(e); return e; }
@@ -385,44 +399,138 @@
   };
 
   //Subgraph on the same node-set and partial edge-set
-  template<typename Graph, typename EdgeFilterMap>
+  template<typename Graph, typename NodeFilterMap, 
+	   typename EdgeFilterMap>
   class SubGraphWrapper : public GraphWrapper<Graph> {
   protected:
-    EdgeFilterMap* filter_map;
+    NodeFilterMap* node_filter_map;
+    EdgeFilterMap* edge_filter_map;
   public:
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
-    typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
-    typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
+//     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
+    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
+		    EdgeFilterMap& _edge_filter_map) : 
+      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
+      edge_filter_map(&_edge_filter_map) { }  
 
-//     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
-    SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) : 
-      GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }  
 
-    template<typename I> I& first(I& i) const { 
-      graph->first(i); 
-      //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
-      while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
+    typedef typename Graph::Node Node;
+    class NodeIt : public Graph::NodeIt { 
+//      typedef typename Graph::NodeIt GraphNodeIt;
+    public:
+      NodeIt() { }
+      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
+      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
+      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
+	Graph::NodeIt(*(_G.graph)) { 
+	while (_G.graph->valid((*this)/*.GraphNodeIt*/) && 
+	       !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 
+	  _G.graph->next((*this)/*.GraphNodeIt*/);
+      }
+    };
+    typedef typename Graph::Edge Edge;
+    class OutEdgeIt : public Graph::OutEdgeIt { 
+//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
+      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
+      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 
+		_G, const Node& n) : 
+	Graph::OutEdgeIt(*(_G.graph), n) { 
+	while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && 
+	       !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 
+	  _G.graph->next((*this)/*.GraphOutEdgeIt*/);
+      }
+    };
+    class InEdgeIt : public Graph::InEdgeIt { 
+//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
+    public:
+      InEdgeIt() { }
+      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
+      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
+      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
+	       const Node& n) : 
+	Graph::InEdgeIt(*(_G.graph), n) { 
+	while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && 
+	       !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 
+	  _G.graph->next((*this)/*.GraphInEdgeIt*/);
+      }
+    };
+//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    class EdgeIt : public Graph::EdgeIt { 
+//      typedef typename Graph::EdgeIt GraphEdgeIt;
+    public:
+      EdgeIt() { }
+      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
+      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
+      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
+	Graph::EdgeIt(*(_G.graph)) { 
+	while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && 
+	       !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 
+	  _G.graph->next((*this)/*.GraphEdgeIt*/);
+      }
+    };
+   
+    NodeIt& first(NodeIt& i) const {
+      i=NodeIt(*this);
       return i;
     }
-    template<typename I, typename P> I& first(I& i, const P& p) const { 
-      graph->first(i, p); 
-//      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
-      while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
+    OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
+      i=OutEdgeIt(*this, n);
+      return i;
+    }
+    InEdgeIt& first(InEdgeIt& i, const Node& n) const {
+      i=InEdgeIt(*this, n);
+      return i;
+    }
+    EdgeIt& first(EdgeIt& i) const {
+      i=EdgeIt(*this);
       return i;
     }
     
+//     template<typename I> I& first(I& i) const { 
+//       graph->first(i); 
+//       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
+//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
+//       return i;
+//     }
+//     template<typename I, typename P> I& first(I& i, const P& p) const { 
+//       graph->first(i, p); 
+// //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
+//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
+//       return i;
+//     }
+
+    NodeIt& next(NodeIt& i) const {
+      graph->next(i); 
+      while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
+      return i;
+    }
+    OutEdgeIt& next(OutEdgeIt& i) const {
+      graph->next(i); 
+      while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
+      return i;
+    }
+    InEdgeIt& next(InEdgeIt& i) const {
+      graph->next(i); 
+      while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
+      return i;
+    }
+    EdgeIt& next(EdgeIt& i) const {
+      graph->next(i); 
+      while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
+      return i;
+    }
+
     //template<typename I> I getNext(const I& i) const { 
     //  return gw.getNext(i); 
     //}
-    template<typename I> I& next(I &i) const { 
-      graph->next(i); 
-//      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
-      while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
-      return i;
-    }
+//     template<typename I> I& next(I &i) const { 
+//       graph->next(i); 
+// //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
+//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
+//       return i;
+//     }
     
     template< typename It > It first() const { 
       It e; this->first(e); return e; }
@@ -844,10 +952,7 @@
 
 
   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-  class ResGraphWrapper : public GraphWrapper<Graph>{
-  public:
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+  class ResGraphWrapper : public GraphWrapper<Graph> {
   protected:
     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     typedef typename Graph::InEdgeIt GraphInEdgeIt;
@@ -865,6 +970,8 @@
     friend class Edge; 
     friend class OutEdgeIt; 
 
+    typedef typename GraphWrapper<Graph>::Node Node;
+    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     class Edge {
       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     protected:
@@ -892,8 +999,6 @@
 	if (out_or_in) return(out); else return(in);
       }
     };
-
-
     class OutEdgeIt : public Edge {
       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     public:
@@ -930,7 +1035,7 @@
     };
 
     //FIXME This is just for having InEdgeIt
-    typedef void InEdgeIt;
+//    class InEdgeIt : public Edge { };
 
     class EdgeIt : public Edge {
       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
@@ -993,18 +1098,25 @@
 //       }
     };
 
-    NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
-    OutEdgeIt& first(OutEdgeIt& e, Node v) const { 
-      e=OutEdgeIt(*this, v); 
-      return e;
+    NodeIt& first(NodeIt& i) const { 
+      i=NodeIt(*this); 
+      return i; 
     }
+    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
+      i=OutEdgeIt(*this, p);
+      return i;
+    }
+    //FIXME Not yet implemented
+    //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
+    //i=InEdgeIt(*this, p);
+    //  return i;
+    //}
     EdgeIt& first(EdgeIt& e) const { 
       e=EdgeIt(*this); 
       return e;
     }
    
     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
-
     OutEdgeIt& next(OutEdgeIt& e) const { 
       if (e.out_or_in) {
 	Node v=graph->aNode(e.out);
@@ -1021,7 +1133,10 @@
       }
       return e;
     }
-
+    //FIXME Not yet implemented
+    //InEdgeIt& next(InEdgeIt& e) const {
+    //  return e;
+    //}
     EdgeIt& next(EdgeIt& e) const { 
       if (e.out_or_in) {
 	graph->next(e.out);
@@ -1169,38 +1284,106 @@
   protected:
     FirstOutEdgesMap* first_out_edges;
   public:
-    typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-    typedef typename GraphWrapper<Graph>::Edge Edge;
-    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
-    typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
-    typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
-
     ErasingFirstGraphWrapper(Graph& _graph, 
 			     FirstOutEdgesMap& _first_out_edges) : 
       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
 
-    template<typename I> I& first(I& i) const { 
-      graph->first(i); 
+    typedef typename Graph::Node Node;
+    class NodeIt : public Graph::NodeIt { 
+    public:
+      NodeIt() { }
+      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
+      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
+      NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
+	Graph::NodeIt(*(_G.graph)) { }
+    };
+    typedef typename Graph::Edge Edge;
+    class OutEdgeIt : public Graph::OutEdgeIt { 
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
+      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
+      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
+		const Node& n) : 
+	Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
+    };
+    class InEdgeIt : public Graph::InEdgeIt { 
+    public:
+      InEdgeIt() { }
+      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
+      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
+      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
+	       const Node& n) : 
+	Graph::InEdgeIt(*(_G.graph), n) { }
+    };
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    class EdgeIt : public Graph::EdgeIt { 
+    public:
+      EdgeIt() { }
+      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
+      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
+      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
+	Graph::EdgeIt(*(_G.graph)) { }
+    };
+
+    NodeIt& first(NodeIt& i) const {
+      i=NodeIt(*this);
       return i;
     }
-    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
-//      e=first_out_edges->get(n);
-      e=(*first_out_edges)[n];
-      return e;
-    }
-    template<typename I, typename P> I& first(I& i, const P& p) const { 
-      graph->first(i, p); 
+    OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
+      i=OutEdgeIt(*this, n);
+//      i=(*first_out_edges)[n];
       return i;
     }
+    InEdgeIt& first(InEdgeIt& i, const Node& n) const {
+      i=InEdgeIt(*this, n);
+      return i;
+    }
+    EdgeIt& first(EdgeIt& i) const {
+      i=EdgeIt(*this);
+      return i;
+    }
+
+//     template<typename I> I& first(I& i) const { 
+//       graph->first(i); 
+//       return i;
+//     }
+//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
+// //      e=first_out_edges->get(n);
+//       e=(*first_out_edges)[n];
+//       return e;
+//     }
+//     template<typename I, typename P> I& first(I& i, const P& p) const { 
+//       graph->first(i, p); 
+//       return i;
+//     }
     
     //template<typename I> I getNext(const I& i) const { 
     //  return gw.getNext(i); 
     //}
-    template<typename I> I& next(I &i) const { 
+
+
+    NodeIt& next(NodeIt& i) const {
       graph->next(i); 
       return i;
     }
+    OutEdgeIt& next(OutEdgeIt& i) const {
+      graph->next(i); 
+      return i;
+    }
+    InEdgeIt& next(InEdgeIt& i) const {
+      graph->next(i); 
+      return i;
+    }
+    EdgeIt& next(EdgeIt& i) const {
+      graph->next(i); 
+      return i;
+    }
+
+//     template<typename I> I& next(I &i) const { 
+//       graph->next(i); 
+//       return i;
+//     }
     
     template< typename It > It first() const { 
       It e; this->first(e); return e; }