COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/bfs_iterator.hh @ 160:f1a7005e9dff

Last change on this file since 160:f1a7005e9dff was 158:4f54d89fa9d2, checked in by marci, 21 years ago

a lot of interesting and very useful wrapper graphs

File size: 25.0 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    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
631    GraphWrapper G;
632    std::queue<NodeIt> bfs_queue;
633    ReachedMap& reached;
634    bool b_node_newly_reached;
635    OutEdgeIt actual_edge;
636    bool own_reached_map;
637  public:
638    BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
639      G(_G), reached(_reached),
640      own_reached_map(false) { }
641    BfsIterator5(const GraphWrapper& _G) :
642      G(_G), reached(*(new ReachedMap(G /*, false*/))),
643      own_reached_map(true) { }
644//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
645//               ReachedMap& _reached) :
646//       G(_G), reached(_reached),
647//       own_reached_map(false) { }
648//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
649//       G(_G), reached(*(new ReachedMap(G /*, false*/))),
650//       own_reached_map(true) { }
651    ~BfsIterator5() { if (own_reached_map) delete &reached; }
652    void pushAndSetReached(NodeIt s) {
653      reached.set(s, true);
654      if (bfs_queue.empty()) {
655        bfs_queue.push(s);
656        G.getFirst(actual_edge, s);
657        if (G.valid(actual_edge)/*.valid()*/) {
658          NodeIt w=G.bNode(actual_edge);
659          if (!reached.get(w)) {
660            bfs_queue.push(w);
661            reached.set(w, true);
662            b_node_newly_reached=true;
663          } else {
664            b_node_newly_reached=false;
665          }
666        }
667      } else {
668        bfs_queue.push(s);
669      }
670    }
671    BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
672    operator++() {
673      if (G.valid(actual_edge)/*.valid()*/) {
674        /*++*/G.next(actual_edge);
675        if (G.valid(actual_edge)/*.valid()*/) {
676          NodeIt w=G.bNode(actual_edge);
677          if (!reached.get(w)) {
678            bfs_queue.push(w);
679            reached.set(w, true);
680            b_node_newly_reached=true;
681          } else {
682            b_node_newly_reached=false;
683          }
684        }
685      } else {
686        bfs_queue.pop();
687        if (!bfs_queue.empty()) {
688          G.getFirst(actual_edge, bfs_queue.front());
689          if (G.valid(actual_edge)/*.valid()*/) {
690            NodeIt w=G.bNode(actual_edge);
691            if (!reached.get(w)) {
692              bfs_queue.push(w);
693              reached.set(w, true);
694              b_node_newly_reached=true;
695            } else {
696              b_node_newly_reached=false;
697            }
698          }
699        }
700      }
701      return *this;
702    }
703    bool finished() const { return bfs_queue.empty(); }
704    operator OutEdgeIt () const { return actual_edge; }
705    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
706    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
707    NodeIt aNode() const { return bfs_queue.front(); }
708    NodeIt bNode() const { return G.bNode(actual_edge); }
709    const ReachedMap& getReachedMap() const { return reached; }
710    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
711  }; 
712
713  template <typename Graph, typename OutEdgeIt,
714            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
715  class DfsIterator4 {
716    typedef typename Graph::NodeIt NodeIt;
717    const Graph& G;
718    std::stack<OutEdgeIt> dfs_stack;
719    bool b_node_newly_reached;
720    OutEdgeIt actual_edge;
721    NodeIt actual_node;
722    ReachedMap& reached;
723    bool own_reached_map;
724  public:
725    DfsIterator4(const Graph& _G, ReachedMap& _reached) :
726      G(_G), reached(_reached),
727      own_reached_map(false) { }
728    DfsIterator4(const Graph& _G) :
729      G(_G), reached(*(new ReachedMap(G /*, false*/))),
730      own_reached_map(true) { }
731    ~DfsIterator4() { if (own_reached_map) delete &reached; }
732    void pushAndSetReached(NodeIt s) {
733      actual_node=s;
734      reached.set(s, true);
735      dfs_stack.push(G.template first<OutEdgeIt>(s));
736    }
737    DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
738    operator++() {
739      actual_edge=dfs_stack.top();
740      //actual_node=G.aNode(actual_edge);
741      if (G.valid(actual_edge)/*.valid()*/) {
742        NodeIt w=G.bNode(actual_edge);
743        actual_node=w;
744        if (!reached.get(w)) {
745          dfs_stack.push(G.template first<OutEdgeIt>(w));
746          reached.set(w, true);
747          b_node_newly_reached=true;
748        } else {
749          actual_node=G.aNode(actual_edge);
750          /*++*/G.next(dfs_stack.top());
751          b_node_newly_reached=false;
752        }
753      } else {
754        //actual_node=G.aNode(dfs_stack.top());
755        dfs_stack.pop();
756      }
757      return *this;
758    }
759    bool finished() const { return dfs_stack.empty(); }
760    operator OutEdgeIt () const { return actual_edge; }
761    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
762    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
763    NodeIt aNode() const { return actual_node; /*FIXME*/}
764    NodeIt bNode() const { return G.bNode(actual_edge); }
765    const ReachedMap& getReachedMap() const { return reached; }
766    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
767  };
768
769  template <typename GraphWrapper, /*typename OutEdgeIt,*/
770            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
771  class DfsIterator5 {
772    typedef typename GraphWrapper::NodeIt NodeIt;
773    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
774    GraphWrapper G;
775    std::stack<OutEdgeIt> dfs_stack;
776    bool b_node_newly_reached;
777    OutEdgeIt actual_edge;
778    NodeIt actual_node;
779    ReachedMap& reached;
780    bool own_reached_map;
781  public:
782    DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
783      G(_G), reached(_reached),
784      own_reached_map(false) { }
785    DfsIterator5(const GraphWrapper& _G) :
786      G(_G), reached(*(new ReachedMap(G /*, false*/))),
787      own_reached_map(true) { }
788    ~DfsIterator5() { if (own_reached_map) delete &reached; }
789    void pushAndSetReached(NodeIt s) {
790      actual_node=s;
791      reached.set(s, true);
792      dfs_stack.push(G.template first<OutEdgeIt>(s));
793    }
794    DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
795    operator++() {
796      actual_edge=dfs_stack.top();
797      //actual_node=G.aNode(actual_edge);
798      if (G.valid(actual_edge)/*.valid()*/) {
799        NodeIt w=G.bNode(actual_edge);
800        actual_node=w;
801        if (!reached.get(w)) {
802          dfs_stack.push(G.template first<OutEdgeIt>(w));
803          reached.set(w, true);
804          b_node_newly_reached=true;
805        } else {
806          actual_node=G.aNode(actual_edge);
807          /*++*/G.next(dfs_stack.top());
808          b_node_newly_reached=false;
809        }
810      } else {
811        //actual_node=G.aNode(dfs_stack.top());
812        dfs_stack.pop();
813      }
814      return *this;
815    }
816    bool finished() const { return dfs_stack.empty(); }
817    operator OutEdgeIt () const { return actual_edge; }
818    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
819    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
820    NodeIt aNode() const { return actual_node; /*FIXME*/}
821    NodeIt bNode() const { return G.bNode(actual_edge); }
822    const ReachedMap& getReachedMap() const { return reached; }
823    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
824  };
825
826
827
828} // namespace hugo
829
830#endif //BFS_ITERATOR_HH
Note: See TracBrowser for help on using the repository browser.