diff -r ee5959aa4410 -r c280de819a73 src/work/marci/oldies/bfs_iterator.hh
--- a/src/work/marci/oldies/bfs_iterator.hh	Sun Apr 17 18:57:22 2005 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,836 +0,0 @@
-#ifndef BFS_ITERATOR_HH
-#define BFS_ITERATOR_HH
-
-#include <queue>
-#include <stack>
-#include <utility>
-#include <graph_wrapper.h>
-
-namespace hugo {
-
-  template <typename Graph>
-  struct bfs {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    Graph& G;
-    NodeIt s;
-    typename Graph::NodeMap<bool> reached;
-    typename Graph::NodeMap<EdgeIt> pred;
-    typename Graph::NodeMap<int> dist;
-    std::queue<NodeIt> bfs_queue;
-    bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
-      bfs_queue.push(s); 
-      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) 
-	reached.set(i, false);
-      reached.set(s, true);
-      dist.set(s, 0); 
-    }
-    
-    void run() {
-      while (!bfs_queue.empty()) {
-	NodeIt v=bfs_queue.front();
-	OutEdgeIt e=G.template first<OutEdgeIt>(v);
-	bfs_queue.pop();
-	for( ; e.valid(); ++e) {
-	  NodeIt 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 {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    Graph& G;
-    bfs_visitor(Graph& _G) : G(_G) { }
-    void at_previously_reached(OutEdgeIt& e) { 
-      //NodeIt v=G.aNode(e);
-      NodeIt w=G.bNode(e);
-      std::cout << G.id(w) << " is already reached" << std::endl;
-   }
-    void at_newly_reached(OutEdgeIt& e) { 
-      //NodeIt v=G.aNode(e);
-      NodeIt w=G.bNode(e);
-      std::cout << G.id(w) << " is newly reached :-)" << std::endl;
-    }
-  };
-
-  template <typename Graph, typename ReachedMap, typename visitor_type>
-  struct bfs_iterator {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    Graph& G;
-    std::queue<OutEdgeIt>& bfs_queue;
-    ReachedMap& reached;
-    visitor_type& visitor;
-    void process() {
-      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-      if (bfs_queue.empty()) return;
-      OutEdgeIt e=bfs_queue.front();
-      //NodeIt v=G.aNode(e);
-      NodeIt w=G.bNode(e);
-      if (!reached.get(w)) {
-	visitor.at_newly_reached(e);
-	bfs_queue.push(G.template first<OutEdgeIt>(w));
-	reached.set(w, true);
-      } else {
-	visitor.at_previously_reached(e);
-      }
-    }
-    bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 
-      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-      valid();
-    }
-    bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { 
-      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-      //if (bfs_queue.empty()) return *this;
-      if (!valid()) return *this;
-      ++(bfs_queue.front());
-      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-      valid();
-      return *this;
-    }
-    //void next() { 
-    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-    //  if (bfs_queue.empty()) return;
-    //  ++(bfs_queue.front());
-    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-    //}
-    bool valid() { 
-      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-      if (bfs_queue.empty()) return false; else return true;
-    }
-    //bool finished() { 
-    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-    //  if (bfs_queue.empty()) return true; else return false;
-    //}
-    operator EdgeIt () { return bfs_queue.front(); }
-
-  };
-
-  template <typename Graph, typename ReachedMap>
-  struct bfs_iterator1 {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    Graph& G;
-    std::queue<OutEdgeIt>& bfs_queue;
-    ReachedMap& reached;
-    bool _newly_reached;
-    bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
-      valid();
-      if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
-	OutEdgeIt e=bfs_queue.front();
-	NodeIt w=G.bNode(e);
-	if (!reached.get(w)) {
-	  bfs_queue.push(G.template first<OutEdgeIt>(w));
-	  reached.set(w, true);
-	  _newly_reached=true;
-	} else {
-	  _newly_reached=false;
-	}
-      }
-    }
-    bfs_iterator1<Graph, ReachedMap>& operator++() { 
-      if (!valid()) return *this;
-      ++(bfs_queue.front());
-      valid();
-      if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
-	OutEdgeIt e=bfs_queue.front();
-	NodeIt w=G.bNode(e);
-	if (!reached.get(w)) {
-	  bfs_queue.push(G.template first<OutEdgeIt>(w));
-	  reached.set(w, true);
-	  _newly_reached=true;
-	} else {
-	  _newly_reached=false;
-	}
-      }
-      return *this;
-    }
-    bool valid() { 
-      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
-      if (bfs_queue.empty()) return false; else return true;
-    }
-    operator OutEdgeIt() { return bfs_queue.front(); }
-    //ize
-    bool newly_reached() { return _newly_reached; }
-
-  };
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  struct BfsIterator {
-    typedef typename Graph::NodeIt NodeIt;
-    Graph& G;
-    std::queue<OutEdgeIt>& bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    BfsIterator(Graph& _G, 
-		std::queue<OutEdgeIt>& _bfs_queue, 
-		ReachedMap& _reached) : 
-      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
-      actual_edge=bfs_queue.front();
-      if (actual_edge.valid()) { 
-	NodeIt w=G.bNode(actual_edge);
-	if (!reached.get(w)) {
-	  bfs_queue.push(G.firstOutEdge(w));
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  b_node_newly_reached=false;
-	}
-      }
-    }
-    BfsIterator<Graph, OutEdgeIt, ReachedMap>& 
-    operator++() { 
-      if (bfs_queue.front().valid()) { 
-	++(bfs_queue.front());
-	actual_edge=bfs_queue.front();
-	if (actual_edge.valid()) {
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(G.firstOutEdge(w));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      } else {
-	bfs_queue.pop(); 
-	actual_edge=bfs_queue.front();
-	if (actual_edge.valid()) {
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(G.firstOutEdge(w));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      }
-      return *this;
-    }
-    bool finished() { return bfs_queue.empty(); }
-    operator OutEdgeIt () { return actual_edge; }
-    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
-    bool aNodeIsExamined() { return !(actual_edge.valid()); }
-  };
-
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  struct DfsIterator {
-    typedef typename Graph::NodeIt NodeIt;
-    Graph& G;
-    std::stack<OutEdgeIt>& bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    DfsIterator(Graph& _G, 
-		std::stack<OutEdgeIt>& _bfs_queue, 
-		ReachedMap& _reached) : 
-      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
-      actual_edge=bfs_queue.top();
-      if (actual_edge.valid()) { 
-	NodeIt w=G.bNode(actual_edge);
-	if (!reached.get(w)) {
-	  bfs_queue.push(G.firstOutEdge(w));
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  ++(bfs_queue.top());
-	  b_node_newly_reached=false;
-	}
-      } else {
-	bfs_queue.pop();
-      }
-    }
-    DfsIterator<Graph, OutEdgeIt, ReachedMap>& 
-    operator++() { 
-      actual_edge=bfs_queue.top();
-      if (actual_edge.valid()) { 
-	NodeIt w=G.bNode(actual_edge);
-	if (!reached.get(w)) {
-	  bfs_queue.push(G.firstOutEdge(w));
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  ++(bfs_queue.top());
-	  b_node_newly_reached=false;
-	}
-      } else {
-	bfs_queue.pop();
-      }
-      return *this;
-    }
-    bool finished() { return bfs_queue.empty(); }
-    operator OutEdgeIt () { return actual_edge; }
-    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
-    bool aNodeIsExamined() { return !(actual_edge.valid()); }
-  };
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  struct BfsIterator1 {
-    typedef typename Graph::NodeIt NodeIt;
-    Graph& G;
-    std::queue<OutEdgeIt>& bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    BfsIterator1(Graph& _G, 
-		std::queue<OutEdgeIt>& _bfs_queue, 
-		ReachedMap& _reached) : 
-      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
-      actual_edge=bfs_queue.front();
-      if (actual_edge.valid()) { 
-      	NodeIt w=G.bNode(actual_edge);
-	if (!reached.get(w)) {
-	  bfs_queue.push(OutEdgeIt(G, w));
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  b_node_newly_reached=false;
-	}
-      }
-    }
-    void next() { 
-      if (bfs_queue.front().valid()) { 
-	++(bfs_queue.front());
-	actual_edge=bfs_queue.front();
-	if (actual_edge.valid()) {
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(OutEdgeIt(G, w));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      } else {
-	bfs_queue.pop(); 
-	actual_edge=bfs_queue.front();
-	if (actual_edge.valid()) {
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(OutEdgeIt(G, w));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      }
-      //return *this;
-    }
-    bool finished() { return bfs_queue.empty(); }
-    operator OutEdgeIt () { return actual_edge; }
-    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
-    bool aNodeIsExamined() { return !(actual_edge.valid()); }
-  };
-
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  struct DfsIterator1 {
-    typedef typename Graph::NodeIt NodeIt;
-    Graph& G;
-    std::stack<OutEdgeIt>& bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    DfsIterator1(Graph& _G, 
-		std::stack<OutEdgeIt>& _bfs_queue, 
-		ReachedMap& _reached) : 
-      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
-      //actual_edge=bfs_queue.top();
-      //if (actual_edge.valid()) { 
-      //	NodeIt w=G.bNode(actual_edge);
-      //if (!reached.get(w)) {
-      //  bfs_queue.push(OutEdgeIt(G, w));
-      //  reached.set(w, true);
-      //  b_node_newly_reached=true;
-      //} else {
-      //  ++(bfs_queue.top());
-      //  b_node_newly_reached=false;
-      //}
-      //} else {
-      //	bfs_queue.pop();
-      //}
-    }
-    void next() { 
-      actual_edge=bfs_queue.top();
-      if (actual_edge.valid()) { 
-	NodeIt w=G.bNode(actual_edge);
-	if (!reached.get(w)) {
-	  bfs_queue.push(OutEdgeIt(G, w));
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  ++(bfs_queue.top());
-	  b_node_newly_reached=false;
-	}
-      } else {
-	bfs_queue.pop();
-      }
-      //return *this;
-    }
-    bool finished() { return bfs_queue.empty(); }
-    operator OutEdgeIt () { return actual_edge; }
-    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
-    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
-  };
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  class BfsIterator2 {
-    typedef typename Graph::NodeIt NodeIt;
-    const Graph& G;
-    std::queue<OutEdgeIt> bfs_queue;
-    ReachedMap reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-  public:
-    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
-    void pushAndSetReached(NodeIt s) { 
-      reached.set(s, true);
-      if (bfs_queue.empty()) {
-	bfs_queue.push(G.template first<OutEdgeIt>(s));
-	actual_edge=bfs_queue.front();
-	if (actual_edge.valid()) { 
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(G.template first<OutEdgeIt>(w));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	} //else {
-	//}
-      } else {
-	bfs_queue.push(G.template first<OutEdgeIt>(s));
-      }
-    }
-    BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
-    operator++() { 
-      if (bfs_queue.front().valid()) { 
-	++(bfs_queue.front());
-	actual_edge=bfs_queue.front();
-	if (actual_edge.valid()) {
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(G.template first<OutEdgeIt>(w));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      } else {
-	bfs_queue.pop(); 
-	if (!bfs_queue.empty()) {
-	  actual_edge=bfs_queue.front();
-	  if (actual_edge.valid()) {
-	    NodeIt w=G.bNode(actual_edge);
-	    if (!reached.get(w)) {
-	      bfs_queue.push(G.template first<OutEdgeIt>(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 !(actual_edge.valid()); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
- };
-
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  class BfsIterator3 {
-    typedef typename Graph::NodeIt NodeIt;
-    const Graph& G;
-    std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
-    ReachedMap reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-  public:
-    BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
-    void pushAndSetReached(NodeIt s) { 
-      reached.set(s, true);
-      if (bfs_queue.empty()) {
-	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
-	actual_edge=bfs_queue.front().second;
-	if (actual_edge.valid()) { 
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	} //else {
-	//}
-      } else {
-	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
-      }
-    }
-    BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
-    operator++() { 
-      if (bfs_queue.front().second.valid()) { 
-	++(bfs_queue.front().second);
-	actual_edge=bfs_queue.front().second;
-	if (actual_edge.valid()) {
-	  NodeIt w=G.bNode(actual_edge);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      } else {
-	bfs_queue.pop(); 
-	if (!bfs_queue.empty()) {
-	  actual_edge=bfs_queue.front().second;
-	  if (actual_edge.valid()) {
-	    NodeIt w=G.bNode(actual_edge);
-	    if (!reached.get(w)) {
-	      bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(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 !(actual_edge.valid()); }
-    NodeIt aNode() const { return bfs_queue.front().first; }
-    NodeIt bNode() const { return G.bNode(actual_edge); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
- };
-
-
-  template <typename Graph, typename OutEdgeIt, 
-	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
-  class BfsIterator4 {
-    typedef typename Graph::NodeIt NodeIt;
-    const Graph& G;
-    std::queue<NodeIt> 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(NodeIt 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.getFirst(actual_edge, s);
-	//std::cout << "kiki" << std::endl;
-	if (G.valid(actual_edge)/*.valid()*/) { 
-	  NodeIt 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()*/) {
-	  NodeIt 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.getFirst(actual_edge, bfs_queue.front());
-	  if (G.valid(actual_edge)/*.valid()*/) {
-	    NodeIt 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()*/); }
-    NodeIt aNode() const { return bfs_queue.front(); }
-    NodeIt bNode() const { return G.bNode(actual_edge); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
- };  
-
-
-  template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
-	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
-  class BfsIterator5 {
-    typedef typename GraphWrapper::NodeIt NodeIt;
-    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
-    GraphWrapper G;
-    std::queue<NodeIt> bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    bool own_reached_map;
-  public:
-    BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
-      G(_G), reached(_reached), 
-      own_reached_map(false) { }
-    BfsIterator5(const GraphWrapper& _G) : 
-      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
-      own_reached_map(true) { }
-//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G, 
-// 		 ReachedMap& _reached) : 
-//       G(_G), reached(_reached), 
-//       own_reached_map(false) { }
-//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : 
-//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
-//       own_reached_map(true) { }
-    ~BfsIterator5() { if (own_reached_map) delete &reached; }
-    void pushAndSetReached(NodeIt s) { 
-      reached.set(s, true);
-      if (bfs_queue.empty()) {
-	bfs_queue.push(s);
-	G.getFirst(actual_edge, s);
-	if (G.valid(actual_edge)/*.valid()*/) { 
-	  NodeIt 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.push(s);
-      }
-    }
-    BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
-    operator++() { 
-      if (G.valid(actual_edge)/*.valid()*/) { 
-	/*++*/G.next(actual_edge);
-	if (G.valid(actual_edge)/*.valid()*/) {
-	  NodeIt 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.getFirst(actual_edge, bfs_queue.front());
-	  if (G.valid(actual_edge)/*.valid()*/) {
-	    NodeIt 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()*/); }
-    NodeIt aNode() const { return bfs_queue.front(); }
-    NodeIt bNode() const { return G.bNode(actual_edge); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
-  };  
-
-  template <typename Graph, typename OutEdgeIt, 
-	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
-  class DfsIterator4 {
-    typedef typename Graph::NodeIt NodeIt;
-    const Graph& G;
-    std::stack<OutEdgeIt> dfs_stack;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    NodeIt 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(NodeIt 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()*/) { 
-	NodeIt 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()*/); }
-    NodeIt aNode() const { return actual_node; /*FIXME*/}
-    NodeIt 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>*/ >
-  class DfsIterator5 {
-    typedef typename GraphWrapper::NodeIt NodeIt;
-    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
-    GraphWrapper G;
-    std::stack<OutEdgeIt> dfs_stack;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    NodeIt actual_node;
-    ReachedMap& reached;
-    bool own_reached_map;
-  public:
-    DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
-      G(_G), reached(_reached), 
-      own_reached_map(false) { }
-    DfsIterator5(const GraphWrapper& _G) : 
-      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
-      own_reached_map(true) { }
-    ~DfsIterator5() { if (own_reached_map) delete &reached; }
-    void pushAndSetReached(NodeIt s) { 
-      actual_node=s;
-      reached.set(s, true);
-      dfs_stack.push(G.template first<OutEdgeIt>(s)); 
-    }
-    DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
-    operator++() { 
-      actual_edge=dfs_stack.top();
-      //actual_node=G.aNode(actual_edge);
-      if (G.valid(actual_edge)/*.valid()*/) { 
-	NodeIt 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()*/); }
-    NodeIt aNode() const { return actual_node; /*FIXME*/}
-    NodeIt bNode() const { return G.bNode(actual_edge); }
-    const ReachedMap& getReachedMap() const { return reached; }
-    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
-  };
-
-
-
-} // namespace hugo
-
-#endif //BFS_ITERATOR_HH