# HG changeset patch
# User marci
# Date 1084206708 0
# Node ID a6e2b02f496a254ce413eee1e91084744c19ae89
# Parent c43e7d0f075b60dbae877b5519891de8a481c7f2
bfs, dfs docs
diff -r c43e7d0f075b -r a6e2b02f496a src/work/marci/bfs_iterator.h
--- a/src/work/marci/bfs_iterator.h Mon May 10 15:15:37 2004 +0000
+++ b/src/work/marci/bfs_iterator.h Mon May 10 16:31:48 2004 +0000
@@ -10,6 +10,9 @@
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 <typename Graph, /*typename OutEdgeIt,*/
typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
class BfsIterator {
@@ -23,17 +26,24 @@
OutEdgeIt actual_edge;
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);
if (bfs_queue.empty()) {
@@ -87,22 +97,33 @@
}
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<Node>& 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 <typename Graph,
typename ReachedMap=typename Graph::template NodeMap<bool>,
typename PredMap
@@ -115,12 +136,15 @@
PredMap& pred;
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<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_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]) {
Parent::pushAndSetReached(s);
@@ -130,11 +154,13 @@
dist.set(s, 0);
}
}
- /// 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<Graph, ReachedMap, PredMap, DistMap> operator++() {
Parent::operator++();
if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
@@ -144,10 +170,15 @@
}
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 <typename Graph, /*typename OutEdgeIt,*/
typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
class DfsIterator {
@@ -162,13 +193,20 @@
ReachedMap& reached;
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;
reached.set(s, true);
@@ -176,6 +214,8 @@
graph->first(e, s);
dfs_stack.push(e);
}
+ /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
+ /// its \c operator++() iterates on the edges in a dfs order.
DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
operator++() {
actual_edge=dfs_stack.top();
@@ -200,19 +240,28 @@
}
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<OutEdgeIt>& 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 <typename Graph,
typename ReachedMap=typename Graph::template NodeMap<bool>,
typename PredMap
@@ -223,12 +272,15 @@
typedef typename Parent::Node Node;
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<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_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]) {
Parent::pushAndSetReached(s);
@@ -237,11 +289,13 @@
pred.set(s, INVALID);
}
}
- /// 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<Graph, ReachedMap, PredMap> operator++() {
Parent::operator++();
if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
@@ -250,6 +304,7 @@
}
return *this;
}
+ ///
const PredMap& getPredMap() const { return pred; }
};