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

Timestamp:

12/14/03 16:32:46 (21 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

File:

• src/work/bfsdemo.cc (modified) (3 diffs)

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