source: lemon-0.x/src/include/bfs.h @ 3:272a5677bd6d

// -*-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-tel
//   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 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(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());
  };
}
#endif