Index: src/work/marci/bfs_iterator.h
===================================================================
--- src/work/marci/bfs_iterator.h (revision 560)
+++ src/work/marci/bfs_iterator.h (revision 597)
@@ -11,4 +11,7 @@
namespace hugo {
+ /// Bfs searches for the nodes wich are not marked in
+ /// \c reached_map
+ /// Reached have to work as read-write bool Node-map.
template */ >
@@ -24,15 +27,22 @@
bool own_reached_map;
public:
+ /// In that constructor \c _reached have to be a reference
+ /// for a bool Node-map. The algorithm will search in a bfs order for
+ /// the nodes which are \c false initially
BfsIterator(const Graph& _graph, ReachedMap& _reached) :
graph(&_graph), reached(_reached),
own_reached_map(false) { }
+ /// The same as above, but the map storing the reached nodes
+ /// is constructed dynamically to everywhere false.
BfsIterator(const Graph& _graph) :
graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
own_reached_map(true) { }
+ /// The storing the reached nodes have to be destroyed if
+ /// it was constructed dynamically
~BfsIterator() { if (own_reached_map) delete &reached; }
- /// 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.
+ /// This method markes \c s reached.
+ /// If the queue is empty, then \c s is pushed in the bfs queue
+ /// and the first out-edge is processed.
+ /// If the queue is not empty, then \c s is simply pushed.
void pushAndSetReached(Node s) {
reached.set(s, true);
@@ -88,20 +98,31 @@
return *this;
}
+ ///
bool finished() const { return bfs_queue.empty(); }
/// The conversion operator makes for converting the bfs-iterator
/// to an \c out-edge-iterator.
+ ///\bug Edge have to be in HUGO 0.2
operator OutEdgeIt() const { return actual_edge; }
+ ///
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+ ///
bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
+ ///
Node aNode() const { return bfs_queue.front(); }
+ ///
Node bNode() const { return graph->bNode(actual_edge); }
+ ///
const ReachedMap& getReachedMap() const { return reached; }
+ ///
const std::queue& getBfsQueue() const { return bfs_queue; }
};
- /// Bfs searches from s for the nodes wich are not marked in
+ /// Bfs searches for the nodes wich are not marked in
/// \c reached_map
- /// Reached is a read-write bool-map, Pred is a write-nodemap
- /// and dist is an rw-nodemap, have to be.
+ /// Reached have to work as a read-write bool Node-map,
+ /// Pred is a write Edge Node-map and
+ /// Dist is a read-write int Node-map, have to be.
+ ///\todo In fact onsly simple operations requirement are needed for
+ /// Dist::Value.
template ,
@@ -116,10 +137,13 @@
DistMap& dist;
public:
+ /// The algorithm will search in a bfs order for
+ /// the nodes which are \c false initially.
+ /// The constructor makes no initial changes on the maps.
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.
+ /// \c 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.
+ /// If \c s was not marked previously, then
+ /// in addition its pred is set to be \c INVALID, and dist to \c 0.
+ /// if \c s was marked previuosly, then it is simply pushed.
void push(Node s) {
if (this->reached[s]) {
@@ -131,9 +155,11 @@
}
}
- /// A bfs is processed from s.
+ /// A bfs is processed from \c s.
void run(Node s) {
push(s);
while (!this->finished()) this->operator++();
}
+ /// Beside the bfs iteration, \c pred and \dist are saved in a
+ /// newly reached node.
Bfs operator++() {
Parent::operator++();
@@ -145,8 +171,13 @@
return *this;
}
+ ///
const PredMap& getPredMap() const { return pred; }
+ ///
const DistMap& getDistMap() const { return dist; }
};
+ /// Dfs searches for the nodes wich are not marked in
+ /// \c reached_map
+ /// Reached have to be a read-write bool Node-map.
template */ >
@@ -163,11 +194,18 @@
bool own_reached_map;
public:
+ /// In that constructor \c _reached have to be a reference
+ /// for a bool Node-map. The algorithm will search in a dfs order for
+ /// the nodes which are \c false initially
DfsIterator(const Graph& _graph, ReachedMap& _reached) :
graph(&_graph), reached(_reached),
own_reached_map(false) { }
+ /// The same as above, but the map of reached nodes is
+ /// constructed dynamically
+ /// to everywhere false.
DfsIterator(const Graph& _graph) :
graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
own_reached_map(true) { }
~DfsIterator() { if (own_reached_map) delete &reached; }
+ /// This method markes s reached and first out-edge is processed.
void pushAndSetReached(Node s) {
actual_node=s;
@@ -177,4 +215,6 @@
dfs_stack.push(e);
}
+ /// As \c DfsIterator works as an edge-iterator,
+ /// its \c operator++() iterates on the edges in a dfs order.
DfsIterator&
operator++() {
@@ -201,17 +241,26 @@
return *this;
}
+ ///
bool finished() const { return dfs_stack.empty(); }
+ ///
operator OutEdgeIt() const { return actual_edge; }
+ ///
bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+ ///
bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
+ ///
Node aNode() const { return actual_node; /*FIXME*/}
+ ///
Node bNode() const { return graph->bNode(actual_edge); }
+ ///
const ReachedMap& getReachedMap() const { return reached; }
+ ///
const std::stack& getDfsStack() const { return dfs_stack; }
};
- /// Dfs searches from s for the nodes wich are not marked in
+ /// Dfs searches 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.
+ /// Reached is a read-write bool Node-map,
+ /// Pred is a write Node-map, have to be.
template ,
@@ -224,10 +273,13 @@
PredMap& pred;
public:
+ /// The algorithm will search in a dfs order for
+ /// the nodes which are \c false initially.
+ /// The constructor makes no initial changes on the maps.
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.
+ /// \c 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.
+ /// If \c s was not marked previously, then
+ /// in addition its pred is set to be \c INVALID.
+ /// if \c s was marked previuosly, then it is simply pushed.
void push(Node s) {
if (this->reached[s]) {
@@ -238,9 +290,11 @@
}
}
- /// A bfs is processed from s.
+ /// A bfs is processed from \c s.
void run(Node s) {
push(s);
while (!this->finished()) this->operator++();
}
+ /// Beside the dfs iteration, \c pred is saved in a
+ /// newly reached node.
Dfs operator++() {
Parent::operator++();
@@ -251,4 +305,5 @@
return *this;
}
+ ///
const PredMap& getPredMap() const { return pred; }
};