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 @ 225:b72b36a25170

Last change on this file since 225:b72b36a25170 was 168:27fbd1559fb7, checked in by marci, 21 years ago

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