# HG changeset patch
# User alpar
# Date 1071127493 0
# Node ID 37117ebbabe299dbf1a87256f11b0041563b6791
# Parent  207fb3c727cb0cb0a188b7e3f289ab1b80593aaa
bfs

diff -r 207fb3c727cb -r 37117ebbabe2 src/include/bfs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/include/bfs.h	Thu Dec 11 07:24:53 2003 +0000
@@ -0,0 +1,241 @@
+// -*-mode: c++; -*-
+#ifndef _BFS_H_
+#define _BFS_H_
+
+#include <queue>
+#include <graph.h>
+
+namespace NEGRO 
+{
+  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 Set-tel
+//   class do_nothing_map {};
+//   template <typename V,typename T>
+//   void Set(const do_nothing_map &p,const V &v,const T &t) {}
+  
+  struct do_nothing_map {
+  template <typename V,typename T>
+  static void Set(V v,T t) {}
+  };
+  
+
+  template <typename I,typename C, typename T, T C::*M>
+  class class_element_map {
+  public:
+    typedef T value_type;
+    static void Set(const I &i, const T &t) {(*i).*M=t;}
+    static T Get(const I i) {return (*i).*M;}
+    T &operator[](I i) {return (*i).*M;}
+  };
+
+  /* 
+     template <typename C,typename I,typename T, T C::*M>
+     void Set(class_element_map<C,T,M> p,I i, T t)
+     {
+     i->*M=t;   
+     };
+  */
+
+  template <typename P,typename I,typename T>
+  inline void Set(P &p,const I &i, const T &t)
+  {
+    p.Set(i,t);   
+  };
+  template <typename P,typename I>
+  inline typename P::value_type Get(const P &p,const I &i)
+  {
+    return p.Get(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>
+  struct bfs_node_data 
+  {
+    bool visited;
+    typename G::EdgeIterator tree;
+    int dist;
+    int priority;
+  };
+  
+  template <class G>
+  class bfs_static_maps
+  {
+  public:
+    typedef typename G::NodeType NodeType;
+    
+    /*    class_element_map<typename G::NodeIterator,
+		      typename G::NodeType,
+		      bfs_node_data<G>,&NT::D> n_d; //node-> data
+    */
+    class 
+    {
+    public:
+      bfs_node_data<G> NodeType::*d;
+      typedef bool value_type;
+      void Set(typename G::NodeIterator &i, const value_type &t)
+      {((*i).*d).visited=t;}
+      value_type Get(const typename G::NodeIterator &i) const
+      {return ((*i).*d).visited;}
+    } visited;
+    
+    class 
+    {
+    public:
+      bfs_node_data<G> NodeType::*d;
+      typedef typename G::EdgeIterator value_type;
+      void Set(typename G::NodeIterator &i, const value_type &t)
+      {((*i).*d).tree=t;}
+      value_type Get(const typename G::NodeIterator &i) const
+      {return ((*i).*d).tree;}
+    } tree;
+    
+    class 
+    {
+    public:
+      bfs_node_data<G> NodeType::*d;
+      typedef int value_type;
+      void Set(typename G::NodeIterator &i, const value_type &t)
+      {((*i).*d).dist=t;}
+      value_type Get(const typename G::NodeIterator &i) const
+      {return ((*i).*d).dist;}
+    } dist;
+    
+    class 
+    {
+    public:
+      bfs_node_data<G> NodeType::*d;
+      typedef int value_type;
+      void Set(typename G::NodeIterator &i,  const value_type &t)
+      {((*i).*d).priority=t;}
+      value_type Get(const typename G::NodeIterator &i) const
+      {return ((*i).*d).priority;}
+    } priority;
+    
+    //do_nothing_map tree;   //node->EdgeIterator (W)
+    //    do_nothing_map dist;   //node->int (W)
+    //    do_nothing_map priority; //node->int (W)
+
+    void SetDataField(const bfs_node_data<G> NodeType::*dd)
+    {
+      tree.d=visited.d=dist.d=priority.d=dd;
+    }
+    
+    bfs_static_maps(const bfs_node_data<G> NodeType::*dd) 
+    {
+      SetDataField(dd);
+    }
+    
+    bfs_static_maps(const bfs_static_maps<G> &B) 
+    {
+      tree.d=B.tree.d;visited.d=B.visited.d;
+      dist.d=B.dist.d;priority.d=B.priority.d;
+    }
+    
+  };
+  
+  template<typename I>
+  struct BFS_Q
+  {
+    I n;
+    int dist;
+    //  BFS_Q() {}
+    //  BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
+  };
+  
+  template<class G,class M>
+  void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
+  {
+    using namespace std;
+    
+    typedef BFS_Q<typename G::NodeIterator> Q_T;
+    
+    Q_T q;
+    
+    int pr=0;
+    typename G::NodeIterator n,m;
+    typename G::OutEdgeIterator e;
+    int d;
+    
+    for(Gr.GetFirst(n);n.isValid();++n)
+      Set(maps.visited,n,false);
+    
+    queue<Q_T> Q;
+    
+    q.n=start_node;
+    q.dist=0;
+    Q.push(q);
+    Set(maps.visited,start_node,true);
+    //      Set(maps::tree,start_node,?????);
+    Set(maps.dist,start_node,0);
+    Set(maps.priority,start_node,pr++);
+    
+    do {
+      n=Q.front().n;d=Q.front().dist+1;
+      Q.pop();
+      for(Gr.GetFirst(e,n);e.isValid();++e)
+	if(!Get(maps.visited,(m=e.Bnode()))) {
+	  q.n=m;
+	  q.dist=d;
+	  Q.push(q);
+	  Set(maps.visited,m,true);
+	  Set(maps.tree,m,e);
+	  Set(maps.dist,m,d);
+	  Set(maps.priority,m,pr++);
+	}
+    } while(!Q.empty());
+  };
+}
+#endif
diff -r 207fb3c727cb -r 37117ebbabe2 src/include/graph.h
--- a/src/include/graph.h	Sat Dec 06 19:32:27 2003 +0000
+++ b/src/include/graph.h	Thu Dec 11 07:24:53 2003 +0000
@@ -72,6 +72,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 
       friend class Graph;
       friend class EdgeIterator;
       friend class InEdgeIterator;
@@ -114,7 +115,10 @@
       
       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; }
+      //If the edges are indexable 
+
       friend class Graph;
       friend class InEdgeIterator;
       friend class OutEdgeIterator;
diff -r 207fb3c727cb -r 37117ebbabe2 src/work/graphdemo.cc
--- a/src/work/graphdemo.cc	Sat Dec 06 19:32:27 2003 +0000
+++ b/src/work/graphdemo.cc	Thu Dec 11 07:24:53 2003 +0000
@@ -1,5 +1,6 @@
 #include <iostream>
 #include <graph.h>
+#include <bfs.h>
 
 using namespace NEGRO;
 using namespace std;
@@ -14,6 +15,7 @@
 public:
   int id;
   bool isVis;
+  bfs_node_data<TestGraph> bfs;
 };
 
 class EdgeData
