marci@9: #ifndef MARCI_BFS_HH
marci@9: #define MARCI_BFS_HH
marci@9: 
marci@9: #include <queue>
marci@9: 
marci@9: #include <marci_property_vector.hh>
marci@9: 
alpar@107: namespace hugo {
marci@9: 
marci@9:   template <typename graph_type>
marci@9:   struct bfs {
marci@19:     typedef typename graph_type::node_iterator node_iterator;
marci@19:     typedef typename graph_type::edge_iterator edge_iterator;
marci@19:     typedef typename graph_type::each_node_iterator each_node_iterator;
marci@19:     typedef typename graph_type::out_edge_iterator out_edge_iterator;
marci@9:     graph_type& G;
marci@9:     node_iterator s;
marci@9:     node_property_vector<graph_type, bool> reached;
marci@9:     node_property_vector<graph_type, edge_iterator> pred;
marci@9:     node_property_vector<graph_type, int> dist;
marci@9:     std::queue<node_iterator> bfs_queue;
marci@9:     bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
marci@9:       bfs_queue.push(s); 
marci@19:       for(each_node_iterator i=G.first_node(); i.valid(); ++i) 
marci@9: 	reached.put(i, false);
marci@9:       reached.put(s, true);
marci@9:       dist.put(s, 0); 
marci@9:     }
marci@9:     
marci@9:     void run() {
marci@9:       while (!bfs_queue.empty()) {
marci@9: 	node_iterator v=bfs_queue.front();
marci@9: 	out_edge_iterator e=G.first_out_edge(v);
marci@9: 	bfs_queue.pop();
marci@19: 	for( ; e.valid(); ++e) {
marci@9: 	  node_iterator w=G.head(e);
marci@9: 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
marci@9: 	  if (!reached.get(w)) {
marci@9: 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@9: 	    bfs_queue.push(w);
marci@9: 	    dist.put(w, dist.get(v)+1);
marci@9: 	    pred.put(w, e);
marci@9: 	    reached.put(w, true);
marci@9: 	  } else {
marci@9: 	    std::cout << G.id(w) << " is already reached" << std::endl;
marci@9: 	  }
marci@9: 	}
marci@9:       }
marci@9:     }
marci@9:   };
marci@9: 
marci@9:   template <typename graph_type> 
marci@9:   struct bfs_visitor {
marci@19:     typedef typename graph_type::node_iterator node_iterator;
marci@19:     typedef typename graph_type::edge_iterator edge_iterator;
marci@19:     typedef typename graph_type::out_edge_iterator out_edge_iterator;
marci@9:     graph_type& G;
marci@9:     bfs_visitor(graph_type& _G) : G(_G) { }
marci@9:     void at_previously_reached(out_edge_iterator& e) { 
marci@9:       //node_iterator v=G.tail(e);
marci@9:       node_iterator w=G.head(e);
marci@9:       std::cout << G.id(w) << " is already reached" << std::endl;
marci@9:    }
marci@9:     void at_newly_reached(out_edge_iterator& e) { 
marci@9:       //node_iterator v=G.tail(e);
marci@9:       node_iterator w=G.head(e);
marci@9:       std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@9:     }
marci@9:   };
marci@9: 
marci@9:   template <typename graph_type, typename reached_type, typename visitor_type>
marci@9:   struct bfs_iterator {
marci@19:     typedef typename graph_type::node_iterator node_iterator;
marci@19:     typedef typename graph_type::edge_iterator edge_iterator;
marci@19:     typedef typename graph_type::out_edge_iterator out_edge_iterator;
marci@9:     graph_type& G;
marci@9:     std::queue<out_edge_iterator>& bfs_queue;
marci@9:     reached_type& reached;
marci@9:     visitor_type& visitor;
marci@9:     void process() {
marci@19:       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@9:       if (bfs_queue.empty()) return;
marci@9:       out_edge_iterator e=bfs_queue.front();
marci@9:       //node_iterator v=G.tail(e);
marci@9:       node_iterator w=G.head(e);
marci@9:       if (!reached.get(w)) {
marci@9: 	visitor.at_newly_reached(e);
marci@9: 	bfs_queue.push(G.first_out_edge(w));
marci@9: 	reached.put(w, true);
marci@9:       } else {
marci@9: 	visitor.at_previously_reached(e);
marci@9:       }
marci@9:     }
marci@9:     bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 
marci@19:       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@19:       valid();
marci@9:     }
marci@9:     bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { 
marci@19:       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@9:       //if (bfs_queue.empty()) return *this;
marci@19:       if (!valid()) return *this;
marci@9:       ++(bfs_queue.front());
marci@19:       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@19:       valid();
marci@9:       return *this;
marci@9:     }
marci@9:     //void next() { 
marci@19:     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@9:     //  if (bfs_queue.empty()) return;
marci@9:     //  ++(bfs_queue.front());
marci@19:     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@9:     //}
marci@19:     bool valid() { 
marci@19:       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@9:       if (bfs_queue.empty()) return false; else return true;
marci@9:     }
marci@9:     //bool finished() { 
marci@19:     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@9:     //  if (bfs_queue.empty()) return true; else return false;
marci@9:     //}
marci@9:     operator edge_iterator () { return bfs_queue.front(); }
marci@9: 
marci@9:   };
marci@9: 
marci@11:   template <typename graph_type, typename reached_type>
marci@11:   struct bfs_iterator1 {
marci@19:     typedef typename graph_type::node_iterator node_iterator;
marci@19:     typedef typename graph_type::edge_iterator edge_iterator;
marci@19:     typedef typename graph_type::out_edge_iterator out_edge_iterator;
marci@11:     graph_type& G;
marci@11:     std::queue<out_edge_iterator>& bfs_queue;
marci@11:     reached_type& reached;
marci@19:     bool _newly_reached;
marci@11:     bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@19:       valid();
marci@19:       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
marci@11: 	out_edge_iterator e=bfs_queue.front();
marci@11: 	node_iterator w=G.head(e);
marci@11: 	if (!reached.get(w)) {
marci@11: 	  bfs_queue.push(G.first_out_edge(w));
marci@11: 	  reached.put(w, true);
marci@19: 	  _newly_reached=true;
marci@11: 	} else {
marci@19: 	  _newly_reached=false;
marci@11: 	}
marci@11:       }
marci@11:     }
marci@11:     bfs_iterator1<graph_type, reached_type>& operator++() { 
marci@19:       if (!valid()) return *this;
marci@11:       ++(bfs_queue.front());
marci@19:       valid();
marci@19:       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
marci@11: 	out_edge_iterator e=bfs_queue.front();
marci@11: 	node_iterator w=G.head(e);
marci@11: 	if (!reached.get(w)) {
marci@11: 	  bfs_queue.push(G.first_out_edge(w));
marci@11: 	  reached.put(w, true);
marci@19: 	  _newly_reached=true;
marci@11: 	} else {
marci@19: 	  _newly_reached=false;
marci@11: 	}
marci@11:       }
marci@11:       return *this;
marci@11:     }
marci@19:     bool valid() { 
marci@19:       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@11:       if (bfs_queue.empty()) return false; else return true;
marci@11:     }
marci@11:     operator edge_iterator () { return bfs_queue.front(); }
marci@19:     bool newly_reached() { return _newly_reached; }
marci@11: 
marci@11:   };
marci@9: 
alpar@107: } // namespace hugo
marci@9: 
marci@9: #endif //MARCI_BFS_HH