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
2.1 --- a/src/include/graph.h Sat Dec 06 19:32:27 2003 +0000
2.2 +++ b/src/include/graph.h Thu Dec 11 07:24:53 2003 +0000
2.3 @@ -72,6 +72,7 @@
2.4 bool operator==(const NodeIterator &i) const {return n==i.n;}
2.5 bool operator!=(const NodeIterator &i) const {return n!=i.n;}
2.6
2.7 + int Index() { return n; } //If the nodes are indexable
2.8 friend class Graph;
2.9 friend class EdgeIterator;
2.10 friend class InEdgeIterator;
2.11 @@ -114,7 +115,10 @@
2.12
2.13 bool operator==(const EdgeIterator &i) const {return e==i.e;}
2.14 bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
2.15 -
2.16 +
2.17 + int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
2.18 + //If the edges are indexable
2.19 +
2.20 friend class Graph;
2.21 friend class InEdgeIterator;
2.22 friend class OutEdgeIterator;
3.1 --- a/src/work/graphdemo.cc Sat Dec 06 19:32:27 2003 +0000
3.2 +++ b/src/work/graphdemo.cc Thu Dec 11 07:24:53 2003 +0000
3.3 @@ -1,5 +1,6 @@
3.4 #include <iostream>
3.5 #include <graph.h>
3.6 +#include <bfs.h>
3.7
3.8 using namespace NEGRO;
3.9 using namespace std;
3.10 @@ -14,6 +15,7 @@
3.11 public:
3.12 int id;
3.13 bool isVis;
3.14 + bfs_node_data<TestGraph> bfs;
3.15 };
3.16
3.17 class EdgeData
3.18 @@ -22,8 +24,101 @@
3.19 int id;
3.20 };
3.21
3.22 +typedef Graph<NodeData,EdgeData> TestGraph;
3.23
3.24 -typedef Graph<NodeData,EdgeData> TestGraph;
3.25 +/*
3.26 +struct isVis_map {};
3.27 +bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
3.28 +void Set(isVis_map p,TestGraph::NodeIterator i,bool b) { i->isVis=b;}
3.29 +*/
3.30 +
3.31 +class my_bfs_maps
3.32 +{
3.33 +public:
3.34 + //isVis_map visited; //node->bool (RW)
3.35 + class_element_map<TestGraph::NodeIterator,
3.36 + TestGraph::NodeType,
3.37 + bool,
3.38 + &NodeData::isVis> visited;
3.39 + struct _tree_map_t {
3.40 + typedef TestGraph::EdgeIterator value_type;
3.41 + void Set(const TestGraph::NodeIterator &n,const value_type &t)
3.42 + {
3.43 + cout << t.From()->id << "->" << t.To()->id << '\n';
3.44 + }
3.45 + } tree;
3.46 + do_nothing_map dist; //node->int (W)
3.47 + do_nothing_map priority; //node->int (W)
3.48 + //priority_map priority; //node->int (W)
3.49 +};
3.50 +
3.51 +
3.52 +
3.53 +
3.54 +class IGraph
3.55 +{
3.56 +public:
3.57 +
3.58 + // struct NodeType {bfs_node_data<TestGraph> bfs;};
3.59 + struct NodeType {bool isVis;};
3.60 +
3.61 + vector<NodeType> nodes;
3.62 +
3.63 + class NodeIterator
3.64 + {
3.65 + public:
3.66 + IGraph *G;
3.67 + int n;
3.68 + NodeIterator &operator ++() { n++; return *this;}
3.69 + NodeType &operator *() const { return G->nodes[n];}
3.70 + NodeType *operator ->() const { return &(G->nodes[n]);}
3.71 + bool isValid() const {return n<=5000;}
3.72 + int Index() {return n;} //csak a kiirashoz kell
3.73 + };
3.74 +
3.75 + void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
3.76 +
3.77 + class OutEdgeIterator
3.78 + {
3.79 + public:
3.80 + IGraph *G;
3.81 + int f,t;
3.82 + int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
3.83 + OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
3.84 + bool isValid() const {return t<=5000;}
3.85 + NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
3.86 + NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
3.87 + NodeIterator Anode() const {return From();}
3.88 + NodeIterator Bnode() const {return To();}
3.89 + };
3.90 +
3.91 + typedef OutEdgeIterator EdgeIterator;
3.92 + void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
3.93 + {i.G=this;i.f=n.n;i.t=0;++i;}
3.94 +
3.95 + IGraph() : nodes(5000) {}
3.96 +};
3.97 +
3.98 +class IMaps_t
3.99 +{
3.100 +public:
3.101 +// class_element_map<IGraph::NodeIterator,
3.102 +// IGraph::NodeType,
3.103 +// bool,
3.104 +// &IGraph::NodeType::isVis> visited;
3.105 + struct _visited_map_t {
3.106 + typedef bool value_type;
3.107 + void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
3.108 + value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
3.109 + } visited;
3.110 + struct _tree_map_t {
3.111 + typedef IGraph::EdgeIterator value_type;
3.112 + void Set(const IGraph::NodeIterator &n,const value_type &t)
3.113 + { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
3.114 + } tree;
3.115 + do_nothing_map dist; //node->int (W)
3.116 + do_nothing_map priority; //node->int (W)
3.117 +};
3.118
3.119 void main()
3.120 {
3.121 @@ -82,6 +177,8 @@
3.122 else ++e;
3.123 }
3.124
3.125 + // cout << "Number of edges: " << i << "\n\n";
3.126 +
3.127 for(a=G.First();a.isValid();++a)
3.128 cout << a->id << ": " << a.From()->id << "->" << a.To()->id << " ";
3.129
3.130 @@ -95,4 +192,26 @@
3.131 cout << '\n';
3.132 }
3.133
3.134 + n=G.First();
3.135 +
3.136 +
3.137 + //G.Clean();
3.138 +
3.139 + cout << "\n\n\n BFS \n\n\n";
3.140 + //my_bfs_maps Maps;
3.141 + // bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
3.142 +
3.143 + /// bfs(G,n,Maps);
3.144 +
3.145 + cout << '\n';
3.146 +
3.147 + IGraph IG;
3.148 + IMaps_t IMaps;
3.149 +
3.150 + IGraph::NodeIterator in;
3.151 + IG.GetFirst(in);
3.152 + ++in;
3.153 + bfs(IG,in,IMaps);
3.154 +
3.155 +
3.156 }
4.1 --- a/src/work/makefile Sat Dec 06 19:32:27 2003 +0000
4.2 +++ b/src/work/makefile Thu Dec 11 07:24:53 2003 +0000
4.3 @@ -1,3 +1,3 @@
4.4 -graphdemo: graphdemo.cc ../include/graph.h \
4.5 +graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
4.6 ../include/oldgraph.h makefile
4.7 g++ -g -I../include -o graphdemo graphdemo.cc