1.1 --- a/src/include/bfs.h Mon Apr 05 13:55:55 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,352 +0,0 @@
1.4 -// -*-mode: c++; -*-
1.5 -#ifndef _BFS_H_
1.6 -#define _BFS_H_
1.7 -
1.8 -#include <queue>
1.9 -#include <graph.h>
1.10 -
1.11 -namespace NEGRO
1.12 -{
1.13 - using namespace std;
1.14 -
1.15 - // template <typename G,typename> class bfs_T
1.16 - // {
1.17 - // typedef G Graph;
1.18 - // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
1.19 - // typedef Graph::NodeIterator NodeIterator;
1.20 -
1.21 - // class bfs_node_D
1.22 - // {
1.23 - // EdgeIterator Tree;
1.24 - // int Dist;
1.25 - // int Priority;
1.26 - // }
1.27 - // }
1.28 -
1.29 -
1.30 - // // template <bfs_T<G>>
1.31 - // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
1.32 -
1.33 -
1.34 -
1.35 - // template <class G>
1.36 - // class bfs_maps_T
1.37 - // {
1.38 - // typedef visited; //node->bool (RW)
1.39 - // typedef tree; //node->EdgeIterator (W)
1.40 - // typedef dist; //node->int (W)
1.41 - // typedef priority; //node->int (W)
1.42 - // };
1.43 -
1.44 -
1.45 - // Nem jo! Osszeakad a masik Put-tal
1.46 - // class do_nothing_map {};
1.47 - // template <typename V,typename T>
1.48 - // void Put(const do_nothing_map &p,const V &v,const T &t) {}
1.49 -
1.50 - struct do_nothing_map {
1.51 - template <typename V,typename T> static void Put(V v,T t) {}
1.52 - template <typename G> void SetG(G &g) {}
1.53 - };
1.54 -
1.55 -
1.56 - template <typename I,typename C, typename T, T C::*M>
1.57 - class class_element_map {
1.58 - public:
1.59 - typedef T value_type;
1.60 - static void Put(const I &i, const T &t) {(*i).*M=t;}
1.61 - static T Get(const I i) {return (*i).*M;}
1.62 - T &operator[](I i) {return (*i).*M;}
1.63 - };
1.64 -
1.65 - /*
1.66 - template <typename C,typename I,typename T, T C::*M>
1.67 - void Put(class_element_map<C,T,M> p,I i, T t)
1.68 - {
1.69 - i->*M=t;
1.70 - };
1.71 - */
1.72 -
1.73 - template <typename P,typename I,typename T>
1.74 - inline void Put(P &p,const I &i, const T &t)
1.75 - {
1.76 - p.Put(i,t);
1.77 - };
1.78 - template <typename P,typename I>
1.79 - inline typename P::value_type Get(const P &p,const I &i)
1.80 - {
1.81 - return p.Get(i);
1.82 - };
1.83 -
1.84 - /*
1.85 - template <typename G,typename T, typename G::EdgeType::*M>
1.86 - T Get(edge_element_map p,G::EdgeIterator i)
1.87 - {
1.88 - return i->*M;
1.89 - };
1.90 - */
1.91 -
1.92 - /*
1.93 - template <class G>
1.94 - class default_bfs_maps
1.95 - {
1.96 - public:
1.97 - typedef typename G::NodeType NodeType;
1.98 -
1.99 - class_element_map<typename G::NodeIterator,
1.100 - typename G::NodeType,
1.101 - bool,&NodeType::isVis> visited; //node->bool (RW)
1.102 - do_nothing_map tree; //node->EdgeIterator (W)
1.103 - do_nothing_map dist; //node->int (W)
1.104 - do_nothing_map priority; //node->int (W)
1.105 - };
1.106 - */
1.107 -
1.108 - template<class G>
1.109 - struct bfs_node_data
1.110 - {
1.111 - bool visited;
1.112 - typename G::EdgeIterator tree;
1.113 - int dist;
1.114 - int priority;
1.115 - };
1.116 -
1.117 - template <class G>
1.118 - class bfs_static_maps
1.119 - {
1.120 - public:
1.121 - typedef typename G::NodeType NodeType;
1.122 -
1.123 - /* class_element_map<typename G::NodeIterator,
1.124 - typename G::NodeType,
1.125 - bfs_node_data<G>,&NT::D> n_d; //node-> data
1.126 - */
1.127 - class
1.128 - {
1.129 - public:
1.130 - bfs_node_data<G> NodeType::*d;
1.131 - typedef bool value_type;
1.132 - void Put(typename G::NodeIterator &i, const value_type &t)
1.133 - {((*i).*d).visited=t;}
1.134 - value_type Get(const typename G::NodeIterator &i) const
1.135 - {return ((*i).*d).visited;}
1.136 - } visited;
1.137 -
1.138 - class
1.139 - {
1.140 - public:
1.141 - bfs_node_data<G> NodeType::*d;
1.142 - typedef typename G::EdgeIterator value_type;
1.143 - void Put(typename G::NodeIterator &i, const value_type &t)
1.144 - {((*i).*d).tree=t;}
1.145 - value_type Get(const typename G::NodeIterator &i) const
1.146 - {return ((*i).*d).tree;}
1.147 - } tree;
1.148 -
1.149 - class
1.150 - {
1.151 - public:
1.152 - bfs_node_data<G> NodeType::*d;
1.153 - typedef int value_type;
1.154 - void Put(typename G::NodeIterator &i, const value_type &t)
1.155 - {((*i).*d).dist=t;}
1.156 - value_type Get(const typename G::NodeIterator &i) const
1.157 - {return ((*i).*d).dist;}
1.158 - } dist;
1.159 -
1.160 - class
1.161 - {
1.162 - public:
1.163 - bfs_node_data<G> NodeType::*d;
1.164 - typedef int value_type;
1.165 - void Put(typename G::NodeIterator &i, const value_type &t)
1.166 - {((*i).*d).priority=t;}
1.167 - value_type Get(const typename G::NodeIterator &i) const
1.168 - {return ((*i).*d).priority;}
1.169 - } priority;
1.170 -
1.171 - //do_nothing_map tree; //node->EdgeIterator (W)
1.172 - // do_nothing_map dist; //node->int (W)
1.173 - // do_nothing_map priority; //node->int (W)
1.174 -
1.175 - void SetDataField(const bfs_node_data<G> NodeType::*dd)
1.176 - {
1.177 - tree.d=visited.d=dist.d=priority.d=dd;
1.178 - }
1.179 -
1.180 - bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
1.181 - {
1.182 - PutDataField(dd);
1.183 - }
1.184 -
1.185 - bfs_static_maps(const bfs_static_maps<G> &B)
1.186 - {
1.187 - tree.d=B.tree.d;visited.d=B.visited.d;
1.188 - dist.d=B.dist.d;priority.d=B.priority.d;
1.189 - }
1.190 -
1.191 - };
1.192 -
1.193 - template<typename I>
1.194 - struct BFS_Q
1.195 - {
1.196 - I n;
1.197 - int dist;
1.198 - // BFS_Q() {}
1.199 - // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
1.200 - };
1.201 -
1.202 - template<class G,class M>
1.203 - void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
1.204 - {
1.205 - using namespace std;
1.206 -
1.207 - typedef BFS_Q<typename G::NodeIterator> Q_T;
1.208 -
1.209 - Q_T q;
1.210 -
1.211 - int pr=0;
1.212 - typename G::NodeIterator n,m;
1.213 - typename G::OutEdgeIterator e;
1.214 - int d;
1.215 -
1.216 - for(Gr.GetFirst(n);n.isValid();++n)
1.217 - Put(maps.visited,n,false);
1.218 -
1.219 - queue<Q_T> Q;
1.220 -
1.221 - q.n=start_node;
1.222 - q.dist=0;
1.223 - Q.push(q);
1.224 - Put(maps.visited,start_node,true);
1.225 - // Put(maps::tree,start_node,?????);
1.226 - Put(maps.dist,start_node,0);
1.227 - Put(maps.priority,start_node,pr++);
1.228 -
1.229 - do {
1.230 - n=Q.front().n;d=Q.front().dist+1;
1.231 - Q.pop();
1.232 - for(Gr.GetFirst(e,n);e.isValid();++e)
1.233 - if(!Get(maps.visited,(m=e.Bnode()))) {
1.234 - q.n=m;
1.235 - q.dist=d;
1.236 - Q.push(q);
1.237 - Put(maps.visited,m,true);
1.238 - Put(maps.tree,m,e);
1.239 - Put(maps.dist,m,d);
1.240 - Put(maps.priority,m,pr++);
1.241 - }
1.242 - } while(!Q.empty());
1.243 - };
1.244 -
1.245 - // bfs algorithm class
1.246 -
1.247 - template<class G> //the default traits
1.248 - class default_bfs_T
1.249 - {
1.250 - public:
1.251 -
1.252 - typedef G Graph;
1.253 - typedef typename G::OutEdgeIterator SearchEdgeIterator;
1.254 -
1.255 - typedef typename G::NodeMap<bool> visited_map_t;
1.256 - typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
1.257 -
1.258 - typedef typename G::NodeMap<int> dist_map_t; //node->int (W)
1.259 - typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
1.260 -};
1.261 -
1.262 - template<class T>
1.263 - class Bfs
1.264 - {
1.265 - public:
1.266 - typedef typename T::Graph Graph;
1.267 - typedef typename Graph::NodeIterator NodeIterator;
1.268 - typedef typename Graph::EdgeIterator EdgeIterator;
1.269 -
1.270 - typedef typename T::SearchEdgeIterator SearchEdgeIterator;
1.271 -
1.272 - typename T::visited_map_t visited_map;
1.273 - typename T::tree_map_t tree_map;
1.274 - typename T::dist_map_t dist_map;
1.275 - typename T::priority_map_t priority_map;
1.276 -
1.277 - struct bfs_queue_cont
1.278 - {
1.279 - NodeIterator n;
1.280 - int dist;
1.281 - };
1.282 -
1.283 - std::queue<bfs_queue_cont> bfs_queue;
1.284 -
1.285 - int priority;
1.286 - Graph *G;
1.287 -
1.288 - //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
1.289 - Bfs() {}
1.290 -
1.291 - void SetG(Graph &Gr)
1.292 - {
1.293 - G=&Gr;
1.294 - visited_map.SetG(Gr);
1.295 - tree_map.SetG(Gr);
1.296 - dist_map.SetG(Gr);
1.297 - priority_map.SetG(Gr);
1.298 - }
1.299 -
1.300 - void Init()
1.301 - {
1.302 - //There must be a better way to do this:
1.303 - while(!bfs_queue.empty()) bfs_queue.pop();
1.304 -
1.305 - for(NodeIterator n(*G);n.isValid();++n)
1.306 - Put(visited_map,n,false);
1.307 -
1.308 - priority=0;
1.309 - }
1.310 -
1.311 - void AddStartNode(const NodeIterator &start_node,int dist=0)
1.312 - {
1.313 - bfs_queue_cont q;
1.314 - q.n=start_node;
1.315 - q.dist=dist;
1.316 - bfs_queue.push(q);
1.317 -
1.318 - Put(visited_map,start_node,true);
1.319 - // Put(tree_map,start_node,?????);
1.320 - Put(dist_map,start_node,dist);
1.321 - Put(priority_map,start_node,priority++);
1.322 - }
1.323 -
1.324 - void Init(const NodeIterator &start_node,int dist=0)
1.325 - {
1.326 - Init();
1.327 - AddStartNode(start_node,dist);
1.328 - }
1.329 -
1.330 - void Run()
1.331 - {
1.332 - NodeIterator n,m;
1.333 - int d;
1.334 -
1.335 - bfs_queue_cont q;
1.336 - while(!(bfs_queue.empty()/* && other stop conditions */)) {
1.337 - n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
1.338 - bfs_queue.pop();
1.339 - for(SearchEdgeIterator e(*G,n);e.isValid();++e)
1.340 - if(!Get(visited_map,(m=e.Bnode()))) {
1.341 - q.n=m;
1.342 - q.dist=d;
1.343 - bfs_queue.push(q);
1.344 - Put(visited_map,m,true);
1.345 - Put(tree_map,m,e);
1.346 - Put(dist_map,m,d);
1.347 - Put(priority_map,m,priority++);
1.348 - }
1.349 - }
1.350 - }
1.351 - };
1.352 -
1.353 -}
1.354 -
1.355 -#endif