@@ -22,8 +24,101 @@
   int id;
 };
 
+typedef Graph<NodeData,EdgeData> TestGraph;
 
-typedef Graph<NodeData,EdgeData> TestGraph;
+/*
+struct isVis_map {};
+bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
+void Set(isVis_map p,TestGraph::NodeIterator i,bool b) {  i->isVis=b;}
+*/
+
+class my_bfs_maps
+{
+public:
+  //isVis_map visited;  //node->bool (RW)
+  class_element_map<TestGraph::NodeIterator,
+		    TestGraph::NodeType,
+		    bool,
+		    &NodeData::isVis> visited;
+  struct _tree_map_t {
+    typedef TestGraph::EdgeIterator value_type;
+    void Set(const TestGraph::NodeIterator &n,const value_type &t)
+    {
+      cout << t.From()->id << "->" << t.To()->id << '\n';
+    }
+  } tree;
+  do_nothing_map dist;   //node->int (W)
+  do_nothing_map priority; //node->int (W)
+  //priority_map priority; //node->int (W)
+};
+
+
+
+
+class IGraph 
+{
+public:
+
+  //  struct NodeType {bfs_node_data<TestGraph> bfs;};
+  struct NodeType {bool isVis;};
+
+  vector<NodeType> nodes;
+  
+  class NodeIterator 
+  {
+  public:
+    IGraph *G;
+    int n;
+    NodeIterator &operator ++() { n++; return *this;}
+    NodeType &operator *() const { return G->nodes[n];}
+    NodeType *operator ->() const { return &(G->nodes[n]);}
+    bool isValid() const {return n<=5000;}
+    int Index() {return n;} //csak a kiirashoz kell
+  };
+
+  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
+
+  class OutEdgeIterator 
+  {    
+  public:
+    IGraph *G;
+    int f,t;
+    int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
+    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
+    bool isValid() const {return t<=5000;}
+    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
+    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
+    NodeIterator Anode() const {return From();}
+    NodeIterator Bnode() const {return To();}
+  };
+
+  typedef OutEdgeIterator EdgeIterator;
+  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
+  {i.G=this;i.f=n.n;i.t=0;++i;}
+
+  IGraph() : nodes(5000) {}
+};
+
+class IMaps_t
+{
+public:
+//     class_element_map<IGraph::NodeIterator,
+//   		    IGraph::NodeType,
+//   		    bool,
+//   		    &IGraph::NodeType::isVis> visited;
+  struct _visited_map_t {
+    typedef bool value_type;
+    void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
+    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
+  } visited;
+  struct _tree_map_t {
+    typedef IGraph::EdgeIterator value_type;
+    void Set(const IGraph::NodeIterator &n,const value_type &t)
+    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
+  } tree;
+  do_nothing_map dist;   //node->int (W)
+  do_nothing_map priority; //node->int (W)
+};
 
 void main()
 {
@@ -82,6 +177,8 @@
 	else ++e;
     }
   
+  // cout << "Number of edges: " << i << "\n\n";
+
   for(a=G.First();a.isValid();++a)
     cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
   
@@ -95,4 +192,26 @@
       cout << '\n';
     }
   
+  n=G.First();
+
+
+  //G.Clean();
+
+  cout << "\n\n\n BFS \n\n\n";
+  //my_bfs_maps Maps;
+  //  bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
+  
+  /// bfs(G,n,Maps);
+
+  cout << '\n';
+
+  IGraph IG;
+  IMaps_t IMaps;
+
+  IGraph::NodeIterator in;
+  IG.GetFirst(in);
+  ++in;
+  bfs(IG,in,IMaps);
+  
+  
 }
diff -r 207fb3c727cb -r 37117ebbabe2 src/work/makefile
--- a/src/work/makefile	Sat Dec 06 19:32:27 2003 +0000
+++ b/src/work/makefile	Thu Dec 11 07:24:53 2003 +0000
@@ -1,3 +1,3 @@
-graphdemo: graphdemo.cc ../include/graph.h \
+graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
 	../include/oldgraph.h makefile
 	g++ -g -I../include -o graphdemo graphdemo.cc