Changeset 58:f71840c04b2a in lemon-0.x for src/work
- Timestamp:
- 02/04/04 13:45:32 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/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.