# 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();
 }