// -*- 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();

}