#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