# HG changeset patch
# User alpar
# Date 1090944171 0
# Node ID 7237eaaf5d84c86b168dc1c572a218357f280ee8
# Parent  3bb5553ec41b7b8c71e8b8db1f993189c8b442ae
It is really obsolete, but containes interesting stuffs.

diff -r 3bb5553ec41b -r 7237eaaf5d84 src/work/alpar/attic/bfs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/alpar/attic/bfs.h	Tue Jul 27 16:02:51 2004 +0000
@@ -0,0 +1,352 @@
+// -*-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 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 G> void SetG(G &g) {}
+  };
+  
+
+  template <typename I,typename C, typename T, T C::*M>
+  class class_element_map {
+  public:
+    typedef T value_type;
+    static void Put(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 Put(class_element_map<C,T,M> p,I i, T t)
+     {
+     i->*M=t;   
+     };
+  */
+
+  template <typename P,typename I,typename T>
+  inline void Put(P &p,const I &i, const T &t)
+  {
+    p.Put(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 Put(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 Put(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 Put(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 Put(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) 
+    {
+      PutDataField(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_fn(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)
+      Put(maps.visited,n,false);
+    
+    queue<Q_T> Q;
+    
+    q.n=start_node;
+    q.dist=0;
+    Q.push(q);
+    Put(maps.visited,start_node,true);
+    //      Put(maps::tree,start_node,?????);
+    Put(maps.dist,start_node,0);
+    Put(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);
+	  Put(maps.visited,m,true);
+	  Put(maps.tree,m,e);
+	  Put(maps.dist,m,d);
+	  Put(maps.priority,m,pr++);
+	}
+    } while(!Q.empty());
+  };
+
+  // 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 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;
+    
+    //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()
+    {
+      //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
diff -r 3bb5553ec41b -r 7237eaaf5d84 src/work/alpar/bfs.h
--- a/src/work/alpar/bfs.h	Sat Jul 24 14:33:37 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,352 +0,0 @@
-// -*-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 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 G> void SetG(G &g) {}
-  };
-  
-
-  template <typename I,typename C, typename T, T C::*M>
-  class class_element_map {
-  public:
-    typedef T value_type;
-    static void Put(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 Put(class_element_map<C,T,M> p,I i, T t)
-     {
-     i->*M=t;   
-     };
-  */
-
-  template <typename P,typename I,typename T>
-  inline void Put(P &p,const I &i, const T &t)
-  {
-    p.Put(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 Put(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 Put(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 Put(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 Put(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) 
-    {
-      PutDataField(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_fn(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)
-      Put(maps.visited,n,false);
-    
-    queue<Q_T> Q;
-    
-    q.n=start_node;
-    q.dist=0;
-    Q.push(q);
-    Put(maps.visited,start_node,true);
-    //      Put(maps::tree,start_node,?????);
-    Put(maps.dist,start_node,0);
-    Put(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);
-	  Put(maps.visited,m,true);
-	  Put(maps.tree,m,e);
-	  Put(maps.dist,m,d);
-	  Put(maps.priority,m,pr++);
-	}
-    } while(!Q.empty());
-  };
-
-  // 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 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;
-    
-    //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()
-    {
-      //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