1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/bfs_iterator.hh Fri Jan 30 14:48:06 2004 +0000
1.3 @@ -0,0 +1,400 @@
1.4 +#ifndef MARCI_BFS_HH
1.5 +#define MARCI_BFS_HH
1.6 +
1.7 +#include <queue>
1.8 +#include <stack>
1.9 +
1.10 +namespace marci {
1.11 +
1.12 + template <typename Graph>
1.13 + struct bfs {
1.14 + typedef typename Graph::NodeIt NodeIt;
1.15 + typedef typename Graph::EdgeIt EdgeIt;
1.16 + typedef typename Graph::EachNodeIt EachNodeIt;
1.17 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.18 + Graph& G;
1.19 + NodeIt s;
1.20 + typename Graph::NodeMap<bool> reached;
1.21 + typename Graph::NodeMap<EdgeIt> pred;
1.22 + typename Graph::NodeMap<int> dist;
1.23 + std::queue<NodeIt> bfs_queue;
1.24 + bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.25 + bfs_queue.push(s);
1.26 + for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
1.27 + reached.set(i, false);
1.28 + reached.set(s, true);
1.29 + dist.set(s, 0);
1.30 + }
1.31 +
1.32 + void run() {
1.33 + while (!bfs_queue.empty()) {
1.34 + NodeIt v=bfs_queue.front();
1.35 + OutEdgeIt e=G.template first<OutEdgeIt>(v);
1.36 + bfs_queue.pop();
1.37 + for( ; e.valid(); ++e) {
1.38 + NodeIt w=G.bNode(e);
1.39 + std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.40 + if (!reached.get(w)) {
1.41 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.42 + bfs_queue.push(w);
1.43 + dist.set(w, dist.get(v)+1);
1.44 + pred.set(w, e);
1.45 + reached.set(w, true);
1.46 + } else {
1.47 + std::cout << G.id(w) << " is already reached" << std::endl;
1.48 + }
1.49 + }
1.50 + }
1.51 + }
1.52 + };
1.53 +
1.54 + template <typename Graph>
1.55 + struct bfs_visitor {
1.56 + typedef typename Graph::NodeIt NodeIt;
1.57 + typedef typename Graph::EdgeIt EdgeIt;
1.58 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.59 + Graph& G;
1.60 + bfs_visitor(Graph& _G) : G(_G) { }
1.61 + void at_previously_reached(OutEdgeIt& e) {
1.62 + //NodeIt v=G.aNode(e);
1.63 + NodeIt w=G.bNode(e);
1.64 + std::cout << G.id(w) << " is already reached" << std::endl;
1.65 + }
1.66 + void at_newly_reached(OutEdgeIt& e) {
1.67 + //NodeIt v=G.aNode(e);
1.68 + NodeIt w=G.bNode(e);
1.69 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.70 + }
1.71 + };
1.72 +
1.73 + template <typename Graph, typename ReachedMap, typename visitor_type>
1.74 + struct bfs_iterator {
1.75 + typedef typename Graph::NodeIt NodeIt;
1.76 + typedef typename Graph::EdgeIt EdgeIt;
1.77 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.78 + Graph& G;
1.79 + std::queue<OutEdgeIt>& bfs_queue;
1.80 + ReachedMap& reached;
1.81 + visitor_type& visitor;
1.82 + void process() {
1.83 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.84 + if (bfs_queue.empty()) return;
1.85 + OutEdgeIt e=bfs_queue.front();
1.86 + //NodeIt v=G.aNode(e);
1.87 + NodeIt w=G.bNode(e);
1.88 + if (!reached.get(w)) {
1.89 + visitor.at_newly_reached(e);
1.90 + bfs_queue.push(G.template first<OutEdgeIt>(w));
1.91 + reached.set(w, true);
1.92 + } else {
1.93 + visitor.at_previously_reached(e);
1.94 + }
1.95 + }
1.96 + bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
1.97 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.98 + valid();
1.99 + }
1.100 + bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
1.101 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.102 + //if (bfs_queue.empty()) return *this;
1.103 + if (!valid()) return *this;
1.104 + ++(bfs_queue.front());
1.105 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.106 + valid();
1.107 + return *this;
1.108 + }
1.109 + //void next() {
1.110 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.111 + // if (bfs_queue.empty()) return;
1.112 + // ++(bfs_queue.front());
1.113 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.114 + //}
1.115 + bool valid() {
1.116 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.117 + if (bfs_queue.empty()) return false; else return true;
1.118 + }
1.119 + //bool finished() {
1.120 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.121 + // if (bfs_queue.empty()) return true; else return false;
1.122 + //}
1.123 + operator EdgeIt () { return bfs_queue.front(); }
1.124 +
1.125 + };
1.126 +
1.127 + template <typename Graph, typename ReachedMap>
1.128 + struct bfs_iterator1 {
1.129 + typedef typename Graph::NodeIt NodeIt;
1.130 + typedef typename Graph::EdgeIt EdgeIt;
1.131 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.132 + Graph& G;
1.133 + std::queue<OutEdgeIt>& bfs_queue;
1.134 + ReachedMap& reached;
1.135 + bool _newly_reached;
1.136 + bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.137 + valid();
1.138 + if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.139 + OutEdgeIt e=bfs_queue.front();
1.140 + NodeIt w=G.bNode(e);
1.141 + if (!reached.get(w)) {
1.142 + bfs_queue.push(G.template first<OutEdgeIt>(w));
1.143 + reached.set(w, true);
1.144 + _newly_reached=true;
1.145 + } else {
1.146 + _newly_reached=false;
1.147 + }
1.148 + }
1.149 + }
1.150 + bfs_iterator1<Graph, ReachedMap>& operator++() {
1.151 + if (!valid()) return *this;
1.152 + ++(bfs_queue.front());
1.153 + valid();
1.154 + if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.155 + OutEdgeIt e=bfs_queue.front();
1.156 + NodeIt w=G.bNode(e);
1.157 + if (!reached.get(w)) {
1.158 + bfs_queue.push(G.template first<OutEdgeIt>(w));
1.159 + reached.set(w, true);
1.160 + _newly_reached=true;
1.161 + } else {
1.162 + _newly_reached=false;
1.163 + }
1.164 + }
1.165 + return *this;
1.166 + }
1.167 + bool valid() {
1.168 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.169 + if (bfs_queue.empty()) return false; else return true;
1.170 + }
1.171 + operator OutEdgeIt() { return bfs_queue.front(); }
1.172 + //ize
1.173 + bool newly_reached() { return _newly_reached; }
1.174 +
1.175 + };
1.176 +
1.177 + template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.178 + struct BfsIterator {
1.179 + typedef typename Graph::NodeIt NodeIt;
1.180 + Graph& G;
1.181 + std::queue<OutEdgeIt>& bfs_queue;
1.182 + ReachedMap& reached;
1.183 + bool b_node_newly_reached;
1.184 + OutEdgeIt actual_edge;
1.185 + BfsIterator(Graph& _G,
1.186 + std::queue<OutEdgeIt>& _bfs_queue,
1.187 + ReachedMap& _reached) :
1.188 + G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.189 + actual_edge=bfs_queue.front();
1.190 + if (actual_edge.valid()) {
1.191 + NodeIt w=G.bNode(actual_edge);
1.192 + if (!reached.get(w)) {
1.193 + bfs_queue.push(G.firstOutEdge(w));
1.194 + reached.set(w, true);
1.195 + b_node_newly_reached=true;
1.196 + } else {
1.197 + b_node_newly_reached=false;
1.198 + }
1.199 + }
1.200 + }
1.201 + BfsIterator<Graph, OutEdgeIt, ReachedMap>&
1.202 + operator++() {
1.203 + if (bfs_queue.front().valid()) {
1.204 + ++(bfs_queue.front());
1.205 + actual_edge=bfs_queue.front();
1.206 + if (actual_edge.valid()) {
1.207 + NodeIt w=G.bNode(actual_edge);
1.208 + if (!reached.get(w)) {
1.209 + bfs_queue.push(G.firstOutEdge(w));
1.210 + reached.set(w, true);
1.211 + b_node_newly_reached=true;
1.212 + } else {
1.213 + b_node_newly_reached=false;
1.214 + }
1.215 + }
1.216 + } else {
1.217 + bfs_queue.pop();
1.218 + actual_edge=bfs_queue.front();
1.219 + if (actual_edge.valid()) {
1.220 + NodeIt w=G.bNode(actual_edge);
1.221 + if (!reached.get(w)) {
1.222 + bfs_queue.push(G.firstOutEdge(w));
1.223 + reached.set(w, true);
1.224 + b_node_newly_reached=true;
1.225 + } else {
1.226 + b_node_newly_reached=false;
1.227 + }
1.228 + }
1.229 + }
1.230 + return *this;
1.231 + }
1.232 + bool finished() { return bfs_queue.empty(); }
1.233 + operator OutEdgeIt () { return actual_edge; }
1.234 + bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.235 + bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.236 + };
1.237 +
1.238 +
1.239 + template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.240 + struct DfsIterator {
1.241 + typedef typename Graph::NodeIt NodeIt;
1.242 + Graph& G;
1.243 + std::stack<OutEdgeIt>& bfs_queue;
1.244 + ReachedMap& reached;
1.245 + bool b_node_newly_reached;
1.246 + OutEdgeIt actual_edge;
1.247 + DfsIterator(Graph& _G,
1.248 + std::stack<OutEdgeIt>& _bfs_queue,
1.249 + ReachedMap& _reached) :
1.250 + G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.251 + actual_edge=bfs_queue.top();
1.252 + if (actual_edge.valid()) {
1.253 + NodeIt w=G.bNode(actual_edge);
1.254 + if (!reached.get(w)) {
1.255 + bfs_queue.push(G.firstOutEdge(w));
1.256 + reached.set(w, true);
1.257 + b_node_newly_reached=true;
1.258 + } else {
1.259 + ++(bfs_queue.top());
1.260 + b_node_newly_reached=false;
1.261 + }
1.262 + } else {
1.263 + bfs_queue.pop();
1.264 + }
1.265 + }
1.266 + DfsIterator<Graph, OutEdgeIt, ReachedMap>&
1.267 + operator++() {
1.268 + actual_edge=bfs_queue.top();
1.269 + if (actual_edge.valid()) {
1.270 + NodeIt w=G.bNode(actual_edge);
1.271 + if (!reached.get(w)) {
1.272 + bfs_queue.push(G.firstOutEdge(w));
1.273 + reached.set(w, true);
1.274 + b_node_newly_reached=true;
1.275 + } else {
1.276 + ++(bfs_queue.top());
1.277 + b_node_newly_reached=false;
1.278 + }
1.279 + } else {
1.280 + bfs_queue.pop();
1.281 + }
1.282 + return *this;
1.283 + }
1.284 + bool finished() { return bfs_queue.empty(); }
1.285 + operator OutEdgeIt () { return actual_edge; }
1.286 + bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.287 + bool aNodeIsLeaved() { return !(actual_edge.valid()); }
1.288 + };
1.289 +
1.290 + template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.291 + struct BfsIterator1 {
1.292 + typedef typename Graph::NodeIt NodeIt;
1.293 + Graph& G;
1.294 + std::queue<OutEdgeIt>& bfs_queue;
1.295 + ReachedMap& reached;
1.296 + bool b_node_newly_reached;
1.297 + OutEdgeIt actual_edge;
1.298 + BfsIterator1(Graph& _G,
1.299 + std::queue<OutEdgeIt>& _bfs_queue,
1.300 + ReachedMap& _reached) :
1.301 + G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.302 + actual_edge=bfs_queue.front();
1.303 + if (actual_edge.valid()) {
1.304 + NodeIt w=G.bNode(actual_edge);
1.305 + if (!reached.get(w)) {
1.306 + bfs_queue.push(OutEdgeIt(G, w));
1.307 + reached.set(w, true);
1.308 + b_node_newly_reached=true;
1.309 + } else {
1.310 + b_node_newly_reached=false;
1.311 + }
1.312 + }
1.313 + }
1.314 + void next() {
1.315 + if (bfs_queue.front().valid()) {
1.316 + ++(bfs_queue.front());
1.317 + actual_edge=bfs_queue.front();
1.318 + if (actual_edge.valid()) {
1.319 + NodeIt w=G.bNode(actual_edge);
1.320 + if (!reached.get(w)) {
1.321 + bfs_queue.push(OutEdgeIt(G, w));
1.322 + reached.set(w, true);
1.323 + b_node_newly_reached=true;
1.324 + } else {
1.325 + b_node_newly_reached=false;
1.326 + }
1.327 + }
1.328 + } else {
1.329 + bfs_queue.pop();
1.330 + actual_edge=bfs_queue.front();
1.331 + if (actual_edge.valid()) {
1.332 + NodeIt w=G.bNode(actual_edge);
1.333 + if (!reached.get(w)) {
1.334 + bfs_queue.push(OutEdgeIt(G, w));
1.335 + reached.set(w, true);
1.336 + b_node_newly_reached=true;
1.337 + } else {
1.338 + b_node_newly_reached=false;
1.339 + }
1.340 + }
1.341 + }
1.342 + //return *this;
1.343 + }
1.344 + bool finished() { return bfs_queue.empty(); }
1.345 + operator OutEdgeIt () { return actual_edge; }
1.346 + bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.347 + bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.348 + };
1.349 +
1.350 +
1.351 + template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.352 + struct DfsIterator1 {
1.353 + typedef typename Graph::NodeIt NodeIt;
1.354 + Graph& G;
1.355 + std::stack<OutEdgeIt>& bfs_queue;
1.356 + ReachedMap& reached;
1.357 + bool b_node_newly_reached;
1.358 + OutEdgeIt actual_edge;
1.359 + DfsIterator1(Graph& _G,
1.360 + std::stack<OutEdgeIt>& _bfs_queue,
1.361 + ReachedMap& _reached) :
1.362 + G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.363 + //actual_edge=bfs_queue.top();
1.364 + //if (actual_edge.valid()) {
1.365 + // NodeIt w=G.bNode(actual_edge);
1.366 + //if (!reached.get(w)) {
1.367 + // bfs_queue.push(OutEdgeIt(G, w));
1.368 + // reached.set(w, true);
1.369 + // b_node_newly_reached=true;
1.370 + //} else {
1.371 + // ++(bfs_queue.top());
1.372 + // b_node_newly_reached=false;
1.373 + //}
1.374 + //} else {
1.375 + // bfs_queue.pop();
1.376 + //}
1.377 + }
1.378 + void next() {
1.379 + actual_edge=bfs_queue.top();
1.380 + if (actual_edge.valid()) {
1.381 + NodeIt w=G.bNode(actual_edge);
1.382 + if (!reached.get(w)) {
1.383 + bfs_queue.push(OutEdgeIt(G, w));
1.384 + reached.set(w, true);
1.385 + b_node_newly_reached=true;
1.386 + } else {
1.387 + ++(bfs_queue.top());
1.388 + b_node_newly_reached=false;
1.389 + }
1.390 + } else {
1.391 + bfs_queue.pop();
1.392 + }
1.393 + //return *this;
1.394 + }
1.395 + bool finished() { return bfs_queue.empty(); }
1.396 + operator OutEdgeIt () { return actual_edge; }
1.397 + bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.398 + bool aNodeIsLeaved() { return !(actual_edge.valid()); }
1.399 + };
1.400 +
1.401 +} // namespace marci
1.402 +
1.403 +#endif //MARCI_BFS_HH