COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/bfs_iterator.hh @ 133:0631992fe7a1

Last change on this file since 133:0631992fe7a1 was 133:0631992fe7a1, checked in by marci, 16 years ago

Dinits blocking flow added to edmonds_karp_demo.hh.

File size: 22.1 KB
Line 
1#ifndef BFS_ITERATOR_HH
2#define BFS_ITERATOR_HH
3
4#include <queue>
5#include <stack>
6#include <utility>
7#include <graph_wrapper.h>
8
9namespace hugo {
10
11  template <typename Graph>
12  struct bfs {
13    typedef typename Graph::NodeIt NodeIt;
14    typedef typename Graph::EdgeIt EdgeIt;
15    typedef typename Graph::EachNodeIt EachNodeIt;
16    typedef typename Graph::OutEdgeIt OutEdgeIt;
17    Graph& G;
18    NodeIt s;
19    typename Graph::NodeMap<bool> reached;
20    typename Graph::NodeMap<EdgeIt> pred;
21    typename Graph::NodeMap<int> dist;
22    std::queue<NodeIt> bfs_queue;
23    bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
24      bfs_queue.push(s);
25      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
26        reached.set(i, false);
27      reached.set(s, true);
28      dist.set(s, 0);
29    }
30   
31    void run() {
32      while (!bfs_queue.empty()) {
33        NodeIt v=bfs_queue.front();
34        OutEdgeIt e=G.template first<OutEdgeIt>(v);
35        bfs_queue.pop();
36        for( ; e.valid(); ++e) {
37          NodeIt w=G.bNode(e);
38          std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
39          if (!reached.get(w)) {
40            std::cout << G.id(w) << " is newly reached :-)" << std::endl;
41            bfs_queue.push(w);
42            dist.set(w, dist.get(v)+1);
43            pred.set(w, e);
44            reached.set(w, true);
45          } else {
46            std::cout << G.id(w) << " is already reached" << std::endl;
47          }
48        }
49      }
50    }
51  };
52
53  template <typename Graph>
54  struct bfs_visitor {
55    typedef typename Graph::NodeIt NodeIt;
56    typedef typename Graph::EdgeIt EdgeIt;
57    typedef typename Graph::OutEdgeIt OutEdgeIt;
58    Graph& G;
59    bfs_visitor(Graph& _G) : G(_G) { }
60    void at_previously_reached(OutEdgeIt& e) {
61      //NodeIt v=G.aNode(e);
62      NodeIt w=G.bNode(e);
63      std::cout << G.id(w) << " is already reached" << std::endl;
64   }
65    void at_newly_reached(OutEdgeIt& e) {
66      //NodeIt v=G.aNode(e);
67      NodeIt w=G.bNode(e);
68      std::cout << G.id(w) << " is newly reached :-)" << std::endl;
69    }
70  };
71
72  template <typename Graph, typename ReachedMap, typename visitor_type>
73  struct bfs_iterator {
74    typedef typename Graph::NodeIt NodeIt;
75    typedef typename Graph::EdgeIt EdgeIt;
76    typedef typename Graph::OutEdgeIt OutEdgeIt;
77    Graph& G;
78    std::queue<OutEdgeIt>& bfs_queue;
79    ReachedMap& reached;
80    visitor_type& visitor;
81    void process() {
82      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
83      if (bfs_queue.empty()) return;
84      OutEdgeIt e=bfs_queue.front();
85      //NodeIt v=G.aNode(e);
86      NodeIt w=G.bNode(e);
87      if (!reached.get(w)) {
88        visitor.at_newly_reached(e);
89        bfs_queue.push(G.template first<OutEdgeIt>(w));
90        reached.set(w, true);
91      } else {
92        visitor.at_previously_reached(e);
93      }
94    }
95    bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
96      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
97      valid();
98    }
99    bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
100      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
101      //if (bfs_queue.empty()) return *this;
102      if (!valid()) return *this;
103      ++(bfs_queue.front());
104      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
105      valid();
106      return *this;
107    }
108    //void next() {
109    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
110    //  if (bfs_queue.empty()) return;
111    //  ++(bfs_queue.front());
112    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
113    //}
114    bool valid() {
115      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
116      if (bfs_queue.empty()) return false; else return true;
117    }
118    //bool finished() {
119    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
120    //  if (bfs_queue.empty()) return true; else return false;
121    //}
122    operator EdgeIt () { return bfs_queue.front(); }
123
124  };
125
126  template <typename Graph, typename ReachedMap>
127  struct bfs_iterator1 {
128    typedef typename Graph::NodeIt NodeIt;
129    typedef typename Graph::EdgeIt EdgeIt;
130    typedef typename Graph::OutEdgeIt OutEdgeIt;
131    Graph& G;
132    std::queue<OutEdgeIt>& bfs_queue;
133    ReachedMap& reached;
134    bool _newly_reached;
135    bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
136      valid();
137      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
138        OutEdgeIt e=bfs_queue.front();
139        NodeIt w=G.bNode(e);
140        if (!reached.get(w)) {
141          bfs_queue.push(G.template first<OutEdgeIt>(w));
142          reached.set(w, true);
143          _newly_reached=true;
144        } else {
145          _newly_reached=false;
146        }
147      }
148    }
149    bfs_iterator1<Graph, ReachedMap>& operator++() {
150      if (!valid()) return *this;
151      ++(bfs_queue.front());
152      valid();
153      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
154        OutEdgeIt e=bfs_queue.front();
155        NodeIt w=G.bNode(e);
156        if (!reached.get(w)) {
157          bfs_queue.push(G.template first<OutEdgeIt>(w));
158          reached.set(w, true);
159          _newly_reached=true;
160        } else {
161          _newly_reached=false;
162        }
163      }
164      return *this;
165    }
166    bool valid() {
167      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
168      if (bfs_queue.empty()) return false; else return true;
169    }
170    operator OutEdgeIt() { return bfs_queue.front(); }
171    //ize
172    bool newly_reached() { return _newly_reached; }
173
174  };
175
176  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
177  struct BfsIterator {
178    typedef typename Graph::NodeIt NodeIt;
179    Graph& G;
180    std::queue<OutEdgeIt>& bfs_queue;
181    ReachedMap& reached;
182    bool b_node_newly_reached;
183    OutEdgeIt actual_edge;
184    BfsIterator(Graph& _G,
185                std::queue<OutEdgeIt>& _bfs_queue,
186                ReachedMap& _reached) :
187      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
188      actual_edge=bfs_queue.front();
189      if (actual_edge.valid()) {
190        NodeIt w=G.bNode(actual_edge);
191        if (!reached.get(w)) {
192          bfs_queue.push(G.firstOutEdge(w));
193          reached.set(w, true);
194          b_node_newly_reached=true;
195        } else {
196          b_node_newly_reached=false;
197        }
198      }
199    }
200    BfsIterator<Graph, OutEdgeIt, ReachedMap>&
201    operator++() {
202      if (bfs_queue.front().valid()) {
203        ++(bfs_queue.front());
204        actual_edge=bfs_queue.front();
205        if (actual_edge.valid()) {
206          NodeIt w=G.bNode(actual_edge);
207          if (!reached.get(w)) {
208            bfs_queue.push(G.firstOutEdge(w));
209            reached.set(w, true);
210            b_node_newly_reached=true;
211          } else {
212            b_node_newly_reached=false;
213          }
214        }
215      } else {
216        bfs_queue.pop();
217        actual_edge=bfs_queue.front();
218        if (actual_edge.valid()) {
219          NodeIt w=G.bNode(actual_edge);
220          if (!reached.get(w)) {
221            bfs_queue.push(G.firstOutEdge(w));
222            reached.set(w, true);
223            b_node_newly_reached=true;
224          } else {
225            b_node_newly_reached=false;
226          }
227        }
228      }
229      return *this;
230    }
231    bool finished() { return bfs_queue.empty(); }
232    operator OutEdgeIt () { return actual_edge; }
233    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
234    bool aNodeIsExamined() { return !(actual_edge.valid()); }
235  };
236
237
238  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
239  struct DfsIterator {
240    typedef typename Graph::NodeIt NodeIt;
241    Graph& G;
242    std::stack<OutEdgeIt>& bfs_queue;
243    ReachedMap& reached;
244    bool b_node_newly_reached;
245    OutEdgeIt actual_edge;
246    DfsIterator(Graph& _G,
247                std::stack<OutEdgeIt>& _bfs_queue,
248                ReachedMap& _reached) :
249      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
250      actual_edge=bfs_queue.top();
251      if (actual_edge.valid()) {
252        NodeIt w=G.bNode(actual_edge);
253        if (!reached.get(w)) {
254          bfs_queue.push(G.firstOutEdge(w));
255          reached.set(w, true);
256          b_node_newly_reached=true;
257        } else {
258          ++(bfs_queue.top());
259          b_node_newly_reached=false;
260        }
261      } else {
262        bfs_queue.pop();
263      }
264    }
265    DfsIterator<Graph, OutEdgeIt, ReachedMap>&
266    operator++() {
267      actual_edge=bfs_queue.top();
268      if (actual_edge.valid()) {
269        NodeIt w=G.bNode(actual_edge);
270        if (!reached.get(w)) {
271          bfs_queue.push(G.firstOutEdge(w));
272          reached.set(w, true);
273          b_node_newly_reached=true;
274        } else {
275          ++(bfs_queue.top());
276          b_node_newly_reached=false;
277        }
278      } else {
279        bfs_queue.pop();
280      }
281      return *this;
282    }
283    bool finished() { return bfs_queue.empty(); }
284    operator OutEdgeIt () { return actual_edge; }
285    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
286    bool aNodeIsExamined() { return !(actual_edge.valid()); }
287  };
288
289  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
290  struct BfsIterator1 {
291    typedef typename Graph::NodeIt NodeIt;
292    Graph& G;
293    std::queue<OutEdgeIt>& bfs_queue;
294    ReachedMap& reached;
295    bool b_node_newly_reached;
296    OutEdgeIt actual_edge;
297    BfsIterator1(Graph& _G,
298                std::queue<OutEdgeIt>& _bfs_queue,
299                ReachedMap& _reached) :
300      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
301      actual_edge=bfs_queue.front();
302      if (actual_edge.valid()) {
303        NodeIt w=G.bNode(actual_edge);
304        if (!reached.get(w)) {
305          bfs_queue.push(OutEdgeIt(G, w));
306          reached.set(w, true);
307          b_node_newly_reached=true;
308        } else {
309          b_node_newly_reached=false;
310        }
311      }
312    }
313    void next() {
314      if (bfs_queue.front().valid()) {
315        ++(bfs_queue.front());
316        actual_edge=bfs_queue.front();
317        if (actual_edge.valid()) {
318          NodeIt w=G.bNode(actual_edge);
319          if (!reached.get(w)) {
320            bfs_queue.push(OutEdgeIt(G, w));
321            reached.set(w, true);
322            b_node_newly_reached=true;
323          } else {
324            b_node_newly_reached=false;
325          }
326        }
327      } else {
328        bfs_queue.pop();
329        actual_edge=bfs_queue.front();
330        if (actual_edge.valid()) {
331          NodeIt w=G.bNode(actual_edge);
332          if (!reached.get(w)) {
333            bfs_queue.push(OutEdgeIt(G, w));
334            reached.set(w, true);
335            b_node_newly_reached=true;
336          } else {
337            b_node_newly_reached=false;
338          }
339        }
340      }
341      //return *this;
342    }
343    bool finished() { return bfs_queue.empty(); }
344    operator OutEdgeIt () { return actual_edge; }
345    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
346    bool aNodeIsExamined() { return !(actual_edge.valid()); }
347  };
348
349
350  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
351  struct DfsIterator1 {
352    typedef typename Graph::NodeIt NodeIt;
353    Graph& G;
354    std::stack<OutEdgeIt>& bfs_queue;
355    ReachedMap& reached;
356    bool b_node_newly_reached;
357    OutEdgeIt actual_edge;
358    DfsIterator1(Graph& _G,
359                std::stack<OutEdgeIt>& _bfs_queue,
360                ReachedMap& _reached) :
361      G(_G), bfs_queue(_bfs_queue), reached(_reached) {
362      //actual_edge=bfs_queue.top();
363      //if (actual_edge.valid()) {
364      //        NodeIt w=G.bNode(actual_edge);
365      //if (!reached.get(w)) {
366      //  bfs_queue.push(OutEdgeIt(G, w));
367      //  reached.set(w, true);
368      //  b_node_newly_reached=true;
369      //} else {
370      //  ++(bfs_queue.top());
371      //  b_node_newly_reached=false;
372      //}
373      //} else {
374      //        bfs_queue.pop();
375      //}
376    }
377    void next() {
378      actual_edge=bfs_queue.top();
379      if (actual_edge.valid()) {
380        NodeIt w=G.bNode(actual_edge);
381        if (!reached.get(w)) {
382          bfs_queue.push(OutEdgeIt(G, w));
383          reached.set(w, true);
384          b_node_newly_reached=true;
385        } else {
386          ++(bfs_queue.top());
387          b_node_newly_reached=false;
388        }
389      } else {
390        bfs_queue.pop();
391      }
392      //return *this;
393    }
394    bool finished() { return bfs_queue.empty(); }
395    operator OutEdgeIt () { return actual_edge; }
396    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
397    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
398  };
399
400  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
401  class BfsIterator2 {
402    typedef typename Graph::NodeIt NodeIt;
403    const Graph& G;
404    std::queue<OutEdgeIt> bfs_queue;
405    ReachedMap reached;
406    bool b_node_newly_reached;
407    OutEdgeIt actual_edge;
408  public:
409    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
410    void pushAndSetReached(NodeIt s) {
411      reached.set(s, true);
412      if (bfs_queue.empty()) {
413        bfs_queue.push(G.template first<OutEdgeIt>(s));
414        actual_edge=bfs_queue.front();
415        if (actual_edge.valid()) {
416          NodeIt w=G.bNode(actual_edge);
417          if (!reached.get(w)) {
418            bfs_queue.push(G.template first<OutEdgeIt>(w));
419            reached.set(w, true);
420            b_node_newly_reached=true;
421          } else {
422            b_node_newly_reached=false;
423          }
424        } //else {
425        //}
426      } else {
427        bfs_queue.push(G.template first<OutEdgeIt>(s));
428      }
429    }
430    BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
431    operator++() {
432      if (bfs_queue.front().valid()) {
433        ++(bfs_queue.front());
434        actual_edge=bfs_queue.front();
435        if (actual_edge.valid()) {
436          NodeIt w=G.bNode(actual_edge);
437          if (!reached.get(w)) {
438            bfs_queue.push(G.template first<OutEdgeIt>(w));
439            reached.set(w, true);
440            b_node_newly_reached=true;
441          } else {
442            b_node_newly_reached=false;
443          }
444        }
445      } else {
446        bfs_queue.pop();
447        if (!bfs_queue.empty()) {
448          actual_edge=bfs_queue.front();
449          if (actual_edge.valid()) {
450            NodeIt w=G.bNode(actual_edge);
451            if (!reached.get(w)) {
452              bfs_queue.push(G.template first<OutEdgeIt>(w));
453              reached.set(w, true);
454              b_node_newly_reached=true;
455            } else {
456              b_node_newly_reached=false;
457            }
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  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
473  class BfsIterator3 {
474    typedef typename Graph::NodeIt NodeIt;
475    const Graph& G;
476    std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
477    ReachedMap reached;
478    bool b_node_newly_reached;
479    OutEdgeIt actual_edge;
480  public:
481    BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
482    void pushAndSetReached(NodeIt s) {
483      reached.set(s, true);
484      if (bfs_queue.empty()) {
485        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
486        actual_edge=bfs_queue.front().second;
487        if (actual_edge.valid()) {
488          NodeIt w=G.bNode(actual_edge);
489          if (!reached.get(w)) {
490            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
491            reached.set(w, true);
492            b_node_newly_reached=true;
493          } else {
494            b_node_newly_reached=false;
495          }
496        } //else {
497        //}
498      } else {
499        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
500      }
501    }
502    BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
503    operator++() {
504      if (bfs_queue.front().second.valid()) {
505        ++(bfs_queue.front().second);
506        actual_edge=bfs_queue.front().second;
507        if (actual_edge.valid()) {
508          NodeIt w=G.bNode(actual_edge);
509          if (!reached.get(w)) {
510            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
511            reached.set(w, true);
512            b_node_newly_reached=true;
513          } else {
514            b_node_newly_reached=false;
515          }
516        }
517      } else {
518        bfs_queue.pop();
519        if (!bfs_queue.empty()) {
520          actual_edge=bfs_queue.front().second;
521          if (actual_edge.valid()) {
522            NodeIt w=G.bNode(actual_edge);
523            if (!reached.get(w)) {
524              bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
525              reached.set(w, true);
526              b_node_newly_reached=true;
527            } else {
528              b_node_newly_reached=false;
529            }
530          }
531        }
532      }
533      return *this;
534    }
535    bool finished() const { return bfs_queue.empty(); }
536    operator OutEdgeIt () const { return actual_edge; }
537    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
538    bool isANodeExamined() const { return !(actual_edge.valid()); }
539    NodeIt aNode() const { return bfs_queue.front().first; }
540    NodeIt bNode() const { return G.bNode(actual_edge); }
541    const ReachedMap& getReachedMap() const { return reached; }
542    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
543 };
544
545  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
546  class BfsIterator4 {
547    typedef typename Graph::NodeIt NodeIt;
548    const Graph& G;
549    std::queue<NodeIt> bfs_queue;
550    ReachedMap reached;
551    bool b_node_newly_reached;
552    OutEdgeIt actual_edge;
553  public:
554    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
555    void pushAndSetReached(NodeIt s) {
556      reached.set(s, true);
557      if (bfs_queue.empty()) {
558        bfs_queue.push(s);
559        G.getFirst(actual_edge, s);
560        if (actual_edge.valid()) {
561          NodeIt w=G.bNode(actual_edge);
562          if (!reached.get(w)) {
563            bfs_queue.push(w);
564            reached.set(w, true);
565            b_node_newly_reached=true;
566          } else {
567            b_node_newly_reached=false;
568          }
569        }
570      } else {
571        bfs_queue.push(s);
572      }
573    }
574    BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
575    operator++() {
576      if (actual_edge.valid()) {
577        ++actual_edge;
578        if (actual_edge.valid()) {
579          NodeIt w=G.bNode(actual_edge);
580          if (!reached.get(w)) {
581            bfs_queue.push(w);
582            reached.set(w, true);
583            b_node_newly_reached=true;
584          } else {
585            b_node_newly_reached=false;
586          }
587        }
588      } else {
589        bfs_queue.pop();
590        if (!bfs_queue.empty()) {
591          G.getFirst(actual_edge, bfs_queue.front());
592          if (actual_edge.valid()) {
593            NodeIt w=G.bNode(actual_edge);
594            if (!reached.get(w)) {
595              bfs_queue.push(w);
596              reached.set(w, true);
597              b_node_newly_reached=true;
598            } else {
599              b_node_newly_reached=false;
600            }
601          }
602        }
603      }
604      return *this;
605    }
606    bool finished() const { return bfs_queue.empty(); }
607    operator OutEdgeIt () const { return actual_edge; }
608    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
609    bool isANodeExamined() const { return !(actual_edge.valid()); }
610    NodeIt aNode() const { return bfs_queue.front(); }
611    NodeIt bNode() const { return G.bNode(actual_edge); }
612    const ReachedMap& getReachedMap() const { return reached; }
613    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
614 };
615
616
617  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
618  struct DfsIterator4 {
619    typedef typename Graph::NodeIt NodeIt;
620    const Graph& G;
621    std::stack<OutEdgeIt> dfs_stack;
622    //ReachedMap& reached;
623    bool b_node_newly_reached;
624    OutEdgeIt actual_edge;
625    NodeIt actual_node;
626    ReachedMap reached;
627    DfsIterator4(const Graph& _G
628                 /*, std::stack<OutEdgeIt>& _bfs_queue,
629                   ReachedMap& _reached*/) :
630      G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ {
631      //actual_edge=bfs_queue.top();
632      //if (actual_edge.valid()) {
633      //        NodeIt w=G.bNode(actual_edge);
634      //if (!reached.get(w)) {
635      //  bfs_queue.push(OutEdgeIt(G, w));
636      //  reached.set(w, true);
637      //  b_node_newly_reached=true;
638      //} else {
639      //  ++(bfs_queue.top());
640      //  b_node_newly_reached=false;
641      //}
642      //} else {
643      //        bfs_queue.pop();
644      //}
645    }
646    void pushAndSetReached(NodeIt s) {
647      actual_node=s;
648      reached.set(s, true);
649      dfs_stack.push(G.template first<OutEdgeIt>(s));
650    }
651    DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
652    operator++() {
653      actual_edge=dfs_stack.top();
654      //actual_node=G.aNode(actual_edge);
655      if (actual_edge.valid()) {
656        NodeIt w=G.bNode(actual_edge);
657        actual_node=w;
658        if (!reached.get(w)) {
659          dfs_stack.push(G.template first<OutEdgeIt>(w));
660          reached.set(w, true);
661          b_node_newly_reached=true;
662        } else {
663          actual_node=G.aNode(actual_edge);
664          ++(dfs_stack.top());
665          b_node_newly_reached=false;
666        }
667      } else {
668        //actual_node=G.aNode(dfs_stack.top());
669        dfs_stack.pop();
670      }
671      return *this;
672    }
673    bool finished() const { return dfs_stack.empty(); }
674    operator OutEdgeIt () const { return actual_edge; }
675    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
676    bool isANodeExamined() const { return !(actual_edge.valid()); }
677    NodeIt aNode() const { return actual_node; /*FIXME*/}
678    NodeIt bNode() const { return G.bNode(actual_edge); }
679    const ReachedMap& getReachedMap() const { return reached; }
680    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
681  };
682
683
684
685  template <typename GraphWrapper, typename ReachedMap>
686  class BfsIterator5 {
687    typedef typename GraphWrapper::NodeIt NodeIt;
688    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
689    GraphWrapper gw;
690    std::queue<NodeIt> bfs_queue;
691    ReachedMap reached;
692    bool b_node_newly_reached;
693    OutEdgeIt actual_edge;
694  public:
695    BfsIterator5(GraphWrapper _gw) :
696      gw(_gw), reached(_gw.getGraph()) { }
697    void pushAndSetReached(NodeIt s) {
698      reached.set(s, true);
699      if (bfs_queue.empty()) {
700        bfs_queue.push(s);
701        gw.getFirst(actual_edge, s);
702        if (actual_edge.valid()) {
703          NodeIt w=gw.bNode(actual_edge);
704          if (!reached.get(w)) {
705            bfs_queue.push(w);
706            reached.set(w, true);
707            b_node_newly_reached=true;
708          } else {
709            b_node_newly_reached=false;
710          }
711        }
712      } else {
713        bfs_queue.push(s);
714      }
715    }
716    BfsIterator5<GraphWrapper, ReachedMap>&
717    operator++() {
718      if (actual_edge.valid()) {
719        ++actual_edge;
720        if (actual_edge.valid()) {
721          NodeIt w=gw.bNode(actual_edge);
722          if (!reached.get(w)) {
723            bfs_queue.push(w);
724            reached.set(w, true);
725            b_node_newly_reached=true;
726          } else {
727            b_node_newly_reached=false;
728          }
729        }
730      } else {
731        bfs_queue.pop();
732        if (!bfs_queue.empty()) {
733          gw.getFirst(actual_edge, bfs_queue.front());
734          if (actual_edge.valid()) {
735            NodeIt w=gw.bNode(actual_edge);
736            if (!reached.get(w)) {
737              bfs_queue.push(w);
738              reached.set(w, true);
739              b_node_newly_reached=true;
740            } else {
741              b_node_newly_reached=false;
742            }
743          }
744        }
745      }
746      return *this;
747    }
748    bool finished() const { return bfs_queue.empty(); }
749    operator OutEdgeIt () const { return actual_edge; }
750    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
751    bool isANodeExamined() const { return !(actual_edge.valid()); }
752    NodeIt aNode() const { return bfs_queue.front(); }
753    NodeIt bNode() const { return gw.bNode(actual_edge); }
754    const ReachedMap& getReachedMap() const { return reached; }
755    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
756 };
757
758
759
760} // namespace hugo
761
762#endif //BFS_ITERATOR_HH
Note: See TracBrowser for help on using the repository browser.