alpar@741: // -*- mode:C++ -*-
alpar@741: 
alpar@921: #include <lemon/smart_graph.h>
alpar@921: #include <lemon/maps.h>
alpar@741: #include <vector>
alpar@743: #include <iostream>
alpar@741: 
alpar@921: using namespace lemon;
alpar@741: 
alpar@741: struct _BFS_DEFAULT_VIS {};
alpar@741: struct _BFS_CUSTOM_VIS {};
alpar@741: 
alpar@741: template<class GT,class VT,class DVT,class PNT,class PET,class PT >
alpar@741: class _BFS 
alpar@741: {
alpar@741:  public:
alpar@741:   typedef GT Graph;
alpar@741:   typedef VT Visited;
alpar@741:   typedef PNT PredNode;
alpar@741:   typedef PET PredEdge;
alpar@741:   typedef PT Priority;
alpar@741:   //  typedef QDT QueueData;
alpar@741:   
alpar@741:   typedef typename Graph::Node Node;
alpar@741:   typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@741: 
alpar@741:   typedef DVT DefaultVisitedTag;
alpar@741:   
alpar@741:   const Graph &_graph;
alpar@741: 
alpar@741:   Node _source;
alpar@741:   
alpar@741:   Visited *_visited;
alpar@741:   PredNode _predNode;
alpar@741:   PredEdge _predEdge;
alpar@741:   Priority _priority;
alpar@741: 
alpar@741:   _BFS(const Graph &g,
alpar@741:        Node s,
alpar@741:        Visited *v,
alpar@741:        PredNode &pn,
alpar@741:        PredEdge &pe,
alpar@741:        Priority &pr) :_graph(g), _source(s),
alpar@741: 		     _visited(v), 
alpar@741: 		     _predNode(pn), _predEdge(pe), _priority(pr) { }
alpar@741: 
alpar@741:   
alpar@741:   int run(const _BFS_CUSTOM_VIS &) 
alpar@741:   {
alpar@741:     using namespace std;
alpar@741:     
alpar@741:     int N=_graph.nodeNum();
alpar@741:     vector<Node> Q(N);
alpar@741:     int Qh=0;
alpar@741:     int Qt=0;
alpar@741:     
alpar@945:     for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
alpar@741:       _visited->set(n,false);
alpar@741: 
alpar@741:     Q[Qh++]=_source;
alpar@741:     _visited->set(_source,true);
alpar@741:     do {
alpar@741:       Node m;
alpar@741:       Node n=Q[Qt++];
alpar@945:       for(OutEdgeIt e(_graph,n);e!=INVALID;++e)
alpar@741: 	if(!(*_visited)[m=_graph.head(e)]) {
alpar@741: 	  Q[Qh++]=m;
alpar@741: 	  _visited->set(m,true);
alpar@741: 	  _predNode.set(m,n);
alpar@741: 	  _predEdge.set(m,e);	  
alpar@741: 	}
alpar@741:     } while(Qt!=Qh);
alpar@741: 
alpar@741:     return 1; //Why return 1?
alpar@741:   }
alpar@741:   int run(const _BFS_DEFAULT_VIS &) 
alpar@741:   {
alpar@741:     _visited= new Visited(_graph);
alpar@741:     int r = run(_BFS_CUSTOM_VIS());
alpar@741:     delete _visited;
alpar@741:     return r;
alpar@741:   }
alpar@741:   int run() { return run(DefaultVisitedTag());}
alpar@741: 
alpar@741:   template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
alpar@741:   setVisitMap(T &t)
alpar@741:   {
alpar@741:     return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
alpar@741:       (_graph,_source,&t,_predNode,_predEdge,_priority);
alpar@741:   }
alpar@741: 
alpar@741:   template<class T>
alpar@743:   _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
alpar@741:   setPredNodeMap(T &t)
alpar@741:   {
alpar@743:     return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
alpar@741:       (_graph,_source,
alpar@741:        _visited,
alpar@741:        t,_predEdge,_priority);
alpar@741:   }
alpar@741: 
alpar@741:   template<class T>
alpar@743:   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
alpar@741:   setPredEdgeMap(T &t)
alpar@741:   {
alpar@743:     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
alpar@741:       (_graph,_source,
alpar@741:        _visited,
alpar@741:       _predNode,t,_priority);
alpar@741:   }
alpar@741: 
alpar@743:   _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
alpar@741:   setNothing()
alpar@741:   {
alpar@743:     return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
alpar@741:       (_graph,_source,
alpar@741:        _visited,
alpar@741:        _predNode,_predEdge,_priority);
alpar@741:   }
alpar@741: };
alpar@741: 
alpar@741: 
alpar@741: template<class G>
alpar@741: _BFS<G,
alpar@741:      typename G::template NodeMap<bool>,
alpar@741:      _BFS_DEFAULT_VIS,
alpar@741:      NullMap<typename G::Node,typename G::Node>,
alpar@741:      NullMap<typename G::Node,typename G::Edge>,
alpar@741:      NullMap<typename G::Node,int> >
alpar@741: bfs(const G &g,typename G::Node s)
alpar@741: {
alpar@741:   //  typename G::template NodeMap<bool> v(g);
alpar@741: 
alpar@741:   return _BFS < G,
alpar@741:     typename G::template NodeMap<bool>,
alpar@741:     _BFS_DEFAULT_VIS,
alpar@741:      NullMap<typename G::Node,typename G::Node>,
alpar@741:      NullMap<typename G::Node,typename G::Edge>,
alpar@741:     NullMap<typename G::Node,int> >
alpar@741:     (g,s,
alpar@741:      (typename G::template NodeMap<bool>*)(NULL),
alpar@741:      *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
alpar@741:      *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
alpar@741:      *((NullMap<typename G::Node,int> *)(NULL))
alpar@741:      );
alpar@741: }
alpar@741: 
alpar@741: 
alpar@743: class MyVisitedMap : public SmartGraph::NodeMap<bool>
alpar@743: {
alpar@743:   const SmartGraph &_G;
alpar@743: public:
alpar@743:   MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
alpar@743:   void set(SmartGraph::Node n,bool b)
alpar@743:   {
alpar@743:     SmartGraph::NodeMap<bool>::set(n,b);
alpar@743:     if(b) std::cout << _G.id(n) << std::endl;
alpar@743:   }
alpar@743: };
alpar@743: 
alpar@743: 
alpar@741: int main()
alpar@741: {
alpar@741:   SmartGraph G;
alpar@743:   SmartGraph::Node s=G.addNode();
alpar@743:   SmartGraph::Node n1=G.addNode();
alpar@743:   SmartGraph::Node n2=G.addNode();
alpar@743:   SmartGraph::Node n3=G.addNode();
alpar@743:   SmartGraph::Node n4=G.addNode();
alpar@743:   SmartGraph::Node n5=G.addNode();
alpar@743:   SmartGraph::Node n6=G.addNode();
alpar@743:   SmartGraph::Node n7=G.addNode();
alpar@743: 
alpar@743:   G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3);
alpar@743:   G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5);
alpar@743:   G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s);
alpar@743: 
alpar@743:   
alpar@743:   
alpar@741:   SmartGraph::NodeMap<SmartGraph::Node> m(G);
alpar@741:   SmartGraph::NodeMap<SmartGraph::Edge> em(G);
alpar@743: 
alpar@743:   MyVisitedMap vm(G);
alpar@743: 
alpar@743: 
alpar@744:   //Runs BFS on graph 'G' from node 's'.
alpar@744:   //(It practically does nothing, for it throws away its result.) 
alpar@744:   bfs(G,s).run(); 
alpar@743: 
alpar@744:   //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'.
alpar@743:   bfs(G,s).setPredNodeMap(m).run();
alpar@743: 
alpar@744:   //Runs BFS on graph 'G' from node 's'.
alpar@744:   //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'.
alpar@743:   bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run();
alpar@743: 
alpar@744:   //Runs BFS on graph 'G' from node 's'.
alpar@744:   //It uses a scpecial 'visited map' that prints out the reached nodes.
alpar@743:   bfs(G,s).setVisitMap(vm).run();
alpar@741: 
alpar@741: }