|
1 // -*- c++ -*- |
|
2 #ifndef HUGO_BFS_DFS_H |
|
3 #define HUGO_BFS_DFS_H |
|
4 |
|
5 #include <queue> |
|
6 #include <stack> |
|
7 #include <utility> |
|
8 |
|
9 #include <hugo/invalid.h> |
|
10 |
|
11 namespace hugo { |
|
12 |
|
13 /// Bfs searches for the nodes wich are not marked in |
|
14 /// \c reached_map |
|
15 /// Reached have to work as read-write bool Node-map. |
|
16 template <typename Graph, /*typename OutEdgeIt,*/ |
|
17 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
|
18 class BfsIterator { |
|
19 protected: |
|
20 typedef typename Graph::Node Node; |
|
21 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
22 const Graph* graph; |
|
23 std::queue<Node> bfs_queue; |
|
24 ReachedMap& reached; |
|
25 bool b_node_newly_reached; |
|
26 OutEdgeIt actual_edge; |
|
27 bool own_reached_map; |
|
28 public: |
|
29 /// In that constructor \c _reached have to be a reference |
|
30 /// for a bool Node-map. The algorithm will search in a bfs order for |
|
31 /// the nodes which are \c false initially |
|
32 BfsIterator(const Graph& _graph, ReachedMap& _reached) : |
|
33 graph(&_graph), reached(_reached), |
|
34 own_reached_map(false) { } |
|
35 /// The same as above, but the map storing the reached nodes |
|
36 /// is constructed dynamically to everywhere false. |
|
37 BfsIterator(const Graph& _graph) : |
|
38 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
|
39 own_reached_map(true) { } |
|
40 /// The storing the reached nodes have to be destroyed if |
|
41 /// it was constructed dynamically |
|
42 ~BfsIterator() { if (own_reached_map) delete &reached; } |
|
43 /// This method markes \c s reached. |
|
44 /// If the queue is empty, then \c s is pushed in the bfs queue |
|
45 /// and the first out-edge is processed. |
|
46 /// If the queue is not empty, then \c s is simply pushed. |
|
47 void pushAndSetReached(Node s) { |
|
48 reached.set(s, true); |
|
49 if (bfs_queue.empty()) { |
|
50 bfs_queue.push(s); |
|
51 graph->first(actual_edge, s); |
|
52 if (graph->valid(actual_edge)) { |
|
53 Node w=graph->bNode(actual_edge); |
|
54 if (!reached[w]) { |
|
55 bfs_queue.push(w); |
|
56 reached.set(w, true); |
|
57 b_node_newly_reached=true; |
|
58 } else { |
|
59 b_node_newly_reached=false; |
|
60 } |
|
61 } |
|
62 } else { |
|
63 bfs_queue.push(s); |
|
64 } |
|
65 } |
|
66 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, |
|
67 /// its \c operator++() iterates on the edges in a bfs order. |
|
68 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
|
69 operator++() { |
|
70 if (graph->valid(actual_edge)) { |
|
71 graph->next(actual_edge); |
|
72 if (graph->valid(actual_edge)) { |
|
73 Node w=graph->bNode(actual_edge); |
|
74 if (!reached[w]) { |
|
75 bfs_queue.push(w); |
|
76 reached.set(w, true); |
|
77 b_node_newly_reached=true; |
|
78 } else { |
|
79 b_node_newly_reached=false; |
|
80 } |
|
81 } |
|
82 } else { |
|
83 bfs_queue.pop(); |
|
84 if (!bfs_queue.empty()) { |
|
85 graph->first(actual_edge, bfs_queue.front()); |
|
86 if (graph->valid(actual_edge)) { |
|
87 Node w=graph->bNode(actual_edge); |
|
88 if (!reached[w]) { |
|
89 bfs_queue.push(w); |
|
90 reached.set(w, true); |
|
91 b_node_newly_reached=true; |
|
92 } else { |
|
93 b_node_newly_reached=false; |
|
94 } |
|
95 } |
|
96 } |
|
97 } |
|
98 return *this; |
|
99 } |
|
100 /// |
|
101 bool finished() const { return bfs_queue.empty(); } |
|
102 /// The conversion operator makes for converting the bfs-iterator |
|
103 /// to an \c out-edge-iterator. |
|
104 ///\bug Edge have to be in HUGO 0.2 |
|
105 operator OutEdgeIt() const { return actual_edge; } |
|
106 /// |
|
107 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
108 /// |
|
109 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
|
110 /// |
|
111 Node aNode() const { return bfs_queue.front(); } |
|
112 /// |
|
113 Node bNode() const { return graph->bNode(actual_edge); } |
|
114 /// |
|
115 const ReachedMap& getReachedMap() const { return reached; } |
|
116 /// |
|
117 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
|
118 }; |
|
119 |
|
120 /// Bfs searches for the nodes wich are not marked in |
|
121 /// \c reached_map |
|
122 /// Reached have to work as a read-write bool Node-map, |
|
123 /// Pred is a write Edge Node-map and |
|
124 /// Dist is a read-write int Node-map, have to be. |
|
125 ///\todo In fact onsly simple operations requirement are needed for |
|
126 /// Dist::Value. |
|
127 template <typename Graph, |
|
128 typename ReachedMap=typename Graph::template NodeMap<bool>, |
|
129 typename PredMap |
|
130 =typename Graph::template NodeMap<typename Graph::Edge>, |
|
131 typename DistMap=typename Graph::template NodeMap<int> > |
|
132 class Bfs : public BfsIterator<Graph, ReachedMap> { |
|
133 typedef BfsIterator<Graph, ReachedMap> Parent; |
|
134 protected: |
|
135 typedef typename Parent::Node Node; |
|
136 PredMap& pred; |
|
137 DistMap& dist; |
|
138 public: |
|
139 /// The algorithm will search in a bfs order for |
|
140 /// the nodes which are \c false initially. |
|
141 /// The constructor makes no initial changes on the maps. |
|
142 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } |
|
143 /// \c s is marked to be reached and pushed in the bfs queue. |
|
144 /// If the queue is empty, then the first out-edge is processed. |
|
145 /// If \c s was not marked previously, then |
|
146 /// in addition its pred is set to be \c INVALID, and dist to \c 0. |
|
147 /// if \c s was marked previuosly, then it is simply pushed. |
|
148 void push(Node s) { |
|
149 if (this->reached[s]) { |
|
150 Parent::pushAndSetReached(s); |
|
151 } else { |
|
152 Parent::pushAndSetReached(s); |
|
153 pred.set(s, INVALID); |
|
154 dist.set(s, 0); |
|
155 } |
|
156 } |
|
157 /// A bfs is processed from \c s. |
|
158 void run(Node s) { |
|
159 push(s); |
|
160 while (!this->finished()) this->operator++(); |
|
161 } |
|
162 /// Beside the bfs iteration, \c pred and \dist are saved in a |
|
163 /// newly reached node. |
|
164 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { |
|
165 Parent::operator++(); |
|
166 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
|
167 { |
|
168 pred.set(this->bNode(), this->actual_edge); |
|
169 dist.set(this->bNode(), dist[this->aNode()]); |
|
170 } |
|
171 return *this; |
|
172 } |
|
173 /// |
|
174 const PredMap& getPredMap() const { return pred; } |
|
175 /// |
|
176 const DistMap& getDistMap() const { return dist; } |
|
177 }; |
|
178 |
|
179 /// Dfs searches for the nodes wich are not marked in |
|
180 /// \c reached_map |
|
181 /// Reached have to be a read-write bool Node-map. |
|
182 template <typename Graph, /*typename OutEdgeIt,*/ |
|
183 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
|
184 class DfsIterator { |
|
185 protected: |
|
186 typedef typename Graph::Node Node; |
|
187 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
188 const Graph* graph; |
|
189 std::stack<OutEdgeIt> dfs_stack; |
|
190 bool b_node_newly_reached; |
|
191 OutEdgeIt actual_edge; |
|
192 Node actual_node; |
|
193 ReachedMap& reached; |
|
194 bool own_reached_map; |
|
195 public: |
|
196 /// In that constructor \c _reached have to be a reference |
|
197 /// for a bool Node-map. The algorithm will search in a dfs order for |
|
198 /// the nodes which are \c false initially |
|
199 DfsIterator(const Graph& _graph, ReachedMap& _reached) : |
|
200 graph(&_graph), reached(_reached), |
|
201 own_reached_map(false) { } |
|
202 /// The same as above, but the map of reached nodes is |
|
203 /// constructed dynamically |
|
204 /// to everywhere false. |
|
205 DfsIterator(const Graph& _graph) : |
|
206 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
|
207 own_reached_map(true) { } |
|
208 ~DfsIterator() { if (own_reached_map) delete &reached; } |
|
209 /// This method markes s reached and first out-edge is processed. |
|
210 void pushAndSetReached(Node s) { |
|
211 actual_node=s; |
|
212 reached.set(s, true); |
|
213 OutEdgeIt e; |
|
214 graph->first(e, s); |
|
215 dfs_stack.push(e); |
|
216 } |
|
217 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, |
|
218 /// its \c operator++() iterates on the edges in a dfs order. |
|
219 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
|
220 operator++() { |
|
221 actual_edge=dfs_stack.top(); |
|
222 //actual_node=G.aNode(actual_edge); |
|
223 if (graph->valid(actual_edge)/*.valid()*/) { |
|
224 Node w=graph->bNode(actual_edge); |
|
225 actual_node=w; |
|
226 if (!reached[w]) { |
|
227 OutEdgeIt e; |
|
228 graph->first(e, w); |
|
229 dfs_stack.push(e); |
|
230 reached.set(w, true); |
|
231 b_node_newly_reached=true; |
|
232 } else { |
|
233 actual_node=graph->aNode(actual_edge); |
|
234 graph->next(dfs_stack.top()); |
|
235 b_node_newly_reached=false; |
|
236 } |
|
237 } else { |
|
238 //actual_node=G.aNode(dfs_stack.top()); |
|
239 dfs_stack.pop(); |
|
240 } |
|
241 return *this; |
|
242 } |
|
243 /// |
|
244 bool finished() const { return dfs_stack.empty(); } |
|
245 /// |
|
246 operator OutEdgeIt() const { return actual_edge; } |
|
247 /// |
|
248 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
249 /// |
|
250 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
|
251 /// |
|
252 Node aNode() const { return actual_node; /*FIXME*/} |
|
253 /// |
|
254 Node bNode() const { return graph->bNode(actual_edge); } |
|
255 /// |
|
256 const ReachedMap& getReachedMap() const { return reached; } |
|
257 /// |
|
258 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
|
259 }; |
|
260 |
|
261 /// Dfs searches for the nodes wich are not marked in |
|
262 /// \c reached_map |
|
263 /// Reached is a read-write bool Node-map, |
|
264 /// Pred is a write Node-map, have to be. |
|
265 template <typename Graph, |
|
266 typename ReachedMap=typename Graph::template NodeMap<bool>, |
|
267 typename PredMap |
|
268 =typename Graph::template NodeMap<typename Graph::Edge> > |
|
269 class Dfs : public DfsIterator<Graph, ReachedMap> { |
|
270 typedef DfsIterator<Graph, ReachedMap> Parent; |
|
271 protected: |
|
272 typedef typename Parent::Node Node; |
|
273 PredMap& pred; |
|
274 public: |
|
275 /// The algorithm will search in a dfs order for |
|
276 /// the nodes which are \c false initially. |
|
277 /// The constructor makes no initial changes on the maps. |
|
278 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { } |
|
279 /// \c s is marked to be reached and pushed in the bfs queue. |
|
280 /// If the queue is empty, then the first out-edge is processed. |
|
281 /// If \c s was not marked previously, then |
|
282 /// in addition its pred is set to be \c INVALID. |
|
283 /// if \c s was marked previuosly, then it is simply pushed. |
|
284 void push(Node s) { |
|
285 if (this->reached[s]) { |
|
286 Parent::pushAndSetReached(s); |
|
287 } else { |
|
288 Parent::pushAndSetReached(s); |
|
289 pred.set(s, INVALID); |
|
290 } |
|
291 } |
|
292 /// A bfs is processed from \c s. |
|
293 void run(Node s) { |
|
294 push(s); |
|
295 while (!this->finished()) this->operator++(); |
|
296 } |
|
297 /// Beside the dfs iteration, \c pred is saved in a |
|
298 /// newly reached node. |
|
299 Dfs<Graph, ReachedMap, PredMap> operator++() { |
|
300 Parent::operator++(); |
|
301 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
|
302 { |
|
303 pred.set(this->bNode(), this->actual_edge); |
|
304 } |
|
305 return *this; |
|
306 } |
|
307 /// |
|
308 const PredMap& getPredMap() const { return pred; } |
|
309 }; |
|
310 |
|
311 |
|
312 } // namespace hugo |
|
313 |
|
314 #endif //HUGO_BFS_DFS_H |