1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/bfs.h Mon Apr 05 15:31:21 2004 +0000
1.3 @@ -0,0 +1,352 @@
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