source: lemon-0.x/src/include/bfs.h @ 151:c0e556186c55

// -*-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