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/marci/bfs_iterator.h @ 303:1b377a730d02

Last change on this file since 303:1b377a730d02 was 303:1b377a730d02, checked in by marci, 20 years ago

konvergalunk, konvergalunk...
File size: 26.7 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
9namespace hugo {
10
11//   template <typename Graph>
12//   struct bfs {
13//     typedef typename Graph::Node Node;
14//     typedef typename Graph::Edge Edge;
15//     typedef typename Graph::NodeIt NodeIt;
16//     typedef typename Graph::OutEdgeIt OutEdgeIt;
17//     Graph& G;
18//     Node s;
19//     typename Graph::NodeMap<bool> reached;
20//     typename Graph::NodeMap<Edge> pred;
21//     typename Graph::NodeMap<int> dist;
22//     std::queue<Node> bfs_queue;
23//     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
24//       bfs_queue.push(s);
25//       for(NodeIt i=G.template first<NodeIt>(); 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//      Node v=bfs_queue.front();
34//      OutEdgeIt e=G.template first<OutEdgeIt>(v);
35//      bfs_queue.pop();
36//      for( ; e.valid(); ++e) {
37//        Node 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::Node Node;
56//     typedef typename Graph::Edge Edge;
57//     typedef typename Graph::OutEdgeIt OutEdgeIt;
58//     Graph& G;
59//     bfs_visitor(Graph& _G) : G(_G) { }
60//     void at_previously_reached(OutEdgeIt& e) {
61//       //Node v=G.aNode(e);
62//       Node w=G.bNode(e);
63//       std::cout << G.id(w) << " is already reached" << std::endl;
64//    }
65//     void at_newly_reached(OutEdgeIt& e) {
66//       //Node v=G.aNode(e);
67//       Node 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::Node Node;
75//     typedef typename Graph::Edge Edge;
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//       //Node v=G.aNode(e);
86//       Node 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 Edge () { return bfs_queue.front(); }
123
124//   };
125
126//   template <typename Graph, typename ReachedMap>
127//   struct bfs_iterator1 {
128//     typedef typename Graph::Node Node;
129//     typedef typename Graph::Edge Edge;
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//      Node 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//      Node 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::Node Node;
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//      Node 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//        Node 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//        Node 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::Node Node;
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//      Node 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//      Node 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::Node Node;
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//              Node 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//        Node 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//        Node 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::Node Node;
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//       //     Node 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//      Node 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::Node Node;
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(Node 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//        Node 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//        Node 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//          Node 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::Node Node;
475//     const Graph& G;
476//     std::queue< std::pair<Node, 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(Node s) {
483//       reached.set(s, true);
484//       if (bfs_queue.empty()) {
485//      bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
486//      actual_edge=bfs_queue.front().second;
487//      if (actual_edge.valid()) {
488//        Node w=G.bNode(actual_edge);
489//        if (!reached.get(w)) {
490//          bfs_queue.push(std::pair<Node, 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<Node, 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//        Node w=G.bNode(actual_edge);
509//        if (!reached.get(w)) {
510//          bfs_queue.push(std::pair<Node, 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//          Node w=G.bNode(actual_edge);
523//          if (!reached.get(w)) {
524//            bfs_queue.push(std::pair<Node, 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//     Node aNode() const { return bfs_queue.front().first; }
540//     Node bNode() const { return G.bNode(actual_edge); }
541//     const ReachedMap& getReachedMap() const { return reached; }
542//     //const std::queue< std::pair<Node, 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::Node Node;
550//     const Graph& G;
551//     std::queue<Node> 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(Node 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./*getF*/first(actual_edge, s);
573//      //std::cout << "kiki" << std::endl;
574//      if (G.valid(actual_edge)/*.valid()*/) {
575//        Node 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//        Node 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./*getF*/first(actual_edge, bfs_queue.front());
607//        if (G.valid(actual_edge)/*.valid()*/) {
608//          Node 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//     Node aNode() const { return bfs_queue.front(); }
626//     Node bNode() const { return G.bNode(actual_edge); }
627//     const ReachedMap& getReachedMap() const { return reached; }
628//     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
629//  }; 
630
631
632  template <typename Graph, /*typename OutEdgeIt,*/
633            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
634  class BfsIterator5 {
635  protected:
636    typedef typename Graph::Node Node;
637    typedef typename Graph::OutEdgeIt OutEdgeIt;
638    const Graph* graph;
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 Graph& _graph, ReachedMap& _reached) :
646      graph(&_graph), reached(_reached),
647      own_reached_map(false) { }
648    BfsIterator5(const Graph& _graph) :
649      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
650      own_reached_map(true) { }
651    ~BfsIterator5() { if (own_reached_map) delete &reached; }
652    void pushAndSetReached(Node s) {
653      reached.set(s, true);
654      if (bfs_queue.empty()) {
655        bfs_queue.push(s);
656        graph->first(actual_edge, s);
657        if (graph->valid(actual_edge)) {
658          Node w=graph->bNode(actual_edge);
659          if (!reached[w]) {
660            bfs_queue.push(w);
661            reached.set(w, true);
662            b_node_newly_reached=true;
663          } else {
664            b_node_newly_reached=false;
665          }
666        }
667      } else {
668        bfs_queue.push(s);
669      }
670    }
671    BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
672    operator++() {
673      if (graph->valid(actual_edge)) {
674        graph->next(actual_edge);
675        if (graph->valid(actual_edge)) {
676          Node w=graph->bNode(actual_edge);
677          if (!reached[w]) {
678            bfs_queue.push(w);
679            reached.set(w, true);
680            b_node_newly_reached=true;
681          } else {
682            b_node_newly_reached=false;
683          }
684        }
685      } else {
686        bfs_queue.pop();
687        if (!bfs_queue.empty()) {
688          graph->first(actual_edge, bfs_queue.front());
689          if (graph->valid(actual_edge)) {
690            Node w=graph->bNode(actual_edge);
691            if (!reached[w]) {
692              bfs_queue.push(w);
693              reached.set(w, true);
694              b_node_newly_reached=true;
695            } else {
696              b_node_newly_reached=false;
697            }
698          }
699        }
700      }
701      return *this;
702    }
703    bool finished() const { return bfs_queue.empty(); }
704    operator OutEdgeIt () const { return actual_edge; }
705    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
706    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
707    Node aNode() const { return bfs_queue.front(); }
708    Node bNode() const { return graph->bNode(actual_edge); }
709    const ReachedMap& getReachedMap() const { return reached; }
710    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
711  }; 
712
713//   template <typename Graph, typename OutEdgeIt,
714//          typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
715//   class DfsIterator4 {
716//     typedef typename Graph::Node Node;
717//     const Graph& G;
718//     std::stack<OutEdgeIt> dfs_stack;
719//     bool b_node_newly_reached;
720//     OutEdgeIt actual_edge;
721//     Node actual_node;
722//     ReachedMap& reached;
723//     bool own_reached_map;
724//   public:
725//     DfsIterator4(const Graph& _G, ReachedMap& _reached) :
726//       G(_G), reached(_reached),
727//       own_reached_map(false) { }
728//     DfsIterator4(const Graph& _G) :
729//       G(_G), reached(*(new ReachedMap(G /*, false*/))),
730//       own_reached_map(true) { }
731//     ~DfsIterator4() { if (own_reached_map) delete &reached; }
732//     void pushAndSetReached(Node s) {
733//       actual_node=s;
734//       reached.set(s, true);
735//       dfs_stack.push(G.template first<OutEdgeIt>(s));
736//     }
737//     DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
738//     operator++() {
739//       actual_edge=dfs_stack.top();
740//       //actual_node=G.aNode(actual_edge);
741//       if (G.valid(actual_edge)/*.valid()*/) {
742//      Node w=G.bNode(actual_edge);
743//      actual_node=w;
744//      if (!reached.get(w)) {
745//        dfs_stack.push(G.template first<OutEdgeIt>(w));
746//        reached.set(w, true);
747//        b_node_newly_reached=true;
748//      } else {
749//        actual_node=G.aNode(actual_edge);
750//        /*++*/G.next(dfs_stack.top());
751//        b_node_newly_reached=false;
752//      }
753//       } else {
754//      //actual_node=G.aNode(dfs_stack.top());
755//      dfs_stack.pop();
756//       }
757//       return *this;
758//     }
759//     bool finished() const { return dfs_stack.empty(); }
760//     operator OutEdgeIt () const { return actual_edge; }
761//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
762//     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
763//     Node aNode() const { return actual_node; /*FIXME*/}
764//     Node bNode() const { return G.bNode(actual_edge); }
765//     const ReachedMap& getReachedMap() const { return reached; }
766//     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
767//   };
768
769  template <typename Graph, /*typename OutEdgeIt,*/
770            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
771  class DfsIterator5 {
772  protected:
773    typedef typename Graph::Node Node;
774    typedef typename Graph::OutEdgeIt OutEdgeIt;
775    const Graph* graph;
776    std::stack<OutEdgeIt> dfs_stack;
777    bool b_node_newly_reached;
778    OutEdgeIt actual_edge;
779    Node actual_node;
780    ReachedMap& reached;
781    bool own_reached_map;
782  public:
783    DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
784      graph(&_graph), reached(_reached),
785      own_reached_map(false) { }
786    DfsIterator5(const Graph& _graph) :
787      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
788      own_reached_map(true) { }
789    ~DfsIterator5() { if (own_reached_map) delete &reached; }
790    void pushAndSetReached(Node s) {
791      actual_node=s;
792      reached.set(s, true);
793      OutEdgeIt e;
794      graph->first(e, s);
795      dfs_stack.push(e);
796    }
797    DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
798    operator++() {
799      actual_edge=dfs_stack.top();
800      //actual_node=G.aNode(actual_edge);
801      if (graph->valid(actual_edge)/*.valid()*/) {
802        Node w=graph->bNode(actual_edge);
803        actual_node=w;
804        if (!reached[w]) {
805          OutEdgeIt e;
806          graph->first(e, w);
807          dfs_stack.push(e);
808          reached.set(w, true);
809          b_node_newly_reached=true;
810        } else {
811          actual_node=graph->aNode(actual_edge);
812          graph->next(dfs_stack.top());
813          b_node_newly_reached=false;
814        }
815      } else {
816        //actual_node=G.aNode(dfs_stack.top());
817        dfs_stack.pop();
818      }
819      return *this;
820    }
821    bool finished() const { return dfs_stack.empty(); }
822    operator OutEdgeIt () const { return actual_edge; }
823    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
824    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
825    Node aNode() const { return actual_node; /*FIXME*/}
826    Node bNode() const { return G.bNode(actual_edge); }
827    const ReachedMap& getReachedMap() const { return reached; }
828    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
829  };
830
831
832
833} // namespace hugo
834
835#endif //HUGO_BFS_ITERATOR_H
Note: See TracBrowser for help on using the repository browser.