26 own_reached_map(false) { } |
26 own_reached_map(false) { } |
27 BfsIterator(const Graph& _graph) : |
27 BfsIterator(const Graph& _graph) : |
28 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
28 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
29 own_reached_map(true) { } |
29 own_reached_map(true) { } |
30 ~BfsIterator() { if (own_reached_map) delete &reached; } |
30 ~BfsIterator() { if (own_reached_map) delete &reached; } |
31 //s is marcked reached. |
31 /// This method markes s reached. |
32 //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe. |
32 /// If the queue is empty, then s is pushed in the bfs queue |
33 //is the queue is not empty, then is it pushed. |
33 /// and the first OutEdgeIt is processed. |
|
34 /// If the queue is not empty, then s is simply pushed. |
34 void pushAndSetReached(Node s) { |
35 void pushAndSetReached(Node s) { |
35 reached.set(s, true); |
36 reached.set(s, true); |
36 if (bfs_queue.empty()) { |
37 if (bfs_queue.empty()) { |
37 bfs_queue.push(s); |
38 bfs_queue.push(s); |
38 graph->first(actual_edge, s); |
39 graph->first(actual_edge, s); |
48 } |
49 } |
49 } else { |
50 } else { |
50 bfs_queue.push(s); |
51 bfs_queue.push(s); |
51 } |
52 } |
52 } |
53 } |
|
54 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, |
|
55 /// its \c operator++() iterates on the edges in a bfs order. |
53 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
56 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
54 operator++() { |
57 operator++() { |
55 if (graph->valid(actual_edge)) { |
58 if (graph->valid(actual_edge)) { |
56 graph->next(actual_edge); |
59 graph->next(actual_edge); |
57 if (graph->valid(actual_edge)) { |
60 if (graph->valid(actual_edge)) { |
81 } |
84 } |
82 } |
85 } |
83 return *this; |
86 return *this; |
84 } |
87 } |
85 bool finished() const { return bfs_queue.empty(); } |
88 bool finished() const { return bfs_queue.empty(); } |
|
89 /// The conversion operator makes for converting the bfs-iterator |
|
90 /// to an \c out-edge-iterator. |
86 operator OutEdgeIt() const { return actual_edge; } |
91 operator OutEdgeIt() const { return actual_edge; } |
87 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
92 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
88 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
93 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
89 Node aNode() const { return bfs_queue.front(); } |
94 Node aNode() const { return bfs_queue.front(); } |
90 Node bNode() const { return graph->bNode(actual_edge); } |
95 Node bNode() const { return graph->bNode(actual_edge); } |
91 const ReachedMap& getReachedMap() const { return reached; } |
96 const ReachedMap& getReachedMap() const { return reached; } |
92 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
97 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
93 }; |
98 }; |
94 |
99 |
95 /// Bfs searches from s for the nodes wich are not marked in |
100 /// Bfs searches from s for the nodes wich are not marked in |
96 /// reachedmap |
101 /// \c reached_map |
|
102 /// Reached is a read-write bool-map, Pred is a write-nodemap |
|
103 /// and dist is an rw-nodemap, have to be. |
97 template <typename Graph, |
104 template <typename Graph, |
98 typename ReachedMap=typename Graph::template NodeMap<bool>, |
105 typename ReachedMap=typename Graph::template NodeMap<bool>, |
99 typename PredMap |
106 typename PredMap |
100 =typename Graph::template NodeMap<typename Graph::Edge>, |
107 =typename Graph::template NodeMap<typename Graph::Edge>, |
101 typename DistMap=typename Graph::template NodeMap<int> > |
108 typename DistMap=typename Graph::template NodeMap<int> > |
105 typedef typename Parent::Node Node; |
112 typedef typename Parent::Node Node; |
106 PredMap& pred; |
113 PredMap& pred; |
107 DistMap& dist; |
114 DistMap& dist; |
108 public: |
115 public: |
109 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } |
116 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } |
110 //s is marked to be reached and pushed in the bfs queue. |
117 /// s is marked to be reached and pushed in the bfs queue. |
111 //if the queue is empty, then the first out-edge is processed |
118 /// If the queue is empty, then the first out-edge is processed. |
112 //If s was not marked previously, then |
119 /// If s was not marked previously, then |
113 //in addition its pred is set to be INVALID, and dist to 0. |
120 /// in addition its pred is set to be INVALID, and dist to 0. |
114 //if s was marked previuosly, then it is simply pushed. |
121 /// if s was marked previuosly, then it is simply pushed. |
115 void push(Node s) { |
122 void push(Node s) { |
116 if (this->reached[s]) { |
123 if (this->reached[s]) { |
117 Parent::pushAndSetReached(s); |
124 Parent::pushAndSetReached(s); |
118 } else { |
125 } else { |
119 Parent::pushAndSetReached(s); |
126 Parent::pushAndSetReached(s); |
120 pred.set(s, INVALID); |
127 pred.set(s, INVALID); |
121 dist.set(s, 0); |
128 dist.set(s, 0); |
122 } |
129 } |
123 } |
130 } |
|
131 /// A bfs is processed from s. |
124 void run(Node s) { |
132 void run(Node s) { |
125 push(s); |
133 push(s); |
126 while (!this->finished()) this->operator++(); |
134 while (!this->finished()) this->operator++(); |
127 } |
135 } |
128 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { |
136 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { |
198 Node bNode() const { return graph->bNode(actual_edge); } |
206 Node bNode() const { return graph->bNode(actual_edge); } |
199 const ReachedMap& getReachedMap() const { return reached; } |
207 const ReachedMap& getReachedMap() const { return reached; } |
200 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
208 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
201 }; |
209 }; |
202 |
210 |
|
211 /// Dfs searches from s for the nodes wich are not marked in |
|
212 /// \c reached_map |
|
213 /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be. |
|
214 template <typename Graph, |
|
215 typename ReachedMap=typename Graph::template NodeMap<bool>, |
|
216 typename PredMap |
|
217 =typename Graph::template NodeMap<typename Graph::Edge> > |
|
218 class Dfs : public DfsIterator<Graph, ReachedMap> { |
|
219 typedef DfsIterator<Graph, ReachedMap> Parent; |
|
220 protected: |
|
221 typedef typename Parent::Node Node; |
|
222 PredMap& pred; |
|
223 public: |
|
224 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { } |
|
225 /// s is marked to be reached and pushed in the bfs queue. |
|
226 /// If the queue is empty, then the first out-edge is processed. |
|
227 /// If s was not marked previously, then |
|
228 /// in addition its pred is set to be INVALID. |
|
229 /// if s was marked previuosly, then it is simply pushed. |
|
230 void push(Node s) { |
|
231 if (this->reached[s]) { |
|
232 Parent::pushAndSetReached(s); |
|
233 } else { |
|
234 Parent::pushAndSetReached(s); |
|
235 pred.set(s, INVALID); |
|
236 } |
|
237 } |
|
238 /// A bfs is processed from s. |
|
239 void run(Node s) { |
|
240 push(s); |
|
241 while (!this->finished()) this->operator++(); |
|
242 } |
|
243 Dfs<Graph, ReachedMap, PredMap> operator++() { |
|
244 Parent::operator++(); |
|
245 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
|
246 { |
|
247 pred.set(this->bNode(), this->actual_edge); |
|
248 } |
|
249 return *this; |
|
250 } |
|
251 const PredMap& getPredMap() const { return pred; } |
|
252 }; |
|
253 |
|
254 |
203 } // namespace hugo |
255 } // namespace hugo |
204 |
256 |
205 #endif //HUGO_BFS_ITERATOR_H |
257 #endif //HUGO_BFS_ITERATOR_H |