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