#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