1.1 --- a/src/work/marci/bfs_iterator.h Mon May 10 15:15:37 2004 +0000
1.2 +++ b/src/work/marci/bfs_iterator.h Mon May 10 16:31:48 2004 +0000
1.3 @@ -10,6 +10,9 @@
1.4
1.5 namespace hugo {
1.6
1.7 + /// Bfs searches for the nodes wich are not marked in
1.8 + /// \c reached_map
1.9 + /// Reached have to work as read-write bool Node-map.
1.10 template <typename Graph, /*typename OutEdgeIt,*/
1.11 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.12 class BfsIterator {
1.13 @@ -23,17 +26,24 @@
1.14 OutEdgeIt actual_edge;
1.15 bool own_reached_map;
1.16 public:
1.17 + /// In that constructor \c _reached have to be a reference
1.18 + /// for a bool Node-map. The algorithm will search in a bfs order for
1.19 + /// the nodes which are \c false initially
1.20 BfsIterator(const Graph& _graph, ReachedMap& _reached) :
1.21 graph(&_graph), reached(_reached),
1.22 own_reached_map(false) { }
1.23 + /// The same as above, but the map storing the reached nodes
1.24 + /// is constructed dynamically to everywhere false.
1.25 BfsIterator(const Graph& _graph) :
1.26 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.27 own_reached_map(true) { }
1.28 + /// The storing the reached nodes have to be destroyed if
1.29 + /// it was constructed dynamically
1.30 ~BfsIterator() { if (own_reached_map) delete &reached; }
1.31 - /// This method markes s reached.
1.32 - /// If the queue is empty, then s is pushed in the bfs queue
1.33 - /// and the first OutEdgeIt is processed.
1.34 - /// If the queue is not empty, then s is simply pushed.
1.35 + /// This method markes \c s reached.
1.36 + /// If the queue is empty, then \c s is pushed in the bfs queue
1.37 + /// and the first out-edge is processed.
1.38 + /// If the queue is not empty, then \c s is simply pushed.
1.39 void pushAndSetReached(Node s) {
1.40 reached.set(s, true);
1.41 if (bfs_queue.empty()) {
1.42 @@ -87,22 +97,33 @@
1.43 }
1.44 return *this;
1.45 }
1.46 + ///
1.47 bool finished() const { return bfs_queue.empty(); }
1.48 /// The conversion operator makes for converting the bfs-iterator
1.49 /// to an \c out-edge-iterator.
1.50 + ///\bug Edge have to be in HUGO 0.2
1.51 operator OutEdgeIt() const { return actual_edge; }
1.52 + ///
1.53 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.54 + ///
1.55 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.56 + ///
1.57 Node aNode() const { return bfs_queue.front(); }
1.58 + ///
1.59 Node bNode() const { return graph->bNode(actual_edge); }
1.60 + ///
1.61 const ReachedMap& getReachedMap() const { return reached; }
1.62 + ///
1.63 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.64 };
1.65
1.66 - /// Bfs searches from s for the nodes wich are not marked in
1.67 + /// Bfs searches for the nodes wich are not marked in
1.68 /// \c reached_map
1.69 - /// Reached is a read-write bool-map, Pred is a write-nodemap
1.70 - /// and dist is an rw-nodemap, have to be.
1.71 + /// Reached have to work as a read-write bool Node-map,
1.72 + /// Pred is a write Edge Node-map and
1.73 + /// Dist is a read-write int Node-map, have to be.
1.74 + ///\todo In fact onsly simple operations requirement are needed for
1.75 + /// Dist::Value.
1.76 template <typename Graph,
1.77 typename ReachedMap=typename Graph::template NodeMap<bool>,
1.78 typename PredMap
1.79 @@ -115,12 +136,15 @@
1.80 PredMap& pred;
1.81 DistMap& dist;
1.82 public:
1.83 + /// The algorithm will search in a bfs order for
1.84 + /// the nodes which are \c false initially.
1.85 + /// The constructor makes no initial changes on the maps.
1.86 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
1.87 - /// s is marked to be reached and pushed in the bfs queue.
1.88 + /// \c s is marked to be reached and pushed in the bfs queue.
1.89 /// If the queue is empty, then the first out-edge is processed.
1.90 - /// If s was not marked previously, then
1.91 - /// in addition its pred is set to be INVALID, and dist to 0.
1.92 - /// if s was marked previuosly, then it is simply pushed.
1.93 + /// If \c s was not marked previously, then
1.94 + /// in addition its pred is set to be \c INVALID, and dist to \c 0.
1.95 + /// if \c s was marked previuosly, then it is simply pushed.
1.96 void push(Node s) {
1.97 if (this->reached[s]) {
1.98 Parent::pushAndSetReached(s);
1.99 @@ -130,11 +154,13 @@
1.100 dist.set(s, 0);
1.101 }
1.102 }
1.103 - /// A bfs is processed from s.
1.104 + /// A bfs is processed from \c s.
1.105 void run(Node s) {
1.106 push(s);
1.107 while (!this->finished()) this->operator++();
1.108 }
1.109 + /// Beside the bfs iteration, \c pred and \dist are saved in a
1.110 + /// newly reached node.
1.111 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
1.112 Parent::operator++();
1.113 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
1.114 @@ -144,10 +170,15 @@
1.115 }
1.116 return *this;
1.117 }
1.118 + ///
1.119 const PredMap& getPredMap() const { return pred; }
1.120 + ///
1.121 const DistMap& getDistMap() const { return dist; }
1.122 };
1.123
1.124 + /// Dfs searches for the nodes wich are not marked in
1.125 + /// \c reached_map
1.126 + /// Reached have to be a read-write bool Node-map.
1.127 template <typename Graph, /*typename OutEdgeIt,*/
1.128 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.129 class DfsIterator {
1.130 @@ -162,13 +193,20 @@
1.131 ReachedMap& reached;
1.132 bool own_reached_map;
1.133 public:
1.134 + /// In that constructor \c _reached have to be a reference
1.135 + /// for a bool Node-map. The algorithm will search in a dfs order for
1.136 + /// the nodes which are \c false initially
1.137 DfsIterator(const Graph& _graph, ReachedMap& _reached) :
1.138 graph(&_graph), reached(_reached),
1.139 own_reached_map(false) { }
1.140 + /// The same as above, but the map of reached nodes is
1.141 + /// constructed dynamically
1.142 + /// to everywhere false.
1.143 DfsIterator(const Graph& _graph) :
1.144 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.145 own_reached_map(true) { }
1.146 ~DfsIterator() { if (own_reached_map) delete &reached; }
1.147 + /// This method markes s reached and first out-edge is processed.
1.148 void pushAndSetReached(Node s) {
1.149 actual_node=s;
1.150 reached.set(s, true);
1.151 @@ -176,6 +214,8 @@
1.152 graph->first(e, s);
1.153 dfs_stack.push(e);
1.154 }
1.155 + /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
1.156 + /// its \c operator++() iterates on the edges in a dfs order.
1.157 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.158 operator++() {
1.159 actual_edge=dfs_stack.top();
1.160 @@ -200,19 +240,28 @@
1.161 }
1.162 return *this;
1.163 }
1.164 + ///
1.165 bool finished() const { return dfs_stack.empty(); }
1.166 + ///
1.167 operator OutEdgeIt() const { return actual_edge; }
1.168 + ///
1.169 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.170 + ///
1.171 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.172 + ///
1.173 Node aNode() const { return actual_node; /*FIXME*/}
1.174 + ///
1.175 Node bNode() const { return graph->bNode(actual_edge); }
1.176 + ///
1.177 const ReachedMap& getReachedMap() const { return reached; }
1.178 + ///
1.179 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.180 };
1.181
1.182 - /// Dfs searches from s for the nodes wich are not marked in
1.183 + /// Dfs searches for the nodes wich are not marked in
1.184 /// \c reached_map
1.185 - /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
1.186 + /// Reached is a read-write bool Node-map,
1.187 + /// Pred is a write Node-map, have to be.
1.188 template <typename Graph,
1.189 typename ReachedMap=typename Graph::template NodeMap<bool>,
1.190 typename PredMap
1.191 @@ -223,12 +272,15 @@
1.192 typedef typename Parent::Node Node;
1.193 PredMap& pred;
1.194 public:
1.195 + /// The algorithm will search in a dfs order for
1.196 + /// the nodes which are \c false initially.
1.197 + /// The constructor makes no initial changes on the maps.
1.198 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
1.199 - /// s is marked to be reached and pushed in the bfs queue.
1.200 + /// \c s is marked to be reached and pushed in the bfs queue.
1.201 /// If the queue is empty, then the first out-edge is processed.
1.202 - /// If s was not marked previously, then
1.203 - /// in addition its pred is set to be INVALID.
1.204 - /// if s was marked previuosly, then it is simply pushed.
1.205 + /// If \c s was not marked previously, then
1.206 + /// in addition its pred is set to be \c INVALID.
1.207 + /// if \c s was marked previuosly, then it is simply pushed.
1.208 void push(Node s) {
1.209 if (this->reached[s]) {
1.210 Parent::pushAndSetReached(s);
1.211 @@ -237,11 +289,13 @@
1.212 pred.set(s, INVALID);
1.213 }
1.214 }
1.215 - /// A bfs is processed from s.
1.216 + /// A bfs is processed from \c s.
1.217 void run(Node s) {
1.218 push(s);
1.219 while (!this->finished()) this->operator++();
1.220 }
1.221 + /// Beside the dfs iteration, \c pred is saved in a
1.222 + /// newly reached node.
1.223 Dfs<Graph, ReachedMap, PredMap> operator++() {
1.224 Parent::operator++();
1.225 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
1.226 @@ -250,6 +304,7 @@
1.227 }
1.228 return *this;
1.229 }
1.230 + ///
1.231 const PredMap& getPredMap() const { return pred; }
1.232 };
1.233