// -*- mode:C++ -*-

 #include <lemon/smart_graph.h>

 #include <lemon/maps.h>

 #include <vector>

 #include <iostream>

 using namespace lemon;

 struct _BFS_DEFAULT_VIS {};

 struct _BFS_CUSTOM_VIS {};

 template<class GT,class VT,class DVT,class PNT,class PET,class PT >

 class _BFS 

 {

  public:

   typedef GT Graph;

   typedef VT Visited;

   typedef PNT PredNode;

   typedef PET PredEdge;

   typedef PT Priority;

   //  typedef QDT QueueData;

   typedef typename Graph::Node Node;

   typedef typename Graph::OutEdgeIt OutEdgeIt;

   typedef DVT DefaultVisitedTag;

   const Graph &_graph;

   Node _source;

   Visited *_visited;

   PredNode _predNode;

   PredEdge _predEdge;

   Priority _priority;

   _BFS(const Graph &g,

        Node s,

        Visited *v,

        PredNode &pn,

        PredEdge &pe,

        Priority &pr) :_graph(g), _source(s),

 		     _visited(v), 

 		     _predNode(pn), _predEdge(pe), _priority(pr) { }

   int run(const _BFS_CUSTOM_VIS &) 

   {

     using namespace std;

     int N=_graph.nodeNum();

     vector<Node> Q(N);

     int Qh=0;

     int Qt=0;

     for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))

       _visited->set(n,false);

     Q[Qh++]=_source;

     _visited->set(_source,true);

     do {

       Node m;

       Node n=Q[Qt++];

       for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))

 	if(!(*_visited)[m=_graph.head(e)]) {

 	  Q[Qh++]=m;

 	  _visited->set(m,true);

 	  _predNode.set(m,n);

 	  _predEdge.set(m,e);	  

 	}

     } while(Qt!=Qh);

     return 1; //Why return 1?

   }

   int run(const _BFS_DEFAULT_VIS &) 

   {

     _visited= new Visited(_graph);

     int r = run(_BFS_CUSTOM_VIS());

     delete _visited;

     return r;

   }

   int run() { return run(DefaultVisitedTag());}

   template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>

   setVisitMap(T &t)

   {

     return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>

       (_graph,_source,&t,_predNode,_predEdge,_priority);

   }

   template<class T>

   _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>

   setPredNodeMap(T &t)

   {

     return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>

       (_graph,_source,

        _visited,

        t,_predEdge,_priority);

   }

   template<class T>

   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>

   setPredEdgeMap(T &t)

   {

     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>

       (_graph,_source,

        _visited,

       _predNode,t,_priority);

   }

   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>

   setNothing()

   {

     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>

       (_graph,_source,

        _visited,

        _predNode,_predEdge,_priority);

   }

 };

 template<class G>

 _BFS<G,

      typename G::template NodeMap<bool>,

      _BFS_DEFAULT_VIS,

      NullMap<typename G::Node,typename G::Node>,

      NullMap<typename G::Node,typename G::Edge>,

      NullMap<typename G::Node,int> >

 bfs(const G &g,typename G::Node s)

 {

   //  typename G::template NodeMap<bool> v(g);

   return _BFS < G,

     typename G::template NodeMap<bool>,

     _BFS_DEFAULT_VIS,

      NullMap<typename G::Node,typename G::Node>,

      NullMap<typename G::Node,typename G::Edge>,

     NullMap<typename G::Node,int> >

     (g,s,

      (typename G::template NodeMap<bool>*)(NULL),

      *((NullMap<typename G::Node,typename G::Node>*)(NULL)),

      *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),

      *((NullMap<typename G::Node,int> *)(NULL))

      );

 }

 class MyVisitedMap : public SmartGraph::NodeMap<bool>

 {

   const SmartGraph &_G;

 public:

   MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}

   void set(SmartGraph::Node n,bool b)

   {

     SmartGraph::NodeMap<bool>::set(n,b);

     if(b) std::cout << _G.id(n) << std::endl;

   }

 };

 int main()

 {

   SmartGraph G;

   SmartGraph::Node s=G.addNode();

   SmartGraph::Node n1=G.addNode();

   SmartGraph::Node n2=G.addNode();

   SmartGraph::Node n3=G.addNode();

   SmartGraph::Node n4=G.addNode();

   SmartGraph::Node n5=G.addNode();

   SmartGraph::Node n6=G.addNode();

   SmartGraph::Node n7=G.addNode();

   G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3);

   G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5);

   G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s);

   SmartGraph::NodeMap<SmartGraph::Node> m(G);

   SmartGraph::NodeMap<SmartGraph::Edge> em(G);

   MyVisitedMap vm(G);

   //Runs BFS on graph 'G' from node 's'.

   //(It practically does nothing, for it throws away its result.) 

   bfs(G,s).run(); 

   //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'.

   bfs(G,s).setPredNodeMap(m).run();

   //Runs BFS on graph 'G' from node 's'.

   //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'.

   bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run();

   //Runs BFS on graph 'G' from node 's'.

   //It uses a scpecial 'visited map' that prints out the reached nodes.

   bfs(G,s).setVisitMap(vm).run();

 }