COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/experiment/bfs_iterator_1.h @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 15 years ago

hugo -> lemon

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