Index: src/work/marci/bfs_iterator.h
===================================================================
--- src/work/marci/bfs_iterator.h (revision 415)
+++ src/work/marci/bfs_iterator.h (revision 448)
@@ -29,7 +29,8 @@
own_reached_map(true) { }
~BfsIterator() { if (own_reached_map) delete &reached; }
- //s is marcked reached.
- //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
- //is the queue is not empty, then is it pushed.
+ /// This method markes s reached.
+ /// If the queue is empty, then s is pushed in the bfs queue
+ /// and the first OutEdgeIt is processed.
+ /// If the queue is not empty, then s is simply pushed.
void pushAndSetReached(Node s) {
reached.set(s, true);
@@ -51,4 +52,6 @@
}
}
+ /// As \c BfsIterator works as an edge-iterator,
+ /// its \c operator++() iterates on the edges in a bfs order.
BfsIterator&
operator++() {
@@ -84,4 +87,6 @@
}
bool finished() const { return bfs_queue.empty(); }
+ /// The conversion operator makes for converting the bfs-iterator
+ /// to an \c out-edge-iterator.
operator OutEdgeIt() const { return actual_edge; }
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
@@ -94,5 +99,7 @@
/// Bfs searches from s for the nodes wich are not marked in
- /// reachedmap
+ /// \c reached_map
+ /// Reached is a read-write bool-map, Pred is a write-nodemap
+ /// and dist is an rw-nodemap, have to be.
template ,
@@ -108,9 +115,9 @@
public:
Bfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator(_graph, _reached), pred(&_pred), dist(&_dist) { }
- //s is marked to be reached and pushed in the bfs queue.
- //if the queue is empty, then the first out-edge is processed
- //If s was not marked previously, then
- //in addition its pred is set to be INVALID, and dist to 0.
- //if s was marked previuosly, then it is simply pushed.
+ /// s is marked to be reached and pushed in the bfs queue.
+ /// If the queue is empty, then the first out-edge is processed.
+ /// If s was not marked previously, then
+ /// in addition its pred is set to be INVALID, and dist to 0.
+ /// if s was marked previuosly, then it is simply pushed.
void push(Node s) {
if (this->reached[s]) {
@@ -122,4 +129,5 @@
}
}
+ /// A bfs is processed from s.
void run(Node s) {
push(s);
@@ -201,4 +209,48 @@
};
+ /// Dfs searches from s for the nodes wich are not marked in
+ /// \c reached_map
+ /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
+ template ,
+ typename PredMap
+ =typename Graph::template NodeMap >
+ class Dfs : public DfsIterator {
+ typedef DfsIterator Parent;
+ protected:
+ typedef typename Parent::Node Node;
+ PredMap& pred;
+ public:
+ Dfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator(_graph, _reached), pred(&_pred) { }
+ /// s is marked to be reached and pushed in the bfs queue.
+ /// If the queue is empty, then the first out-edge is processed.
+ /// If s was not marked previously, then
+ /// in addition its pred is set to be INVALID.
+ /// if s was marked previuosly, then it is simply pushed.
+ void push(Node s) {
+ if (this->reached[s]) {
+ Parent::pushAndSetReached(s);
+ } else {
+ Parent::pushAndSetReached(s);
+ pred.set(s, INVALID);
+ }
+ }
+ /// A bfs is processed from s.
+ void run(Node s) {
+ push(s);
+ while (!this->finished()) this->operator++();
+ }
+ Dfs operator++() {
+ Parent::operator++();
+ if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
+ {
+ pred.set(this->bNode(), this->actual_edge);
+ }
+ return *this;
+ }
+ const PredMap& getPredMap() const { return pred; }
+ };
+
+
} // namespace hugo