ResGraphWrapper<Graph> is done, so does dimacs.h.
7 /// \brief Bfs and dfs iterators.
9 /// This file contains bfs and dfs iterator classes.
11 // /// \author Marton Makai
17 #include <hugo/invalid.h>
21 /// Bfs searches for the nodes wich are not marked in
23 /// Reached have to be a read-write bool node-map.
25 template <typename Graph, /*typename OutEdgeIt,*/
26 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
29 typedef typename Graph::Node Node;
30 typedef typename Graph::OutEdgeIt OutEdgeIt;
32 std::queue<Node> bfs_queue;
34 bool b_node_newly_reached;
35 OutEdgeIt actual_edge;
38 /// In that constructor \c _reached have to be a reference
39 /// for a bool bode-map. The algorithm will search for the
40 /// initially \c false nodes
42 BfsIterator(const Graph& _graph, ReachedMap& _reached) :
43 graph(&_graph), reached(_reached),
44 own_reached_map(false) { }
45 /// The same as above, but the map storing the reached nodes
46 /// is constructed dynamically to everywhere false.
48 BfsIterator(const Graph& _graph) :
49 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
50 own_reached_map(true) { }
51 /// The map storing the reached nodes have to be destroyed if
52 /// it was constructed dynamically
53 ~BfsIterator() { if (own_reached_map) delete &reached; }
54 /// This method markes \c s reached.
55 /// If the queue is empty, then \c s is pushed in the bfs queue
56 /// and the first out-edge is processed.
57 /// If the queue is not empty, then \c s is simply pushed.
58 void pushAndSetReached(Node s) {
60 if (bfs_queue.empty()) {
62 graph->first(actual_edge, s);
63 if (actual_edge!=INVALID) {
64 Node w=graph->head(actual_edge);
68 b_node_newly_reached=true;
70 b_node_newly_reached=false;
77 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
78 /// its \c operator++() iterates on the edges in a bfs order.
79 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
81 if (actual_edge!=INVALID) {
83 if (actual_edge!=INVALID) {
84 Node w=graph->head(actual_edge);
88 b_node_newly_reached=true;
90 b_node_newly_reached=false;
95 if (!bfs_queue.empty()) {
96 graph->first(actual_edge, bfs_queue.front());
97 if (actual_edge!=INVALID) {
98 Node w=graph->head(actual_edge);
101 reached.set(w, true);
102 b_node_newly_reached=true;
104 b_node_newly_reached=false;
111 /// Returns true iff the algorithm is finished.
112 bool finished() const { return bfs_queue.empty(); }
113 /// The conversion operator makes for converting the bfs-iterator
114 /// to an \c out-edge-iterator.
115 ///\bug Edge have to be in HUGO 0.2
116 operator OutEdgeIt() const { return actual_edge; }
117 /// Returns if b-node has been reached just now.
118 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
119 /// Returns if a-node is examined.
120 bool isANodeExamined() const { return actual_edge==INVALID; }
121 /// Returns a-node of the actual edge, so does if the edge is invalid.
122 Node aNode() const { return bfs_queue.front(); }
123 /// \pre The actual edge have to be valid.
124 Node bNode() const { return graph->bNode(actual_edge); }
127 const ReachedMap& getReachedMap() const { return reached; }
130 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
133 /// Bfs searches for the nodes wich are not marked in
135 /// Reached have to work as a read-write bool Node-map,
136 /// Pred is a write edge node-map and
137 /// Dist is a read-write node-map of integral value, have to be.
139 template <typename Graph,
140 typename ReachedMap=typename Graph::template NodeMap<bool>,
142 =typename Graph::template NodeMap<typename Graph::Edge>,
143 typename DistMap=typename Graph::template NodeMap<int> >
144 class Bfs : public BfsIterator<Graph, ReachedMap> {
145 typedef BfsIterator<Graph, ReachedMap> Parent;
147 typedef typename Parent::Node Node;
151 /// The algorithm will search in a bfs order for
152 /// the nodes which are \c false initially.
153 /// The constructor makes no initial changes on the maps.
154 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) :
155 BfsIterator<Graph, ReachedMap>(_graph, _reached),
156 pred(_pred), dist(_dist) { }
157 /// \c s is marked to be reached and pushed in the bfs queue.
158 /// If the queue is empty, then the first out-edge is processed.
159 /// If \c s was not marked previously, then
160 /// in addition its pred is set to be \c INVALID, and dist to \c 0.
161 /// if \c s was marked previuosly, then it is simply pushed.
163 if (this->reached[s]) {
164 Parent::pushAndSetReached(s);
166 Parent::pushAndSetReached(s);
167 pred.set(s, INVALID);
171 /// A bfs is processed from \c s.
174 while (!this->finished()) this->operator++();
176 /// Beside the bfs iteration, \c pred and \dist are saved in a
177 /// newly reached node.
178 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
179 Parent::operator++();
180 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
182 pred.set(this->bNode(), this->actual_edge);
183 dist.set(this->bNode(), dist[this->aNode()]);
189 const PredMap& getPredMap() const { return pred; }
192 const DistMap& getDistMap() const { return dist; }
195 /// Dfs searches for the nodes wich are not marked in
197 /// Reached have to be a read-write bool Node-map.
199 template <typename Graph, /*typename OutEdgeIt,*/
200 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
203 typedef typename Graph::Node Node;
204 typedef typename Graph::OutEdgeIt OutEdgeIt;
206 std::stack<OutEdgeIt> dfs_stack;
207 bool b_node_newly_reached;
208 OutEdgeIt actual_edge;
211 bool own_reached_map;
213 /// In that constructor \c _reached have to be a reference
214 /// for a bool node-map. The algorithm will search in a dfs order for
215 /// the nodes which are \c false initially
216 DfsIterator(const Graph& _graph, ReachedMap& _reached) :
217 graph(&_graph), reached(_reached),
218 own_reached_map(false) { }
219 /// The same as above, but the map of reached nodes is
220 /// constructed dynamically
221 /// to everywhere false.
222 DfsIterator(const Graph& _graph) :
223 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
224 own_reached_map(true) { }
225 ~DfsIterator() { if (own_reached_map) delete &reached; }
226 /// This method markes s reached and first out-edge is processed.
227 void pushAndSetReached(Node s) {
229 reached.set(s, true);
234 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
235 /// its \c operator++() iterates on the edges in a dfs order.
236 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
238 actual_edge=dfs_stack.top();
239 //actual_node=G.aNode(actual_edge);
240 if (actual_edge!=INVALID/*.valid()*/) {
241 Node w=graph->head(actual_edge);
247 reached.set(w, true);
248 b_node_newly_reached=true;
250 actual_node=graph->tail(actual_edge);
252 b_node_newly_reached=false;
255 //actual_node=G.aNode(dfs_stack.top());
260 /// Returns true iff the algorithm is finished.
261 bool finished() const { return dfs_stack.empty(); }
262 /// The conversion operator makes for converting the bfs-iterator
263 /// to an \c out-edge-iterator.
264 ///\bug Edge have to be in HUGO 0.2
265 operator OutEdgeIt() const { return actual_edge; }
266 /// Returns if b-node has been reached just now.
267 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
268 /// Returns if a-node is examined.
269 bool isANodeExamined() const { return actual_edge==INVALID; }
270 /// Returns a-node of the actual edge, so does if the edge is invalid.
271 Node aNode() const { return actual_node; /*FIXME*/}
272 /// Returns b-node of the actual edge.
273 /// \pre The actual edge have to be valid.
274 Node bNode() const { return graph->bNode(actual_edge); }
277 const ReachedMap& getReachedMap() const { return reached; }
280 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
283 /// Dfs searches for the nodes wich are not marked in
285 /// Reached is a read-write bool node-map,
286 /// Pred is a write node-map, have to be.
288 template <typename Graph,
289 typename ReachedMap=typename Graph::template NodeMap<bool>,
291 =typename Graph::template NodeMap<typename Graph::Edge> >
292 class Dfs : public DfsIterator<Graph, ReachedMap> {
293 typedef DfsIterator<Graph, ReachedMap> Parent;
295 typedef typename Parent::Node Node;
298 /// The algorithm will search in a dfs order for
299 /// the nodes which are \c false initially.
300 /// The constructor makes no initial changes on the maps.
301 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
302 /// \c s is marked to be reached and pushed in the bfs queue.
303 /// If the queue is empty, then the first out-edge is processed.
304 /// If \c s was not marked previously, then
305 /// in addition its pred is set to be \c INVALID.
306 /// if \c s was marked previuosly, then it is simply pushed.
308 if (this->reached[s]) {
309 Parent::pushAndSetReached(s);
311 Parent::pushAndSetReached(s);
312 pred.set(s, INVALID);
315 /// A bfs is processed from \c s.
318 while (!this->finished()) this->operator++();
320 /// Beside the dfs iteration, \c pred is saved in a
321 /// newly reached node.
322 Dfs<Graph, ReachedMap, PredMap>& operator++() {
323 Parent::operator++();
324 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
326 pred.set(this->bNode(), this->actual_edge);
332 const PredMap& getPredMap() const { return pred; }
338 #endif //HUGO_BFS_DFS_H