Changeset 409:7ab7f083760a in lemon-0.x for src/work/marci/bfs_iterator.h
- Timestamp:
- 04/26/04 11:54:24 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@542
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/bfs_iterator.h
r389 r409 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 34 void pushAndSetReached(Node s) { 32 35 reached.set(s, true); … … 81 84 } 82 85 bool finished() const { return bfs_queue.empty(); } 83 operator OutEdgeIt 86 operator OutEdgeIt() const { return actual_edge; } 84 87 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 85 88 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } … … 89 92 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } 90 93 }; 94 95 /// Bfs searches from s for the nodes wich are not marked in 96 /// reachedmap 97 template <typename Graph, 98 typename ReachedMap=typename Graph::template NodeMap<bool>, 99 typename PredMap 100 =typename Graph::template NodeMap<typename Graph::Edge>, 101 typename DistMap=typename Graph::template NodeMap<int> > 102 class Bfs : public BfsIterator<Graph, ReachedMap> { 103 typedef BfsIterator<Graph, ReachedMap> Parent; 104 protected: 105 typedef typename Parent::Node Node; 106 PredMap& pred; 107 DistMap& dist; 108 public: 109 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 out-edge is processed 112 //If s was not marked previously, then 113 //in addition its pred is set to be INVALID, and dist to 0. 114 //if s was marked previuosly, then it is simply pushed. 115 void push(Node s) { 116 if (this->reached[s]) { 117 Parent::pushAndSetReached(s); 118 } else { 119 Parent::pushAndSetReached(s); 120 pred.set(s, INVALID); 121 dist.set(s, 0); 122 } 123 } 124 void run(Node s) { 125 push(s); 126 while (!this->finished()) this->operator++(); 127 } 128 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { 129 Parent::operator++(); 130 if (this->graph->valid(actual_edge) && this->b_node_newly_reached) { 131 pred.set(s, actual_edge); 132 dist.set(s, dist[this->aNode()]); 133 } 134 return *this; 135 } 136 const PredMap& getPredMap() const { return pred; } 137 const DistMap& getDistMap() const { return dist; } 138 }; 91 139 92 140 template <typename Graph, /*typename OutEdgeIt,*/ … … 143 191 } 144 192 bool finished() const { return dfs_stack.empty(); } 145 operator OutEdgeIt 193 operator OutEdgeIt() const { return actual_edge; } 146 194 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 147 195 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
Note: See TracChangeset
for help on using the changeset viewer.