Changeset 4:8009bb5ddd09 in lemon0.x
 Timestamp:
 12/14/03 16:32:46 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@16
 Location:
 src
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/include/bfs.h
r3 r4 10 10 using namespace std; 11 11 12 // template <typename G,typename> class bfs_T 13 // { 14 // typedef G Graph; 15 // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell 16 // typedef Graph::NodeIterator NodeIterator; 17 18 // class bfs_node_D 19 // { 20 // EdgeIterator Tree; 21 // int Dist; 22 // int Priority; 23 // } 24 25 26 // // template <bfs_T<G>> 27 // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps) 28 29 30 31 // template <class G> 32 // class bfs_maps_T 33 // { 34 // typedef visited; //node>bool (RW) 35 // typedef tree; //node>EdgeIterator (W) 36 // typedef dist; //node>int (W) 37 // typedef priority; //node>int (W) 38 // }; 39 40 41 // Nem jo! Osszeakad a masik Puttel 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) {} 12 // template <typename G,typename> class bfs_T 13 // { 14 // typedef G Graph; 15 // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell 16 // typedef Graph::NodeIterator NodeIterator; 17 18 // class bfs_node_D 19 // { 20 // EdgeIterator Tree; 21 // int Dist; 22 // int Priority; 23 // } 24 // } 25 26 27 // // template <bfs_T<G>> 28 // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps) 29 30 31 32 // template <class G> 33 // class bfs_maps_T 34 // { 35 // typedef visited; //node>bool (RW) 36 // typedef tree; //node>EdgeIterator (W) 37 // typedef dist; //node>int (W) 38 // typedef priority; //node>int (W) 39 // }; 40 41 42 // Nem jo! Osszeakad a masik Puttal 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) {} 45 46 46 47 struct do_nothing_map { 47 template <typename V,typename T>48 static void Put(V v,T t) {}48 template <typename V,typename T> 49 static void Put(V v,T t) {} 49 50 }; 50 51 … … 79 80 80 81 /* 81 template <typename G,typename T, typename G::EdgeType::*M>82 T Get(edge_element_map p,G::EdgeIterator i)83 {82 template <typename G,typename T, typename G::EdgeType::*M> 83 T Get(edge_element_map p,G::EdgeIterator i) 84 { 84 85 return i>*M; 85 };86 }; 86 87 */ 87 88 88 89 /* 89 template <class G>90 class default_bfs_maps91 {92 public:93 typedef typename G::NodeType NodeType;94 95 class_element_map<typename G::NodeIterator,96 97 98 do_nothing_map tree; //node>EdgeIterator (W)99 do_nothing_map dist; //node>int (W)100 do_nothing_map priority; //node>int (W)101 };90 template <class G> 91 class default_bfs_maps 92 { 93 public: 94 typedef typename G::NodeType NodeType; 95 96 class_element_map<typename G::NodeIterator, 97 typename G::NodeType, 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) 102 }; 102 103 */ 103 104 … … 118 119 119 120 /* class_element_map<typename G::NodeIterator, 120 121 121 typename G::NodeType, 122 bfs_node_data<G>,&NT::D> n_d; //node> data 122 123 */ 123 124 class … … 197 198 198 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 202 using namespace std; … … 238 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 331 #endif 
src/work/bfsdemo.cc
r3 r4 25 25 bool isValid() const {return n<=5000;} 26 26 int Index() {return n;} //csak a kiirashoz kell 27 28 NodeIterator() {} 29 NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this. 27 30 }; 28 31 … … 41 44 NodeIterator Anode() const {return From();} 42 45 NodeIterator Bnode() const {return To();} 46 47 OutEdgeIterator() {} 48 OutEdgeIterator(IGraph &Gr,NodeIterator &n) //Bfs class prefer this. 49 {G=&Gr;f=n.n;t=0;operator++();} 43 50 }; 44 51 … … 71 78 }; 72 79 80 // New style bfs traits 81 class BFS_T 82 { 83 public: 84 85 typedef IGraph Graph_t; 86 typedef IGraph::OutEdgeIterator SearchEdgeIterator; 87 88 struct visited_map_t { 89 typedef bool value_type; 90 void Put(const IGraph::NodeIterator &n,const value_type &t) { n>isVis=t; } 91 value_type Get(const IGraph::NodeIterator &n) const { return n>isVis; } 92 }; 93 struct tree_map_t { 94 typedef IGraph::EdgeIterator value_type; 95 void Put(const IGraph::NodeIterator &n,const value_type &t) 96 { cout << t.From().Index() << ">" << t.To().Index() << '\n'; } 97 }; 98 typedef do_nothing_map dist_map_t; //node>int (W) 99 typedef do_nothing_map priority_map_t; //node>int (W) 100 }; 101 73 102 74 103 int main() 75 104 { 76 105 IGraph IG; 77 IMaps_t IMaps;78 106 107 // //Functionsyte calling 108 // IMaps_t IMaps; 109 110 // IGraph::NodeIterator in; 111 // IG.GetFirst(in); 112 // ++in; 113 // bfs_fn(IG,in,IMaps); 114 115 //Classstyle calling: 116 79 117 IGraph::NodeIterator in; 80 118 IG.GetFirst(in); 81 119 ++in; 82 bfs(IG,in,IMaps); 120 Bfs<BFS_T> bfs; 121 bfs.SetG(IG); 122 bfs.Init(in); 123 bfs.Run(); 83 124 }
Note: See TracChangeset
for help on using the changeset viewer.