COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/bfs.h @ 261:796101caedb7

Last change on this file since 261:796101caedb7 was 8:cd54905012bc, checked in by Alpar Juttner, 20 years ago

-New test: bfsdemo2.cc added

  • Graph class has a NodeMap? and an EdgeMap? member class
  • default_bfs_T uning the above Maps is added
  • a (property)map must provide a member function SetG() to attach the map to a graph
File size: 8.0 KB
Line 
1// -*-mode: c++; -*-
2#ifndef _BFS_H_
3#define _BFS_H_
4
5#include <queue>
6#include <graph.h>
7
8namespace NEGRO
9{
10  using namespace std;
11 
12  //   template <typename G,typename> class bfs_T
13  //   {
14  //     typedef G Graph;
15  //     typedef Graph::OutEdgeIterator EdgeIterator; //Ez kell
16  //     typedef Graph::NodeIterator NodeIterator;
17   
18  //     class bfs_node_D
19  //     {
20  //       EdgeIterator Tree;
21  //       int Dist;
22  //       int Priority;
23  //     }
24  //   }
25   
26
27  //     //    template <bfs_T<G>>
28  //     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
29
30   
31 
32  //   template <class G>
33  //   class bfs_maps_T
34  //   {
35  //     typedef visited; //node->bool (RW)
36  //     typedef tree;    //node->EdgeIterator (W)
37  //     typedef dist;   //node->int (W)
38  //     typedef priority; //node->int (W)
39  //   };
40 
41 
42  //   Nem jo! Osszeakad a masik Put-tal
43  //   class do_nothing_map {};
44  //   template <typename V,typename T>
45  //   void Put(const do_nothing_map &p,const V &v,const T &t) {}
46 
47  struct do_nothing_map {
48    template <typename V,typename T> static void Put(V v,T t) {}
49    template <typename G> void SetG(G &g) {}
50  };
51 
52
53  template <typename I,typename C, typename T, T C::*M>
54  class class_element_map {
55  public:
56    typedef T value_type;
57    static void Put(const I &i, const T &t) {(*i).*M=t;}
58    static T Get(const I i) {return (*i).*M;}
59    T &operator[](I i) {return (*i).*M;}
60  };
61
62  /*
63     template <typename C,typename I,typename T, T C::*M>
64     void Put(class_element_map<C,T,M> p,I i, T t)
65     {
66     i->*M=t;   
67     };
68  */
69
70  template <typename P,typename I,typename T>
71  inline void Put(P &p,const I &i, const T &t)
72  {
73    p.Put(i,t);   
74  };
75  template <typename P,typename I>
76  inline typename P::value_type Get(const P &p,const I &i)
77  {
78    return p.Get(i);   
79  };
80
81  /*
82    template <typename G,typename T, typename G::EdgeType::*M>
83    T Get(edge_element_map p,G::EdgeIterator i)
84    {
85    return i->*M;
86    };
87  */
88 
89  /*
90     template <class G>
91     class default_bfs_maps
92     {
93     public:
94     typedef typename G::NodeType NodeType;
95   
96     class_element_map<typename G::NodeIterator,
97     typename G::NodeType,
98     bool,&NodeType::isVis> visited; //node->bool (RW)
99     do_nothing_map tree;   //node->EdgeIterator (W)
100     do_nothing_map dist;   //node->int (W)
101     do_nothing_map priority; //node->int (W)
102     };
103  */
104
105  template<class G>
106  struct bfs_node_data
107  {
108    bool visited;
109    typename G::EdgeIterator tree;
110    int dist;
111    int priority;
112  };
113 
114  template <class G>
115  class bfs_static_maps
116  {
117  public:
118    typedef typename G::NodeType NodeType;
119   
120    /*    class_element_map<typename G::NodeIterator,
121          typename G::NodeType,
122          bfs_node_data<G>,&NT::D> n_d; //node-> data
123    */
124    class
125    {
126    public:
127      bfs_node_data<G> NodeType::*d;
128      typedef bool value_type;
129      void Put(typename G::NodeIterator &i, const value_type &t)
130      {((*i).*d).visited=t;}
131      value_type Get(const typename G::NodeIterator &i) const
132      {return ((*i).*d).visited;}
133    } visited;
134   
135    class
136    {
137    public:
138      bfs_node_data<G> NodeType::*d;
139      typedef typename G::EdgeIterator value_type;
140      void Put(typename G::NodeIterator &i, const value_type &t)
141      {((*i).*d).tree=t;}
142      value_type Get(const typename G::NodeIterator &i) const
143      {return ((*i).*d).tree;}
144    } tree;
145   
146    class
147    {
148    public:
149      bfs_node_data<G> NodeType::*d;
150      typedef int value_type;
151      void Put(typename G::NodeIterator &i, const value_type &t)
152      {((*i).*d).dist=t;}
153      value_type Get(const typename G::NodeIterator &i) const
154      {return ((*i).*d).dist;}
155    } dist;
156   
157    class
158    {
159    public:
160      bfs_node_data<G> NodeType::*d;
161      typedef int value_type;
162      void Put(typename G::NodeIterator &i,  const value_type &t)
163      {((*i).*d).priority=t;}
164      value_type Get(const typename G::NodeIterator &i) const
165      {return ((*i).*d).priority;}
166    } priority;
167   
168    //do_nothing_map tree;   //node->EdgeIterator (W)
169    //    do_nothing_map dist;   //node->int (W)
170    //    do_nothing_map priority; //node->int (W)
171
172    void SetDataField(const bfs_node_data<G> NodeType::*dd)
173    {
174      tree.d=visited.d=dist.d=priority.d=dd;
175    }
176   
177    bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
178    {
179      PutDataField(dd);
180    }
181   
182    bfs_static_maps(const bfs_static_maps<G> &B)
183    {
184      tree.d=B.tree.d;visited.d=B.visited.d;
185      dist.d=B.dist.d;priority.d=B.priority.d;
186    }
187   
188  };
189 
190  template<typename I>
191  struct BFS_Q
192  {
193    I n;
194    int dist;
195    //  BFS_Q() {}
196    //  BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
197  };
198 
199  template<class G,class M>
200  void bfs_fn(G &Gr,const typename G::NodeIterator &start_node,M &maps)
201  {
202    using namespace std;
203   
204    typedef BFS_Q<typename G::NodeIterator> Q_T;
205   
206    Q_T q;
207   
208    int pr=0;
209    typename G::NodeIterator n,m;
210    typename G::OutEdgeIterator e;
211    int d;
212   
213    for(Gr.GetFirst(n);n.isValid();++n)
214      Put(maps.visited,n,false);
215   
216    queue<Q_T> Q;
217   
218    q.n=start_node;
219    q.dist=0;
220    Q.push(q);
221    Put(maps.visited,start_node,true);
222    //      Put(maps::tree,start_node,?????);
223    Put(maps.dist,start_node,0);
224    Put(maps.priority,start_node,pr++);
225   
226    do {
227      n=Q.front().n;d=Q.front().dist+1;
228      Q.pop();
229      for(Gr.GetFirst(e,n);e.isValid();++e)
230        if(!Get(maps.visited,(m=e.Bnode()))) {
231          q.n=m;
232          q.dist=d;
233          Q.push(q);
234          Put(maps.visited,m,true);
235          Put(maps.tree,m,e);
236          Put(maps.dist,m,d);
237          Put(maps.priority,m,pr++);
238        }
239    } while(!Q.empty());
240  };
241
242  // bfs algorithm class
243
244  template<class G>  //the default traits
245  class default_bfs_T
246  {
247  public:
248   
249    typedef G Graph;
250    typedef typename G::OutEdgeIterator SearchEdgeIterator;
251   
252    typedef typename G::NodeMap<bool> visited_map_t;
253    typedef typename G::NodeMap<typename G::EdgeIterator> tree_map_t;
254   
255    typedef typename G::NodeMap<int> dist_map_t;   //node->int (W)
256    typedef typename G::NodeMap<int> priority_map_t; //node->int (W)
257};
258
259  template<class T>
260  class Bfs
261  {
262  public:
263    typedef typename T::Graph Graph;
264    typedef typename Graph::NodeIterator NodeIterator;
265    typedef typename Graph::EdgeIterator EdgeIterator;
266   
267    typedef typename T::SearchEdgeIterator SearchEdgeIterator;
268   
269    typename T::visited_map_t visited_map;
270    typename T::tree_map_t tree_map;
271    typename T::dist_map_t dist_map;
272    typename T::priority_map_t priority_map;
273   
274    struct bfs_queue_cont
275    {
276      NodeIterator n;
277      int dist;
278    };
279   
280    std::queue<bfs_queue_cont> bfs_queue;
281   
282    int priority;
283    Graph *G;
284   
285    //Bfs(int i): visited_map(G), tree_map(G), dist_map(G), priority_map(G) {}
286    Bfs() {}
287
288    void SetG(Graph &Gr)
289    {
290      G=&Gr;
291      visited_map.SetG(Gr);
292      tree_map.SetG(Gr);
293      dist_map.SetG(Gr);
294      priority_map.SetG(Gr);
295    }
296   
297    void Init()
298    {
299      //There must be a better way to do this:
300      while(!bfs_queue.empty()) bfs_queue.pop();
301
302      for(NodeIterator n(*G);n.isValid();++n)
303        Put(visited_map,n,false);
304     
305      priority=0;
306    }
307   
308    void AddStartNode(const NodeIterator &start_node,int dist=0)
309    {
310      bfs_queue_cont q;
311      q.n=start_node;
312      q.dist=dist;
313      bfs_queue.push(q);
314
315      Put(visited_map,start_node,true);
316      //      Put(tree_map,start_node,?????);
317      Put(dist_map,start_node,dist);
318      Put(priority_map,start_node,priority++);   
319    }
320   
321    void Init(const NodeIterator &start_node,int dist=0)
322    {
323      Init();
324      AddStartNode(start_node,dist);
325    }
326
327    void Run()
328    {
329      NodeIterator n,m;
330      int d;
331
332      bfs_queue_cont q;
333      while(!(bfs_queue.empty()/* && other stop conditions */)) {
334        n=bfs_queue.front().n;d=bfs_queue.front().dist+1;
335        bfs_queue.pop();
336        for(SearchEdgeIterator e(*G,n);e.isValid();++e)
337          if(!Get(visited_map,(m=e.Bnode()))) {
338            q.n=m;
339            q.dist=d;
340            bfs_queue.push(q);
341            Put(visited_map,m,true);
342            Put(tree_map,m,e);
343            Put(dist_map,m,d);
344            Put(priority_map,m,priority++);
345          }
346      }
347    }
348  };
349 
350}
351 
352#endif
Note: See TracBrowser for help on using the repository browser.