Changeset 597:a6e2b02f496a in lemon0.x for src/work/marci/bfs_iterator.h
 Timestamp:
 05/10/04 18:31:48 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@777
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bfs_iterator.h
r560 r597 11 11 namespace hugo { 12 12 13 /// Bfs searches for the nodes wich are not marked in 14 /// \c reached_map 15 /// Reached have to work as readwrite bool Nodemap. 13 16 template <typename Graph, /*typename OutEdgeIt,*/ 14 17 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > … … 24 27 bool own_reached_map; 25 28 public: 29 /// In that constructor \c _reached have to be a reference 30 /// for a bool Nodemap. The algorithm will search in a bfs order for 31 /// the nodes which are \c false initially 26 32 BfsIterator(const Graph& _graph, ReachedMap& _reached) : 27 33 graph(&_graph), reached(_reached), 28 34 own_reached_map(false) { } 35 /// The same as above, but the map storing the reached nodes 36 /// is constructed dynamically to everywhere false. 29 37 BfsIterator(const Graph& _graph) : 30 38 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 31 39 own_reached_map(true) { } 40 /// The storing the reached nodes have to be destroyed if 41 /// it was constructed dynamically 32 42 ~BfsIterator() { if (own_reached_map) delete &reached; } 33 /// This method markes s reached.34 /// If the queue is empty, then s is pushed in the bfs queue35 /// and the first OutEdgeItis processed.36 /// If the queue is not empty, then s is simply pushed.43 /// This method markes \c s reached. 44 /// If the queue is empty, then \c s is pushed in the bfs queue 45 /// and the first outedge is processed. 46 /// If the queue is not empty, then \c s is simply pushed. 37 47 void pushAndSetReached(Node s) { 38 48 reached.set(s, true); … … 88 98 return *this; 89 99 } 100 /// 90 101 bool finished() const { return bfs_queue.empty(); } 91 102 /// The conversion operator makes for converting the bfsiterator 92 103 /// to an \c outedgeiterator. 104 ///\bug Edge have to be in HUGO 0.2 93 105 operator OutEdgeIt() const { return actual_edge; } 106 /// 94 107 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 108 /// 95 109 bool isANodeExamined() const { return !(graph>valid(actual_edge)); } 110 /// 96 111 Node aNode() const { return bfs_queue.front(); } 112 /// 97 113 Node bNode() const { return graph>bNode(actual_edge); } 114 /// 98 115 const ReachedMap& getReachedMap() const { return reached; } 116 /// 99 117 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } 100 118 }; 101 119 102 /// Bfs searches f rom s for the nodes wich are not marked in120 /// Bfs searches for the nodes wich are not marked in 103 121 /// \c reached_map 104 /// Reached is a readwrite boolmap, Pred is a writenodemap 105 /// and dist is an rwnodemap, have to be. 122 /// Reached have to work as a readwrite bool Nodemap, 123 /// Pred is a write Edge Nodemap and 124 /// Dist is a readwrite int Nodemap, have to be. 125 ///\todo In fact onsly simple operations requirement are needed for 126 /// Dist::Value. 106 127 template <typename Graph, 107 128 typename ReachedMap=typename Graph::template NodeMap<bool>, … … 116 137 DistMap& dist; 117 138 public: 139 /// The algorithm will search in a bfs order for 140 /// the nodes which are \c false initially. 141 /// The constructor makes no initial changes on the maps. 118 142 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } 119 /// s is marked to be reached and pushed in the bfs queue.143 /// \c s is marked to be reached and pushed in the bfs queue. 120 144 /// If the queue is empty, then the first outedge is processed. 121 /// If s was not marked previously, then122 /// in addition its pred is set to be INVALID, and dist to0.123 /// if s was marked previuosly, then it is simply pushed.145 /// If \c s was not marked previously, then 146 /// in addition its pred is set to be \c INVALID, and dist to \c 0. 147 /// if \c s was marked previuosly, then it is simply pushed. 124 148 void push(Node s) { 125 149 if (this>reached[s]) { … … 131 155 } 132 156 } 133 /// A bfs is processed from s.157 /// A bfs is processed from \c s. 134 158 void run(Node s) { 135 159 push(s); 136 160 while (!this>finished()) this>operator++(); 137 161 } 162 /// Beside the bfs iteration, \c pred and \dist are saved in a 163 /// newly reached node. 138 164 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { 139 165 Parent::operator++(); … … 145 171 return *this; 146 172 } 173 /// 147 174 const PredMap& getPredMap() const { return pred; } 175 /// 148 176 const DistMap& getDistMap() const { return dist; } 149 177 }; 150 178 179 /// Dfs searches for the nodes wich are not marked in 180 /// \c reached_map 181 /// Reached have to be a readwrite bool Nodemap. 151 182 template <typename Graph, /*typename OutEdgeIt,*/ 152 183 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > … … 163 194 bool own_reached_map; 164 195 public: 196 /// In that constructor \c _reached have to be a reference 197 /// for a bool Nodemap. The algorithm will search in a dfs order for 198 /// the nodes which are \c false initially 165 199 DfsIterator(const Graph& _graph, ReachedMap& _reached) : 166 200 graph(&_graph), reached(_reached), 167 201 own_reached_map(false) { } 202 /// The same as above, but the map of reached nodes is 203 /// constructed dynamically 204 /// to everywhere false. 168 205 DfsIterator(const Graph& _graph) : 169 206 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 170 207 own_reached_map(true) { } 171 208 ~DfsIterator() { if (own_reached_map) delete &reached; } 209 /// This method markes s reached and first outedge is processed. 172 210 void pushAndSetReached(Node s) { 173 211 actual_node=s; … … 177 215 dfs_stack.push(e); 178 216 } 217 /// As \c DfsIterator<Graph, ReachedMap> works as an edgeiterator, 218 /// its \c operator++() iterates on the edges in a dfs order. 179 219 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 180 220 operator++() { … … 201 241 return *this; 202 242 } 243 /// 203 244 bool finished() const { return dfs_stack.empty(); } 245 /// 204 246 operator OutEdgeIt() const { return actual_edge; } 247 /// 205 248 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 249 /// 206 250 bool isANodeExamined() const { return !(graph>valid(actual_edge)); } 251 /// 207 252 Node aNode() const { return actual_node; /*FIXME*/} 253 /// 208 254 Node bNode() const { return graph>bNode(actual_edge); } 255 /// 209 256 const ReachedMap& getReachedMap() const { return reached; } 257 /// 210 258 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 211 259 }; 212 260 213 /// Dfs searches f rom s for the nodes wich are not marked in261 /// Dfs searches for the nodes wich are not marked in 214 262 /// \c reached_map 215 /// Reached is a readwrite boolmap, Pred is a writenodemap, have to be. 263 /// Reached is a readwrite bool Nodemap, 264 /// Pred is a write Nodemap, have to be. 216 265 template <typename Graph, 217 266 typename ReachedMap=typename Graph::template NodeMap<bool>, … … 224 273 PredMap& pred; 225 274 public: 275 /// The algorithm will search in a dfs order for 276 /// the nodes which are \c false initially. 277 /// The constructor makes no initial changes on the maps. 226 278 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { } 227 /// s is marked to be reached and pushed in the bfs queue.279 /// \c s is marked to be reached and pushed in the bfs queue. 228 280 /// If the queue is empty, then the first outedge is processed. 229 /// If s was not marked previously, then230 /// in addition its pred is set to be INVALID.231 /// if s was marked previuosly, then it is simply pushed.281 /// If \c s was not marked previously, then 282 /// in addition its pred is set to be \c INVALID. 283 /// if \c s was marked previuosly, then it is simply pushed. 232 284 void push(Node s) { 233 285 if (this>reached[s]) { … … 238 290 } 239 291 } 240 /// A bfs is processed from s.292 /// A bfs is processed from \c s. 241 293 void run(Node s) { 242 294 push(s); 243 295 while (!this>finished()) this>operator++(); 244 296 } 297 /// Beside the dfs iteration, \c pred is saved in a 298 /// newly reached node. 245 299 Dfs<Graph, ReachedMap, PredMap> operator++() { 246 300 Parent::operator++(); … … 251 305 return *this; 252 306 } 307 /// 253 308 const PredMap& getPredMap() const { return pred; } 254 309 };
Note: See TracChangeset
for help on using the changeset viewer.