36 // typedef dist; //node->int (W) |
36 // typedef dist; //node->int (W) |
37 // typedef priority; //node->int (W) |
37 // typedef priority; //node->int (W) |
38 // }; |
38 // }; |
39 |
39 |
40 |
40 |
41 // Nem jo! Osszeakad a masik Set-tel |
41 // Nem jo! Osszeakad a masik Put-tel |
42 // class do_nothing_map {}; |
42 // class do_nothing_map {}; |
43 // template <typename V,typename T> |
43 // template <typename V,typename T> |
44 // void Set(const do_nothing_map &p,const V &v,const T &t) {} |
44 // void Put(const do_nothing_map &p,const V &v,const T &t) {} |
45 |
45 |
46 struct do_nothing_map { |
46 struct do_nothing_map { |
47 template <typename V,typename T> |
47 template <typename V,typename T> |
48 static void Set(V v,T t) {} |
48 static void Put(V v,T t) {} |
49 }; |
49 }; |
50 |
50 |
51 |
51 |
52 template <typename I,typename C, typename T, T C::*M> |
52 template <typename I,typename C, typename T, T C::*M> |
53 class class_element_map { |
53 class class_element_map { |
54 public: |
54 public: |
55 typedef T value_type; |
55 typedef T value_type; |
56 static void Set(const I &i, const T &t) {(*i).*M=t;} |
56 static void Put(const I &i, const T &t) {(*i).*M=t;} |
57 static T Get(const I i) {return (*i).*M;} |
57 static T Get(const I i) {return (*i).*M;} |
58 T &operator[](I i) {return (*i).*M;} |
58 T &operator[](I i) {return (*i).*M;} |
59 }; |
59 }; |
60 |
60 |
61 /* |
61 /* |
62 template <typename C,typename I,typename T, T C::*M> |
62 template <typename C,typename I,typename T, T C::*M> |
63 void Set(class_element_map<C,T,M> p,I i, T t) |
63 void Put(class_element_map<C,T,M> p,I i, T t) |
64 { |
64 { |
65 i->*M=t; |
65 i->*M=t; |
66 }; |
66 }; |
67 */ |
67 */ |
68 |
68 |
69 template <typename P,typename I,typename T> |
69 template <typename P,typename I,typename T> |
70 inline void Set(P &p,const I &i, const T &t) |
70 inline void Put(P &p,const I &i, const T &t) |
71 { |
71 { |
72 p.Set(i,t); |
72 p.Put(i,t); |
73 }; |
73 }; |
74 template <typename P,typename I> |
74 template <typename P,typename I> |
75 inline typename P::value_type Get(const P &p,const I &i) |
75 inline typename P::value_type Get(const P &p,const I &i) |
76 { |
76 { |
77 return p.Get(i); |
77 return p.Get(i); |
123 class |
123 class |
124 { |
124 { |
125 public: |
125 public: |
126 bfs_node_data<G> NodeType::*d; |
126 bfs_node_data<G> NodeType::*d; |
127 typedef bool value_type; |
127 typedef bool value_type; |
128 void Set(typename G::NodeIterator &i, const value_type &t) |
128 void Put(typename G::NodeIterator &i, const value_type &t) |
129 {((*i).*d).visited=t;} |
129 {((*i).*d).visited=t;} |
130 value_type Get(const typename G::NodeIterator &i) const |
130 value_type Get(const typename G::NodeIterator &i) const |
131 {return ((*i).*d).visited;} |
131 {return ((*i).*d).visited;} |
132 } visited; |
132 } visited; |
133 |
133 |
134 class |
134 class |
135 { |
135 { |
136 public: |
136 public: |
137 bfs_node_data<G> NodeType::*d; |
137 bfs_node_data<G> NodeType::*d; |
138 typedef typename G::EdgeIterator value_type; |
138 typedef typename G::EdgeIterator value_type; |
139 void Set(typename G::NodeIterator &i, const value_type &t) |
139 void Put(typename G::NodeIterator &i, const value_type &t) |
140 {((*i).*d).tree=t;} |
140 {((*i).*d).tree=t;} |
141 value_type Get(const typename G::NodeIterator &i) const |
141 value_type Get(const typename G::NodeIterator &i) const |
142 {return ((*i).*d).tree;} |
142 {return ((*i).*d).tree;} |
143 } tree; |
143 } tree; |
144 |
144 |
145 class |
145 class |
146 { |
146 { |
147 public: |
147 public: |
148 bfs_node_data<G> NodeType::*d; |
148 bfs_node_data<G> NodeType::*d; |
149 typedef int value_type; |
149 typedef int value_type; |
150 void Set(typename G::NodeIterator &i, const value_type &t) |
150 void Put(typename G::NodeIterator &i, const value_type &t) |
151 {((*i).*d).dist=t;} |
151 {((*i).*d).dist=t;} |
152 value_type Get(const typename G::NodeIterator &i) const |
152 value_type Get(const typename G::NodeIterator &i) const |
153 {return ((*i).*d).dist;} |
153 {return ((*i).*d).dist;} |
154 } dist; |
154 } dist; |
155 |
155 |
156 class |
156 class |
157 { |
157 { |
158 public: |
158 public: |
159 bfs_node_data<G> NodeType::*d; |
159 bfs_node_data<G> NodeType::*d; |
160 typedef int value_type; |
160 typedef int value_type; |
161 void Set(typename G::NodeIterator &i, const value_type &t) |
161 void Put(typename G::NodeIterator &i, const value_type &t) |
162 {((*i).*d).priority=t;} |
162 {((*i).*d).priority=t;} |
163 value_type Get(const typename G::NodeIterator &i) const |
163 value_type Get(const typename G::NodeIterator &i) const |
164 {return ((*i).*d).priority;} |
164 {return ((*i).*d).priority;} |
165 } priority; |
165 } priority; |
166 |
166 |
208 typename G::NodeIterator n,m; |
208 typename G::NodeIterator n,m; |
209 typename G::OutEdgeIterator e; |
209 typename G::OutEdgeIterator e; |
210 int d; |
210 int d; |
211 |
211 |
212 for(Gr.GetFirst(n);n.isValid();++n) |
212 for(Gr.GetFirst(n);n.isValid();++n) |
213 Set(maps.visited,n,false); |
213 Put(maps.visited,n,false); |
214 |
214 |
215 queue<Q_T> Q; |
215 queue<Q_T> Q; |
216 |
216 |
217 q.n=start_node; |
217 q.n=start_node; |
218 q.dist=0; |
218 q.dist=0; |
219 Q.push(q); |
219 Q.push(q); |
220 Set(maps.visited,start_node,true); |
220 Put(maps.visited,start_node,true); |
221 // Set(maps::tree,start_node,?????); |
221 // Put(maps::tree,start_node,?????); |
222 Set(maps.dist,start_node,0); |
222 Put(maps.dist,start_node,0); |
223 Set(maps.priority,start_node,pr++); |
223 Put(maps.priority,start_node,pr++); |
224 |
224 |
225 do { |
225 do { |
226 n=Q.front().n;d=Q.front().dist+1; |
226 n=Q.front().n;d=Q.front().dist+1; |
227 Q.pop(); |
227 Q.pop(); |
228 for(Gr.GetFirst(e,n);e.isValid();++e) |
228 for(Gr.GetFirst(e,n);e.isValid();++e) |
229 if(!Get(maps.visited,(m=e.Bnode()))) { |
229 if(!Get(maps.visited,(m=e.Bnode()))) { |
230 q.n=m; |
230 q.n=m; |
231 q.dist=d; |
231 q.dist=d; |
232 Q.push(q); |
232 Q.push(q); |
233 Set(maps.visited,m,true); |
233 Put(maps.visited,m,true); |
234 Set(maps.tree,m,e); |
234 Put(maps.tree,m,e); |
235 Set(maps.dist,m,d); |
235 Put(maps.dist,m,d); |
236 Set(maps.priority,m,pr++); |
236 Put(maps.priority,m,pr++); |
237 } |
237 } |
238 } while(!Q.empty()); |
238 } while(!Q.empty()); |
239 }; |
239 }; |
240 } |
240 } |
241 #endif |
241 #endif |