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

}