Step toward to a standardised graph interface.
12 // template <typename G,typename> class bfs_T
15 // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
16 // typedef Graph::NodeIterator NodeIterator;
27 // // template <bfs_T<G>>
28 // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
35 // typedef visited; //node->bool (RW)
36 // typedef tree; //node->EdgeIterator (W)
37 // typedef dist; //node->int (W)
38 // typedef priority; //node->int (W)
42 // Nem jo! Osszeakad a masik Put-tal
43 // class do_nothing_map {};
44 // template <typename V,typename T>
45 // void Put(const do_nothing_map &p,const V &v,const T &t) {}
47 struct do_nothing_map {
48 template <typename V,typename T> static void Put(V v,T t) {}
49 template <typename G> void SetG(G &g) {}
53 template <typename I,typename C, typename T, T C::*M>
54 class class_element_map {
57 static void Put(const I &i, const T &t) {(*i).*M=t;}
58 static T Get(const I i) {return (*i).*M;}
59 T &operator[](I i) {return (*i).*M;}
63 template <typename C,typename I,typename T, T C::*M>
64 void Put(class_element_map<C,T,M> p,I i, T t)
70 template <typename P,typename I,typename T>
71 inline void Put(P &p,const I &i, const T &t)
75 template <typename P,typename I>
76 inline typename P::value_type Get(const P &p,const I &i)
82 template <typename G,typename T, typename G::EdgeType::*M>
83 T Get(edge_element_map p,G::EdgeIterator i)
91 class default_bfs_maps
94 typedef typename G::NodeType NodeType;
96 class_element_map<typename G::NodeIterator,
98 bool,&NodeType::isVis> visited; //node->bool (RW)
99 do_nothing_map tree; //node->EdgeIterator (W)
100 do_nothing_map dist; //node->int (W)
101 do_nothing_map priority; //node->int (W)
109 typename G::EdgeIterator tree;
115 class bfs_static_maps
118 typedef typename G::NodeType NodeType;
120 /* class_element_map<typename G::NodeIterator,
121 typename G::NodeType,
122 bfs_node_data<G>,&NT::D> n_d; //node-> data
127 bfs_node_data<G> NodeType::*d;
128 typedef bool value_type;
129 void Put(typename G::NodeIterator &i, const value_type &t)
130 {((*i).*d).visited=t;}
131 value_type Get(const typename G::NodeIterator &i) const
132 {return ((*i).*d).visited;}
138 bfs_node_data<G> NodeType::*d;
139 typedef typename G::EdgeIterator value_type;
140 void Put(typename G::NodeIterator &i, const value_type &t)
142 value_type Get(const typename G::NodeIterator &i) const
143 {return ((*i).*d).tree;}
149 bfs_node_data<G> NodeType::*d;
150 typedef int value_type;
151 void Put(typename G::NodeIterator &i, const value_type &t)
153 value_type Get(const typename G::NodeIterator &i) const
154 {return ((*i).*d).dist;}
160 bfs_node_data<G> NodeType::*d;
161 typedef int value_type;
162 void Put(typename G::NodeIterator &i, const value_type &t)
163 {((*i).*d).priority=t;}
164 value_type Get(const typename G::NodeIterator &i) const
165 {return ((*i).*d).priority;}
168 //do_nothing_map tree; //node->EdgeIterator (W)
169 // do_nothing_map dist; //node->int (W)
170 // do_nothing_map priority; //node->int (W)
172 void SetDataField(const bfs_node_data<G> NodeType::*dd)
174 tree.d=visited.d=dist.d=priority.d=dd;
177 bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
182 bfs_static_maps(const bfs_static_maps<G> &B)
184 tree.d=B.tree.d;visited.d=B.visited.d;
185 dist.d=B.dist.d;priority.d=B.priority.d;
196 // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
199 template<class G,class M>
200 void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
204 typedef BFS_Q<typename G::NodeIterator> Q_T;
209 typename G::NodeIterator n,m;
210 typename G::OutEdgeIterator e;
213 for(Gr.GetFirst(n);n.isValid();++n)
214 Put(maps.visited,n,false);
221 Put(maps.visited,start_node,true);
222 // Put(maps::tree,start_node,?????);
223 Put(maps.dist,start_node,0);
224 Put(maps.priority,start_node,pr++);
227 n=Q.front().n;d=Q.front().dist+1;
229 for(Gr.GetFirst(e,n);e.isValid();++e)
230 if(!Get(maps.visited,(m=e.Bnode()))) {
234 Put(maps.visited,m,true);
237 Put(maps.priority,m,pr++);
242 // bfs algorithm class
244 template<class G> //the default traits
250 typedef typename G::OutEdgeIterator SearchEdgeIterator;
252 typedef typename G::NodeMap<bool> visited_map_t;
253 typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
255 typedef typename G::NodeMap<int> dist_map_t; //node->int (W)
256 typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
263 typedef typename T::Graph Graph;
264 typedef typename Graph::NodeIterator NodeIterator;
265 typedef typename Graph::EdgeIterator EdgeIterator;
267 typedef typename T::SearchEdgeIterator SearchEdgeIterator;
269 typename T::visited_map_t visited_map;
270 typename T::tree_map_t tree_map;
271 typename T::dist_map_t dist_map;
272 typename T::priority_map_t priority_map;
274 struct bfs_queue_cont
280 std::queue<bfs_queue_cont> bfs_queue;
285 //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
291 visited_map.SetG(Gr);
294 priority_map.SetG(Gr);
299 //There must be a better way to do this:
300 while(!bfs_queue.empty()) bfs_queue.pop();
302 for(NodeIterator n(*G);n.isValid();++n)
303 Put(visited_map,n,false);
308 void AddStartNode(const NodeIterator &start_node,int dist=0)
315 Put(visited_map,start_node,true);
316 // Put(tree_map,start_node,?????);
317 Put(dist_map,start_node,dist);
318 Put(priority_map,start_node,priority++);
321 void Init(const NodeIterator &start_node,int dist=0)
324 AddStartNode(start_node,dist);
333 while(!(bfs_queue.empty()/* && other stop conditions */)) {
334 n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
336 for(SearchEdgeIterator e(*G,n);e.isValid();++e)
337 if(!Get(visited_map,(m=e.Bnode()))) {
341 Put(visited_map,m,true);
344 Put(priority_map,m,priority++);