nem hekkelunk.
1 #ifndef BFS_ITERATOR_HH
2 #define BFS_ITERATOR_HH
7 #include <graph_wrapper.h>
11 template <typename Graph>
13 typedef typename Graph::NodeIt NodeIt;
14 typedef typename Graph::EdgeIt EdgeIt;
15 typedef typename Graph::EachNodeIt EachNodeIt;
16 typedef typename Graph::OutEdgeIt OutEdgeIt;
19 typename Graph::NodeMap<bool> reached;
20 typename Graph::NodeMap<EdgeIt> pred;
21 typename Graph::NodeMap<int> dist;
22 std::queue<NodeIt> bfs_queue;
23 bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
25 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
26 reached.set(i, false);
32 while (!bfs_queue.empty()) {
33 NodeIt v=bfs_queue.front();
34 OutEdgeIt e=G.template first<OutEdgeIt>(v);
36 for( ; e.valid(); ++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;
42 dist.set(w, dist.get(v)+1);
46 std::cout << G.id(w) << " is already reached" << std::endl;
53 template <typename Graph>
55 typedef typename Graph::NodeIt NodeIt;
56 typedef typename Graph::EdgeIt EdgeIt;
57 typedef typename Graph::OutEdgeIt OutEdgeIt;
59 bfs_visitor(Graph& _G) : G(_G) { }
60 void at_previously_reached(OutEdgeIt& e) {
61 //NodeIt v=G.aNode(e);
63 std::cout << G.id(w) << " is already reached" << std::endl;
65 void at_newly_reached(OutEdgeIt& e) {
66 //NodeIt v=G.aNode(e);
68 std::cout << G.id(w) << " is newly reached :-)" << std::endl;
72 template <typename Graph, typename ReachedMap, typename visitor_type>
74 typedef typename Graph::NodeIt NodeIt;
75 typedef typename Graph::EdgeIt EdgeIt;
76 typedef typename Graph::OutEdgeIt OutEdgeIt;
78 std::queue<OutEdgeIt>& bfs_queue;
80 visitor_type& visitor;
82 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
83 if (bfs_queue.empty()) return;
84 OutEdgeIt e=bfs_queue.front();
85 //NodeIt v=G.aNode(e);
87 if (!reached.get(w)) {
88 visitor.at_newly_reached(e);
89 bfs_queue.push(G.template first<OutEdgeIt>(w));
92 visitor.at_previously_reached(e);
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(); }
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(); }
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(); }
115 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
116 if (bfs_queue.empty()) return false; else return true;
119 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
120 // if (bfs_queue.empty()) return true; else return false;
122 operator EdgeIt () { return bfs_queue.front(); }
126 template <typename Graph, typename ReachedMap>
127 struct bfs_iterator1 {
128 typedef typename Graph::NodeIt NodeIt;
129 typedef typename Graph::EdgeIt EdgeIt;
130 typedef typename Graph::OutEdgeIt OutEdgeIt;
132 std::queue<OutEdgeIt>& bfs_queue;
135 bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
137 if (!bfs_queue.empty() && bfs_queue.front().valid()) {
138 OutEdgeIt e=bfs_queue.front();
140 if (!reached.get(w)) {
141 bfs_queue.push(G.template first<OutEdgeIt>(w));
142 reached.set(w, true);
145 _newly_reached=false;
149 bfs_iterator1<Graph, ReachedMap>& operator++() {
150 if (!valid()) return *this;
151 ++(bfs_queue.front());
153 if (!bfs_queue.empty() && bfs_queue.front().valid()) {
154 OutEdgeIt e=bfs_queue.front();
156 if (!reached.get(w)) {
157 bfs_queue.push(G.template first<OutEdgeIt>(w));
158 reached.set(w, true);
161 _newly_reached=false;
167 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
168 if (bfs_queue.empty()) return false; else return true;
170 operator OutEdgeIt() { return bfs_queue.front(); }
172 bool newly_reached() { return _newly_reached; }
176 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
178 typedef typename Graph::NodeIt NodeIt;
180 std::queue<OutEdgeIt>& bfs_queue;
182 bool b_node_newly_reached;
183 OutEdgeIt actual_edge;
184 BfsIterator(Graph& _G,
185 std::queue<OutEdgeIt>& _bfs_queue,
186 ReachedMap& _reached) :
187 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
188 actual_edge=bfs_queue.front();
189 if (actual_edge.valid()) {
190 NodeIt w=G.bNode(actual_edge);
191 if (!reached.get(w)) {
192 bfs_queue.push(G.firstOutEdge(w));
193 reached.set(w, true);
194 b_node_newly_reached=true;
196 b_node_newly_reached=false;
200 BfsIterator<Graph, OutEdgeIt, ReachedMap>&
202 if (bfs_queue.front().valid()) {
203 ++(bfs_queue.front());
204 actual_edge=bfs_queue.front();
205 if (actual_edge.valid()) {
206 NodeIt w=G.bNode(actual_edge);
207 if (!reached.get(w)) {
208 bfs_queue.push(G.firstOutEdge(w));
209 reached.set(w, true);
210 b_node_newly_reached=true;
212 b_node_newly_reached=false;
217 actual_edge=bfs_queue.front();
218 if (actual_edge.valid()) {
219 NodeIt w=G.bNode(actual_edge);
220 if (!reached.get(w)) {
221 bfs_queue.push(G.firstOutEdge(w));
222 reached.set(w, true);
223 b_node_newly_reached=true;
225 b_node_newly_reached=false;
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()); }
238 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
240 typedef typename Graph::NodeIt NodeIt;
242 std::stack<OutEdgeIt>& bfs_queue;
244 bool b_node_newly_reached;
245 OutEdgeIt actual_edge;
246 DfsIterator(Graph& _G,
247 std::stack<OutEdgeIt>& _bfs_queue,
248 ReachedMap& _reached) :
249 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
250 actual_edge=bfs_queue.top();
251 if (actual_edge.valid()) {
252 NodeIt w=G.bNode(actual_edge);
253 if (!reached.get(w)) {
254 bfs_queue.push(G.firstOutEdge(w));
255 reached.set(w, true);
256 b_node_newly_reached=true;
259 b_node_newly_reached=false;
265 DfsIterator<Graph, OutEdgeIt, ReachedMap>&
267 actual_edge=bfs_queue.top();
268 if (actual_edge.valid()) {
269 NodeIt w=G.bNode(actual_edge);
270 if (!reached.get(w)) {
271 bfs_queue.push(G.firstOutEdge(w));
272 reached.set(w, true);
273 b_node_newly_reached=true;
276 b_node_newly_reached=false;
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()); }
289 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
290 struct BfsIterator1 {
291 typedef typename Graph::NodeIt NodeIt;
293 std::queue<OutEdgeIt>& bfs_queue;
295 bool b_node_newly_reached;
296 OutEdgeIt actual_edge;
297 BfsIterator1(Graph& _G,
298 std::queue<OutEdgeIt>& _bfs_queue,
299 ReachedMap& _reached) :
300 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
301 actual_edge=bfs_queue.front();
302 if (actual_edge.valid()) {
303 NodeIt w=G.bNode(actual_edge);
304 if (!reached.get(w)) {
305 bfs_queue.push(OutEdgeIt(G, w));
306 reached.set(w, true);
307 b_node_newly_reached=true;
309 b_node_newly_reached=false;
314 if (bfs_queue.front().valid()) {
315 ++(bfs_queue.front());
316 actual_edge=bfs_queue.front();
317 if (actual_edge.valid()) {
318 NodeIt w=G.bNode(actual_edge);
319 if (!reached.get(w)) {
320 bfs_queue.push(OutEdgeIt(G, w));
321 reached.set(w, true);
322 b_node_newly_reached=true;
324 b_node_newly_reached=false;
329 actual_edge=bfs_queue.front();
330 if (actual_edge.valid()) {
331 NodeIt w=G.bNode(actual_edge);
332 if (!reached.get(w)) {
333 bfs_queue.push(OutEdgeIt(G, w));
334 reached.set(w, true);
335 b_node_newly_reached=true;
337 b_node_newly_reached=false;
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()); }
350 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
351 struct DfsIterator1 {
352 typedef typename Graph::NodeIt NodeIt;
354 std::stack<OutEdgeIt>& bfs_queue;
356 bool b_node_newly_reached;
357 OutEdgeIt actual_edge;
358 DfsIterator1(Graph& _G,
359 std::stack<OutEdgeIt>& _bfs_queue,
360 ReachedMap& _reached) :
361 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
362 //actual_edge=bfs_queue.top();
363 //if (actual_edge.valid()) {
364 // NodeIt w=G.bNode(actual_edge);
365 //if (!reached.get(w)) {
366 // bfs_queue.push(OutEdgeIt(G, w));
367 // reached.set(w, true);
368 // b_node_newly_reached=true;
370 // ++(bfs_queue.top());
371 // b_node_newly_reached=false;
378 actual_edge=bfs_queue.top();
379 if (actual_edge.valid()) {
380 NodeIt w=G.bNode(actual_edge);
381 if (!reached.get(w)) {
382 bfs_queue.push(OutEdgeIt(G, w));
383 reached.set(w, true);
384 b_node_newly_reached=true;
387 b_node_newly_reached=false;
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()); }
400 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
402 typedef typename Graph::NodeIt NodeIt;
404 std::queue<OutEdgeIt> bfs_queue;
406 bool b_node_newly_reached;
407 OutEdgeIt actual_edge;
409 BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
410 void pushAndSetReached(NodeIt s) {
411 reached.set(s, true);
412 if (bfs_queue.empty()) {
413 bfs_queue.push(G.template first<OutEdgeIt>(s));
414 actual_edge=bfs_queue.front();
415 if (actual_edge.valid()) {
416 NodeIt w=G.bNode(actual_edge);
417 if (!reached.get(w)) {
418 bfs_queue.push(G.template first<OutEdgeIt>(w));
419 reached.set(w, true);
420 b_node_newly_reached=true;
422 b_node_newly_reached=false;
427 bfs_queue.push(G.template first<OutEdgeIt>(s));
430 BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
432 if (bfs_queue.front().valid()) {
433 ++(bfs_queue.front());
434 actual_edge=bfs_queue.front();
435 if (actual_edge.valid()) {
436 NodeIt w=G.bNode(actual_edge);
437 if (!reached.get(w)) {
438 bfs_queue.push(G.template first<OutEdgeIt>(w));
439 reached.set(w, true);
440 b_node_newly_reached=true;
442 b_node_newly_reached=false;
447 if (!bfs_queue.empty()) {
448 actual_edge=bfs_queue.front();
449 if (actual_edge.valid()) {
450 NodeIt w=G.bNode(actual_edge);
451 if (!reached.get(w)) {
452 bfs_queue.push(G.template first<OutEdgeIt>(w));
453 reached.set(w, true);
454 b_node_newly_reached=true;
456 b_node_newly_reached=false;
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; }
472 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
474 typedef typename Graph::NodeIt NodeIt;
476 std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
478 bool b_node_newly_reached;
479 OutEdgeIt actual_edge;
481 BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
482 void pushAndSetReached(NodeIt s) {
483 reached.set(s, true);
484 if (bfs_queue.empty()) {
485 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
486 actual_edge=bfs_queue.front().second;
487 if (actual_edge.valid()) {
488 NodeIt w=G.bNode(actual_edge);
489 if (!reached.get(w)) {
490 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
491 reached.set(w, true);
492 b_node_newly_reached=true;
494 b_node_newly_reached=false;
499 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
502 BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
504 if (bfs_queue.front().second.valid()) {
505 ++(bfs_queue.front().second);
506 actual_edge=bfs_queue.front().second;
507 if (actual_edge.valid()) {
508 NodeIt w=G.bNode(actual_edge);
509 if (!reached.get(w)) {
510 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
511 reached.set(w, true);
512 b_node_newly_reached=true;
514 b_node_newly_reached=false;
519 if (!bfs_queue.empty()) {
520 actual_edge=bfs_queue.front().second;
521 if (actual_edge.valid()) {
522 NodeIt w=G.bNode(actual_edge);
523 if (!reached.get(w)) {
524 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
525 reached.set(w, true);
526 b_node_newly_reached=true;
528 b_node_newly_reached=false;
535 bool finished() const { return bfs_queue.empty(); }
536 operator OutEdgeIt () const { return actual_edge; }
537 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
538 bool isANodeExamined() const { return !(actual_edge.valid()); }
539 NodeIt aNode() const { return bfs_queue.front().first; }
540 NodeIt bNode() const { return G.bNode(actual_edge); }
541 const ReachedMap& getReachedMap() const { return reached; }
542 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
545 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
547 typedef typename Graph::NodeIt NodeIt;
549 std::queue<NodeIt> bfs_queue;
551 bool b_node_newly_reached;
552 OutEdgeIt actual_edge;
554 BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
555 void pushAndSetReached(NodeIt s) {
556 reached.set(s, true);
557 if (bfs_queue.empty()) {
559 G.getFirst(actual_edge, s);
560 if (actual_edge.valid()) {
561 NodeIt w=G.bNode(actual_edge);
562 if (!reached.get(w)) {
564 reached.set(w, true);
565 b_node_newly_reached=true;
567 b_node_newly_reached=false;
574 BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
576 if (actual_edge.valid()) {
578 if (actual_edge.valid()) {
579 NodeIt w=G.bNode(actual_edge);
580 if (!reached.get(w)) {
582 reached.set(w, true);
583 b_node_newly_reached=true;
585 b_node_newly_reached=false;
590 if (!bfs_queue.empty()) {
591 G.getFirst(actual_edge, bfs_queue.front());
592 if (actual_edge.valid()) {
593 NodeIt w=G.bNode(actual_edge);
594 if (!reached.get(w)) {
596 reached.set(w, true);
597 b_node_newly_reached=true;
599 b_node_newly_reached=false;
606 bool finished() const { return bfs_queue.empty(); }
607 operator OutEdgeIt () const { return actual_edge; }
608 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
609 bool isANodeExamined() const { return !(actual_edge.valid()); }
610 NodeIt aNode() const { return bfs_queue.front(); }
611 NodeIt bNode() const { return G.bNode(actual_edge); }
612 const ReachedMap& getReachedMap() const { return reached; }
613 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
617 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
618 struct DfsIterator4 {
619 typedef typename Graph::NodeIt NodeIt;
621 std::stack<OutEdgeIt> dfs_stack;
622 //ReachedMap& reached;
623 bool b_node_newly_reached;
624 OutEdgeIt actual_edge;
627 DfsIterator4(const Graph& _G
628 /*, std::stack<OutEdgeIt>& _bfs_queue,
629 ReachedMap& _reached*/) :
630 G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ {
631 //actual_edge=bfs_queue.top();
632 //if (actual_edge.valid()) {
633 // NodeIt w=G.bNode(actual_edge);
634 //if (!reached.get(w)) {
635 // bfs_queue.push(OutEdgeIt(G, w));
636 // reached.set(w, true);
637 // b_node_newly_reached=true;
639 // ++(bfs_queue.top());
640 // b_node_newly_reached=false;
646 void pushAndSetReached(NodeIt s) {
648 reached.set(s, true);
649 dfs_stack.push(G.template first<OutEdgeIt>(s));
651 DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
653 actual_edge=dfs_stack.top();
654 //actual_node=G.aNode(actual_edge);
655 if (actual_edge.valid()) {
656 NodeIt w=G.bNode(actual_edge);
658 if (!reached.get(w)) {
659 dfs_stack.push(G.template first<OutEdgeIt>(w));
660 reached.set(w, true);
661 b_node_newly_reached=true;
663 actual_node=G.aNode(actual_edge);
665 b_node_newly_reached=false;
668 //actual_node=G.aNode(dfs_stack.top());
673 bool finished() const { return dfs_stack.empty(); }
674 operator OutEdgeIt () const { return actual_edge; }
675 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
676 bool isANodeExamined() const { return !(actual_edge.valid()); }
677 NodeIt aNode() const { return actual_node; /*FIXME*/}
678 NodeIt bNode() const { return G.bNode(actual_edge); }
679 const ReachedMap& getReachedMap() const { return reached; }
680 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
685 template <typename GraphWrapper, typename ReachedMap>
687 typedef typename GraphWrapper::NodeIt NodeIt;
688 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
690 std::queue<NodeIt> bfs_queue;
692 bool b_node_newly_reached;
693 OutEdgeIt actual_edge;
695 BfsIterator5(GraphWrapper _gw) :
696 gw(_gw), reached(_gw.getGraph()) { }
697 void pushAndSetReached(NodeIt s) {
698 reached.set(s, true);
699 if (bfs_queue.empty()) {
701 gw.getFirst(actual_edge, s);
702 if (actual_edge.valid()) {
703 NodeIt w=gw.bNode(actual_edge);
704 if (!reached.get(w)) {
706 reached.set(w, true);
707 b_node_newly_reached=true;
709 b_node_newly_reached=false;
716 BfsIterator5<GraphWrapper, ReachedMap>&
718 if (actual_edge.valid()) {
720 if (actual_edge.valid()) {
721 NodeIt w=gw.bNode(actual_edge);
722 if (!reached.get(w)) {
724 reached.set(w, true);
725 b_node_newly_reached=true;
727 b_node_newly_reached=false;
732 if (!bfs_queue.empty()) {
733 gw.getFirst(actual_edge, bfs_queue.front());
734 if (actual_edge.valid()) {
735 NodeIt w=gw.bNode(actual_edge);
736 if (!reached.get(w)) {
738 reached.set(w, true);
739 b_node_newly_reached=true;
741 b_node_newly_reached=false;
748 bool finished() const { return bfs_queue.empty(); }
749 operator OutEdgeIt () const { return actual_edge; }
750 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
751 bool isANodeExamined() const { return !(actual_edge.valid()); }
752 NodeIt aNode() const { return bfs_queue.front(); }
753 NodeIt bNode() const { return gw.bNode(actual_edge); }
754 const ReachedMap& getReachedMap() const { return reached; }
755 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
762 #endif //BFS_ITERATOR_HH