7 |
7 |
8 namespace NEGRO |
8 namespace NEGRO |
9 { |
9 { |
10 using namespace std; |
10 using namespace std; |
11 |
11 |
12 // template <typename G,typename> class bfs_T |
12 // template <typename G,typename> class bfs_T |
13 // { |
13 // { |
14 // typedef G Graph; |
14 // typedef G Graph; |
15 // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell |
15 // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell |
16 // typedef Graph::NodeIterator NodeIterator; |
16 // typedef Graph::NodeIterator NodeIterator; |
17 |
17 |
18 // class bfs_node_D |
18 // class bfs_node_D |
19 // { |
19 // { |
20 // EdgeIterator Tree; |
20 // EdgeIterator Tree; |
21 // int Dist; |
21 // int Dist; |
22 // int Priority; |
22 // int Priority; |
23 // } |
23 // } |
24 |
24 // } |
25 |
25 |
26 // // template <bfs_T<G>> |
26 |
27 // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps) |
27 // // template <bfs_T<G>> |
28 |
28 // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps) |
29 |
29 |
30 |
30 |
31 // template <class G> |
31 |
32 // class bfs_maps_T |
32 // template <class G> |
33 // { |
33 // class bfs_maps_T |
34 // typedef visited; //node->bool (RW) |
34 // { |
35 // typedef tree; //node->EdgeIterator (W) |
35 // typedef visited; //node->bool (RW) |
36 // typedef dist; //node->int (W) |
36 // typedef tree; //node->EdgeIterator (W) |
37 // typedef priority; //node->int (W) |
37 // typedef dist; //node->int (W) |
38 // }; |
38 // typedef priority; //node->int (W) |
39 |
39 // }; |
40 |
40 |
41 // Nem jo! Osszeakad a masik Put-tel |
41 |
42 // class do_nothing_map {}; |
42 // Nem jo! Osszeakad a masik Put-tal |
43 // template <typename V,typename T> |
43 // class do_nothing_map {}; |
44 // void Put(const do_nothing_map &p,const V &v,const T &t) {} |
44 // template <typename V,typename T> |
|
45 // void Put(const do_nothing_map &p,const V &v,const T &t) {} |
45 |
46 |
46 struct do_nothing_map { |
47 struct do_nothing_map { |
47 template <typename V,typename T> |
48 template <typename V,typename T> |
48 static void Put(V v,T t) {} |
49 static void Put(V v,T t) {} |
49 }; |
50 }; |
50 |
51 |
51 |
52 |
52 template <typename I,typename C, typename T, T C::*M> |
53 template <typename I,typename C, typename T, T C::*M> |
53 class class_element_map { |
54 class class_element_map { |
76 { |
77 { |
77 return p.Get(i); |
78 return p.Get(i); |
78 }; |
79 }; |
79 |
80 |
80 /* |
81 /* |
81 template <typename G,typename T, typename G::EdgeType::*M> |
82 template <typename G,typename T, typename G::EdgeType::*M> |
82 T Get(edge_element_map p,G::EdgeIterator i) |
83 T Get(edge_element_map p,G::EdgeIterator i) |
83 { |
84 { |
84 return i->*M; |
85 return i->*M; |
85 }; |
86 }; |
86 */ |
87 */ |
87 |
88 |
88 /* |
89 /* |
89 template <class G> |
90 template <class G> |
90 class default_bfs_maps |
91 class default_bfs_maps |
91 { |
92 { |
92 public: |
93 public: |
93 typedef typename G::NodeType NodeType; |
94 typedef typename G::NodeType NodeType; |
94 |
95 |
95 class_element_map<typename G::NodeIterator, |
96 class_element_map<typename G::NodeIterator, |
96 typename G::NodeType, |
97 typename G::NodeType, |
97 bool,&NodeType::isVis> visited; //node->bool (RW) |
98 bool,&NodeType::isVis> visited; //node->bool (RW) |
98 do_nothing_map tree; //node->EdgeIterator (W) |
99 do_nothing_map tree; //node->EdgeIterator (W) |
99 do_nothing_map dist; //node->int (W) |
100 do_nothing_map dist; //node->int (W) |
100 do_nothing_map priority; //node->int (W) |
101 do_nothing_map priority; //node->int (W) |
101 }; |
102 }; |
102 */ |
103 */ |
103 |
104 |
104 template<class G> |
105 template<class G> |
105 struct bfs_node_data |
106 struct bfs_node_data |
106 { |
107 { |
115 { |
116 { |
116 public: |
117 public: |
117 typedef typename G::NodeType NodeType; |
118 typedef typename G::NodeType NodeType; |
118 |
119 |
119 /* class_element_map<typename G::NodeIterator, |
120 /* class_element_map<typename G::NodeIterator, |
120 typename G::NodeType, |
121 typename G::NodeType, |
121 bfs_node_data<G>,&NT::D> n_d; //node-> data |
122 bfs_node_data<G>,&NT::D> n_d; //node-> data |
122 */ |
123 */ |
123 class |
124 class |
124 { |
125 { |
125 public: |
126 public: |
126 bfs_node_data<G> NodeType::*d; |
127 bfs_node_data<G> NodeType::*d; |
194 // BFS_Q() {} |
195 // BFS_Q() {} |
195 // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;} |
196 // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;} |
196 }; |
197 }; |
197 |
198 |
198 template<class G,class M> |
199 template<class G,class M> |
199 void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps) |
200 void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps) |
200 { |
201 { |
201 using namespace std; |
202 using namespace std; |
202 |
203 |
203 typedef BFS_Q<typename G::NodeIterator> Q_T; |
204 typedef BFS_Q<typename G::NodeIterator> Q_T; |
204 |
205 |
235 Put(maps.dist,m,d); |
236 Put(maps.dist,m,d); |
236 Put(maps.priority,m,pr++); |
237 Put(maps.priority,m,pr++); |
237 } |
238 } |
238 } while(!Q.empty()); |
239 } while(!Q.empty()); |
239 }; |
240 }; |
|
241 |
|
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; |
|
250 |
|
251 typedef typename T::SearchEdgeIterator SearchEdgeIterator; |
|
252 |
|
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; |
|
257 |
|
258 struct bfs_queue_cont |
|
259 { |
|
260 NodeIterator n; |
|
261 int dist; |
|
262 }; |
|
263 |
|
264 std::queue<bfs_queue_cont> bfs_queue; |
|
265 |
|
266 int priority; |
|
267 Graph *G; |
|
268 |
|
269 void SetG(Graph &Gr) |
|
270 { |
|
271 G=&Gr; |
|
272 } |
|
273 |
|
274 void Init() |
|
275 { |
|
276 //There must be a better way to do this: |
|
277 while(!bfs_queue.empty()) bfs_queue.pop(); |
|
278 |
|
279 for(NodeIterator n(*G);n.isValid();++n) |
|
280 Put(visited_map,n,false); |
|
281 |
|
282 priority=0; |
|
283 |
|
284 } |
|
285 |
|
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); |
|
292 |
|
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 } |
|
298 |
|
299 void Init(const NodeIterator &start_node,int dist=0) |
|
300 { |
|
301 |
|
302 Init(); |
|
303 AddStartNode(start_node,dist); |
|
304 } |
|
305 |
|
306 void Run() |
|
307 { |
|
308 NodeIterator n,m; |
|
309 int d; |
|
310 |
|
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 }; |
|
328 |
240 } |
329 } |
|
330 |
241 #endif |
331 #endif |