1.1 --- a/src/work/marci/oldies/marci_bfs.hh Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,176 +0,0 @@
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