COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/bfs_iterator.hh @ 59:41c7f9c09a12

Last change on this file since 59:41c7f9c09a12 was 58:f71840c04b2a, checked in by marci, 21 years ago

BfsIterator2
File size: 13.6 KB
Line 
1#ifndef BFS_ITERATOR_HH
2#define BFS_ITERATOR_HH
3
4#include <queue>
5#include <stack>
6
7namespace marci {
8
9  template <typename Graph>
10  struct bfs {
11    typedef typename Graph::NodeIt NodeIt;
12    typedef typename Graph::EdgeIt EdgeIt;
13    typedef typename Graph::EachNodeIt EachNodeIt;
14    typedef typename Graph::OutEdgeIt OutEdgeIt;
15    Graph& G;
16    NodeIt s;
17    typename Graph::NodeMap<bool> reached;
18    typename Graph::NodeMap<EdgeIt> pred;
19    typename Graph::NodeMap<int> dist;
20    std::queue<NodeIt> bfs_queue;
21    bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
22      bfs_queue.push(s);
23      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
24        reached.set(i, false);
25      reached.set(s, true);
26      dist.set(s, 0);
27    }
28   
29    void run() {
30      while (!bfs_queue.empty()) {
31        NodeIt v=bfs_queue.front();
32        OutEdgeIt e=G.template first<OutEdgeIt>(v);
33        bfs_queue.pop();
34        for( ; e.valid(); ++e) {
35          NodeIt w=G.bNode(e);
36          std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
37          if (!reached.get(w)) {
38            std::cout << G.id(w) << " is newly reached :-)" << std::endl;
39            bfs_queue.push(w);
40            dist.set(w, dist.get(v)+1);
41            pred.set(w, e);
42            reached.set(w, true);
43          } else {
44            std::cout << G.id(w) << " is already reached" << std::endl;
45          }
46        }
47      }
48    }
49  };
50
51  template <typename Graph>
52  struct bfs_visitor {
53    typedef typename Graph::NodeIt NodeIt;
54    typedef typename Graph::EdgeIt EdgeIt;
55    typedef typename Graph::OutEdgeIt OutEdgeIt;
56    Graph& G;
57    bfs_visitor(Graph& _G) : G(_G) { }
58    void at_previously_reached(OutEdgeIt& e) {
59      //NodeIt v=G.aNode(e);
60      NodeIt w=G.bNode(e);
61      std::cout << G.id(w) << " is already reached" << std::endl;
62   }
63    void at_newly_reached(OutEdgeIt& e) {
64      //NodeIt v=G.aNode(e);
65      NodeIt w=G.bNode(e);
66      std::cout << G.id(w) << " is newly reached :-)" << std::endl;
67    }
68  };
69
70  template <typename Graph, typename ReachedMap, typename visitor_type>
71  struct bfs_iterator {
72    typedef typename Graph::NodeIt NodeIt;
73    typedef typename Graph::EdgeIt EdgeIt;
74    typedef typename Graph::OutEdgeIt OutEdgeIt;
75    Graph& G;
76    std::queue<OutEdgeIt>& bfs_queue;
77    ReachedMap& reached;
78    visitor_type& visitor;
79    void process() {
80      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
81      if (bfs_queue.empty()) return;
82      OutEdgeIt e=bfs_queue.front();
83      //NodeIt v=G.aNode(e);
84      NodeIt w=G.bNode(e);
85      if (!reached.get(w)) {
86        visitor.at_newly_reached(e);
87        bfs_queue.push(G.template first<OutEdgeIt>(w));
88        reached.set(w, true);
89      } else {
90        visitor.at_previously_reached(e);
91      }
92    }
93    bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
94      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
95      valid();
96    }
97    bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
98      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
99      //if (bfs_queue.empty()) return *this;
100      if (!valid()) return *this;
101      ++(bfs_queue.front());
102      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
103      valid();
104      return *this;
105    }
106    //void next() {
107    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
108    //  if (bfs_queue.empty()) return;
109    //  ++(bfs_queue.front());
110    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
111    //}
112    bool valid() {
113      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
114      if (bfs_queue.empty()) return false; else return true;
115    }
116    //bool finished() {
117    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
118    //  if (bfs_queue.empty()) return true; else return false;
119    //}
120    operator EdgeIt () { return bfs_queue.front(); }
121
122  };
123
124  template <typename Graph, typename ReachedMap>
125  struct bfs_iterator1 {
126    typedef typename Graph::NodeIt NodeIt;
127    typedef typename Graph::EdgeIt EdgeIt;
128    typedef typename Graph::OutEdgeIt OutEdgeIt;
129    Graph& G;
130    std::queue<OutEdgeIt>& bfs_queue;
131    ReachedMap& reached;
132    bool _newly_reached;
133    bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
134      valid();
135      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
136        OutEdgeIt e=bfs_queue.front();
137        NodeIt w=G.bNode(e);
138        if (!reached.get(w)) {
139          bfs_queue.push(G.template first<OutEdgeIt>(w));
140          reached.set(w, true);
141          _newly_reached=true;
142        } else {
143          _newly_reached=false;
144        }
145      }
146    }
147    bfs_iterator1<Graph, ReachedMap>& operator++() {
148      if (!valid()) return *this;
149      ++(bfs_queue.front());
150      valid();
151      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
152        OutEdgeIt e=bfs_queue.front();
153        NodeIt w=G.bNode(e);
154        if (!reached.get(w)) {
155          bfs_queue.push(G.template first<OutEdgeIt>(w));
156          reached.set(w, true);
157          _newly_reached=true;
158        } else {
159          _newly_reached=false;
160        }
161      }
162      return *this;
163    }
164    bool valid() {
165      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
166      if (bfs_queue.empty()) return false; else return true;
167    }
168    operator OutEdgeIt() { return bfs_queue.front(); }
169    //ize
170    bool newly_reached() { return _newly_reached; }
171
172  };
173
174  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
175  struct BfsIterator {
176    typedef typename Graph::NodeIt NodeIt;
177    Graph& G;
178    std::queue<OutEdgeIt>& bfs_queue;
179    ReachedMap& reached;
180    bool b_node_newly_reached;
181    OutEdgeIt actual_edge;
182    BfsIterator(Graph& _G,
183                std::queue<OutEdgeIt>& _bfs_queue,
184                ReachedMap& _reached) :
185      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
186      actual_edge=bfs_queue.front();
187      if (actual_edge.valid()) {
188        NodeIt w=G.bNode(actual_edge);
189        if (!reached.get(w)) {
190          bfs_queue.push(G.firstOutEdge(w));
191          reached.set(w, true);
192          b_node_newly_reached=true;
193        } else {
194          b_node_newly_reached=false;
195        }
196      }
197    }
198    BfsIterator<Graph, OutEdgeIt, ReachedMap>&
199    operator++() {
200      if (bfs_queue.front().valid()) {
201        ++(bfs_queue.front());
202        actual_edge=bfs_queue.front();
203        if (actual_edge.valid()) {
204          NodeIt w=G.bNode(actual_edge);
205          if (!reached.get(w)) {
206            bfs_queue.push(G.firstOutEdge(w));
207            reached.set(w, true);
208            b_node_newly_reached=true;
209          } else {
210            b_node_newly_reached=false;
211          }
212        }
213      } else {
214        bfs_queue.pop();
215        actual_edge=bfs_queue.front();
216        if (actual_edge.valid()) {
217          NodeIt w=G.bNode(actual_edge);
218          if (!reached.get(w)) {
219            bfs_queue.push(G.firstOutEdge(w));
220            reached.set(w, true);
221            b_node_newly_reached=true;
222          } else {
223            b_node_newly_reached=false;
224          }
225        }
226      }
227      return *this;
228    }
229    bool finished() { return bfs_queue.empty(); }
230    operator OutEdgeIt () { return actual_edge; }
231    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
232    bool aNodeIsExamined() { return !(actual_edge.valid()); }
233  };
234
235
236  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
237  struct DfsIterator {
238    typedef typename Graph::NodeIt NodeIt;
239    Graph& G;
240    std::stack<OutEdgeIt>& bfs_queue;
241    ReachedMap& reached;
242    bool b_node_newly_reached;
243    OutEdgeIt actual_edge;
244    DfsIterator(Graph& _G,
245                std::stack<OutEdgeIt>& _bfs_queue,
246                ReachedMap& _reached) :
247      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
248      actual_edge=bfs_queue.top();
249      if (actual_edge.valid()) {
250        NodeIt w=G.bNode(actual_edge);
251        if (!reached.get(w)) {
252          bfs_queue.push(G.firstOutEdge(w));
253          reached.set(w, true);
254          b_node_newly_reached=true;
255        } else {
256          ++(bfs_queue.top());
257          b_node_newly_reached=false;
258        }
259      } else {
260        bfs_queue.pop();
261      }
262    }
263    DfsIterator<Graph, OutEdgeIt, ReachedMap>&
264    operator++() {
265      actual_edge=bfs_queue.top();
266      if (actual_edge.valid()) {
267        NodeIt w=G.bNode(actual_edge);
268        if (!reached.get(w)) {
269          bfs_queue.push(G.firstOutEdge(w));
270          reached.set(w, true);
271          b_node_newly_reached=true;
272        } else {
273          ++(bfs_queue.top());
274          b_node_newly_reached=false;
275        }
276      } else {
277        bfs_queue.pop();
278      }
279      return *this;
280    }
281    bool finished() { return bfs_queue.empty(); }
282    operator OutEdgeIt () { return actual_edge; }
283    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
284    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
285  };
286
287  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
288  struct BfsIterator1 {
289    typedef typename Graph::NodeIt NodeIt;
290    Graph& G;
291    std::queue<OutEdgeIt>& bfs_queue;
292    ReachedMap& reached;
293    bool b_node_newly_reached;
294    OutEdgeIt actual_edge;
295    BfsIterator1(Graph& _G,
296                std::queue<OutEdgeIt>& _bfs_queue,
297                ReachedMap& _reached) :
298      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
299      actual_edge=bfs_queue.front();
300      if (actual_edge.valid()) {
301        NodeIt w=G.bNode(actual_edge);
302        if (!reached.get(w)) {
303          bfs_queue.push(OutEdgeIt(G, w));
304          reached.set(w, true);
305          b_node_newly_reached=true;
306        } else {
307          b_node_newly_reached=false;
308        }
309      }
310    }
311    void next() {
312      if (bfs_queue.front().valid()) {
313        ++(bfs_queue.front());
314        actual_edge=bfs_queue.front();
315        if (actual_edge.valid()) {
316          NodeIt w=G.bNode(actual_edge);
317          if (!reached.get(w)) {
318            bfs_queue.push(OutEdgeIt(G, w));
319            reached.set(w, true);
320            b_node_newly_reached=true;
321          } else {
322            b_node_newly_reached=false;
323          }
324        }
325      } else {
326        bfs_queue.pop();
327        actual_edge=bfs_queue.front();
328        if (actual_edge.valid()) {
329          NodeIt w=G.bNode(actual_edge);
330          if (!reached.get(w)) {
331            bfs_queue.push(OutEdgeIt(G, w));
332            reached.set(w, true);
333            b_node_newly_reached=true;
334          } else {
335            b_node_newly_reached=false;
336          }
337        }
338      }
339      //return *this;
340    }
341    bool finished() { return bfs_queue.empty(); }
342    operator OutEdgeIt () { return actual_edge; }
343    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
344    bool aNodeIsExamined() { return !(actual_edge.valid()); }
345  };
346
347
348  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
349  struct DfsIterator1 {
350    typedef typename Graph::NodeIt NodeIt;
351    Graph& G;
352    std::stack<OutEdgeIt>& bfs_queue;
353    ReachedMap& reached;
354    bool b_node_newly_reached;
355    OutEdgeIt actual_edge;
356    DfsIterator1(Graph& _G,
357                std::stack<OutEdgeIt>& _bfs_queue,
358                ReachedMap& _reached) :
359      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
360      //actual_edge=bfs_queue.top();
361      //if (actual_edge.valid()) {
362      //        NodeIt w=G.bNode(actual_edge);
363      //if (!reached.get(w)) {
364      //  bfs_queue.push(OutEdgeIt(G, w));
365      //  reached.set(w, true);
366      //  b_node_newly_reached=true;
367      //} else {
368      //  ++(bfs_queue.top());
369      //  b_node_newly_reached=false;
370      //}
371      //} else {
372      //        bfs_queue.pop();
373      //}
374    }
375    void next() {
376      actual_edge=bfs_queue.top();
377      if (actual_edge.valid()) {
378        NodeIt w=G.bNode(actual_edge);
379        if (!reached.get(w)) {
380          bfs_queue.push(OutEdgeIt(G, w));
381          reached.set(w, true);
382          b_node_newly_reached=true;
383        } else {
384          ++(bfs_queue.top());
385          b_node_newly_reached=false;
386        }
387      } else {
388        bfs_queue.pop();
389      }
390      //return *this;
391    }
392    bool finished() { return bfs_queue.empty(); }
393    operator OutEdgeIt () { return actual_edge; }
394    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
395    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
396  };
397
398  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
399  class BfsIterator2 {
400    typedef typename Graph::NodeIt NodeIt;
401    const Graph& G;
402    std::queue<OutEdgeIt> bfs_queue;
403    ReachedMap reached;
404    bool b_node_newly_reached;
405    OutEdgeIt actual_edge;
406  public:
407    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
408    void pushAndSetReached(const NodeIt s) {
409      reached.set(s, true);
410      if (bfs_queue.empty()) {
411        bfs_queue.push(G.template first<OutEdgeIt>(s));
412        actual_edge=bfs_queue.front();
413        if (actual_edge.valid()) {
414          NodeIt w=G.bNode(actual_edge);
415          if (!reached.get(w)) {
416            bfs_queue.push(G.template first<OutEdgeIt>(w));
417            reached.set(w, true);
418            b_node_newly_reached=true;
419          } else {
420            b_node_newly_reached=false;
421          }
422        } //else {
423        //}
424      } else {
425        bfs_queue.push(G.template first<OutEdgeIt>(s));
426      }
427    }
428    BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
429    operator++() {
430      if (bfs_queue.front().valid()) {
431        ++(bfs_queue.front());
432        actual_edge=bfs_queue.front();
433        if (actual_edge.valid()) {
434          NodeIt w=G.bNode(actual_edge);
435          if (!reached.get(w)) {
436            bfs_queue.push(G.template first<OutEdgeIt>(w));
437            reached.set(w, true);
438            b_node_newly_reached=true;
439          } else {
440            b_node_newly_reached=false;
441          }
442        }
443      } else {
444        bfs_queue.pop();
445        if (!bfs_queue.empty()) {
446          actual_edge=bfs_queue.front();
447        } else {
448          actual_edge=OutEdgeIt();
449        }
450        if (actual_edge.valid()) {
451          NodeIt w=G.bNode(actual_edge);
452          if (!reached.get(w)) {
453            bfs_queue.push(G.template first<OutEdgeIt>(w));
454            reached.set(w, true);
455            b_node_newly_reached=true;
456          } else {
457            b_node_newly_reached=false;
458          }
459        }
460      }
461      return *this;
462    }
463    bool finished() const { return bfs_queue.empty(); }
464    operator OutEdgeIt () const { return actual_edge; }
465    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
466    bool isANodeExamined() const { return !(actual_edge.valid()); }
467    const ReachedMap& getReachedMap() const { return reached; }
468    const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
469 };
470
471
472} // namespace marci
473
474#endif //BFS_ITERATOR_HH
Note: See TracBrowser for help on using the repository browser.