# HG changeset patch
# User alpar
# Date 1071415966 0
# Node ID 8009bb5ddd09092d818e98f074d983b2b619c27f
# Parent 272a5677bd6d9be669d5a009556c300fa58279a5
a 'bfs algorithm class' proposal added
diff -r 272a5677bd6d -r 8009bb5ddd09 src/include/bfs.h
--- a/src/include/bfs.h Sat Dec 13 15:44:50 2003 +0000
+++ b/src/include/bfs.h Sun Dec 14 15:32:46 2003 +0000
@@ -9,43 +9,44 @@
{
using namespace std;
-// template <typename G,typename> class bfs_T
-// {
-// typedef G Graph;
-// typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
-// typedef Graph::NodeIterator NodeIterator;
+ // template <typename G,typename> class bfs_T
+ // {
+ // typedef G Graph;
+ // typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
+ // typedef Graph::NodeIterator NodeIterator;
-// class bfs_node_D
-// {
-// EdgeIterator Tree;
-// int Dist;
-// int Priority;
-// }
+ // class bfs_node_D
+ // {
+ // EdgeIterator Tree;
+ // int Dist;
+ // int Priority;
+ // }
+ // }
-// // template <bfs_T<G>>
-// // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
+ // // template <bfs_T<G>>
+ // // void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
-// template <class G>
-// class bfs_maps_T
-// {
-// typedef visited; //node->bool (RW)
-// typedef tree; //node->EdgeIterator (W)
-// typedef dist; //node->int (W)
-// typedef priority; //node->int (W)
-// };
+ // template <class G>
+ // class bfs_maps_T
+ // {
+ // typedef visited; //node->bool (RW)
+ // typedef tree; //node->EdgeIterator (W)
+ // typedef dist; //node->int (W)
+ // typedef priority; //node->int (W)
+ // };
-// Nem jo! Osszeakad a masik Put-tel
-// class do_nothing_map {};
-// template <typename V,typename T>
-// void Put(const do_nothing_map &p,const V &v,const T &t) {}
+ // Nem jo! Osszeakad a masik Put-tal
+ // class do_nothing_map {};
+ // template <typename V,typename T>
+ // void Put(const do_nothing_map &p,const V &v,const T &t) {}
struct do_nothing_map {
- template <typename V,typename T>
- static void Put(V v,T t) {}
+ template <typename V,typename T>
+ static void Put(V v,T t) {}
};
@@ -78,27 +79,27 @@
};
/*
- template <typename G,typename T, typename G::EdgeType::*M>
- T Get(edge_element_map p,G::EdgeIterator i)
- {
+ template <typename G,typename T, typename G::EdgeType::*M>
+ T Get(edge_element_map p,G::EdgeIterator i)
+ {
return i->*M;
- };
+ };
*/
/*
- template <class G>
- class default_bfs_maps
- {
- public:
- typedef typename G::NodeType NodeType;
+ template <class G>
+ class default_bfs_maps
+ {
+ public:
+ typedef typename G::NodeType NodeType;
- class_element_map<typename G::NodeIterator,
- typename G::NodeType,
- bool,&NodeType::isVis> visited; //node->bool (RW)
- do_nothing_map tree; //node->EdgeIterator (W)
- do_nothing_map dist; //node->int (W)
- do_nothing_map priority; //node->int (W)
- };
+ class_element_map<typename G::NodeIterator,
+ typename G::NodeType,
+ bool,&NodeType::isVis> visited; //node->bool (RW)
+ do_nothing_map tree; //node->EdgeIterator (W)
+ do_nothing_map dist; //node->int (W)
+ do_nothing_map priority; //node->int (W)
+ };
*/
template<class G>
@@ -117,8 +118,8 @@
typedef typename G::NodeType NodeType;
/* class_element_map<typename G::NodeIterator,
- typename G::NodeType,
- bfs_node_data<G>,&NT::D> n_d; //node-> data
+ typename G::NodeType,
+ bfs_node_data<G>,&NT::D> n_d; //node-> data
*/
class
{
@@ -196,7 +197,7 @@
};
template<class G,class M>
- void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
+ void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
{
using namespace std;
@@ -237,5 +238,94 @@
}
} while(!Q.empty());
};
+
+ // bfs algorithm class
+ template<class T>
+ class Bfs
+ {
+ public:
+ typedef typename T::Graph_t Graph;
+ typedef typename Graph::NodeIterator NodeIterator;
+ typedef typename Graph::EdgeIterator EdgeIterator;
+
+ typedef typename T::SearchEdgeIterator SearchEdgeIterator;
+
+ typename T::visited_map_t visited_map;
+ typename T::tree_map_t tree_map;
+ typename T::dist_map_t dist_map;
+ typename T::priority_map_t priority_map;
+
+ struct bfs_queue_cont
+ {
+ NodeIterator n;
+ int dist;
+ };
+
+ std::queue<bfs_queue_cont> bfs_queue;
+
+ int priority;
+ Graph *G;
+
+ void SetG(Graph &Gr)
+ {
+ G=&Gr;
+ }
+
+ void Init()
+ {
+ //There must be a better way to do this:
+ while(!bfs_queue.empty()) bfs_queue.pop();
+
+ for(NodeIterator n(*G);n.isValid();++n)
+ Put(visited_map,n,false);
+
+ priority=0;
+
+ }
+
+ void AddStartNode(const NodeIterator &start_node,int dist=0)
+ {
+ bfs_queue_cont q;
+ q.n=start_node;
+ q.dist=dist;
+ bfs_queue.push(q);
+
+ Put(visited_map,start_node,true);
+ // Put(tree_map,start_node,?????);
+ Put(dist_map,start_node,dist);
+ Put(priority_map,start_node,priority++);
+ }
+
+ void Init(const NodeIterator &start_node,int dist=0)
+ {
+
+ Init();
+ AddStartNode(start_node,dist);
+ }
+
+ void Run()
+ {
+ NodeIterator n,m;
+ int d;
+
+ bfs_queue_cont q;
+ while(!(bfs_queue.empty()/* && other stop conditions */)) {
+ n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
+ bfs_queue.pop();
+ for(SearchEdgeIterator e(*G,n);e.isValid();++e)
+ if(!Get(visited_map,(m=e.Bnode()))) {
+ q.n=m;
+ q.dist=d;
+ bfs_queue.push(q);
+ Put(visited_map,m,true);
+ Put(tree_map,m,e);
+ Put(dist_map,m,d);
+ Put(priority_map,m,priority++);
+ }
+ }
+ }
+ };
+
}
+
#endif
diff -r 272a5677bd6d -r 8009bb5ddd09 src/work/bfsdemo.cc
--- a/src/work/bfsdemo.cc Sat Dec 13 15:44:50 2003 +0000
+++ b/src/work/bfsdemo.cc Sun Dec 14 15:32:46 2003 +0000
@@ -24,6 +24,9 @@
NodeType *operator ->() const { return &(G->nodes[n]);}
bool isValid() const {return n<=5000;}
int Index() {return n;} //csak a kiirashoz kell
+
+ NodeIterator() {}
+ NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.
};
void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
@@ -40,6 +43,10 @@
NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
NodeIterator Anode() const {return From();}
NodeIterator Bnode() const {return To();}
+
+ OutEdgeIterator() {}
+ OutEdgeIterator(IGraph &Gr,NodeIterator &n) //Bfs class prefer this.
+ {G=&Gr;f=n.n;t=0;operator++();}
};
typedef OutEdgeIterator EdgeIterator;
@@ -70,14 +77,48 @@
do_nothing_map priority; //node->int (W)
};
+// New style bfs traits
+class BFS_T
+{
+public:
+
+ typedef IGraph Graph_t;
+ typedef IGraph::OutEdgeIterator SearchEdgeIterator;
+
+ struct visited_map_t {
+ typedef bool value_type;
+ void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
+ value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
+ };
+ struct tree_map_t {
+ typedef IGraph::EdgeIterator value_type;
+ void Put(const IGraph::NodeIterator &n,const value_type &t)
+ { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
+ };
+ typedef do_nothing_map dist_map_t; //node->int (W)
+ typedef do_nothing_map priority_map_t; //node->int (W)
+};
+
int main()
{
IGraph IG;
- IMaps_t IMaps;
+// //Function-syte calling
+// IMaps_t IMaps;
+
+// IGraph::NodeIterator in;
+// IG.GetFirst(in);
+// ++in;
+// bfs_fn(IG,in,IMaps);
+
+ //Class-style calling:
+
IGraph::NodeIterator in;
IG.GetFirst(in);
++in;
- bfs(IG,in,IMaps);
+ Bfs<BFS_T> bfs;
+ bfs.SetG(IG);
+ bfs.Init(in);
+ bfs.Run();
}