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