Changeset 597:a6e2b02f496a in lemon-0.x for src/work/marci/bfs_iterator.h

Timestamp:

05/10/04 18:31:48 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@777

Message:

bfs, dfs docs

File:

• src/work/marci/bfs_iterator.h (modified) (12 diffs)

src/work/marci/bfs_iterator.h

@@ -11 +11 @@
 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>*/ >
@@ -24 +27 @@
     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 +98 @@
       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>, 
@@ -116 +137 @@
     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]) {
@@ -131 +155 @@
       }
     }
-    /// 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++();
@@ -145 +171 @@
       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>*/ >
@@ -163 +194 @@
     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 +215 @@
       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++() { 
@@ -201 +241 @@
       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>, 
@@ -224 +273 @@
     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]) {
@@ -238 +290 @@
       }
     }
-    /// 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++();
@@ -251 +305 @@
       return *this;
     }
+    ///
     const PredMap& getPredMap() const { return pred; }
   };