Changeset 58:f71840c04b2a in lemon0.x for src/work/bfs_iterator.hh
 Timestamp:
 02/04/04 13:45:32 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@73
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r42 r58 1 #ifndef MARCI_BFS_HH2 #define MARCI_BFS_HH1 #ifndef BFS_ITERATOR_HH 2 #define BFS_ITERATOR_HH 3 3 4 4 #include <queue> … … 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 472 } // namespace marci 399 473 400 #endif // MARCI_BFS_HH474 #endif //BFS_ITERATOR_HH
Note: See TracChangeset
for help on using the changeset viewer.