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.h @ 284:2d4684f76aac

Last change on this file since 284:2d4684f76aac was 279:be43902fadb7, checked in by marci, 21 years ago

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