lemon-0.x: comparison src/work/marci/bfs

equal deleted inserted replaced

-:055a58cb9557
+:4d50edcdb08b
 #include <hugo/invalid.h>
 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 {
 protected:
 typedef typename Graph::Node Node;
 ReachedMap& reached;
 bool b_node_newly_reached;
 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.
+/// This method markes \c s reached.
-/// If the queue is empty, then s is pushed in the bfs queue
+/// If the queue is empty, then \c s is pushed in the bfs queue
-/// and the first OutEdgeIt is processed.
+/// and the first out-edge is processed.
-/// If the queue is not empty, then s is simply pushed.
+/// If the queue is not empty, then \c s is simply pushed.
 void pushAndSetReached(Node s) {
 reached.set(s, true);
 if (bfs_queue.empty()) {
 	bfs_queue.push(s);
 	graph->first(actual_edge, s);
 	  }
 	}
 }
 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
+/// Reached have to work as a read-write bool Node-map,
-/// and dist is an rw-nodemap, have to be.
+/// 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
 	    =typename Graph::template NodeMap<typename Graph::Edge>,
 	    typename DistMap=typename Graph::template NodeMap<int> >
 protected:
 typedef typename Parent::Node Node;
 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
+/// If \c s was not marked previously, then
-/// in addition its pred is set to be INVALID, and dist to 0.
+/// in addition its pred is set to be \c INVALID, and dist to \c 0.
-/// if s was marked previuosly, then it is simply pushed.
+/// if \c 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);
 	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)
 {
 	pred.set(this->bNode(), this->actual_edge);
 	dist.set(this->bNode(), dist[this->aNode()]);
 }
 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 {
 protected:
 typedef typename Graph::Node Node;
 OutEdgeIt actual_edge;
 Node actual_node;
 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);
 OutEdgeIt e;
 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();
 //actual_node=G.aNode(actual_edge);
 if (graph->valid(actual_edge)/*.valid()*/) {
 	//actual_node=G.aNode(dfs_stack.top());
 	dfs_stack.pop();
 }
 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
 	    =typename Graph::template NodeMap<typename Graph::Edge> >
 class Dfs : public DfsIterator<Graph, ReachedMap> {
 typedef DfsIterator<Graph, ReachedMap> Parent;
 protected:
 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
+/// If \c s was not marked previously, then
-/// in addition its pred is set to be INVALID.
+/// in addition its pred is set to be \c INVALID.
-/// if s was marked previuosly, then it is simply pushed.
+/// if \c 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.
+/// 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)
 {
 	pred.set(this->bNode(), this->actual_edge);
 }
 return *this;
 }
+///
 const PredMap& getPredMap() const { return pred; }
 };
 } // namespace hugo

changeset 598	1faa5bec1717
parent 560	5adcef1d7bcc