# HG changeset patch
# User alpar
# Date 1071598671 0
# Node ID cd54905012bc1e220aac07da08c5ddc847dd7d25
# Parent  0f527d1b9149b9c2e28c95b7d98fd7919544cf76
-New test: bfsdemo2.cc added
- Graph class has a NodeMap and an EdgeMap member class
- default_bfs_T uning the above Maps is added
- a (property)map must provide a member function SetG() to attach the map
  to a graph

diff -r 0f527d1b9149 -r cd54905012bc src/include/bfs.h
--- a/src/include/bfs.h	Tue Dec 16 17:52:52 2003 +0000
+++ b/src/include/bfs.h	Tue Dec 16 18:17:51 2003 +0000
@@ -45,8 +45,8 @@
   //   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) {}
+    template <typename G> void SetG(G &g) {}
   };
   
 
@@ -282,9 +282,16 @@
     int priority;
     Graph *G;
     
+    //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
+    Bfs() {}
+
     void SetG(Graph &Gr)
     {
       G=&Gr;
+      visited_map.SetG(Gr);
+      tree_map.SetG(Gr);
+      dist_map.SetG(Gr);
+      priority_map.SetG(Gr);
     }
     
     void Init()
diff -r 0f527d1b9149 -r cd54905012bc src/include/graph.h
--- a/src/include/graph.h	Tue Dec 16 17:52:52 2003 +0000
+++ b/src/include/graph.h	Tue Dec 16 18:17:51 2003 +0000
@@ -75,7 +75,7 @@
       bool operator==(const NodeIterator &i) const {return n==i.n;}
       bool operator!=(const NodeIterator &i) const {return n!=i.n;}
       
-      int Index() { return n; } //If the nodes are indexable 
+      int Index() const { return n; } //If the nodes are indexable 
       friend class Graph;
       friend class EdgeIterator;
       friend class InEdgeIterator;
@@ -119,7 +119,7 @@
       bool operator==(const EdgeIterator &i) const {return e==i.e;}
       bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
        
-      int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
+      int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
       //If the edges are indexable 
 
       friend class Graph;
@@ -401,14 +401,14 @@
 
     public:
       typedef T value_type;
-      void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
-      T &Get(NodeIterator i) {return map[i.Index()];}
-      T &operator[](NodeIterator i) {return map[i.Index()];}
+      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
+      T Get(const NodeIterator i) const {return map[i.Index()];}
+      T operator[](NodeIterator i) {return map[i.Index()];}
 
-      void update() { map.resize(G->OldGraph<N,E>::NodeMax());}
+      void update() { map.resize(G->MaxNode());}
 
-      NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}
-      
+      NodeMap() {}
+      void SetG(Graph<N,E> &Gr) { G=&Gr; update();}      
     };
 
     template<class T> class EdgeMap
@@ -418,19 +418,23 @@
 
     public:
       typedef T value_type;
-      void Set(NodeIterator i, const T &t) {map[i.Index()]=t;}
-      T &Get(NodeIterator i) {return map[i.Index()];}
+      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
+      T &Get(const NodeIterator i) {return map[i.Index()];}
       T &operator[](NodeIterator i) {return map[i.Index()];}
       
       void update()
-	{ map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}
+	{ map.resize(G->MaxEdge());}
       
-      EdgeMap(Graph<N,E> &Gr) 
-	:map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)
-	{ G=&Gr ;}
+      EdgeMap() {}
+      void SetG(Graph<N,E> &Gr) 
+      { G=&Gr ;update();}
       
     };
     
+
+    int MaxNode() { return OldGraph<N,E>::MaxNode();}
+    int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
+    
   };
   
   /*   Ez itt a fiam kommentje:
diff -r 0f527d1b9149 -r cd54905012bc src/work/bfsdemo.cc
--- a/src/work/bfsdemo.cc	Tue Dec 16 17:52:52 2003 +0000
+++ b/src/work/bfsdemo.cc	Tue Dec 16 18:17:51 2003 +0000
@@ -67,11 +67,13 @@
     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; }
+    void SetG(IGraph &G) {}
   } visited;
   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'; }
+    void SetG(IGraph &G) {}
   } tree;
   do_nothing_map dist;   //node->int (W)
   do_nothing_map priority; //node->int (W)
@@ -89,11 +91,13 @@
     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; }
+    void SetG(IGraph &G) {}
   };
   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'; }
+    void SetG(IGraph &G) {}
   };
   typedef do_nothing_map dist_map_t;   //node->int (W)
   typedef do_nothing_map priority_map_t; //node->int (W)
diff -r 0f527d1b9149 -r cd54905012bc src/work/bfsdemo2.cc
--- a/src/work/bfsdemo2.cc	Tue Dec 16 17:52:52 2003 +0000
+++ b/src/work/bfsdemo2.cc	Tue Dec 16 18:17:51 2003 +0000
@@ -15,16 +15,23 @@
   
   TestGraph::NodeIterator tn,n2;
   
-  for(int i=1;i<=5000;i++)
+  cout << "Create nodes\n";
+
+  for(int i=1;i<=500;i++)
     {
       *(tn=G.AddNode())=i;
       if(i==2) n2=tn;
     }
   
+  cout << "Create Edges\n";
+  
   for(TestGraph::NodeIterator n(G);n.isValid();++n)
-    for(TestGraph::NodeIterator m(G);m.isValid();++m)
+    for(TestGraph::NodeIterator m(G);m.isValid();++m) if(n!=m)
       if(gcd(*n,*m)>1) G.AddEdge(n,m);
   
+  
+  cout << "Run BFS\n";
+
   Bfs<default_bfs_T<TestGraph> > bfs;
 
   bfs.SetG(G);
@@ -32,7 +39,12 @@
   bfs.Run();
 
   for(TestGraph::NodeIterator n(G);n.isValid();++n)
-    cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To()
-	 << '\n';
+    if((*n)!=2)
+      cout << (Get(bfs.dist_map,n)) << '\n';
 
+  for(TestGraph::NodeIterator n(G);n.isValid();++n)
+    if(Get(bfs.dist_map,n))
+      cout << *(Get(bfs.tree_map,n).From()) << "->"
+	   << *(Get(bfs.tree_map,n).To())
+	   << '\n';
 }