// -*- 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 {};

class _Bfs_Traits 

{

  typedef ListGraph Graph;

}

template<class T>

class _Bfs 

{

 public:

  typedef typename T::Graph Graph;

  typedef typename T::Reached Reached;

  typedef typename T::PredNode PredNode;

  typedef typename T::PredEdge PredEdge;

  typedef typename T::Priority Priority;

  typedef typename T::DefaultReachedTag DefaultReachedTag;

  typedef typename Graph::Node Node;

  typedef typename Graph::OutEdgeIt OutEdgeIt;

  const Graph &_graph;

  Node _source;

  Reached *_visited;

  PredNode _predNode;

  PredEdge _predEdge;

  Priority _priority;

  _Bfs(const Graph &g,

       Node s,

       Reached *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);n!=INVALID;++n)

      _visited->set(n,false);

    Q[Qh++]=_source;

    _visited->set(_source,true);

    do {

      Node m;

      Node n=Q[Qt++];

      for(OutEdgeIt e(_graph,n);e!=INVALID;++e)

	if(!(*_visited)[m=_graph.target(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 Reached(_graph);

    int r = run(_BFS_CUSTOM_VIS());

    delete _visited;

    return r;

  }

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

  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,Reached,DefaultReachedTag,T,PredEdge,Priority>

  setPredNodeMap(T &t)

  {

    return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority>

      (_graph,_source,

       _visited,

       t,_predEdge,_priority);

  }

  template<class T>

  _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>

  setPredEdgeMap(T &t)

  {

    return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority>

      (_graph,_source,

       _visited,

      _predNode,t,_priority);

  }

  _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority>

  setNothing()

  {

    return _Bfs<Graph,Reached,DefaultReachedTag,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 MyReachedMap : public SmartGraph::NodeMap<bool>

{

  const SmartGraph &_G;

public:

  MyReachedMap(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);

  MyReachedMap 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();

}