Changeset 448:510c53fd06cd in lemon0.x for src/work/marci/bfs_iterator.h
 Timestamp:
 04/27/04 18:27:08 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@596
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bfs_iterator.h
r415 r448 29 29 own_reached_map(true) { } 30 30 ~BfsIterator() { if (own_reached_map) delete &reached; } 31 //s is marcked reached. 32 //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe. 33 //is the queue is not empty, then is it pushed. 31 /// This method markes s reached. 32 /// If the queue is empty, then s is pushed in the bfs queue 33 /// and the first OutEdgeIt is processed. 34 /// If the queue is not empty, then s is simply pushed. 34 35 void pushAndSetReached(Node s) { 35 36 reached.set(s, true); … … 51 52 } 52 53 } 54 /// As \c BfsIterator<Graph, ReachedMap> works as an edgeiterator, 55 /// its \c operator++() iterates on the edges in a bfs order. 53 56 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 54 57 operator++() { … … 84 87 } 85 88 bool finished() const { return bfs_queue.empty(); } 89 /// The conversion operator makes for converting the bfsiterator 90 /// to an \c outedgeiterator. 86 91 operator OutEdgeIt() const { return actual_edge; } 87 92 bool isBNodeNewlyReached() const { return b_node_newly_reached; } … … 94 99 95 100 /// Bfs searches from s for the nodes wich are not marked in 96 /// reachedmap 101 /// \c reached_map 102 /// Reached is a readwrite boolmap, Pred is a writenodemap 103 /// and dist is an rwnodemap, have to be. 97 104 template <typename Graph, 98 105 typename ReachedMap=typename Graph::template NodeMap<bool>, … … 108 115 public: 109 116 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { } 110 // s is marked to be reached and pushed in the bfs queue.111 // if the queue is empty, then the first outedge is processed112 // If s was not marked previously, then113 // in addition its pred is set to be INVALID, and dist to 0.114 // if s was marked previuosly, then it is simply pushed.117 /// s is marked to be reached and pushed in the bfs queue. 118 /// If the queue is empty, then the first outedge is processed. 119 /// If s was not marked previously, then 120 /// in addition its pred is set to be INVALID, and dist to 0. 121 /// if s was marked previuosly, then it is simply pushed. 115 122 void push(Node s) { 116 123 if (this>reached[s]) { … … 122 129 } 123 130 } 131 /// A bfs is processed from s. 124 132 void run(Node s) { 125 133 push(s); … … 201 209 }; 202 210 211 /// Dfs searches from s for the nodes wich are not marked in 212 /// \c reached_map 213 /// Reached is a readwrite boolmap, Pred is a writenodemap, have to be. 214 template <typename Graph, 215 typename ReachedMap=typename Graph::template NodeMap<bool>, 216 typename PredMap 217 =typename Graph::template NodeMap<typename Graph::Edge> > 218 class Dfs : public DfsIterator<Graph, ReachedMap> { 219 typedef DfsIterator<Graph, ReachedMap> Parent; 220 protected: 221 typedef typename Parent::Node Node; 222 PredMap& pred; 223 public: 224 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { } 225 /// s is marked to be reached and pushed in the bfs queue. 226 /// If the queue is empty, then the first outedge is processed. 227 /// If s was not marked previously, then 228 /// in addition its pred is set to be INVALID. 229 /// if s was marked previuosly, then it is simply pushed. 230 void push(Node s) { 231 if (this>reached[s]) { 232 Parent::pushAndSetReached(s); 233 } else { 234 Parent::pushAndSetReached(s); 235 pred.set(s, INVALID); 236 } 237 } 238 /// A bfs is processed from s. 239 void run(Node s) { 240 push(s); 241 while (!this>finished()) this>operator++(); 242 } 243 Dfs<Graph, ReachedMap, PredMap> operator++() { 244 Parent::operator++(); 245 if (this>graph>valid(this>actual_edge) && this>b_node_newly_reached) 246 { 247 pred.set(this>bNode(), this>actual_edge); 248 } 249 return *this; 250 } 251 const PredMap& getPredMap() const { return pred; } 252 }; 253 254 203 255 } // namespace hugo 204 256
Note: See TracChangeset
for help on using the changeset viewer.