1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/attic/bfs.h Tue Jul 27 16:02:51 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
2.1 --- a/src/work/alpar/bfs.h Sat Jul 24 14:33:37 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,352 +0,0 @@
2.4 -// -*-mode: c++; -*-
2.5 -#ifndef _BFS_H_
2.6 -#define _BFS_H_
2.7 -
2.8 -#include <queue>
2.9 -#include <graph.h>
2.10 -
2.11 -namespace NEGRO
2.12 -{
2.13 - using namespace std;
2.14 -
2.15 - // template <typename G,typename> class bfs_T
2.16 - // {
2.17 - // typedef G Graph;
2.18 - // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
2.19 - // typedef Graph::NodeIterator NodeIterator;
2.20 -
2.21 - // class bfs_node_D
2.22 - // {
2.23 - // EdgeIterator Tree;
2.24 - // int Dist;
2.25 - // int Priority;
2.26 - // }
2.27 - // }
2.28 -
2.29 -
2.30 - // // template <bfs_T<G>>
2.31 - // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
2.32 -
2.33 -
2.34 -
2.35 - // template <class G>
2.36 - // class bfs_maps_T
2.37 - // {
2.38 - // typedef visited; //node->bool (RW)
2.39 - // typedef tree; //node->EdgeIterator (W)
2.40 - // typedef dist; //node->int (W)
2.41 - // typedef priority; //node->int (W)
2.42 - // };
2.43 -
2.44 -
2.45 - // Nem jo! Osszeakad a masik Put-tal
2.46 - // class do_nothing_map {};
2.47 - // template <typename V,typename T>
2.48 - // void Put(const do_nothing_map &p,const V &v,const T &t) {}
2.49 -
2.50 - struct do_nothing_map {
2.51 - template <typename V,typename T> static void Put(V v,T t) {}
2.52 - template <typename G> void SetG(G &g) {}
2.53 - };
2.54 -
2.55 -
2.56 - template <typename I,typename C, typename T, T C::*M>
2.57 - class class_element_map {
2.58 - public:
2.59 - typedef T value_type;
2.60 - static void Put(const I &i, const T &t) {(*i).*M=t;}
2.61 - static T Get(const I i) {return (*i).*M;}
2.62 - T &operator[](I i) {return (*i).*M;}
2.63 - };
2.64 -
2.65 - /*
2.66 - template <typename C,typename I,typename T, T C::*M>
2.67 - void Put(class_element_map<C,T,M> p,I i, T t)
2.68 - {
2.69 - i->*M=t;
2.70 - };
2.71 - */
2.72 -
2.73 - template <typename P,typename I,typename T>
2.74 - inline void Put(P &p,const I &i, const T &t)
2.75 - {
2.76 - p.Put(i,t);
2.77 - };
2.78 - template <typename P,typename I>
2.79 - inline typename P::value_type Get(const P &p,const I &i)
2.80 - {
2.81 - return p.Get(i);
2.82 - };
2.83 -
2.84 - /*
2.85 - template <typename G,typename T, typename G::EdgeType::*M>
2.86 - T Get(edge_element_map p,G::EdgeIterator i)
2.87 - {
2.88 - return i->*M;
2.89 - };
2.90 - */
2.91 -
2.92 - /*
2.93 - template <class G>
2.94 - class default_bfs_maps
2.95 - {
2.96 - public:
2.97 - typedef typename G::NodeType NodeType;
2.98 -
2.99 - class_element_map<typename G::NodeIterator,
2.100 - typename G::NodeType,
2.101 - bool,&NodeType::isVis> visited; //node->bool (RW)
2.102 - do_nothing_map tree; //node->EdgeIterator (W)
2.103 - do_nothing_map dist; //node->int (W)
2.104 - do_nothing_map priority; //node->int (W)
2.105 - };
2.106 - */
2.107 -
2.108 - template<class G>
2.109 - struct bfs_node_data
2.110 - {
2.111 - bool visited;
2.112 - typename G::EdgeIterator tree;
2.113 - int dist;
2.114 - int priority;
2.115 - };
2.116 -
2.117 - template <class G>
2.118 - class bfs_static_maps
2.119 - {
2.120 - public:
2.121 - typedef typename G::NodeType NodeType;
2.122 -
2.123 - /* class_element_map<typename G::NodeIterator,
2.124 - typename G::NodeType,
2.125 - bfs_node_data<G>,&NT::D> n_d; //node-> data
2.126 - */
2.127 - class
2.128 - {
2.129 - public:
2.130 - bfs_node_data<G> NodeType::*d;
2.131 - typedef bool value_type;
2.132 - void Put(typename G::NodeIterator &i, const value_type &t)
2.133 - {((*i).*d).visited=t;}
2.134 - value_type Get(const typename G::NodeIterator &i) const
2.135 - {return ((*i).*d).visited;}
2.136 - } visited;
2.137 -
2.138 - class
2.139 - {
2.140 - public:
2.141 - bfs_node_data<G> NodeType::*d;
2.142 - typedef typename G::EdgeIterator value_type;
2.143 - void Put(typename G::NodeIterator &i, const value_type &t)
2.144 - {((*i).*d).tree=t;}
2.145 - value_type Get(const typename G::NodeIterator &i) const
2.146 - {return ((*i).*d).tree;}
2.147 - } tree;
2.148 -
2.149 - class
2.150 - {
2.151 - public:
2.152 - bfs_node_data<G> NodeType::*d;
2.153 - typedef int value_type;
2.154 - void Put(typename G::NodeIterator &i, const value_type &t)
2.155 - {((*i).*d).dist=t;}
2.156 - value_type Get(const typename G::NodeIterator &i) const
2.157 - {return ((*i).*d).dist;}
2.158 - } dist;
2.159 -
2.160 - class
2.161 - {
2.162 - public:
2.163 - bfs_node_data<G> NodeType::*d;
2.164 - typedef int value_type;
2.165 - void Put(typename G::NodeIterator &i, const value_type &t)
2.166 - {((*i).*d).priority=t;}
2.167 - value_type Get(const typename G::NodeIterator &i) const
2.168 - {return ((*i).*d).priority;}
2.169 - } priority;
2.170 -
2.171 - //do_nothing_map tree; //node->EdgeIterator (W)
2.172 - // do_nothing_map dist; //node->int (W)
2.173 - // do_nothing_map priority; //node->int (W)
2.174 -
2.175 - void SetDataField(const bfs_node_data<G> NodeType::*dd)
2.176 - {
2.177 - tree.d=visited.d=dist.d=priority.d=dd;
2.178 - }
2.179 -
2.180 - bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
2.181 - {
2.182 - PutDataField(dd);
2.183 - }
2.184 -
2.185 - bfs_static_maps(const bfs_static_maps<G> &B)
2.186 - {
2.187 - tree.d=B.tree.d;visited.d=B.visited.d;
2.188 - dist.d=B.dist.d;priority.d=B.priority.d;
2.189 - }
2.190 -
2.191 - };
2.192 -
2.193 - template<typename I>
2.194 - struct BFS_Q
2.195 - {
2.196 - I n;
2.197 - int dist;
2.198 - // BFS_Q() {}
2.199 - // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
2.200 - };
2.201 -
2.202 - template<class G,class M>
2.203 - void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
2.204 - {
2.205 - using namespace std;
2.206 -
2.207 - typedef BFS_Q<typename G::NodeIterator> Q_T;
2.208 -
2.209 - Q_T q;
2.210 -
2.211 - int pr=0;
2.212 - typename G::NodeIterator n,m;
2.213 - typename G::OutEdgeIterator e;
2.214 - int d;
2.215 -
2.216 - for(Gr.GetFirst(n);n.isValid();++n)
2.217 - Put(maps.visited,n,false);
2.218 -
2.219 - queue<Q_T> Q;
2.220 -
2.221 - q.n=start_node;
2.222 - q.dist=0;
2.223 - Q.push(q);
2.224 - Put(maps.visited,start_node,true);
2.225 - // Put(maps::tree,start_node,?????);
2.226 - Put(maps.dist,start_node,0);
2.227 - Put(maps.priority,start_node,pr++);
2.228 -
2.229 - do {
2.230 - n=Q.front().n;d=Q.front().dist+1;
2.231 - Q.pop();
2.232 - for(Gr.GetFirst(e,n);e.isValid();++e)
2.233 - if(!Get(maps.visited,(m=e.Bnode()))) {
2.234 - q.n=m;
2.235 - q.dist=d;
2.236 - Q.push(q);
2.237 - Put(maps.visited,m,true);
2.238 - Put(maps.tree,m,e);
2.239 - Put(maps.dist,m,d);
2.240 - Put(maps.priority,m,pr++);
2.241 - }
2.242 - } while(!Q.empty());
2.243 - };
2.244 -
2.245 - // bfs algorithm class
2.246 -
2.247 - template<class G> //the default traits
2.248 - class default_bfs_T
2.249 - {
2.250 - public:
2.251 -
2.252 - typedef G Graph;
2.253 - typedef typename G::OutEdgeIterator SearchEdgeIterator;
2.254 -
2.255 - typedef typename G::NodeMap<bool> visited_map_t;
2.256 - typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
2.257 -
2.258 - typedef typename G::NodeMap<int> dist_map_t; //node->int (W)
2.259 - typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
2.260 -};
2.261 -
2.262 - template<class T>
2.263 - class Bfs
2.264 - {
2.265 - public:
2.266 - typedef typename T::Graph Graph;
2.267 - typedef typename Graph::NodeIterator NodeIterator;
2.268 - typedef typename Graph::EdgeIterator EdgeIterator;
2.269 -
2.270 - typedef typename T::SearchEdgeIterator SearchEdgeIterator;
2.271 -
2.272 - typename T::visited_map_t visited_map;
2.273 - typename T::tree_map_t tree_map;
2.274 - typename T::dist_map_t dist_map;
2.275 - typename T::priority_map_t priority_map;
2.276 -
2.277 - struct bfs_queue_cont
2.278 - {
2.279 - NodeIterator n;
2.280 - int dist;
2.281 - };
2.282 -
2.283 - std::queue<bfs_queue_cont> bfs_queue;
2.284 -
2.285 - int priority;
2.286 - Graph *G;
2.287 -
2.288 - //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
2.289 - Bfs() {}
2.290 -
2.291 - void SetG(Graph &Gr)
2.292 - {
2.293 - G=&Gr;
2.294 - visited_map.SetG(Gr);
2.295 - tree_map.SetG(Gr);
2.296 - dist_map.SetG(Gr);
2.297 - priority_map.SetG(Gr);
2.298 - }
2.299 -
2.300 - void Init()
2.301 - {
2.302 - //There must be a better way to do this:
2.303 - while(!bfs_queue.empty()) bfs_queue.pop();
2.304 -
2.305 - for(NodeIterator n(*G);n.isValid();++n)
2.306 - Put(visited_map,n,false);
2.307 -
2.308 - priority=0;
2.309 - }
2.310 -
2.311 - void AddStartNode(const NodeIterator &start_node,int dist=0)
2.312 - {
2.313 - bfs_queue_cont q;
2.314 - q.n=start_node;
2.315 - q.dist=dist;
2.316 - bfs_queue.push(q);
2.317 -
2.318 - Put(visited_map,start_node,true);
2.319 - // Put(tree_map,start_node,?????);
2.320 - Put(dist_map,start_node,dist);
2.321 - Put(priority_map,start_node,priority++);
2.322 - }
2.323 -
2.324 - void Init(const NodeIterator &start_node,int dist=0)
2.325 - {
2.326 - Init();
2.327 - AddStartNode(start_node,dist);
2.328 - }
2.329 -
2.330 - void Run()
2.331 - {
2.332 - NodeIterator n,m;
2.333 - int d;
2.334 -
2.335 - bfs_queue_cont q;
2.336 - while(!(bfs_queue.empty()/* && other stop conditions */)) {
2.337 - n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
2.338 - bfs_queue.pop();
2.339 - for(SearchEdgeIterator e(*G,n);e.isValid();++e)
2.340 - if(!Get(visited_map,(m=e.Bnode()))) {
2.341 - q.n=m;
2.342 - q.dist=d;
2.343 - bfs_queue.push(q);
2.344 - Put(visited_map,m,true);
2.345 - Put(tree_map,m,e);
2.346 - Put(dist_map,m,d);
2.347 - Put(priority_map,m,priority++);
2.348 - }
2.349 - }
2.350 - }
2.351 - };
2.352 -
2.353 -}
2.354 -
2.355 -#endif