1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/oldies/marci_bfs.hh Sat Apr 03 14:41:31 2004 +0000
1.3 @@ -0,0 +1,176 @@
1.4 +#ifndef MARCI_BFS_HH
1.5 +#define MARCI_BFS_HH
1.6 +
1.7 +#include <queue>
1.8 +
1.9 +#include <marci_property_vector.hh>
1.10 +
1.11 +namespace hugo {
1.12 +
1.13 + template <typename graph_type>
1.14 + struct bfs {
1.15 + typedef typename graph_type::node_iterator node_iterator;
1.16 + typedef typename graph_type::edge_iterator edge_iterator;
1.17 + typedef typename graph_type::each_node_iterator each_node_iterator;
1.18 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.19 + graph_type& G;
1.20 + node_iterator s;
1.21 + node_property_vector<graph_type, bool> reached;
1.22 + node_property_vector<graph_type, edge_iterator> pred;
1.23 + node_property_vector<graph_type, int> dist;
1.24 + std::queue<node_iterator> bfs_queue;
1.25 + bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.26 + bfs_queue.push(s);
1.27 + for(each_node_iterator i=G.first_node(); i.valid(); ++i)
1.28 + reached.put(i, false);
1.29 + reached.put(s, true);
1.30 + dist.put(s, 0);
1.31 + }
1.32 +
1.33 + void run() {
1.34 + while (!bfs_queue.empty()) {
1.35 + node_iterator v=bfs_queue.front();
1.36 + out_edge_iterator e=G.first_out_edge(v);
1.37 + bfs_queue.pop();
1.38 + for( ; e.valid(); ++e) {
1.39 + node_iterator w=G.head(e);
1.40 + std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.41 + if (!reached.get(w)) {
1.42 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.43 + bfs_queue.push(w);
1.44 + dist.put(w, dist.get(v)+1);
1.45 + pred.put(w, e);
1.46 + reached.put(w, true);
1.47 + } else {
1.48 + std::cout << G.id(w) << " is already reached" << std::endl;
1.49 + }
1.50 + }
1.51 + }
1.52 + }
1.53 + };
1.54 +
1.55 + template <typename graph_type>
1.56 + struct bfs_visitor {
1.57 + typedef typename graph_type::node_iterator node_iterator;
1.58 + typedef typename graph_type::edge_iterator edge_iterator;
1.59 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.60 + graph_type& G;
1.61 + bfs_visitor(graph_type& _G) : G(_G) { }
1.62 + void at_previously_reached(out_edge_iterator& e) {
1.63 + //node_iterator v=G.tail(e);
1.64 + node_iterator w=G.head(e);
1.65 + std::cout << G.id(w) << " is already reached" << std::endl;
1.66 + }
1.67 + void at_newly_reached(out_edge_iterator& e) {
1.68 + //node_iterator v=G.tail(e);
1.69 + node_iterator w=G.head(e);
1.70 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.71 + }
1.72 + };
1.73 +
1.74 + template <typename graph_type, typename reached_type, typename visitor_type>
1.75 + struct bfs_iterator {
1.76 + typedef typename graph_type::node_iterator node_iterator;
1.77 + typedef typename graph_type::edge_iterator edge_iterator;
1.78 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.79 + graph_type& G;
1.80 + std::queue<out_edge_iterator>& bfs_queue;
1.81 + reached_type& reached;
1.82 + visitor_type& visitor;
1.83 + void process() {
1.84 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.85 + if (bfs_queue.empty()) return;
1.86 + out_edge_iterator e=bfs_queue.front();
1.87 + //node_iterator v=G.tail(e);
1.88 + node_iterator w=G.head(e);
1.89 + if (!reached.get(w)) {
1.90 + visitor.at_newly_reached(e);
1.91 + bfs_queue.push(G.first_out_edge(w));
1.92 + reached.put(w, true);
1.93 + } else {
1.94 + visitor.at_previously_reached(e);
1.95 + }
1.96 + }
1.97 + 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) {
1.98 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.99 + valid();
1.100 + }
1.101 + bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
1.102 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.103 + //if (bfs_queue.empty()) return *this;
1.104 + if (!valid()) return *this;
1.105 + ++(bfs_queue.front());
1.106 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.107 + valid();
1.108 + return *this;
1.109 + }
1.110 + //void next() {
1.111 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.112 + // if (bfs_queue.empty()) return;
1.113 + // ++(bfs_queue.front());
1.114 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.115 + //}
1.116 + bool valid() {
1.117 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.118 + if (bfs_queue.empty()) return false; else return true;
1.119 + }
1.120 + //bool finished() {
1.121 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.122 + // if (bfs_queue.empty()) return true; else return false;
1.123 + //}
1.124 + operator edge_iterator () { return bfs_queue.front(); }
1.125 +
1.126 + };
1.127 +
1.128 + template <typename graph_type, typename reached_type>
1.129 + struct bfs_iterator1 {
1.130 + typedef typename graph_type::node_iterator node_iterator;
1.131 + typedef typename graph_type::edge_iterator edge_iterator;
1.132 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.133 + graph_type& G;
1.134 + std::queue<out_edge_iterator>& bfs_queue;
1.135 + reached_type& reached;
1.136 + bool _newly_reached;
1.137 + bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.138 + valid();
1.139 + if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.140 + out_edge_iterator e=bfs_queue.front();
1.141 + node_iterator w=G.head(e);
1.142 + if (!reached.get(w)) {
1.143 + bfs_queue.push(G.first_out_edge(w));
1.144 + reached.put(w, true);
1.145 + _newly_reached=true;
1.146 + } else {
1.147 + _newly_reached=false;
1.148 + }
1.149 + }
1.150 + }
1.151 + bfs_iterator1<graph_type, reached_type>& operator++() {
1.152 + if (!valid()) return *this;
1.153 + ++(bfs_queue.front());
1.154 + valid();
1.155 + if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.156 + out_edge_iterator e=bfs_queue.front();
1.157 + node_iterator w=G.head(e);
1.158 + if (!reached.get(w)) {
1.159 + bfs_queue.push(G.first_out_edge(w));
1.160 + reached.put(w, true);
1.161 + _newly_reached=true;
1.162 + } else {
1.163 + _newly_reached=false;
1.164 + }
1.165 + }
1.166 + return *this;
1.167 + }
1.168 + bool valid() {
1.169 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.170 + if (bfs_queue.empty()) return false; else return true;
1.171 + }
1.172 + operator edge_iterator () { return bfs_queue.front(); }
1.173 + bool newly_reached() { return _newly_reached; }
1.174 +
1.175 + };
1.176 +
1.177 +} // namespace hugo
1.178 +
1.179 +#endif //MARCI_BFS_HH