COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/bfs_iterator.hh @ 157:ee17030e5f47

Last change on this file since 157:ee17030e5f47 was 148:004fdf703abb, checked in by marci, 17 years ago

G.next(...), G.valid(...), ...

File size: 24.6 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
546  template <typename Graph, typename OutEdgeIt,
547            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
548  class BfsIterator4 {
549    typedef typename Graph::NodeIt NodeIt;
550    const Graph& G;
551    std::queue<NodeIt> bfs_queue;
552    ReachedMap& reached;
553    bool b_node_newly_reached;
554    OutEdgeIt actual_edge;
555    bool own_reached_map;
556  public:
557    BfsIterator4(const Graph& _G, ReachedMap& _reached) :
558      G(_G), reached(_reached),
559      own_reached_map(false) { }
560    BfsIterator4(const Graph& _G) :
561      G(_G), reached(*(new ReachedMap(G /*, false*/))),
562      own_reached_map(true) { }
563    ~BfsIterator4() { if (own_reached_map) delete &reached; }
564    void pushAndSetReached(NodeIt s) {
565      reached.set(s, true);
566      if (bfs_queue.empty()) {
567        bfs_queue.push(s);
568        G.getFirst(actual_edge, s);
569        if (G.valid(actual_edge)/*.valid()*/) {
570          NodeIt w=G.bNode(actual_edge);
571          if (!reached.get(w)) {
572            bfs_queue.push(w);
573            reached.set(w, true);
574            b_node_newly_reached=true;
575          } else {
576            b_node_newly_reached=false;
577          }
578        }
579      } else {
580        bfs_queue.push(s);
581      }
582    }
583    BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
584    operator++() {
585      if (G.valid(actual_edge)/*.valid()*/) {
586        /*++*/G.next(actual_edge);
587        if (G.valid(actual_edge)/*.valid()*/) {
588          NodeIt w=G.bNode(actual_edge);
589          if (!reached.get(w)) {
590            bfs_queue.push(w);
591            reached.set(w, true);
592            b_node_newly_reached=true;
593          } else {
594            b_node_newly_reached=false;
595          }
596        }
597      } else {
598        bfs_queue.pop();
599        if (!bfs_queue.empty()) {
600          G.getFirst(actual_edge, bfs_queue.front());
601          if (G.valid(actual_edge)/*.valid()*/) {
602            NodeIt w=G.bNode(actual_edge);
603            if (!reached.get(w)) {
604              bfs_queue.push(w);
605              reached.set(w, true);
606              b_node_newly_reached=true;
607            } else {
608              b_node_newly_reached=false;
609            }
610          }
611        }
612      }
613      return *this;
614    }
615    bool finished() const { return bfs_queue.empty(); }
616    operator OutEdgeIt () const { return actual_edge; }
617    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
618    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
619    NodeIt aNode() const { return bfs_queue.front(); }
620    NodeIt bNode() const { return G.bNode(actual_edge); }
621    const ReachedMap& getReachedMap() const { return reached; }
622    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
623 }; 
624
625
626  template <typename GraphWrapper, typename OutEdgeIt,
627            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
628  class BfsIterator5 {
629    typedef typename GraphWrapper::NodeIt NodeIt;
630    GraphWrapper G;
631    std::queue<NodeIt> bfs_queue;
632    ReachedMap& reached;
633    bool b_node_newly_reached;
634    OutEdgeIt actual_edge;
635    bool own_reached_map;
636  public:
637    BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
638      G(_G), reached(_reached),
639      own_reached_map(false) { }
640    BfsIterator5(const GraphWrapper& _G) :
641      G(_G), reached(*(new ReachedMap(G /*, false*/))),
642      own_reached_map(true) { }
643    ~BfsIterator5() { if (own_reached_map) delete &reached; }
644    void pushAndSetReached(NodeIt s) {
645      reached.set(s, true);
646      if (bfs_queue.empty()) {
647        bfs_queue.push(s);
648        G.getFirst(actual_edge, s);
649        if (G.valid(actual_edge)/*.valid()*/) {
650          NodeIt w=G.bNode(actual_edge);
651          if (!reached.get(w)) {
652            bfs_queue.push(w);
653            reached.set(w, true);
654            b_node_newly_reached=true;
655          } else {
656            b_node_newly_reached=false;
657          }
658        }
659      } else {
660        bfs_queue.push(s);
661      }
662    }
663    BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
664    operator++() {
665      if (G.valid(actual_edge)/*.valid()*/) {
666        /*++*/G.next(actual_edge);
667        if (G.valid(actual_edge)/*.valid()*/) {
668          NodeIt w=G.bNode(actual_edge);
669          if (!reached.get(w)) {
670            bfs_queue.push(w);
671            reached.set(w, true);
672            b_node_newly_reached=true;
673          } else {
674            b_node_newly_reached=false;
675          }
676        }
677      } else {
678        bfs_queue.pop();
679        if (!bfs_queue.empty()) {
680          G.getFirst(actual_edge, bfs_queue.front());
681          if (G.valid(actual_edge)/*.valid()*/) {
682            NodeIt w=G.bNode(actual_edge);
683            if (!reached.get(w)) {
684              bfs_queue.push(w);
685              reached.set(w, true);
686              b_node_newly_reached=true;
687            } else {
688              b_node_newly_reached=false;
689            }
690          }
691        }
692      }
693      return *this;
694    }
695    bool finished() const { return bfs_queue.empty(); }
696    operator OutEdgeIt () const { return actual_edge; }
697    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
698    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
699    NodeIt aNode() const { return bfs_queue.front(); }
700    NodeIt bNode() const { return G.bNode(actual_edge); }
701    const ReachedMap& getReachedMap() const { return reached; }
702    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
703  }; 
704
705  template <typename Graph, typename OutEdgeIt,
706            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
707  class DfsIterator4 {
708    typedef typename Graph::NodeIt NodeIt;
709    const Graph& G;
710    std::stack<OutEdgeIt> dfs_stack;
711    bool b_node_newly_reached;
712    OutEdgeIt actual_edge;
713    NodeIt actual_node;
714    ReachedMap& reached;
715    bool own_reached_map;
716  public:
717    DfsIterator4(const Graph& _G, ReachedMap& _reached) :
718      G(_G), reached(_reached),
719      own_reached_map(false) { }
720    DfsIterator4(const Graph& _G) :
721      G(_G), reached(*(new ReachedMap(G /*, false*/))),
722      own_reached_map(true) { }
723    ~DfsIterator4() { if (own_reached_map) delete &reached; }
724    void pushAndSetReached(NodeIt s) {
725      actual_node=s;
726      reached.set(s, true);
727      dfs_stack.push(G.template first<OutEdgeIt>(s));
728    }
729    DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
730    operator++() {
731      actual_edge=dfs_stack.top();
732      //actual_node=G.aNode(actual_edge);
733      if (G.valid(actual_edge)/*.valid()*/) {
734        NodeIt w=G.bNode(actual_edge);
735        actual_node=w;
736        if (!reached.get(w)) {
737          dfs_stack.push(G.template first<OutEdgeIt>(w));
738          reached.set(w, true);
739          b_node_newly_reached=true;
740        } else {
741          actual_node=G.aNode(actual_edge);
742          /*++*/G.next(dfs_stack.top());
743          b_node_newly_reached=false;
744        }
745      } else {
746        //actual_node=G.aNode(dfs_stack.top());
747        dfs_stack.pop();
748      }
749      return *this;
750    }
751    bool finished() const { return dfs_stack.empty(); }
752    operator OutEdgeIt () const { return actual_edge; }
753    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
754    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
755    NodeIt aNode() const { return actual_node; /*FIXME*/}
756    NodeIt bNode() const { return G.bNode(actual_edge); }
757    const ReachedMap& getReachedMap() const { return reached; }
758    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
759  };
760
761  template <typename GraphWrapper, typename OutEdgeIt,
762            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
763  class DfsIterator5 {
764    typedef typename GraphWrapper::NodeIt NodeIt;
765    GraphWrapper G;
766    std::stack<OutEdgeIt> dfs_stack;
767    bool b_node_newly_reached;
768    OutEdgeIt actual_edge;
769    NodeIt actual_node;
770    ReachedMap& reached;
771    bool own_reached_map;
772  public:
773    DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
774      G(_G), reached(_reached),
775      own_reached_map(false) { }
776    DfsIterator5(const GraphWrapper& _G) :
777      G(_G), reached(*(new ReachedMap(G /*, false*/))),
778      own_reached_map(true) { }
779    ~DfsIterator5() { if (own_reached_map) delete &reached; }
780    void pushAndSetReached(NodeIt s) {
781      actual_node=s;
782      reached.set(s, true);
783      dfs_stack.push(G.template first<OutEdgeIt>(s));
784    }
785    DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
786    operator++() {
787      actual_edge=dfs_stack.top();
788      //actual_node=G.aNode(actual_edge);
789      if (G.valid(actual_edge)/*.valid()*/) {
790        NodeIt w=G.bNode(actual_edge);
791        actual_node=w;
792        if (!reached.get(w)) {
793          dfs_stack.push(G.template first<OutEdgeIt>(w));
794          reached.set(w, true);
795          b_node_newly_reached=true;
796        } else {
797          actual_node=G.aNode(actual_edge);
798          /*++*/G.next(dfs_stack.top());
799          b_node_newly_reached=false;
800        }
801      } else {
802        //actual_node=G.aNode(dfs_stack.top());
803        dfs_stack.pop();
804      }
805      return *this;
806    }
807    bool finished() const { return dfs_stack.empty(); }
808    operator OutEdgeIt () const { return actual_edge; }
809    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
810    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
811    NodeIt aNode() const { return actual_node; /*FIXME*/}
812    NodeIt bNode() const { return G.bNode(actual_edge); }
813    const ReachedMap& getReachedMap() const { return reached; }
814    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
815  };
816
817
818
819} // namespace hugo
820
821#endif //BFS_ITERATOR_HH
Note: See TracBrowser for help on using the repository browser.