lemon-0.x: src/include/bfs.h@8009bb5ddd09

     1 // -*-mode: c++; -*-

     2 #ifndef _BFS_H_

     3 #define _BFS_H_

     5 #include <queue>

     6 #include <graph.h>

     8 namespace NEGRO

9 {

    10   using namespace std;

    12   //   template <typename G,typename> class bfs_T

    13   //   {

    14   //     typedef G Graph;

    15   //     typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell

    16   //     typedef Graph::NodeIterator NodeIterator;

    18   //     class bfs_node_D

    19   //     {

    20   //       EdgeIterator Tree;

    21   //       int Dist;

    22   //       int Priority;

    23   //     }

    24   //   }

    27   //     //    template <bfs_T<G>>

    28   //     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)

    32   //   template <class G>

    33   //   class bfs_maps_T

    34   //   {

    35   //     typedef visited; //node->bool (RW)

    36   //     typedef tree;    //node->EdgeIterator (W)

    37   //     typedef dist;   //node->int (W)

    38   //     typedef priority; //node->int (W)

    39   //   };

    42   //   Nem jo! Osszeakad a masik Put-tal

    43   //   class do_nothing_map {};

    44   //   template <typename V,typename T>

    45   //   void Put(const do_nothing_map &p,const V &v,const T &t) {}

    47   struct do_nothing_map {

    48     template <typename V,typename T>

    49     static void Put(V v,T t) {}

    50   };

    53   template <typename I,typename C, typename T, T C::*M>

    54   class class_element_map {

    55   public:

    56     typedef T value_type;

    57     static void Put(const I &i, const T &t) {(*i).*M=t;}

    58     static T Get(const I i) {return (*i).*M;}

    59     T &operator[](I i) {return (*i).*M;}

    60   };

    62   /*

    63      template <typename C,typename I,typename T, T C::*M>

    64      void Put(class_element_map<C,T,M> p,I i, T t)

    65      {

    66      i->*M=t;

    67      };

    68   */

    70   template <typename P,typename I,typename T>

    71   inline void Put(P &p,const I &i, const T &t)

    72   {

    73     p.Put(i,t);

    74   };

    75   template <typename P,typename I>

    76   inline typename P::value_type Get(const P &p,const I &i)

    77   {

    78     return p.Get(i);

    79   };

    81   /*

    82     template <typename G,typename T, typename G::EdgeType::*M>

    83     T Get(edge_element_map p,G::EdgeIterator i)

    84     {

    85     return i->*M;

    86     };

    87   */

    89   /*

    90      template <class G>

    91      class default_bfs_maps

    92      {

    93      public:

    94      typedef typename G::NodeType NodeType;

    96      class_element_map<typename G::NodeIterator,

    97      typename G::NodeType,

    98      bool,&NodeType::isVis> visited; //node->bool (RW)

    99      do_nothing_map tree;   //node->EdgeIterator (W)

   100      do_nothing_map dist;   //node->int (W)

   101      do_nothing_map priority; //node->int (W)

   102      };

   103   */

   105   template<class G>

   106   struct bfs_node_data

   107   {

   108     bool visited;

   109     typename G::EdgeIterator tree;

   110     int dist;

   111     int priority;

   112   };

   114   template <class G>

   115   class bfs_static_maps

   116   {

   117   public:

   118     typedef typename G::NodeType NodeType;

   120     /*    class_element_map<typename G::NodeIterator,

   121 	  typename G::NodeType,

   122 	  bfs_node_data<G>,&NT::D> n_d; //node-> data

   123     */

   124     class

   125     {

   126     public:

   127       bfs_node_data<G> NodeType::*d;

   128       typedef bool value_type;

   129       void Put(typename G::NodeIterator &i, const value_type &t)

   130       {((*i).*d).visited=t;}

   131       value_type Get(const typename G::NodeIterator &i) const

   132       {return ((*i).*d).visited;}

   133     } visited;

   135     class

   136     {

   137     public:

   138       bfs_node_data<G> NodeType::*d;

   139       typedef typename G::EdgeIterator value_type;

   140       void Put(typename G::NodeIterator &i, const value_type &t)

   141       {((*i).*d).tree=t;}

   142       value_type Get(const typename G::NodeIterator &i) const

   143       {return ((*i).*d).tree;}

   144     } tree;

   146     class

   147     {

   148     public:

   149       bfs_node_data<G> NodeType::*d;

   150       typedef int value_type;

   151       void Put(typename G::NodeIterator &i, const value_type &t)

   152       {((*i).*d).dist=t;}

   153       value_type Get(const typename G::NodeIterator &i) const

   154       {return ((*i).*d).dist;}

   155     } dist;

   157     class

   158     {

   159     public:

   160       bfs_node_data<G> NodeType::*d;

   161       typedef int value_type;

   162       void Put(typename G::NodeIterator &i,  const value_type &t)

   163       {((*i).*d).priority=t;}

   164       value_type Get(const typename G::NodeIterator &i) const

   165       {return ((*i).*d).priority;}

   166     } priority;

   168     //do_nothing_map tree;   //node->EdgeIterator (W)

   169     //    do_nothing_map dist;   //node->int (W)

   170     //    do_nothing_map priority; //node->int (W)

   172     void SetDataField(const bfs_node_data<G> NodeType::*dd)

   173     {

   174       tree.d=visited.d=dist.d=priority.d=dd;

   175     }

   177     bfs_static_maps(const bfs_node_data<G> NodeType::*dd)

   178     {

   179       PutDataField(dd);

   180     }

   182     bfs_static_maps(const bfs_static_maps<G> &B)

   183     {

   184       tree.d=B.tree.d;visited.d=B.visited.d;

   185       dist.d=B.dist.d;priority.d=B.priority.d;

   186     }

   188   };

   190   template<typename I>

   191   struct BFS_Q

   192   {

   193     I n;

   194     int dist;

   195     //  BFS_Q() {}

   196     //  BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}

   197   };

   199   template<class G,class M>

   200   void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)

   201   {

   202     using namespace std;

   204     typedef BFS_Q<typename G::NodeIterator> Q_T;

   206     Q_T q;

   208     int pr=0;

   209     typename G::NodeIterator n,m;

   210     typename G::OutEdgeIterator e;

   211     int d;

   213     for(Gr.GetFirst(n);n.isValid();++n)

   214       Put(maps.visited,n,false);

   216     queue<Q_T> Q;

   218     q.n=start_node;

   219     q.dist=0;

   220     Q.push(q);

   221     Put(maps.visited,start_node,true);

   222     //      Put(maps::tree,start_node,?????);

   223     Put(maps.dist,start_node,0);

   224     Put(maps.priority,start_node,pr++);

   226     do {

   227       n=Q.front().n;d=Q.front().dist+1;

   228       Q.pop();

   229       for(Gr.GetFirst(e,n);e.isValid();++e)

   230 	if(!Get(maps.visited,(m=e.Bnode()))) {

   231 	  q.n=m;

   232 	  q.dist=d;

   233 	  Q.push(q);

   234 	  Put(maps.visited,m,true);

   235 	  Put(maps.tree,m,e);

   236 	  Put(maps.dist,m,d);

   237 	  Put(maps.priority,m,pr++);

   238 	}

   239     } while(!Q.empty());

   240   };

   242   // bfs algorithm class

   243   template<class T>

   244   class Bfs

   245   {

   246   public:

   247     typedef typename T::Graph_t Graph;

   248     typedef typename Graph::NodeIterator NodeIterator;

   249     typedef typename Graph::EdgeIterator EdgeIterator;

   251     typedef typename T::SearchEdgeIterator SearchEdgeIterator;

   253     typename T::visited_map_t visited_map;

   254     typename T::tree_map_t tree_map;

   255     typename T::dist_map_t dist_map;

   256     typename T::priority_map_t priority_map;

   258     struct bfs_queue_cont

   259     {

   260       NodeIterator n;

   261       int dist;

   262     };

   264     std::queue<bfs_queue_cont> bfs_queue;

   266     int priority;

   267     Graph *G;

   269     void SetG(Graph &Gr)

   270     {

   271       G=&Gr;

   272     }

   274     void Init()

   275     {

   276       //There must be a better way to do this:

   277       while(!bfs_queue.empty()) bfs_queue.pop();

   279       for(NodeIterator n(*G);n.isValid();++n)

   280 	Put(visited_map,n,false);

   282       priority=0;

   284     }

   286     void AddStartNode(const NodeIterator &start_node,int dist=0)

   287     {

   288       bfs_queue_cont q;

   289       q.n=start_node;

   290       q.dist=dist;

   291       bfs_queue.push(q);

   293       Put(visited_map,start_node,true);

   294       //      Put(tree_map,start_node,?????);

   295       Put(dist_map,start_node,dist);

   296       Put(priority_map,start_node,priority++);

   297     }

   299     void Init(const NodeIterator &start_node,int dist=0)

   300     {

   302       Init();

   303       AddStartNode(start_node,dist);

   304     }

   306     void Run()

   307     {

   308       NodeIterator n,m;

   309       int d;

   311       bfs_queue_cont q;

   312       while(!(bfs_queue.empty()/* && other stop conditions */)) {

   313 	n=bfs_queue.front().n;d=bfs_queue.front().dist+1;

   314 	bfs_queue.pop();

   315 	for(SearchEdgeIterator e(*G,n);e.isValid();++e)

   316 	  if(!Get(visited_map,(m=e.Bnode()))) {

   317 	    q.n=m;

   318 	    q.dist=d;

   319 	    bfs_queue.push(q);

   320 	    Put(visited_map,m,true);

   321 	    Put(tree_map,m,e);

   322 	    Put(dist_map,m,d);

   323 	    Put(priority_map,m,priority++);

   324 	  }

   325       }

   326     }

   327   };

   329 }

   331 #endif

author	alpar
	Sun, 14 Dec 2003 15:32:46 +0000
changeset 4	8009bb5ddd09
parent 3	272a5677bd6d
child 5	f5852ebe00ca
permissions	-rw-r--r--