| 1 | #ifndef MARCI_BFS_HH |
|---|
| 2 | #define MARCI_BFS_HH |
|---|
| 3 | |
|---|
| 4 | #include <queue> |
|---|
| 5 | |
|---|
| 6 | #include <marci_graph_traits.hh> |
|---|
| 7 | #include <marci_property_vector.hh> |
|---|
| 8 | |
|---|
| 9 | namespace marci { |
|---|
| 10 | |
|---|
| 11 | template <typename graph_type> |
|---|
| 12 | struct bfs { |
|---|
| 13 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
|---|
| 14 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
|---|
| 15 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
|---|
| 16 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
|---|
| 17 | |
|---|
| 18 | graph_type& G; |
|---|
| 19 | node_iterator s; |
|---|
| 20 | node_property_vector<graph_type, bool> reached; |
|---|
| 21 | node_property_vector<graph_type, edge_iterator> pred; |
|---|
| 22 | node_property_vector<graph_type, int> dist; |
|---|
| 23 | std::queue<node_iterator> bfs_queue; |
|---|
| 24 | bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { |
|---|
| 25 | bfs_queue.push(s); |
|---|
| 26 | for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) |
|---|
| 27 | reached.put(i, false); |
|---|
| 28 | reached.put(s, true); |
|---|
| 29 | dist.put(s, 0); |
|---|
| 30 | } |
|---|
| 31 | |
|---|
| 32 | void run() { |
|---|
| 33 | while (!bfs_queue.empty()) { |
|---|
| 34 | node_iterator v=bfs_queue.front(); |
|---|
| 35 | out_edge_iterator e=G.first_out_edge(v); |
|---|
| 36 | bfs_queue.pop(); |
|---|
| 37 | for( ; e.is_valid(); ++e) { |
|---|
| 38 | node_iterator w=G.head(e); |
|---|
| 39 | std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; |
|---|
| 40 | if (!reached.get(w)) { |
|---|
| 41 | std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
|---|
| 42 | bfs_queue.push(w); |
|---|
| 43 | dist.put(w, dist.get(v)+1); |
|---|
| 44 | pred.put(w, e); |
|---|
| 45 | reached.put(w, true); |
|---|
| 46 | } else { |
|---|
| 47 | std::cout << G.id(w) << " is already reached" << std::endl; |
|---|
| 48 | } |
|---|
| 49 | } |
|---|
| 50 | } |
|---|
| 51 | } |
|---|
| 52 | }; |
|---|
| 53 | |
|---|
| 54 | template <typename graph_type> |
|---|
| 55 | struct bfs_visitor { |
|---|
| 56 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
|---|
| 57 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
|---|
| 58 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
|---|
| 59 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
|---|
| 60 | graph_type& G; |
|---|
| 61 | bfs_visitor(graph_type& _G) : G(_G) { } |
|---|
| 62 | void at_previously_reached(out_edge_iterator& e) { |
|---|
| 63 | //node_iterator v=G.tail(e); |
|---|
| 64 | node_iterator w=G.head(e); |
|---|
| 65 | std::cout << G.id(w) << " is already reached" << std::endl; |
|---|
| 66 | } |
|---|
| 67 | void at_newly_reached(out_edge_iterator& e) { |
|---|
| 68 | //node_iterator v=G.tail(e); |
|---|
| 69 | node_iterator w=G.head(e); |
|---|
| 70 | std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
|---|
| 71 | } |
|---|
| 72 | }; |
|---|
| 73 | |
|---|
| 74 | template <typename graph_type, typename reached_type, typename visitor_type> |
|---|
| 75 | struct bfs_iterator { |
|---|
| 76 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
|---|
| 77 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
|---|
| 78 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
|---|
| 79 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
|---|
| 80 | |
|---|
| 81 | graph_type& G; |
|---|
| 82 | std::queue<out_edge_iterator>& bfs_queue; |
|---|
| 83 | reached_type& reached; |
|---|
| 84 | visitor_type& visitor; |
|---|
| 85 | void process() { |
|---|
| 86 | while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 87 | if (bfs_queue.empty()) return; |
|---|
| 88 | out_edge_iterator e=bfs_queue.front(); |
|---|
| 89 | //node_iterator v=G.tail(e); |
|---|
| 90 | node_iterator w=G.head(e); |
|---|
| 91 | if (!reached.get(w)) { |
|---|
| 92 | visitor.at_newly_reached(e); |
|---|
| 93 | bfs_queue.push(G.first_out_edge(w)); |
|---|
| 94 | reached.put(w, true); |
|---|
| 95 | } else { |
|---|
| 96 | visitor.at_previously_reached(e); |
|---|
| 97 | } |
|---|
| 98 | } |
|---|
| 99 | 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) { |
|---|
| 100 | //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 101 | is_valid(); |
|---|
| 102 | } |
|---|
| 103 | bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { |
|---|
| 104 | //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 105 | //if (bfs_queue.empty()) return *this; |
|---|
| 106 | if (!is_valid()) return *this; |
|---|
| 107 | ++(bfs_queue.front()); |
|---|
| 108 | //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 109 | is_valid(); |
|---|
| 110 | return *this; |
|---|
| 111 | } |
|---|
| 112 | //void next() { |
|---|
| 113 | // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 114 | // if (bfs_queue.empty()) return; |
|---|
| 115 | // ++(bfs_queue.front()); |
|---|
| 116 | // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 117 | //} |
|---|
| 118 | bool is_valid() { |
|---|
| 119 | while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 120 | if (bfs_queue.empty()) return false; else return true; |
|---|
| 121 | } |
|---|
| 122 | //bool finished() { |
|---|
| 123 | // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 124 | // if (bfs_queue.empty()) return true; else return false; |
|---|
| 125 | //} |
|---|
| 126 | operator edge_iterator () { return bfs_queue.front(); } |
|---|
| 127 | |
|---|
| 128 | }; |
|---|
| 129 | |
|---|
| 130 | template <typename graph_type, typename reached_type> |
|---|
| 131 | struct bfs_iterator1 { |
|---|
| 132 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
|---|
| 133 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
|---|
| 134 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
|---|
| 135 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
|---|
| 136 | |
|---|
| 137 | graph_type& G; |
|---|
| 138 | std::queue<out_edge_iterator>& bfs_queue; |
|---|
| 139 | reached_type& reached; |
|---|
| 140 | bool newly_reached; |
|---|
| 141 | bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|---|
| 142 | is_valid(); |
|---|
| 143 | if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { |
|---|
| 144 | out_edge_iterator e=bfs_queue.front(); |
|---|
| 145 | node_iterator w=G.head(e); |
|---|
| 146 | if (!reached.get(w)) { |
|---|
| 147 | bfs_queue.push(G.first_out_edge(w)); |
|---|
| 148 | reached.put(w, true); |
|---|
| 149 | newly_reached=true; |
|---|
| 150 | } else { |
|---|
| 151 | newly_reached=false; |
|---|
| 152 | } |
|---|
| 153 | } |
|---|
| 154 | } |
|---|
| 155 | bfs_iterator1<graph_type, reached_type>& operator++() { |
|---|
| 156 | if (!is_valid()) return *this; |
|---|
| 157 | ++(bfs_queue.front()); |
|---|
| 158 | is_valid(); |
|---|
| 159 | if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { |
|---|
| 160 | out_edge_iterator e=bfs_queue.front(); |
|---|
| 161 | node_iterator w=G.head(e); |
|---|
| 162 | if (!reached.get(w)) { |
|---|
| 163 | bfs_queue.push(G.first_out_edge(w)); |
|---|
| 164 | reached.put(w, true); |
|---|
| 165 | newly_reached=true; |
|---|
| 166 | } else { |
|---|
| 167 | newly_reached=false; |
|---|
| 168 | } |
|---|
| 169 | } |
|---|
| 170 | return *this; |
|---|
| 171 | } |
|---|
| 172 | bool is_valid() { |
|---|
| 173 | while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } |
|---|
| 174 | if (bfs_queue.empty()) return false; else return true; |
|---|
| 175 | } |
|---|
| 176 | operator edge_iterator () { return bfs_queue.front(); } |
|---|
| 177 | bool is_newly_reached() { return newly_reached; } |
|---|
| 178 | |
|---|
| 179 | }; |
|---|
| 180 | |
|---|
| 181 | } // namespace marci |
|---|
| 182 | |
|---|
| 183 | #endif //MARCI_BFS_HH |
|---|
