# HG changeset patch
# User marci
# Date 1080207779 0
# Node ID a85fd87460e35d9db69201ba16b3730747aa106f
# Parent  b255f25ad394f4505ca1fc47303e164c43aeb6a1
.

diff -r b255f25ad394 -r a85fd87460e3 src/work/bfs_iterator.h
--- a/src/work/bfs_iterator.h	Wed Mar 24 13:06:06 2004 +0000
+++ b/src/work/bfs_iterator.h	Thu Mar 25 09:42:59 2004 +0000
@@ -9,47 +9,47 @@
 
 namespace hugo {
 
-  template <typename Graph>
-  struct bfs {
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    Graph& G;
-    Node s;
-    typename Graph::NodeMap<bool> reached;
-    typename Graph::NodeMap<Edge> pred;
-    typename Graph::NodeMap<int> dist;
-    std::queue<Node> bfs_queue;
-    bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
-      bfs_queue.push(s); 
-      for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) 
-	reached.set(i, false);
-      reached.set(s, true);
-      dist.set(s, 0); 
-    }
+//   template <typename Graph>
+//   struct bfs {
+//     typedef typename Graph::Node Node;
+//     typedef typename Graph::Edge Edge;
+//     typedef typename Graph::NodeIt NodeIt;
+//     typedef typename Graph::OutEdgeIt OutEdgeIt;
+//     Graph& G;
+//     Node s;
+//     typename Graph::NodeMap<bool> reached;
+//     typename Graph::NodeMap<Edge> pred;
+//     typename Graph::NodeMap<int> dist;
+//     std::queue<Node> bfs_queue;
+//     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
+//       bfs_queue.push(s); 
+//       for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) 
+// 	reached.set(i, false);
+//       reached.set(s, true);
+//       dist.set(s, 0); 
+//     }
     
-    void run() {
-      while (!bfs_queue.empty()) {
-	Node v=bfs_queue.front();
-	OutEdgeIt e=G.template first<OutEdgeIt>(v);
-	bfs_queue.pop();
-	for( ; e.valid(); ++e) {
-	  Node w=G.bNode(e);
-	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
-	  if (!reached.get(w)) {
-	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
-	    bfs_queue.push(w);
-	    dist.set(w, dist.get(v)+1);
-	    pred.set(w, e);
-	    reached.set(w, true);
-	  } else {
-	    std::cout << G.id(w) << " is already reached" << std::endl;
-	  }
-	}
-      }
-    }
-  };
+//     void run() {
+//       while (!bfs_queue.empty()) {
+// 	Node v=bfs_queue.front();
+// 	OutEdgeIt e=G.template first<OutEdgeIt>(v);
+// 	bfs_queue.pop();
+// 	for( ; e.valid(); ++e) {
+// 	  Node w=G.bNode(e);
+// 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
+// 	  if (!reached.get(w)) {
+// 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
+// 	    bfs_queue.push(w);
+// 	    dist.set(w, dist.get(v)+1);
+// 	    pred.set(w, e);
+// 	    reached.set(w, true);
+// 	  } else {
+// 	    std::cout << G.id(w) << " is already reached" << std::endl;
+// 	  }
+// 	}
+//       }
+//     }
+//   };
 
 //   template <typename Graph> 
 //   struct bfs_visitor {
@@ -544,90 +544,90 @@
 //  };
 
 
