19 namespace hugo { |
19 namespace hugo { |
20 |
20 |
21 /// Bfs searches for the nodes wich are not marked in |
21 /// Bfs searches for the nodes wich are not marked in |
22 /// \c reached_map |
22 /// \c reached_map |
23 /// Reached have to work as read-write bool Node-map. |
23 /// Reached have to work as read-write bool Node-map. |
|
24 /// \ingroup galgs |
24 template <typename Graph, /*typename OutEdgeIt,*/ |
25 template <typename Graph, /*typename OutEdgeIt,*/ |
25 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
26 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
26 class BfsIterator { |
27 class BfsIterator { |
27 protected: |
28 protected: |
28 typedef typename Graph::Node Node; |
29 typedef typename Graph::Node Node; |
103 } |
104 } |
104 } |
105 } |
105 } |
106 } |
106 return *this; |
107 return *this; |
107 } |
108 } |
108 /// |
109 /// Guess what? |
109 bool finished() const { return bfs_queue.empty(); } |
110 bool finished() const { return bfs_queue.empty(); } |
110 /// The conversion operator makes for converting the bfs-iterator |
111 /// The conversion operator makes for converting the bfs-iterator |
111 /// to an \c out-edge-iterator. |
112 /// to an \c out-edge-iterator. |
112 ///\bug Edge have to be in HUGO 0.2 |
113 ///\bug Edge have to be in HUGO 0.2 |
113 operator OutEdgeIt() const { return actual_edge; } |
114 operator OutEdgeIt() const { return actual_edge; } |
114 /// |
115 /// Guess what? |
115 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
116 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
116 /// |
117 /// Guess what? |
117 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
118 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
118 /// |
119 /// Guess what? |
119 Node aNode() const { return bfs_queue.front(); } |
120 Node aNode() const { return bfs_queue.front(); } |
120 /// |
121 /// Guess what? |
121 Node bNode() const { return graph->bNode(actual_edge); } |
122 Node bNode() const { return graph->bNode(actual_edge); } |
122 /// |
123 /// Guess what? |
123 const ReachedMap& getReachedMap() const { return reached; } |
124 const ReachedMap& getReachedMap() const { return reached; } |
124 /// |
125 /// Guess what? |
125 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
126 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
126 }; |
127 }; |
127 |
128 |
128 /// Bfs searches for the nodes wich are not marked in |
129 /// Bfs searches for the nodes wich are not marked in |
129 /// \c reached_map |
130 /// \c reached_map |
130 /// Reached have to work as a read-write bool Node-map, |
131 /// Reached have to work as a read-write bool Node-map, |
131 /// Pred is a write Edge Node-map and |
132 /// Pred is a write Edge Node-map and |
132 /// Dist is a read-write int Node-map, have to be. |
133 /// Dist is a read-write Node-map of integral value, have to be. |
133 ///\todo In fact onsly simple operations requirement are needed for |
134 /// \ingroup galgs |
134 /// Dist::Value. |
|
135 template <typename Graph, |
135 template <typename Graph, |
136 typename ReachedMap=typename Graph::template NodeMap<bool>, |
136 typename ReachedMap=typename Graph::template NodeMap<bool>, |
137 typename PredMap |
137 typename PredMap |
138 =typename Graph::template NodeMap<typename Graph::Edge>, |
138 =typename Graph::template NodeMap<typename Graph::Edge>, |
139 typename DistMap=typename Graph::template NodeMap<int> > |
139 typename DistMap=typename Graph::template NodeMap<int> > |
176 pred.set(this->bNode(), this->actual_edge); |
176 pred.set(this->bNode(), this->actual_edge); |
177 dist.set(this->bNode(), dist[this->aNode()]); |
177 dist.set(this->bNode(), dist[this->aNode()]); |
178 } |
178 } |
179 return *this; |
179 return *this; |
180 } |
180 } |
181 /// |
181 /// Guess what? |
182 const PredMap& getPredMap() const { return pred; } |
182 const PredMap& getPredMap() const { return pred; } |
183 /// |
183 /// Guess what? |
184 const DistMap& getDistMap() const { return dist; } |
184 const DistMap& getDistMap() const { return dist; } |
185 }; |
185 }; |
186 |
186 |
187 /// Dfs searches for the nodes wich are not marked in |
187 /// Dfs searches for the nodes wich are not marked in |
188 /// \c reached_map |
188 /// \c reached_map |
189 /// Reached have to be a read-write bool Node-map. |
189 /// Reached have to be a read-write bool Node-map. |
|
190 /// \ingroup galgs |
190 template <typename Graph, /*typename OutEdgeIt,*/ |
191 template <typename Graph, /*typename OutEdgeIt,*/ |
191 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
192 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
192 class DfsIterator { |
193 class DfsIterator { |
193 protected: |
194 protected: |
194 typedef typename Graph::Node Node; |
195 typedef typename Graph::Node Node; |
246 //actual_node=G.aNode(dfs_stack.top()); |
247 //actual_node=G.aNode(dfs_stack.top()); |
247 dfs_stack.pop(); |
248 dfs_stack.pop(); |
248 } |
249 } |
249 return *this; |
250 return *this; |
250 } |
251 } |
251 /// |
252 /// Guess what? |
252 bool finished() const { return dfs_stack.empty(); } |
253 bool finished() const { return dfs_stack.empty(); } |
253 /// |
254 /// Guess what? |
254 operator OutEdgeIt() const { return actual_edge; } |
255 operator OutEdgeIt() const { return actual_edge; } |
255 /// |
256 /// Guess what? |
256 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
257 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
257 /// |
258 /// Guess what? |
258 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
259 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
259 /// |
260 /// Guess what? |
260 Node aNode() const { return actual_node; /*FIXME*/} |
261 Node aNode() const { return actual_node; /*FIXME*/} |
261 /// |
262 /// Guess what? |
262 Node bNode() const { return graph->bNode(actual_edge); } |
263 Node bNode() const { return graph->bNode(actual_edge); } |
263 /// |
264 /// Guess what? |
264 const ReachedMap& getReachedMap() const { return reached; } |
265 const ReachedMap& getReachedMap() const { return reached; } |
265 /// |
266 /// Guess what? |
266 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
267 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
267 }; |
268 }; |
268 |
269 |
269 /// Dfs searches for the nodes wich are not marked in |
270 /// Dfs searches for the nodes wich are not marked in |
270 /// \c reached_map |
271 /// \c reached_map |
271 /// Reached is a read-write bool Node-map, |
272 /// Reached is a read-write bool Node-map, |
272 /// Pred is a write Node-map, have to be. |
273 /// Pred is a write Node-map, have to be. |
|
274 /// \ingroup galgs |
273 template <typename Graph, |
275 template <typename Graph, |
274 typename ReachedMap=typename Graph::template NodeMap<bool>, |
276 typename ReachedMap=typename Graph::template NodeMap<bool>, |
275 typename PredMap |
277 typename PredMap |
276 =typename Graph::template NodeMap<typename Graph::Edge> > |
278 =typename Graph::template NodeMap<typename Graph::Edge> > |
277 class Dfs : public DfsIterator<Graph, ReachedMap> { |
279 class Dfs : public DfsIterator<Graph, ReachedMap> { |