// -*- c++ -*-
#ifndef HUGO_BFS_ITERATOR_H
#define HUGO_BFS_ITERATOR_H

#include <queue>
#include <stack>
#include <utility>
#include <graph_wrapper.h>

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); 
//     }
    
//     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 {
//     typedef typename Graph::Node Node;
//     typedef typename Graph::Edge Edge;
//     typedef typename Graph::OutEdgeIt OutEdgeIt;
//     Graph& G;
//     bfs_visitor(Graph& _G) : G(_G) { }
//     void at_previously_reached(OutEdgeIt& e) { 
//       //Node v=G.aNode(e);
//       Node w=G.bNode(e);
//       std::cout << G.id(w) << " is already reached" << std::endl;
//    }
//     void at_newly_reached(OutEdgeIt& e) { 
//       //Node v=G.aNode(e);
//       Node 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::Node Node;
//     typedef typename Graph::Edge Edge;
//     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();
//       //Node v=G.aNode(e);
//       Node 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 Edge () { return bfs_queue.front(); }

//   };

//   template <typename Graph, typename ReachedMap>
//   struct bfs_iterator1 {
//     typedef typename Graph::Node Node;
//     typedef typename Graph::Edge Edge;
//     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();
// 	Node 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();
// 	Node 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::Node Node;
//     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()) { 
// 	Node 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()) {
// 	  Node 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()) {
// 	  Node 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::Node Node;
//     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()) { 
// 	Node 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()) { 
// 	Node 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::Node Node;
//     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()) { 
//       	Node 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()) {
// 	  Node 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()) {
// 	  Node 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::Node Node;
//     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()) { 
//       //	Node 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()) { 
// 	Node 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::Node Node;
//     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(Node 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()) { 
// 	  Node 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()) {
// 	  Node 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()) {
// 	    Node 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::Node Node;
//     const Graph& G;
//     std::queue< std::pair<Node, 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(Node s) { 
//       reached.set(s, true);
//       if (bfs_queue.empty()) {
// 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
// 	actual_edge=bfs_queue.front().second;
// 	if (actual_edge.valid()) { 
// 	  Node w=G.bNode(actual_edge);
// 	  if (!reached.get(w)) {
// 	    bfs_queue.push(std::pair<Node, 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<Node, 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()) {
// 	  Node w=G.bNode(actual_edge);
// 	  if (!reached.get(w)) {
// 	    bfs_queue.push(std::pair<Node, 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()) {
// 	    Node w=G.bNode(actual_edge);
// 	    if (!reached.get(w)) {
// 	      bfs_queue.push(std::pair<Node, 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()); }
//     Node aNode() const { return bfs_queue.front().first; }
//     Node bNode() const { return G.bNode(actual_edge); }
//     const ReachedMap& getReachedMap() const { return reached; }
//     //const std::queue< std::pair<Node, OutEdgeIt> >& 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,*/ 
	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
  class BfsIterator5 {
    typedef typename GraphWrapper::Node Node;
    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    GraphWrapper G;
    std::queue<Node> 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(Node s) { 
      reached.set(s, true);
      if (bfs_queue.empty()) {
	bfs_queue.push(s);
	G./*getF*/first(actual_edge, s);
	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.push(s);
      }
    }
    BfsIterator5<GraphWrapper, /*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 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>*/ >
  class DfsIterator5 {
    typedef typename GraphWrapper::Node Node;
    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    GraphWrapper G;
    std::stack<OutEdgeIt> dfs_stack;
    bool b_node_newly_reached;
    OutEdgeIt actual_edge;
    Node 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(Node s) { 
      actual_node=s;
      reached.set(s, true);
      OutEdgeIt e;
      G.first(e, s);
      dfs_stack.push(e); 
    }
    DfsIterator5<GraphWrapper, /*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)) {
	  OutEdgeIt e;
	  G.first(e, w);
	  dfs_stack.push(e);
	  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; }
  };



} // namespace hugo

#endif //HUGO_BFS_ITERATOR_H