-  template <typename Graph, typename OutEdgeIt, 
-	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
-  class BfsIterator4 {
-    typedef typename Graph::Node Node;
-    const Graph& G;
-    std::queue<Node> bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    bool own_reached_map;
-  public:
-    BfsIterator4(const Graph& _G, ReachedMap& _reached) : 
-      G(_G), reached(_reached), 
-      own_reached_map(false) { }
-    BfsIterator4(const Graph& _G) : 
-      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
-      own_reached_map(true) { }
-    ~BfsIterator4() { if (own_reached_map) delete &reached; }
-    void pushAndSetReached(Node s) { 
-      //std::cout << "mimi" << &reached << std::endl;
-      reached.set(s, true);
-      //std::cout << "mumus" << std::endl;
-      if (bfs_queue.empty()) {
-	//std::cout << "bibi1" << std::endl;
-	bfs_queue.push(s);
-	//std::cout << "zizi" << std::endl;
-	G./*getF*/first(actual_edge, s);
-	//std::cout << "kiki" << std::endl;
-	if (G.valid(actual_edge)/*.valid()*/) { 
-	  Node w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(w);
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	} 
-      } else {
-	//std::cout << "bibi2" << std::endl;
-	bfs_queue.push(s);
-      }
-    }
-    BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
-    operator++() { 
-      if (G.valid(actual_edge)/*.valid()*/) { 
-	/*++*/G.next(actual_edge);
-	if (G.valid(actual_edge)/*.valid()*/) {
-	  Node w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(w);
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      } else {
-	bfs_queue.pop(); 
-	if (!bfs_queue.empty()) {
-	  G./*getF*/first(actual_edge, bfs_queue.front());
-	  if (G.valid(actual_edge)/*.valid()*/) {
-	    Node w=G.bNode(actual_edge);
-	    if (!reached.get(w)) {
-	      bfs_queue.push(w);
-	      reached.set(w, true);
-	      b_node_newly_reached=true;
-	    } else {
-	      b_node_newly_reached=false;
-	    }
-	  }
-	}
-      }
-      return *this;
-    }
-    bool finished() const { return bfs_queue.empty(); }
-    operator OutEdgeIt () const { return actual_edge; }
-    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
-    Node aNode() const { return bfs_queue.front(); }
-    Node bNode() const { return G.bNode(actual_edge); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
- };  
+//   template <typename Graph, typename OutEdgeIt, 
+// 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
+//   class BfsIterator4 {
+//     typedef typename Graph::Node Node;
+//     const Graph& G;
+//     std::queue<Node> bfs_queue;
+//     ReachedMap& reached;
+//     bool b_node_newly_reached;
+//     OutEdgeIt actual_edge;
+//     bool own_reached_map;
+//   public:
+//     BfsIterator4(const Graph& _G, ReachedMap& _reached) : 
+//       G(_G), reached(_reached), 
+//       own_reached_map(false) { }
+//     BfsIterator4(const Graph& _G) : 
+//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+//       own_reached_map(true) { }
+//     ~BfsIterator4() { if (own_reached_map) delete &reached; }
+//     void pushAndSetReached(Node s) { 
+//       //std::cout << "mimi" << &reached << std::endl;
+//       reached.set(s, true);
+//       //std::cout << "mumus" << std::endl;
+//       if (bfs_queue.empty()) {
+// 	//std::cout << "bibi1" << std::endl;
+// 	bfs_queue.push(s);
+// 	//std::cout << "zizi" << std::endl;
+// 	G./*getF*/first(actual_edge, s);
+// 	//std::cout << "kiki" << std::endl;
+// 	if (G.valid(actual_edge)/*.valid()*/) { 
+// 	  Node w=G.bNode(actual_edge);
+// 	  if (!reached.get(w)) {
+// 	    bfs_queue.push(w);
+// 	    reached.set(w, true);
+// 	    b_node_newly_reached=true;
+// 	  } else {
+// 	    b_node_newly_reached=false;
+// 	  }
+// 	} 
+//       } else {
+// 	//std::cout << "bibi2" << std::endl;
+// 	bfs_queue.push(s);
+//       }
+//     }
+//     BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
+//     operator++() { 
+//       if (G.valid(actual_edge)/*.valid()*/) { 
+// 	/*++*/G.next(actual_edge);
+// 	if (G.valid(actual_edge)/*.valid()*/) {
+// 	  Node w=G.bNode(actual_edge);
+// 	  if (!reached.get(w)) {
+// 	    bfs_queue.push(w);
+// 	    reached.set(w, true);
+// 	    b_node_newly_reached=true;
+// 	  } else {
+// 	    b_node_newly_reached=false;
+// 	  }
+// 	}
+//       } else {
+// 	bfs_queue.pop(); 
+// 	if (!bfs_queue.empty()) {
+// 	  G./*getF*/first(actual_edge, bfs_queue.front());
+// 	  if (G.valid(actual_edge)/*.valid()*/) {
+// 	    Node w=G.bNode(actual_edge);
+// 	    if (!reached.get(w)) {
+// 	      bfs_queue.push(w);
+// 	      reached.set(w, true);
+// 	      b_node_newly_reached=true;
+// 	    } else {
+// 	      b_node_newly_reached=false;
+// 	    }
+// 	  }
+// 	}
+//       }
+//       return *this;
+//     }
+//     bool finished() const { return bfs_queue.empty(); }
+//     operator OutEdgeIt () const { return actual_edge; }
+//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+//     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
+//     Node aNode() const { return bfs_queue.front(); }
+//     Node bNode() const { return G.bNode(actual_edge); }
+//     const ReachedMap& getReachedMap() const { return reached; }
+//     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
+//  };  
 
 
   template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
@@ -717,61 +717,61 @@
     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
   };  
 
-  template <typename Graph, typename OutEdgeIt, 
-	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
-  class DfsIterator4 {
-    typedef typename Graph::Node Node;
-    const Graph& G;
-    std::stack<OutEdgeIt> dfs_stack;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    Node actual_node;
-    ReachedMap& reached;
-    bool own_reached_map;
-  public:
-    DfsIterator4(const Graph& _G, ReachedMap& _reached) : 
-      G(_G), reached(_reached), 
-      own_reached_map(false) { }
-    DfsIterator4(const Graph& _G) : 
-      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
-      own_reached_map(true) { }
-    ~DfsIterator4() { if (own_reached_map) delete &reached; }
-    void pushAndSetReached(Node s) { 
-      actual_node=s;
-      reached.set(s, true);
-      dfs_stack.push(G.template first<OutEdgeIt>(s)); 
-    }
-    DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
-    operator++() { 
-      actual_edge=dfs_stack.top();
-      //actual_node=G.aNode(actual_edge);
-      if (G.valid(actual_edge)/*.valid()*/) { 
-	Node w=G.bNode(actual_edge);
-	actual_node=w;
-	if (!reached.get(w)) {
-	  dfs_stack.push(G.template first<OutEdgeIt>(w));
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  actual_node=G.aNode(actual_edge);
-	  /*++*/G.next(dfs_stack.top());
-	  b_node_newly_reached=false;
-	}
-      } else {
-	//actual_node=G.aNode(dfs_stack.top());
-	dfs_stack.pop();
-      }
-      return *this;
-    }
-    bool finished() const { return dfs_stack.empty(); }
-    operator OutEdgeIt () const { return actual_edge; }
-    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
-    Node aNode() const { return actual_node; /*FIXME*/}
-    Node bNode() const { return G.bNode(actual_edge); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
-  };
+//   template <typename Graph, typename OutEdgeIt, 
+// 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
+//   class DfsIterator4 {
+//     typedef typename Graph::Node Node;
+//     const Graph& G;
+//     std::stack<OutEdgeIt> dfs_stack;
+//     bool b_node_newly_reached;
+//     OutEdgeIt actual_edge;
+//     Node actual_node;
+//     ReachedMap& reached;
+//     bool own_reached_map;
+//   public:
+//     DfsIterator4(const Graph& _G, ReachedMap& _reached) : 
+//       G(_G), reached(_reached), 
+//       own_reached_map(false) { }
+//     DfsIterator4(const Graph& _G) : 
+//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+//       own_reached_map(true) { }
+//     ~DfsIterator4() { if (own_reached_map) delete &reached; }
+//     void pushAndSetReached(Node s) { 
+//       actual_node=s;
+//       reached.set(s, true);
+//       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
+//     }
+//     DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
+//     operator++() { 
+//       actual_edge=dfs_stack.top();
+//       //actual_node=G.aNode(actual_edge);
+//       if (G.valid(actual_edge)/*.valid()*/) { 
+// 	Node w=G.bNode(actual_edge);
+// 	actual_node=w;
+// 	if (!reached.get(w)) {
+// 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
+// 	  reached.set(w, true);
+// 	  b_node_newly_reached=true;
+// 	} else {
+// 	  actual_node=G.aNode(actual_edge);
+// 	  /*++*/G.next(dfs_stack.top());
+// 	  b_node_newly_reached=false;
+// 	}
+//       } else {
+// 	//actual_node=G.aNode(dfs_stack.top());
+// 	dfs_stack.pop();
+//       }
+//       return *this;
+//     }
+//     bool finished() const { return dfs_stack.empty(); }
+//     operator OutEdgeIt () const { return actual_edge; }
+//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+//     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
+//     Node aNode() const { return actual_node; /*FIXME*/}
+//     Node bNode() const { return G.bNode(actual_edge); }
+//     const ReachedMap& getReachedMap() const { return reached; }
+//     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
+//   };
 
   template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
diff -r b255f25ad394 -r a85fd87460e3 src/work/edmonds_karp.h
--- a/src/work/edmonds_karp.h	Wed Mar 24 13:06:06 2004 +0000
+++ b/src/work/edmonds_karp.h	Thu Mar 25 09:42:59 2004 +0000
@@ -319,7 +319,7 @@
       AugGraph res_graph(*G, *flow, *capacity);
 
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
+      BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
 
       bfs.pushAndSetReached(s);
       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
@@ -362,8 +362,8 @@
       while (__augment) {
 	__augment=false;
 	//computing blocking flow with dfs
-	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
-	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
+	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
+	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
 	pred.set(sF, typename MutableGraph::Edge(INVALID));
 	//invalid iterators for sources
@@ -420,7 +420,7 @@
 
       //bfs for distances on the residual graph
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
+      BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
       bfs.pushAndSetReached(s);
       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
 
@@ -465,8 +465,8 @@
       while (__augment) {
 	__augment=false;
 	//computing blocking flow with dfs
-	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
-	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
+	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
+	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
 	pred.set(sF, typename MutableGraph::Edge(INVALID));
 	//invalid iterators for sources
@@ -527,9 +527,9 @@
       EAugGraph res_graph(*G, *flow, *capacity);
 
       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator4< 
+      BfsIterator5< 
 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
-	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
+	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 
 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
       
       bfs.pushAndSetReached(s);
@@ -552,7 +552,7 @@
 	__augment=false;
 	//computing blocking flow with dfs
 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
-	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
+	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 
 	  dfs(res_graph);
 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 
 	pred.set(s, EAugEdge(INVALID));
@@ -854,9 +854,9 @@
       EAugGraph res_graph(*G, *flow, *capacity);
 
       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator4< 
+      BfsIterator5< 
 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
-	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
+	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 
 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
 
 
@@ -894,7 +894,7 @@
 	__augment=false;
 	//computing blocking flow with dfs
 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
-	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
+	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 
 	  dfs(res_graph);
 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 
 	//pred.set(s, EAugEdge(INVALID));
diff -r b255f25ad394 -r a85fd87460e3 src/work/makefile
--- a/src/work/makefile	Wed Mar 24 13:06:06 2004 +0000
+++ b/src/work/makefile	Thu Mar 25 09:42:59 2004 +0000
@@ -1,7 +1,7 @@
 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
 CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
 
-BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_demo
+BINARIES ?= bin_heap_demo iterator_bfs_demo
 
 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
 # ismert rendszeren :-)  (Misi)
diff -r b255f25ad394 -r a85fd87460e3 src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc	Wed Mar 24 13:06:06 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc	Thu Mar 25 09:42:59 2004 +0000
@@ -34,8 +34,8 @@
 
   typedef ListGraph MutableGraph;
 
-  typedef SmartGraph Graph;
-  //typedef ListGraph Graph;
+  //typedef SmartGraph Graph;
+  typedef ListGraph Graph;
   typedef Graph::Node Node;
   typedef Graph::EdgeIt EdgeIt;
 
@@ -85,7 +85,7 @@
 
 
   {
-    std::cout << "SmartGraph..." << std::endl;
+    //std::cout << "SmartGraph..." << std::endl;
     std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
@@ -114,7 +114,7 @@
   }
 
   {
-    std::cout << "SmartGraph..." << std::endl;
+    //std::cout << "SmartGraph..." << std::endl;
     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
 
diff -r b255f25ad394 -r a85fd87460e3 src/work/marci_graph_demo.cc
--- a/src/work/marci_graph_demo.cc	Wed Mar 24 13:06:06 2004 +0000
+++ b/src/work/marci_graph_demo.cc	Thu Mar 25 09:42:59 2004 +0000
@@ -2,109 +2,109 @@
 #include <vector>
 #include <string>
 
-#include <list_graph.hh>
-#include <bfs_iterator.hh>
-#include <edmonds_karp.hh>
+#include <list_graph.h>
+#include <bfs_iterator.h>
+#include <edmonds_karp.h>
 
 using namespace hugo;
 
 int main (int, char*[])
 {
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
   typedef ListGraph::NodeIt NodeIt;
   typedef ListGraph::EdgeIt EdgeIt;
-  typedef ListGraph::EachNodeIt EachNodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
   typedef ListGraph::OutEdgeIt OutEdgeIt;
   typedef ListGraph::InEdgeIt InEdgeIt;
   typedef ListGraph::SymEdgeIt SymEdgeIt;
   ListGraph G;
-  std::vector<NodeIt> vector_of_NodeIts;
-  for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
+  std::vector<Node> vector_of_Nodes;
+  for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
   for(int i=0; i!=8; ++i)
     for(int j=0; j!=8; ++j) 
-      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
+      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
 
   std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
-  std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
+  std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
 
-  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
+  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
     std::cout << "node " << G.id(i) << std::endl;
     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
-    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
+    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
     }
     std::cout << std::endl; 
 
     std::cout<< " ";
-    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
+    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
     std::cout<<std::endl;
 
     std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
-    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
+    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 
       std::cout << j << " "; } 
     std::cout << std::endl;
 
     std::cout<< " ";
-    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
+    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 
       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
     std::cout<<std::endl;
 
     std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
-    for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
+    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 
       std::cout << j << " "; } 
     std::cout<<std::endl;
 
     std::cout<< " ";
-    for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
+    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 
       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
     std::cout<<std::endl;
   }
 
   std::cout << "all edges: ";
-  for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
+  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
     std::cout << i << " ";
   }
   std::cout << std::endl;
 
   std::cout << "node property array test" << std::endl;
   ListGraph::NodeMap<int> my_property_vector(G);
-  EachNodeIt v;
-  G.getFirst(v);
+  NodeIt v;
+  G.first(v);
   my_property_vector.set(v, 42);
-  my_property_vector.set(++G.first<EachNodeIt>(), 314);
-  my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
-  my_property_vector.set(vector_of_NodeIts[3], 1989);
-  my_property_vector.set(vector_of_NodeIts[4], 2003);
-  my_property_vector.set(vector_of_NodeIts[7], 1978);
+  my_property_vector.set(G.next(G.first<NodeIt>()), 314);
+  my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
+  my_property_vector.set(vector_of_Nodes[3], 1989);
+  my_property_vector.set(vector_of_Nodes[4], 2003);
+  my_property_vector.set(vector_of_Nodes[7], 1978);
   std::cout << "some node property values..." << std::endl;
-  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
+  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
     std::cout << my_property_vector.get(i) << std::endl;
   }
   int _i=1;
   int _ii=1;
   ListGraph::EdgeMap<int> my_edge_property(G);
