lemon-0.x: src/work/alpar/bfs.h@240003bddaff

     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> static void Put(V v,T t) {}

    49     template <typename G> void SetG(G &g) {}

    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

   244   template<class G>  //the default traits

   245   class default_bfs_T

   246   {

   247   public:

   249     typedef G Graph;

   250     typedef typename G::OutEdgeIterator SearchEdgeIterator;

   252     typedef typename G::NodeMap<bool> visited_map_t;

   253     typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;

   255     typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)

   256     typedef typename G::NodeMap<int> priority_map_t; //node->int (W)

   257 };

   259   template<class T>

   260   class Bfs

   261   {

   262   public:

   263     typedef typename T::Graph Graph;

   264     typedef typename Graph::NodeIterator NodeIterator;

   265     typedef typename Graph::EdgeIterator EdgeIterator;

   267     typedef typename T::SearchEdgeIterator SearchEdgeIterator;

   269     typename T::visited_map_t visited_map;

   270     typename T::tree_map_t tree_map;

   271     typename T::dist_map_t dist_map;

   272     typename T::priority_map_t priority_map;

   274     struct bfs_queue_cont

   275     {

   276       NodeIterator n;

   277       int dist;

   278     };

   280     std::queue<bfs_queue_cont> bfs_queue;

   282     int priority;

   283     Graph *G;

   285     //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}

   286     Bfs() {}

   288     void SetG(Graph &Gr)

   289     {

   290       G=&Gr;

   291       visited_map.SetG(Gr);

   292       tree_map.SetG(Gr);

   293       dist_map.SetG(Gr);

   294       priority_map.SetG(Gr);

   295     }

   297     void Init()

   298     {

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

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

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

   303 	Put(visited_map,n,false);

   305       priority=0;

   306     }

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

   309     {

   310       bfs_queue_cont q;

   311       q.n=start_node;

   312       q.dist=dist;

   313       bfs_queue.push(q);

   315       Put(visited_map,start_node,true);

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

   317       Put(dist_map,start_node,dist);

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

   319     }

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

   322     {

   323       Init();

   324       AddStartNode(start_node,dist);

   325     }

   327     void Run()

   328     {

   329       NodeIterator n,m;

   330       int d;

   332       bfs_queue_cont q;

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

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

   335 	bfs_queue.pop();

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

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

   338 	    q.n=m;

   339 	    q.dist=d;

   340 	    bfs_queue.push(q);

   341 	    Put(visited_map,m,true);

   342 	    Put(tree_map,m,e);

   343 	    Put(dist_map,m,d);

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

   345 	  }

   346       }

   347     }

   348   };

   350 }

   352 #endif

author	alpar
	Thu, 22 Jul 2004 20:06:40 +0000
changeset 733	240003bddaff
permissions	-rw-r--r--