393 operator OutEdgeIt () { return actual_edge; } |
393 operator OutEdgeIt () { return actual_edge; } |
394 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
394 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
395 bool aNodeIsLeaved() { return !(actual_edge.valid()); } |
395 bool aNodeIsLeaved() { return !(actual_edge.valid()); } |
396 }; |
396 }; |
397 |
397 |
|
398 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
399 class BfsIterator2 { |
|
400 typedef typename Graph::NodeIt NodeIt; |
|
401 const Graph& G; |
|
402 std::queue<OutEdgeIt> bfs_queue; |
|
403 ReachedMap reached; |
|
404 bool b_node_newly_reached; |
|
405 OutEdgeIt actual_edge; |
|
406 public: |
|
407 BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { } |
|
408 void pushAndSetReached(const NodeIt s) { |
|
409 reached.set(s, true); |
|
410 if (bfs_queue.empty()) { |
|
411 bfs_queue.push(G.template first<OutEdgeIt>(s)); |
|
412 actual_edge=bfs_queue.front(); |
|
413 if (actual_edge.valid()) { |
|
414 NodeIt w=G.bNode(actual_edge); |
|
415 if (!reached.get(w)) { |
|
416 bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
417 reached.set(w, true); |
|
418 b_node_newly_reached=true; |
|
419 } else { |
|
420 b_node_newly_reached=false; |
|
421 } |
|
422 } //else { |
|
423 //} |
|
424 } else { |
|
425 bfs_queue.push(G.template first<OutEdgeIt>(s)); |
|
426 } |
|
427 } |
|
428 BfsIterator2<Graph, OutEdgeIt, ReachedMap>& |
|
429 operator++() { |
|
430 if (bfs_queue.front().valid()) { |
|
431 ++(bfs_queue.front()); |
|
432 actual_edge=bfs_queue.front(); |
|
433 if (actual_edge.valid()) { |
|
434 NodeIt w=G.bNode(actual_edge); |
|
435 if (!reached.get(w)) { |
|
436 bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
437 reached.set(w, true); |
|
438 b_node_newly_reached=true; |
|
439 } else { |
|
440 b_node_newly_reached=false; |
|
441 } |
|
442 } |
|
443 } else { |
|
444 bfs_queue.pop(); |
|
445 if (!bfs_queue.empty()) { |
|
446 actual_edge=bfs_queue.front(); |
|
447 } else { |
|
448 actual_edge=OutEdgeIt(); |
|
449 } |
|
450 if (actual_edge.valid()) { |
|
451 NodeIt 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 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 |
398 } // namespace marci |
472 } // namespace marci |
399 |
473 |
400 #endif //MARCI_BFS_HH |
474 #endif //BFS_ITERATOR_HH |