COIN-OR::LEMON - Graph Library

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

Last change on this file since 3:272a5677bd6d was 3:272a5677bd6d, checked in by Alpar Juttner, 17 years ago
  • Marci type iterator constructors
  • src/demo/bfsdemo.cc: demo for bfs.h
  • cosmetical changes
File size: 5.4 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//     //    template <bfs_T<G>>
27//     //    void bfs(bfs_T::Graph &G,const bfs_T::NodeIterator &start_node,const &maps)
28
29   
30 
31//   template <class G>
32//   class bfs_maps_T
33//   {
34//     typedef visited; //node->bool (RW)
35//     typedef tree;    //node->EdgeIterator (W)
36//     typedef dist;   //node->int (W)
37//     typedef priority; //node->int (W)
38//   };
39 
40 
41//   Nem jo! Osszeakad a masik Put-tel
42//   class do_nothing_map {};
43//   template <typename V,typename T>
44//   void Put(const do_nothing_map &p,const V &v,const T &t) {}
45 
46  struct do_nothing_map {
47  template <typename V,typename T>
48  static void Put(V v,T t) {}
49  };
50 
51
52  template <typename I,typename C, typename T, T C::*M>
53  class class_element_map {
54  public:
55    typedef T value_type;
56    static void Put(const I &i, const T &t) {(*i).*M=t;}
57    static T Get(const I i) {return (*i).*M;}
58    T &operator[](I i) {return (*i).*M;}
59  };
60
61  /*
62     template <typename C,typename I,typename T, T C::*M>
63     void Put(class_element_map<C,T,M> p,I i, T t)
64     {
65     i->*M=t;   
66     };
67  */
68
69  template <typename P,typename I,typename T>
70  inline void Put(P &p,const I &i, const T &t)
71  {
72    p.Put(i,t);   
73  };
74  template <typename P,typename I>
75  inline typename P::value_type Get(const P &p,const I &i)
76  {
77    return p.Get(i);   
78  };
79
80  /*
81  template <typename G,typename T, typename G::EdgeType::*M>
82  T Get(edge_element_map p,G::EdgeIterator i)
83  {
84    return i->*M;
85  };
86  */
87 
88  /*
89  template <class G>
90  class default_bfs_maps
91  {
92  public:
93    typedef typename G::NodeType NodeType;
94   
95    class_element_map<typename G::NodeIterator,
96                      typename G::NodeType,
97                      bool,&NodeType::isVis> visited; //node->bool (RW)
98    do_nothing_map tree;   //node->EdgeIterator (W)
99    do_nothing_map dist;   //node->int (W)
100    do_nothing_map priority; //node->int (W)
101  };
102  */
103
104  template<class G>
105  struct bfs_node_data
106  {
107    bool visited;
108    typename G::EdgeIterator tree;
109    int dist;
110    int priority;
111  };
112 
113  template <class G>
114  class bfs_static_maps
115  {
116  public:
117    typedef typename G::NodeType NodeType;
118   
119    /*    class_element_map<typename G::NodeIterator,
120                      typename G::NodeType,
121                      bfs_node_data<G>,&NT::D> n_d; //node-> data
122    */
123    class
124    {
125    public:
126      bfs_node_data<G> NodeType::*d;
127      typedef bool value_type;
128      void Put(typename G::NodeIterator &i, const value_type &t)
129      {((*i).*d).visited=t;}
130      value_type Get(const typename G::NodeIterator &i) const
131      {return ((*i).*d).visited;}
132    } visited;
133   
134    class
135    {
136    public:
137      bfs_node_data<G> NodeType::*d;
138      typedef typename G::EdgeIterator value_type;
139      void Put(typename G::NodeIterator &i, const value_type &t)
140      {((*i).*d).tree=t;}
141      value_type Get(const typename G::NodeIterator &i) const
142      {return ((*i).*d).tree;}
143    } tree;
144   
145    class
146    {
147    public:
148      bfs_node_data<G> NodeType::*d;
149      typedef int value_type;
150      void Put(typename G::NodeIterator &i, const value_type &t)
151      {((*i).*d).dist=t;}
152      value_type Get(const typename G::NodeIterator &i) const
153      {return ((*i).*d).dist;}
154    } dist;
155   
156    class
157    {
158    public:
159      bfs_node_data<G> NodeType::*d;
160      typedef int value_type;
161      void Put(typename G::NodeIterator &i,  const value_type &t)
162      {((*i).*d).priority=t;}
163      value_type Get(const typename G::NodeIterator &i) const
164      {return ((*i).*d).priority;}
165    } priority;
166   
167    //do_nothing_map tree;   //node->EdgeIterator (W)
168    //    do_nothing_map dist;   //node->int (W)
169    //    do_nothing_map priority; //node->int (W)
170
171    void SetDataField(const bfs_node_data<G> NodeType::*dd)
172    {
173      tree.d=visited.d=dist.d=priority.d=dd;
174    }
175   
176    bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
177    {
178      PutDataField(dd);
179    }
180   
181    bfs_static_maps(const bfs_static_maps<G> &B)
182    {
183      tree.d=B.tree.d;visited.d=B.visited.d;
184      dist.d=B.dist.d;priority.d=B.priority.d;
185    }
186   
187  };
188 
189  template<typename I>
190  struct BFS_Q
191  {
192    I n;
193    int dist;
194    //  BFS_Q() {}
195    //  BFS_Q(BFS_Q<I> &b) {n=b.n;dist=b.dist;}
196  };
197 
198  template<class G,class M>
199  void bfs(G &Gr,const typename G::NodeIterator &start_node,M &maps)
200  {
201    using namespace std;
202   
203    typedef BFS_Q<typename G::NodeIterator> Q_T;
204   
205    Q_T q;
206   
207    int pr=0;
208    typename G::NodeIterator n,m;
209    typename G::OutEdgeIterator e;
210    int d;
211   
212    for(Gr.GetFirst(n);n.isValid();++n)
213      Put(maps.visited,n,false);
214   
215    queue<Q_T> Q;
216   
217    q.n=start_node;
218    q.dist=0;
219    Q.push(q);
220    Put(maps.visited,start_node,true);
221    //      Put(maps::tree,start_node,?????);
222    Put(maps.dist,start_node,0);
223    Put(maps.priority,start_node,pr++);
224   
225    do {
226      n=Q.front().n;d=Q.front().dist+1;
227      Q.pop();
228      for(Gr.GetFirst(e,n);e.isValid();++e)
229        if(!Get(maps.visited,(m=e.Bnode()))) {
230          q.n=m;
231          q.dist=d;
232          Q.push(q);
233          Put(maps.visited,m,true);
234          Put(maps.tree,m,e);
235          Put(maps.dist,m,d);
236          Put(maps.priority,m,pr++);
237        }
238    } while(!Q.empty());
239  };
240}
241#endif
Note: See TracBrowser for help on using the repository browser.