Changeset 4:8009bb5ddd09 in lemon-0.x for src

Timestamp:

12/14/03 16:32:46 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@16

Message:

a 'bfs algorithm class' proposal added

Location:

src

Files:

• include/bfs.h (modified) (5 diffs)
• work/bfsdemo.cc (modified) (3 diffs)

src/include/bfs.h

@@ -10 +10 @@
   using namespace std;
   
-//   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;
-//     }
-    
-
-//     //    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)
-//   };
-  
-  
-//   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) {}
+  //   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;
+  //     }
+  //   }
+    
+
+  //     //    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)
+  //   };
+  
+  
+  //   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) {}
   };
   
@@ -79 +80 @@
 
   /*
-  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;
-    
-    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>
+     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)
+     };
   */
 
@@ -118 +119 @@
     
     /*    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 
@@ -197 +198 @@
   
   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;
@@ -238 +239 @@
     } 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

src/work/bfsdemo.cc

@@ -25 +25 @@
     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.
   };
   
@@ -41 +44 @@
     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++();}
   };
 
@@ -71 +78 @@
 };
 
+// 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();
 }