26 own_reached_map(false) { } |
26 own_reached_map(false) { } |
27 BfsIterator(const Graph& _graph) : |
27 BfsIterator(const Graph& _graph) : |
28 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
28 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
29 own_reached_map(true) { } |
29 own_reached_map(true) { } |
30 ~BfsIterator() { if (own_reached_map) delete &reached; } |
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 void pushAndSetReached(Node s) { |
34 void pushAndSetReached(Node s) { |
32 reached.set(s, true); |
35 reached.set(s, true); |
33 if (bfs_queue.empty()) { |
36 if (bfs_queue.empty()) { |
34 bfs_queue.push(s); |
37 bfs_queue.push(s); |
35 graph->first(actual_edge, s); |
38 graph->first(actual_edge, s); |
78 } |
81 } |
79 } |
82 } |
80 return *this; |
83 return *this; |
81 } |
84 } |
82 bool finished() const { return bfs_queue.empty(); } |
85 bool finished() const { return bfs_queue.empty(); } |
83 operator OutEdgeIt () const { return actual_edge; } |
86 operator OutEdgeIt() const { return actual_edge; } |
84 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
87 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
85 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
88 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
86 Node aNode() const { return bfs_queue.front(); } |
89 Node aNode() const { return bfs_queue.front(); } |
87 Node bNode() const { return graph->bNode(actual_edge); } |
90 Node bNode() const { return graph->bNode(actual_edge); } |
88 const ReachedMap& getReachedMap() const { return reached; } |
91 const ReachedMap& getReachedMap() const { return reached; } |
89 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
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 template <typename Graph, /*typename OutEdgeIt,*/ |
140 template <typename Graph, /*typename OutEdgeIt,*/ |
93 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
141 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
94 class DfsIterator { |
142 class DfsIterator { |
95 protected: |
143 protected: |
140 dfs_stack.pop(); |
188 dfs_stack.pop(); |
141 } |
189 } |
142 return *this; |
190 return *this; |
143 } |
191 } |
144 bool finished() const { return dfs_stack.empty(); } |
192 bool finished() const { return dfs_stack.empty(); } |
145 operator OutEdgeIt () const { return actual_edge; } |
193 operator OutEdgeIt() const { return actual_edge; } |
146 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
194 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
147 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
195 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
148 Node aNode() const { return actual_node; /*FIXME*/} |
196 Node aNode() const { return actual_node; /*FIXME*/} |
149 Node bNode() const { return graph->bNode(actual_edge); } |
197 Node bNode() const { return graph->bNode(actual_edge); } |
150 const ReachedMap& getReachedMap() const { return reached; } |
198 const ReachedMap& getReachedMap() const { return reached; } |