1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/include/bfs.h Thu Dec 11 07:24:53 2003 +0000
1.3 @@ -0,0 +1,241 @@
1.4 +// -*-mode: c++; -*-
1.5 +#ifndef _BFS_H_
1.6 +#define _BFS_H_
1.7 +
1.8 +#include <queue>
1.9 +#include <graph.h>
1.10 +
1.11 +namespace NEGRO
1.12 +{
1.13 + using namespace std;
1.14 +
1.15 +// template <typename G,typename> class bfs_T
1.16 +// {
1.17 +// typedef G Graph;
1.18 +// typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
1.19 +// typedef Graph::NodeIterator NodeIterator;
1.20 +
1.21 +// class bfs_node_D
1.22 +// {
1.23 +// EdgeIterator Tree;
1.24 +// int Dist;
1.25 +// int Priority;
1.26 +// }
1.27 +
1.28 +
1.29 +// // template <bfs_T<G>>
1.30 +// // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
1.31 +
1.32 +
1.33 +
1.34 +// template <class G>
1.35 +// class bfs_maps_T
1.36 +// {
1.37 +// typedef visited; //node->bool (RW)
1.38 +// typedef tree; //node->EdgeIterator (W)
1.39 +// typedef dist; //node->int (W)
1.40 +// typedef priority; //node->int (W)
1.41 +// };
1.42 +
1.43 +
1.44 +// Nem jo! Osszeakad a masik Set-tel
1.45 +// class do_nothing_map {};
1.46 +// template <typename V,typename T>
1.47 +// void Set(const do_nothing_map &p,const V &v,const T &t) {}
1.48 +
1.49 + struct do_nothing_map {
1.50 + template <typename V,typename T>
1.51 + static void Set(V v,T t) {}
1.52 + };
1.53 +
1.54 +
1.55 + template <typename I,typename C, typename T, T C::*M>
1.56 + class class_element_map {
1.57 + public:
1.58 + typedef T value_type;
1.59 + static void Set(const I &i, const T &t) {(*i).*M=t;}
1.60 + static T Get(const I i) {return (*i).*M;}
1.61 + T &operator[](I i) {return (*i).*M;}
1.62 + };
1.63 +
1.64 + /*
1.65 + template <typename C,typename I,typename T, T C::*M>
1.66 + void Set(class_element_map<C,T,M> p,I i, T t)
1.67 + {
1.68 + i->*M=t;
1.69 + };
1.70 + */
1.71 +
1.72 + template <typename P,typename I,typename T>
1.73 + inline void Set(P &p,const I &i, const T &t)
1.74 + {
1.75 + p.Set(i,t);
1.76 + };
1.77 + template <typename P,typename I>
1.78 + inline typename P::value_type Get(const P &p,const I &i)
1.79 + {
1.80 + return p.Get(i);
1.81 + };
1.82 +
1.83 + /*
1.84 + template <typename G,typename T, typename G::EdgeType::*M>
1.85 + T Get(edge_element_map p,G::EdgeIterator i)
1.86 + {
1.87 + return i->*M;
1.88 + };
1.89 + */
1.90 +
1.91 + /*
1.92 + template <class G>
1.93 + class default_bfs_maps
1.94 + {
1.95 + public:
1.96 + typedef typename G::NodeType NodeType;
1.97 +
1.98 + class_element_map<typename G::NodeIterator,
1.99 + typename G::NodeType,
1.100 + bool,&NodeType::isVis> visited; //node->bool (RW)
1.101 + do_nothing_map tree; //node->EdgeIterator (W)
1.102 + do_nothing_map dist; //node->int (W)
1.103 + do_nothing_map priority; //node->int (W)
1.104 + };
1.105 + */
1.106 +
1.107 + template<class G>
1.108 + struct bfs_node_data
1.109 + {
1.110 + bool visited;
1.111 + typename G::EdgeIterator tree;
1.112 + int dist;
1.113 + int priority;
1.114 + };
1.115 +
1.116 + template <class G>
1.117 + class bfs_static_maps
1.118 + {
1.119 + public:
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 + */
1.126 + class
1.127 + {
1.128 + public:
1.129 + bfs_node_data<G> NodeType::*d;
1.130 + typedef bool value_type;
1.131 + void Set(typename G::NodeIterator &i, const value_type &t)
1.132 + {((*i).*d).visited=t;}
1.133 + value_type Get(const typename G::NodeIterator &i) const
1.134 + {return ((*i).*d).visited;}
1.135 + } visited;
1.136 +
1.137 + class
1.138 + {
1.139 + public:
1.140 + bfs_node_data<G> NodeType::*d;
1.141 + typedef typename G::EdgeIterator value_type;
1.142 + void Set(typename G::NodeIterator &i, const value_type &t)
1.143 + {((*i).*d).tree=t;}
1.144 + value_type Get(const typename G::NodeIterator &i) const
1.145 + {return ((*i).*d).tree;}
1.146 + } tree;
1.147 +
1.148 + class
1.149 + {
1.150 + public:
1.151 + bfs_node_data<G> NodeType::*d;
1.152 + typedef int value_type;
1.153 + void Set(typename G::NodeIterator &i, const value_type &t)
1.154 + {((*i).*d).dist=t;}
1.155 + value_type Get(const typename G::NodeIterator &i) const
1.156 + {return ((*i).*d).dist;}
1.157 + } dist;
1.158 +
1.159 + class
1.160 + {
1.161 + public:
1.162 + bfs_node_data<G> NodeType::*d;
1.163 + typedef int value_type;
1.164 + void Set(typename G::NodeIterator &i, const value_type &t)
1.165 + {((*i).*d).priority=t;}
1.166 + value_type Get(const typename G::NodeIterator &i) const
1.167 + {return ((*i).*d).priority;}
1.168 + } priority;
1.169 +
1.170 + //do_nothing_map tree; //node->EdgeIterator (W)
1.171 + // do_nothing_map dist; //node->int (W)
1.172 + // do_nothing_map priority; //node->int (W)
1.173 +
1.174 + void SetDataField(const bfs_node_data<G> NodeType::*dd)
1.175 + {
1.176 + tree.d=visited.d=dist.d=priority.d=dd;
1.177 + }
1.178 +
1.179 + bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
1.180 + {
1.181 + SetDataField(dd);
1.182 + }
1.183 +
1.184 + bfs_static_maps(const bfs_static_maps<G> &B)
1.185 + {
1.186 + tree.d=B.tree.d;visited.d=B.visited.d;
1.187 + dist.d=B.dist.d;priority.d=B.priority.d;
1.188 + }
1.189 +
1.190 + };
1.191 +
1.192 + template<typename I>
1.193 + struct BFS_Q
1.194 + {
1.195 + I n;
1.196 + int dist;
1.197 + // BFS_Q() {}
1.198 + // BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
1.199 + };
1.200 +
1.201 + template<class G,class M>
1.202 + void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
1.203 + {
1.204 + using namespace std;
1.205 +
1.206 + typedef BFS_Q<typename G::NodeIterator> Q_T;
1.207 +
1.208 + Q_T q;
1.209 +
1.210 + int pr=0;
1.211 + typename G::NodeIterator n,m;
1.212 + typename G::OutEdgeIterator e;
1.213 + int d;
1.214 +
1.215 + for(Gr.GetFirst(n);n.isValid();++n)
1.216 + Set(maps.visited,n,false);
1.217 +
1.218 + queue<Q_T> Q;
1.219 +
1.220 + q.n=start_node;
1.221 + q.dist=0;
1.222 + Q.push(q);
1.223 + Set(maps.visited,start_node,true);
1.224 + // Set(maps::tree,start_node,?????);
1.225 + Set(maps.dist,start_node,0);
1.226 + Set(maps.priority,start_node,pr++);
1.227 +
1.228 + do {
1.229 + n=Q.front().n;d=Q.front().dist+1;
1.230 + Q.pop();
1.231 + for(Gr.GetFirst(e,n);e.isValid();++e)
1.232 + if(!Get(maps.visited,(m=e.Bnode()))) {
1.233 + q.n=m;
1.234 + q.dist=d;
1.235 + Q.push(q);
1.236 + Set(maps.visited,m,true);
1.237 + Set(maps.tree,m,e);
1.238 + Set(maps.dist,m,d);
1.239 + Set(maps.priority,m,pr++);
1.240 + }
1.241 + } while(!Q.empty());
1.242 + };
1.243 +}
1.244 +#endif