12 // template <typename G,typename> class bfs_T
15 // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
16 // typedef Graph::NodeIterator NodeIterator;
26 // // template <bfs_T<G>>
27 // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
34 // typedef visited; //node->bool (RW)
35 // typedef tree; //node->EdgeIterator (W)
36 // typedef dist; //node->int (W)
37 // typedef priority; //node->int (W)
41 // Nem jo! Osszeakad a masik Put-tel
42 // class do_nothing_map {};
43 // template <typename V,typename T>
44 // void Put(const do_nothing_map &p,const V &v,const T &t) {}
46 struct do_nothing_map {
47 template <typename V,typename T>
48 static void Put(V v,T t) {}
52 template <typename I,typename C, typename T, T C::*M>
53 class class_element_map {
56 static void Put(const I &i, const T &t) {(*i).*M=t;}
57 static T Get(const I i) {return (*i).*M;}
58 T &operator[](I i) {return (*i).*M;}
62 template <typename C,typename I,typename T, T C::*M>
63 void Put(class_element_map<C,T,M> p,I i, T t)
69 template <typename P,typename I,typename T>
70 inline void Put(P &p,const I &i, const T &t)
74 template <typename P,typename I>
75 inline typename P::value_type Get(const P &p,const I &i)
81 template <typename G,typename T, typename G::EdgeType::*M>
82 T Get(edge_element_map p,G::EdgeIterator i)
90 class default_bfs_maps
93 typedef typename G::NodeType NodeType;
95 class_element_map<typename G::NodeIterator,
97 bool,&NodeType::isVis> visited; //node->bool (RW)
98 do_nothing_map tree; //node->EdgeIterator (W)
99 do_nothing_map dist; //node->int (W)
100 do_nothing_map priority; //node->int (W)
108 typename G::EdgeIterator tree;
114 class bfs_static_maps
117 typedef typename G::NodeType NodeType;
119 /* class_element_map<typename G::NodeIterator,
120 typename G::NodeType,
121 bfs_node_data<G>,&NT::D> n_d; //node-> data
126 bfs_node_data<G> NodeType::*d;
127 typedef bool value_type;
128 void Put(typename G::NodeIterator &i, const value_type &t)
129 {((*i).*d).visited=t;}
130 value_type Get(const typename G::NodeIterator &i) const
131 {return ((*i).*d).visited;}
137 bfs_node_data<G> NodeType::*d;
138 typedef typename G::EdgeIterator value_type;
139 void Put(typename G::NodeIterator &i, const value_type &t)
141 value_type Get(const typename G::NodeIterator &i) const
142 {return ((*i).*d).tree;}
148 bfs_node_data<G> NodeType::*d;
149 typedef int value_type;
150 void Put(typename G::NodeIterator &i, const value_type &t)
152 value_type Get(const typename G::NodeIterator &i) const
153 {return ((*i).*d).dist;}
159 bfs_node_data<G> NodeType::*d;
160 typedef int value_type;
161 void Put(typename G::NodeIterator &i, const value_type &t)
162 {((*i).*d).priority=t;}
163 value_type Get(const typename G::NodeIterator &i) const
164 {return ((*i).*d).priority;}
167 //do_nothing_map tree; //node->EdgeIterator (W)
168 // do_nothing_map dist; //node->int (W)
169 // do_nothing_map priority; //node->int (W)
171 void SetDataField(const bfs_node_data<G> NodeType::*dd)
173 tree.d=visited.d=dist.d=priority.d=dd;
176 bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
181 bfs_static_maps(const bfs_static_maps<G> &B)
183 tree.d=B.tree.d;visited.d=B.visited.d;
184 dist.d=B.dist.d;priority.d=B.priority.d;
195 // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
198 template<class G,class M>
199 void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
203 typedef BFS_Q<typename G::NodeIterator> Q_T;
208 typename G::NodeIterator n,m;
209 typename G::OutEdgeIterator e;
212 for(Gr.GetFirst(n);n.isValid();++n)
213 Put(maps.visited,n,false);
220 Put(maps.visited,start_node,true);
221 // Put(maps::tree,start_node,?????);
222 Put(maps.dist,start_node,0);
223 Put(maps.priority,start_node,pr++);
226 n=Q.front().n;d=Q.front().dist+1;
228 for(Gr.GetFirst(e,n);e.isValid();++e)
229 if(!Get(maps.visited,(m=e.Bnode()))) {
233 Put(maps.visited,m,true);
236 Put(maps.priority,m,pr++);