alpar@302: // -*-mode: c++; -*-
alpar@302: #ifndef _BFS_H_
alpar@302: #define _BFS_H_
alpar@302: 
alpar@302: #include <queue>
alpar@302: #include <graph.h>
alpar@302: 
alpar@302: namespace NEGRO 
alpar@302: {
alpar@302:   using namespace std;
alpar@302:   
alpar@302:   //   template <typename G,typename> class bfs_T
alpar@302:   //   {
alpar@302:   //     typedef G Graph;
alpar@302:   //     typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
alpar@302:   //     typedef Graph::NodeIterator NodeIterator;
alpar@302:     
alpar@302:   //     class bfs_node_D 
alpar@302:   //     {
alpar@302:   //       EdgeIterator Tree;
alpar@302:   //       int Dist;
alpar@302:   //       int Priority;
alpar@302:   //     }
alpar@302:   //   }
alpar@302:     
alpar@302: 
alpar@302:   //     //    template <bfs_T<G>>
alpar@302:   //     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
alpar@302: 
alpar@302:     
alpar@302:   
alpar@302:   //   template <class G>
alpar@302:   //   class bfs_maps_T
alpar@302:   //   {
alpar@302:   //     typedef visited; //node->bool (RW)
alpar@302:   //     typedef tree;    //node->EdgeIterator (W)
alpar@302:   //     typedef dist;   //node->int (W)
alpar@302:   //     typedef priority; //node->int (W)
alpar@302:   //   };
alpar@302:   
alpar@302:   
alpar@302:   //   Nem jo! Osszeakad a masik Put-tal
alpar@302:   //   class do_nothing_map {};
alpar@302:   //   template <typename V,typename T>
alpar@302:   //   void Put(const do_nothing_map &p,const V &v,const T &t) {}
alpar@302:   
alpar@302:   struct do_nothing_map {
alpar@302:     template <typename V,typename T> static void Put(V v,T t) {}
alpar@302:     template <typename G> void SetG(G &g) {}
alpar@302:   };
alpar@302:   
alpar@302: 
alpar@302:   template <typename I,typename C, typename T, T C::*M>
alpar@302:   class class_element_map {
alpar@302:   public:
alpar@302:     typedef T value_type;
alpar@302:     static void Put(const I &i, const T &t) {(*i).*M=t;}
alpar@302:     static T Get(const I i) {return (*i).*M;}
alpar@302:     T &operator[](I i) {return (*i).*M;}
alpar@302:   };
alpar@302: 
alpar@302:   /* 
alpar@302:      template <typename C,typename I,typename T, T C::*M>
alpar@302:      void Put(class_element_map<C,T,M> p,I i, T t)
alpar@302:      {
alpar@302:      i->*M=t;   
alpar@302:      };
alpar@302:   */
alpar@302: 
alpar@302:   template <typename P,typename I,typename T>
alpar@302:   inline void Put(P &p,const I &i, const T &t)
alpar@302:   {
alpar@302:     p.Put(i,t);   
alpar@302:   };
alpar@302:   template <typename P,typename I>
alpar@302:   inline typename P::value_type Get(const P &p,const I &i)
alpar@302:   {
alpar@302:     return p.Get(i);   
alpar@302:   };
alpar@302: 
alpar@302:   /*
alpar@302:     template <typename G,typename T, typename G::EdgeType::*M>
alpar@302:     T Get(edge_element_map p,G::EdgeIterator i)
alpar@302:     {
alpar@302:     return i->*M;
alpar@302:     };
alpar@302:   */
alpar@302:   
alpar@302:   /* 
alpar@302:      template <class G>
alpar@302:      class default_bfs_maps
alpar@302:      {
alpar@302:      public:
alpar@302:      typedef typename G::NodeType NodeType;
alpar@302:     
alpar@302:      class_element_map<typename G::NodeIterator,
alpar@302:      typename G::NodeType,
alpar@302:      bool,&NodeType::isVis> visited; //node->bool (RW)
alpar@302:      do_nothing_map tree;   //node->EdgeIterator (W)
alpar@302:      do_nothing_map dist;   //node->int (W)
alpar@302:      do_nothing_map priority; //node->int (W)
alpar@302:      };
alpar@302:   */
alpar@302: 
alpar@302:   template<class G>
alpar@302:   struct bfs_node_data 
alpar@302:   {
alpar@302:     bool visited;
alpar@302:     typename G::EdgeIterator tree;
alpar@302:     int dist;
alpar@302:     int priority;
alpar@302:   };
alpar@302:   
alpar@302:   template <class G>
alpar@302:   class bfs_static_maps
alpar@302:   {
alpar@302:   public:
alpar@302:     typedef typename G::NodeType NodeType;
alpar@302:     
alpar@302:     /*    class_element_map<typename G::NodeIterator,
alpar@302: 	  typename G::NodeType,
alpar@302: 	  bfs_node_data<G>,&NT::D> n_d; //node-> data
alpar@302:     */
alpar@302:     class 
alpar@302:     {
alpar@302:     public:
alpar@302:       bfs_node_data<G> NodeType::*d;
alpar@302:       typedef bool value_type;
alpar@302:       void Put(typename G::NodeIterator &i, const value_type &t)
alpar@302:       {((*i).*d).visited=t;}
alpar@302:       value_type Get(const typename G::NodeIterator &i) const
alpar@302:       {return ((*i).*d).visited;}
alpar@302:     } visited;
alpar@302:     
alpar@302:     class 
alpar@302:     {
alpar@302:     public:
alpar@302:       bfs_node_data<G> NodeType::*d;
alpar@302:       typedef typename G::EdgeIterator value_type;
alpar@302:       void Put(typename G::NodeIterator &i, const value_type &t)
alpar@302:       {((*i).*d).tree=t;}
alpar@302:       value_type Get(const typename G::NodeIterator &i) const
alpar@302:       {return ((*i).*d).tree;}
alpar@302:     } tree;
alpar@302:     
alpar@302:     class 
alpar@302:     {
alpar@302:     public:
alpar@302:       bfs_node_data<G> NodeType::*d;
alpar@302:       typedef int value_type;
alpar@302:       void Put(typename G::NodeIterator &i, const value_type &t)
alpar@302:       {((*i).*d).dist=t;}
alpar@302:       value_type Get(const typename G::NodeIterator &i) const
alpar@302:       {return ((*i).*d).dist;}
alpar@302:     } dist;
alpar@302:     
alpar@302:     class 
alpar@302:     {
alpar@302:     public:
alpar@302:       bfs_node_data<G> NodeType::*d;
alpar@302:       typedef int value_type;
alpar@302:       void Put(typename G::NodeIterator &i,  const value_type &t)
alpar@302:       {((*i).*d).priority=t;}
alpar@302:       value_type Get(const typename G::NodeIterator &i) const
alpar@302:       {return ((*i).*d).priority;}
alpar@302:     } priority;
alpar@302:     
alpar@302:     //do_nothing_map tree;   //node->EdgeIterator (W)
alpar@302:     //    do_nothing_map dist;   //node->int (W)
alpar@302:     //    do_nothing_map priority; //node->int (W)
alpar@302: 
alpar@302:     void SetDataField(const bfs_node_data<G> NodeType::*dd)
alpar@302:     {
alpar@302:       tree.d=visited.d=dist.d=priority.d=dd;
alpar@302:     }
alpar@302:     
alpar@302:     bfs_static_maps(const bfs_node_data<G> NodeType::*dd) 
alpar@302:     {
alpar@302:       PutDataField(dd);
alpar@302:     }
alpar@302:     
alpar@302:     bfs_static_maps(const bfs_static_maps<G> &B) 
alpar@302:     {
alpar@302:       tree.d=B.tree.d;visited.d=B.visited.d;
alpar@302:       dist.d=B.dist.d;priority.d=B.priority.d;
alpar@302:     }
alpar@302:     
alpar@302:   };
alpar@302:   
alpar@302:   template<typename I>
alpar@302:   struct BFS_Q
alpar@302:   {
alpar@302:     I n;
alpar@302:     int dist;
alpar@302:     //  BFS_Q() {}
alpar@302:     //  BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
alpar@302:   };
alpar@302:   
alpar@302:   template<class G,class M>
alpar@302:   void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
alpar@302:   {
alpar@302:     using namespace std;
alpar@302:     
alpar@302:     typedef BFS_Q<typename G::NodeIterator> Q_T;
alpar@302:     
alpar@302:     Q_T q;
alpar@302:     
alpar@302:     int pr=0;
alpar@302:     typename G::NodeIterator n,m;
alpar@302:     typename G::OutEdgeIterator e;
alpar@302:     int d;
alpar@302:     
alpar@302:     for(Gr.GetFirst(n);n.isValid();++n)
alpar@302:       Put(maps.visited,n,false);
alpar@302:     
alpar@302:     queue<Q_T> Q;
alpar@302:     
alpar@302:     q.n=start_node;
alpar@302:     q.dist=0;
alpar@302:     Q.push(q);
alpar@302:     Put(maps.visited,start_node,true);
alpar@302:     //      Put(maps::tree,start_node,?????);
alpar@302:     Put(maps.dist,start_node,0);
alpar@302:     Put(maps.priority,start_node,pr++);
alpar@302:     
alpar@302:     do {
alpar@302:       n=Q.front().n;d=Q.front().dist+1;
alpar@302:       Q.pop();
alpar@302:       for(Gr.GetFirst(e,n);e.isValid();++e)
alpar@302: 	if(!Get(maps.visited,(m=e.Bnode()))) {
alpar@302: 	  q.n=m;
alpar@302: 	  q.dist=d;
alpar@302: 	  Q.push(q);
alpar@302: 	  Put(maps.visited,m,true);
alpar@302: 	  Put(maps.tree,m,e);
alpar@302: 	  Put(maps.dist,m,d);
alpar@302: 	  Put(maps.priority,m,pr++);
alpar@302: 	}
alpar@302:     } while(!Q.empty());
alpar@302:   };
alpar@302: 
alpar@302:   // bfs algorithm class
alpar@302: 
alpar@302:   template<class G>  //the default traits
alpar@302:   class default_bfs_T
alpar@302:   {
alpar@302:   public:
alpar@302:     
alpar@302:     typedef G Graph;
alpar@302:     typedef typename G::OutEdgeIterator SearchEdgeIterator;
alpar@302:     
alpar@302:     typedef typename G::NodeMap<bool> visited_map_t;
alpar@302:     typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
alpar@302:     
alpar@302:     typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)
alpar@302:     typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
alpar@302: };
alpar@302: 
alpar@302:   template<class T>
alpar@302:   class Bfs
alpar@302:   {
alpar@302:   public:
alpar@302:     typedef typename T::Graph Graph;
alpar@302:     typedef typename Graph::NodeIterator NodeIterator;
alpar@302:     typedef typename Graph::EdgeIterator EdgeIterator;
alpar@302:     
alpar@302:     typedef typename T::SearchEdgeIterator SearchEdgeIterator;
alpar@302:     
alpar@302:     typename T::visited_map_t visited_map;
alpar@302:     typename T::tree_map_t tree_map;
alpar@302:     typename T::dist_map_t dist_map;
alpar@302:     typename T::priority_map_t priority_map;
alpar@302:     
alpar@302:     struct bfs_queue_cont
alpar@302:     {
alpar@302:       NodeIterator n;
alpar@302:       int dist;
alpar@302:     };
alpar@302:     
alpar@302:     std::queue<bfs_queue_cont> bfs_queue;
alpar@302:     
alpar@302:     int priority;
alpar@302:     Graph *G;
alpar@302:     
alpar@302:     //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
alpar@302:     Bfs() {}
alpar@302: 
alpar@302:     void SetG(Graph &Gr)
alpar@302:     {
alpar@302:       G=&Gr;
alpar@302:       visited_map.SetG(Gr);
alpar@302:       tree_map.SetG(Gr);
alpar@302:       dist_map.SetG(Gr);
alpar@302:       priority_map.SetG(Gr);
alpar@302:     }
alpar@302:     
alpar@302:     void Init()
alpar@302:     {
alpar@302:       //There must be a better way to do this:
alpar@302:       while(!bfs_queue.empty()) bfs_queue.pop();
alpar@302: 
alpar@302:       for(NodeIterator n(*G);n.isValid();++n)
alpar@302: 	Put(visited_map,n,false);
alpar@302:       
alpar@302:       priority=0;
alpar@302:     }
alpar@302:     
alpar@302:     void AddStartNode(const NodeIterator &start_node,int dist=0)
alpar@302:     {
alpar@302:       bfs_queue_cont q;
alpar@302:       q.n=start_node;
alpar@302:       q.dist=dist;
alpar@302:       bfs_queue.push(q);
alpar@302: 
alpar@302:       Put(visited_map,start_node,true);
alpar@302:       //      Put(tree_map,start_node,?????);
alpar@302:       Put(dist_map,start_node,dist);
alpar@302:       Put(priority_map,start_node,priority++);    
alpar@302:     }
alpar@302:     
alpar@302:     void Init(const NodeIterator &start_node,int dist=0)
alpar@302:     {
alpar@302:       Init();
alpar@302:       AddStartNode(start_node,dist);
alpar@302:     }
alpar@302: 
alpar@302:     void Run() 
alpar@302:     {
alpar@302:       NodeIterator n,m;
alpar@302:       int d;
alpar@302: 
alpar@302:       bfs_queue_cont q;
alpar@302:       while(!(bfs_queue.empty()/* && other stop conditions */)) {
alpar@302: 	n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
alpar@302: 	bfs_queue.pop();
alpar@302: 	for(SearchEdgeIterator e(*G,n);e.isValid();++e)
alpar@302: 	  if(!Get(visited_map,(m=e.Bnode()))) {
alpar@302: 	    q.n=m;
alpar@302: 	    q.dist=d;
alpar@302: 	    bfs_queue.push(q);
alpar@302: 	    Put(visited_map,m,true);
alpar@302: 	    Put(tree_map,m,e);
alpar@302: 	    Put(dist_map,m,d);
alpar@302: 	    Put(priority_map,m,priority++);
alpar@302: 	  }
alpar@302:       }
alpar@302:     }
alpar@302:   };
alpar@302:   
alpar@302: }
alpar@302:   
alpar@302: #endif