1.1 --- a/src/include/bfs.h Sat Dec 13 15:44:50 2003 +0000
1.2 +++ b/src/include/bfs.h Sun Dec 14 15:32:46 2003 +0000
1.3 @@ -9,43 +9,44 @@
1.4 {
1.5 using namespace std;
1.6
1.7 -// template <typename G,typename> class bfs_T
1.8 -// {
1.9 -// typedef G Graph;
1.10 -// typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
1.11 -// typedef Graph::NodeIterator NodeIterator;
1.12 + // template <typename G,typename> class bfs_T
1.13 + // {
1.14 + // typedef G Graph;
1.15 + // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
1.16 + // typedef Graph::NodeIterator NodeIterator;
1.17
1.18 -// class bfs_node_D
1.19 -// {
1.20 -// EdgeIterator Tree;
1.21 -// int Dist;
1.22 -// int Priority;
1.23 -// }
1.24 + // class bfs_node_D
1.25 + // {
1.26 + // EdgeIterator Tree;
1.27 + // int Dist;
1.28 + // int Priority;
1.29 + // }
1.30 + // }
1.31
1.32
1.33 -// // template <bfs_T<G>>
1.34 -// // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
1.35 + // // template <bfs_T<G>>
1.36 + // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
1.37
1.38
1.39
1.40 -// template <class G>
1.41 -// class bfs_maps_T
1.42 -// {
1.43 -// typedef visited; //node->bool (RW)
1.44 -// typedef tree; //node->EdgeIterator (W)
1.45 -// typedef dist; //node->int (W)
1.46 -// typedef priority; //node->int (W)
1.47 -// };
1.48 + // template <class G>
1.49 + // class bfs_maps_T
1.50 + // {
1.51 + // typedef visited; //node->bool (RW)
1.52 + // typedef tree; //node->EdgeIterator (W)
1.53 + // typedef dist; //node->int (W)
1.54 + // typedef priority; //node->int (W)
1.55 + // };
1.56
1.57
1.58 -// Nem jo! Osszeakad a masik Put-tel
1.59 -// class do_nothing_map {};
1.60 -// template <typename V,typename T>
1.61 -// void Put(const do_nothing_map &p,const V &v,const T &t) {}
1.62 + // Nem jo! Osszeakad a masik Put-tal
1.63 + // class do_nothing_map {};
1.64 + // template <typename V,typename T>
1.65 + // void Put(const do_nothing_map &p,const V &v,const T &t) {}
1.66
1.67 struct do_nothing_map {
1.68 - template <typename V,typename T>
1.69 - static void Put(V v,T t) {}
1.70 + template <typename V,typename T>
1.71 + static void Put(V v,T t) {}
1.72 };
1.73
1.74
1.75 @@ -78,27 +79,27 @@
1.76 };
1.77
1.78 /*
1.79 - template <typename G,typename T, typename G::EdgeType::*M>
1.80 - T Get(edge_element_map p,G::EdgeIterator i)
1.81 - {
1.82 + template <typename G,typename T, typename G::EdgeType::*M>
1.83 + T Get(edge_element_map p,G::EdgeIterator i)
1.84 + {
1.85 return i->*M;
1.86 - };
1.87 + };
1.88 */
1.89
1.90 /*
1.91 - template <class G>
1.92 - class default_bfs_maps
1.93 - {
1.94 - public:
1.95 - typedef typename G::NodeType NodeType;
1.96 + template <class G>
1.97 + class default_bfs_maps
1.98 + {
1.99 + public:
1.100 + typedef typename G::NodeType NodeType;
1.101
1.102 - class_element_map<typename G::NodeIterator,
1.103 - typename G::NodeType,
1.104 - bool,&NodeType::isVis> visited; //node->bool (RW)
1.105 - do_nothing_map tree; //node->EdgeIterator (W)
1.106 - do_nothing_map dist; //node->int (W)
1.107 - do_nothing_map priority; //node->int (W)
1.108 - };
1.109 + class_element_map<typename G::NodeIterator,
1.110 + typename G::NodeType,
1.111 + bool,&NodeType::isVis> visited; //node->bool (RW)
1.112 + do_nothing_map tree; //node->EdgeIterator (W)
1.113 + do_nothing_map dist; //node->int (W)
1.114 + do_nothing_map priority; //node->int (W)
1.115 + };
1.116 */
1.117
1.118 template<class G>
1.119 @@ -117,8 +118,8 @@
1.120 typedef typename G::NodeType NodeType;
1.121
1.122 /* class_element_map<typename G::NodeIterator,
1.123 - typename G::NodeType,
1.124 - bfs_node_data<G>,&NT::D> n_d; //node-> data
1.125 + typename G::NodeType,
1.126 + bfs_node_data<G>,&NT::D> n_d; //node-> data
1.127 */
1.128 class
1.129 {
1.130 @@ -196,7 +197,7 @@
1.131 };
1.132
1.133 template<class G,class M>
1.134 - void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
1.135 + void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
1.136 {
1.137 using namespace std;
1.138
1.139 @@ -237,5 +238,94 @@
1.140 }
1.141 } while(!Q.empty());
1.142 };
1.143 +
1.144 + // bfs algorithm class
1.145 + template<class T>
1.146 + class Bfs
1.147 + {
1.148 + public:
1.149 + typedef typename T::Graph_t Graph;
1.150 + typedef typename Graph::NodeIterator NodeIterator;
1.151 + typedef typename Graph::EdgeIterator EdgeIterator;
1.152 +
1.153 + typedef typename T::SearchEdgeIterator SearchEdgeIterator;
1.154 +
1.155 + typename T::visited_map_t visited_map;
1.156 + typename T::tree_map_t tree_map;
1.157 + typename T::dist_map_t dist_map;
1.158 + typename T::priority_map_t priority_map;
1.159 +
1.160 + struct bfs_queue_cont
1.161 + {
1.162 + NodeIterator n;
1.163 + int dist;
1.164 + };
1.165 +
1.166 + std::queue<bfs_queue_cont> bfs_queue;
1.167 +
1.168 + int priority;
1.169 + Graph *G;
1.170 +
1.171 + void SetG(Graph &Gr)
1.172 + {
1.173 + G=&Gr;
1.174 + }
1.175 +
1.176 + void Init()
1.177 + {
1.178 + //There must be a better way to do this:
1.179 + while(!bfs_queue.empty()) bfs_queue.pop();
1.180 +
1.181 + for(NodeIterator n(*G);n.isValid();++n)
1.182 + Put(visited_map,n,false);
1.183 +
1.184 + priority=0;
1.185 +
1.186 + }
1.187 +
1.188 + void AddStartNode(const NodeIterator &start_node,int dist=0)
1.189 + {
1.190 + bfs_queue_cont q;
1.191 + q.n=start_node;
1.192 + q.dist=dist;
1.193 + bfs_queue.push(q);
1.194 +
1.195 + Put(visited_map,start_node,true);
1.196 + // Put(tree_map,start_node,?????);
1.197 + Put(dist_map,start_node,dist);
1.198 + Put(priority_map,start_node,priority++);
1.199 + }
1.200 +
1.201 + void Init(const NodeIterator &start_node,int dist=0)
1.202 + {
1.203 +
1.204 + Init();
1.205 + AddStartNode(start_node,dist);
1.206 + }
1.207 +
1.208 + void Run()
1.209 + {
1.210 + NodeIterator n,m;
1.211 + int d;
1.212 +
1.213 + bfs_queue_cont q;
1.214 + while(!(bfs_queue.empty()/* && other stop conditions */)) {
1.215 + n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
1.216 + bfs_queue.pop();
1.217 + for(SearchEdgeIterator e(*G,n);e.isValid();++e)
1.218 + if(!Get(visited_map,(m=e.Bnode()))) {
1.219 + q.n=m;
1.220 + q.dist=d;
1.221 + bfs_queue.push(q);
1.222 + Put(visited_map,m,true);
1.223 + Put(tree_map,m,e);
1.224 + Put(dist_map,m,d);
1.225 + Put(priority_map,m,priority++);
1.226 + }
1.227 + }
1.228 + }
1.229 + };
1.230 +
1.231 }
1.232 +
1.233 #endif
2.1 --- a/src/work/bfsdemo.cc Sat Dec 13 15:44:50 2003 +0000
2.2 +++ b/src/work/bfsdemo.cc Sun Dec 14 15:32:46 2003 +0000
2.3 @@ -24,6 +24,9 @@
2.4 NodeType *operator ->() const { return &(G->nodes[n]);}
2.5 bool isValid() const {return n<=5000;}
2.6 int Index() {return n;} //csak a kiirashoz kell
2.7 +
2.8 + NodeIterator() {}
2.9 + NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.
2.10 };
2.11
2.12 void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
2.13 @@ -40,6 +43,10 @@
2.14 NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
2.15 NodeIterator Anode() const {return From();}
2.16 NodeIterator Bnode() const {return To();}
2.17 +
2.18 + OutEdgeIterator() {}
2.19 + OutEdgeIterator(IGraph &Gr,NodeIterator &n) //Bfs class prefer this.
2.20 + {G=&Gr;f=n.n;t=0;operator++();}
2.21 };
2.22
2.23 typedef OutEdgeIterator EdgeIterator;
2.24 @@ -70,14 +77,48 @@
2.25 do_nothing_map priority; //node->int (W)
2.26 };
2.27
2.28 +// New style bfs traits
2.29 +class BFS_T
2.30 +{
2.31 +public:
2.32 +
2.33 + typedef IGraph Graph_t;
2.34 + typedef IGraph::OutEdgeIterator SearchEdgeIterator;
2.35 +
2.36 + struct visited_map_t {
2.37 + typedef bool value_type;
2.38 + void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
2.39 + value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
2.40 + };
2.41 + struct tree_map_t {
2.42 + typedef IGraph::EdgeIterator value_type;
2.43 + void Put(const IGraph::NodeIterator &n,const value_type &t)
2.44 + { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
2.45 + };
2.46 + typedef do_nothing_map dist_map_t; //node->int (W)
2.47 + typedef do_nothing_map priority_map_t; //node->int (W)
2.48 +};
2.49 +
2.50
2.51 int main()
2.52 {
2.53 IGraph IG;
2.54 - IMaps_t IMaps;
2.55
2.56 +// //Function-syte calling
2.57 +// IMaps_t IMaps;
2.58 +
2.59 +// IGraph::NodeIterator in;
2.60 +// IG.GetFirst(in);
2.61 +// ++in;
2.62 +// bfs_fn(IG,in,IMaps);
2.63 +
2.64 + //Class-style calling:
2.65 +
2.66 IGraph::NodeIterator in;
2.67 IG.GetFirst(in);
2.68 ++in;
2.69 - bfs(IG,in,IMaps);
2.70 + Bfs<BFS_T> bfs;
2.71 + bfs.SetG(IG);
2.72 + bfs.Init(in);
2.73 + bfs.Run();
2.74 }