-  for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
+  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
     my_edge_property.set(i, _i);
     _i*=_ii; ++_ii;
   }
 
   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
-  for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
+  for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
   }
   std::cout << std::endl;
 /*
   std::cout << "bfs from the first node" << std::endl;
-  bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
+  bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
   bfs_test.run();
   std::cout << "reached: ";
-  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
+  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
     std::cout << bfs_test.reached.get(i) << " ";
   }
   std::cout<<std::endl;
   std::cout << "dist: ";
-  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
+  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
     std::cout << bfs_test.dist.get(i) << " ";
   }
   std::cout<<std::endl;
@@ -113,12 +113,12 @@
   std::cout << "augmenting path flow algorithm test..." << std::endl;
   ListGraph flowG;
 
-  NodeIt s=flowG.addNode();
-  NodeIt v1=flowG.addNode();
-  NodeIt v2=flowG.addNode();
-  NodeIt v3=flowG.addNode();
-  NodeIt v4=flowG.addNode();
-  NodeIt t=flowG.addNode();
+  Node s=flowG.addNode();
+  Node v1=flowG.addNode();
+  Node v2=flowG.addNode();
+  Node v3=flowG.addNode();
+  Node v4=flowG.addNode();
+  Node t=flowG.addNode();
   
   ListGraph::NodeMap<std::string> node_name(flowG);
   node_name.set(s, "s");
@@ -128,16 +128,16 @@
   node_name.set(v4, "v4");
   node_name.set(t, "t");
 
-  EdgeIt s_v1=flowG.addEdge(s, v1);
-  EdgeIt s_v2=flowG.addEdge(s, v2);
-  EdgeIt v1_v2=flowG.addEdge(v1, v2);
-  EdgeIt v2_v1=flowG.addEdge(v2, v1);
-  EdgeIt v1_v3=flowG.addEdge(v1, v3);
-  EdgeIt v3_v2=flowG.addEdge(v3, v2);
-  EdgeIt v2_v4=flowG.addEdge(v2, v4);
-  EdgeIt v4_v3=flowG.addEdge(v4, v3);
-  EdgeIt v3_t=flowG.addEdge(v3, t);
-  EdgeIt v4_t=flowG.addEdge(v4, t);
+  Edge s_v1=flowG.addEdge(s, v1);
+  Edge s_v2=flowG.addEdge(s, v2);
+  Edge v1_v2=flowG.addEdge(v1, v2);
+  Edge v2_v1=flowG.addEdge(v2, v1);
+  Edge v1_v3=flowG.addEdge(v1, v3);
+  Edge v3_v2=flowG.addEdge(v3, v2);
+  Edge v2_v4=flowG.addEdge(v2, v4);
+  Edge v4_v3=flowG.addEdge(v4, v3);
+  Edge v3_t=flowG.addEdge(v3, t);
+  Edge v4_t=flowG.addEdge(v4, t);
 
   ListGraph::EdgeMap<int> cap(flowG);
 
@@ -154,13 +154,13 @@
 
   std::cout << "on directed graph graph" << std::endl; //<< flowG;
   std::cout << "names and capacity values" << std::endl; 
-  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
     std::cout << node_name.get(i) << ": ";
     std::cout << "out edges: ";
-    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     std::cout << "in edges: ";
-    for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     std::cout << std::endl;
   }
@@ -174,45 +174,45 @@
   //flowG.setTail(v3_t, v2);
   //flowG.setHead(v3_t, s);
 /*
-  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
     std::cout << node_name.get(i) << ": ";
     std::cout << "out edges: ";
-    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     std::cout << "in edges: ";
-    for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     std::cout << std::endl;
   }
   
-  for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
+  for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
   }
 */
   /*
-  while (flowG.first<EachEdgeIt>().valid()) {
-    flowG.deleteEdge(flowG.first<EachEdgeIt>());
-    for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+  while (flowG.valid(flowG.first<EdgeIt>())) {
+    flowG.deleteEdge(flowG.first<EdgeIt>());
+    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
       std::cout << node_name.get(i) << ": ";
       std::cout << "out edges: ";
-      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
       std::cout << "in edges: ";
-      for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
       std::cout << std::endl;
     }
   }
   
-  while (flowG.first<EachNodeIt>().valid()) {
-    flowG.deleteNode(flowG.first<EachNodeIt>());
-    for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
+  while (flowG.valid(flowG.first<NodeIt>())) {
+    flowG.deleteNode(flowG.first<NodeIt>());
+    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
       std::cout << node_name.get(i) << ": ";
       std::cout << "out edges: ";
-      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
+      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
       std::cout << "in edges: ";
-      for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
+      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
       std::cout << std::endl;
     }
@@ -227,12 +227,12 @@
     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
     /*
     max_flow_test.augmentOnBlockingFlow<ListGraph>();
-    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     }
     std::cout<<std::endl;
     max_flow_test.augmentOnBlockingFlow<ListGraph>();
-    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     }
     std::cout<<std::endl;*/
@@ -240,7 +240,7 @@
     
     //std::cout << "maximum flow: "<< std::endl;
     while (max_flow_test.augmentOnShortestPath()) {
-      for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+      for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
 	std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
       }
       std::cout<<std::endl;
@@ -249,9 +249,9 @@
   }
 /*
   {
-    std::list<NodeIt> S;
+    std::list<Node> S;
     S.push_back(s); S.push_back(v3);
-    std::list<NodeIt> T;
+    std::list<Node> T;
     T.push_back(t);
 
     ListGraph::EdgeMap<int> flow(flowG, 0);
@@ -259,7 +259,7 @@
     max_flow_test.run();
     
     std::cout << "maximum flow: "<< std::endl;
-    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     }
     std::cout<<std::endl;