# HG changeset patch
# User alpar
# Date 1071591548 0
# Node ID b63d1bc367f79ffc1b9f8ebf5a1f3df90d983fe0
# Parent  f5852ebe00cacfca1d5ca78e5aa5fad3339ea98a
!!!Tests!!!

diff -r f5852ebe00ca -r b63d1bc367f7 src/include/bfs.h
--- a/src/include/bfs.h	Mon Dec 15 17:46:22 2003 +0000
+++ b/src/include/bfs.h	Tue Dec 16 16:19:08 2003 +0000
@@ -240,11 +240,27 @@
   };
 
   // bfs algorithm class
+
+  template<class G>  //the default traits
+  class default_bfs_T
+  {
+  public:
+    
+    typedef G Graph;
+    typedef typename G::OutEdgeIterator SearchEdgeIterator;
+    
+    typedef typename G::NodeMap<bool> visited_map_t;
+    typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
+    
+    typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)
+    typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
+};
+
   template<class T>
   class Bfs
   {
   public:
-    typedef typename T::Graph_t Graph;
+    typedef typename T::Graph Graph;
     typedef typename Graph::NodeIterator NodeIterator;
     typedef typename Graph::EdgeIterator EdgeIterator;
     
diff -r f5852ebe00ca -r b63d1bc367f7 src/include/graph.h
--- a/src/include/graph.h	Mon Dec 15 17:46:22 2003 +0000
+++ b/src/include/graph.h	Tue Dec 16 16:19:08 2003 +0000
@@ -4,6 +4,7 @@
 
 //inline void *operator new(size_t s, void *p) { return p; }
 #include <new>
+#include <vector>
 
 namespace NEGRO 
 {
@@ -40,7 +41,7 @@
     class SymEdgeIterator;
     class AllEdgeIterator;
     
-    class FirstAnythingTypeNode;
+    class FirstAnythingTypeNode; //Required by the unified First() function.
 
     friend class NodeIterator;
     friend class EdgeIterator;
@@ -391,6 +392,45 @@
     void Clean() { OldGraph<N,E>::Clean(); }
 
     Graph() : _FST(this) {}
+
+    // MAPS:
+    template<class T> class NodeMap
+    {
+      Graph<N,E> *G;
+      vector<T> map;
+
+    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 update() { map.resize(G->OldGraph<N,E>::NodeMax());}
+
+      NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}
+      
+    };
+
+    template<class T> class EdgeMap
+    {
+      Graph<N,E> *G;
+      vector<T> map;
+
+    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 update()
+	{ map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}
+      
+      EdgeMap(Graph<N,E> &Gr) 
+	:map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)
+	{ G=&Gr ;}
+      
+    };
+    
   };
   
   /*   Ez itt a fiam kommentje:
diff -r f5852ebe00ca -r b63d1bc367f7 src/work/bfsdemo.cc
--- a/src/work/bfsdemo.cc	Mon Dec 15 17:46:22 2003 +0000
+++ b/src/work/bfsdemo.cc	Tue Dec 16 16:19:08 2003 +0000
@@ -82,7 +82,7 @@
 {
 public:
 
-  typedef IGraph Graph_t;
+  typedef IGraph Graph;
   typedef IGraph::OutEdgeIterator SearchEdgeIterator;
   
   struct visited_map_t {
diff -r f5852ebe00ca -r b63d1bc367f7 src/work/bfsdemo2.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/bfsdemo2.cc	Tue Dec 16 16:19:08 2003 +0000
@@ -0,0 +1,38 @@
+#include <iostream>
+#include <graph.h>
+#include <bfs.h>
+
+using namespace NEGRO;
+using namespace std;
+
+typedef Graph<int,int> TestGraph;
+
+int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;}
+
+int main()
+{
+  TestGraph G;
+  
+  TestGraph::NodeIterator tn,n2;
+  
+  for(int i=1;i<=5000;i++)
+    {
+      *(tn=G.AddNode())=i;
+      if(i==2) n2=tn;
+    }
+  
+  for(TestGraph::NodeIterator n(G);n.isValid();++n)
+    for(TestGraph::NodeIterator m(G);m.isValid();++m)
+      if(gcd(*n,*m)>1) G.AddEdge(n,m);
+  
+  Bfs<default_bfs_T<TestGraph> > bfs;
+
+  bfs.SetG(G);
+  bfs.Init(n2);
+  bfs.Run();
+
+  for(TestGraph::NodeIterator n(G);n.isValid();++n)
+    cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To()
+	 << '\n';
+
+}