lemon-0.x: src/work/bfs_iterator.h@5cec393baade

     1 // -*- c++ -*-

     2 #ifndef BFS_ITERATOR_H

     3 #define BFS_ITERATOR_H

     5 #include <queue>

     6 #include <stack>

     7 #include <utility>

     8 #include <graph_wrapper.h>

    10 namespace hugo {

    12   template <typename Graph>

    13   struct bfs {

    14     typedef typename Graph::Node Node;

    15     typedef typename Graph::Edge Edge;

    16     typedef typename Graph::NodeIt NodeIt;

    17     typedef typename Graph::OutEdgeIt OutEdgeIt;

    18     Graph& G;

    19     Node s;

    20     typename Graph::NodeMap<bool> reached;

    21     typename Graph::NodeMap<Edge> pred;

    22     typename Graph::NodeMap<int> dist;

    23     std::queue<Node> bfs_queue;

    24     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {

    25       bfs_queue.push(s);

    26       for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)

    27 	reached.set(i, false);

    28       reached.set(s, true);

    29       dist.set(s, 0);

    30     }

    32     void run() {

    33       while (!bfs_queue.empty()) {

    34 	Node v=bfs_queue.front();

    35 	OutEdgeIt e=G.template first<OutEdgeIt>(v);

    36 	bfs_queue.pop();

    37 	for( ; e.valid(); ++e) {

    38 	  Node w=G.bNode(e);

    39 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;

    40 	  if (!reached.get(w)) {

    41 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;

    42 	    bfs_queue.push(w);

    43 	    dist.set(w, dist.get(v)+1);

    44 	    pred.set(w, e);

    45 	    reached.set(w, true);

    46 	  } else {

    47 	    std::cout << G.id(w) << " is already reached" << std::endl;

    48 	  }

    49 	}

    50       }

    51     }

    52   };

    54 //   template <typename Graph>

    55 //   struct bfs_visitor {

    56 //     typedef typename Graph::Node Node;

    57 //     typedef typename Graph::Edge Edge;

    58 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

    59 //     Graph& G;

    60 //     bfs_visitor(Graph& _G) : G(_G) { }

    61 //     void at_previously_reached(OutEdgeIt& e) {

    62 //       //Node v=G.aNode(e);

    63 //       Node w=G.bNode(e);

    64 //       std::cout << G.id(w) << " is already reached" << std::endl;

    65 //    }

    66 //     void at_newly_reached(OutEdgeIt& e) {

    67 //       //Node v=G.aNode(e);

    68 //       Node w=G.bNode(e);

    69 //       std::cout << G.id(w) << " is newly reached :-)" << std::endl;

    70 //     }

    71 //   };

    73 //   template <typename Graph, typename ReachedMap, typename visitor_type>

    74 //   struct bfs_iterator {

    75 //     typedef typename Graph::Node Node;

    76 //     typedef typename Graph::Edge Edge;

    77 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

    78 //     Graph& G;

    79 //     std::queue<OutEdgeIt>& bfs_queue;

    80 //     ReachedMap& reached;

    81 //     visitor_type& visitor;

    82 //     void process() {

    83 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

    84 //       if (bfs_queue.empty()) return;

    85 //       OutEdgeIt e=bfs_queue.front();

    86 //       //Node v=G.aNode(e);

    87 //       Node w=G.bNode(e);

    88 //       if (!reached.get(w)) {

    89 // 	visitor.at_newly_reached(e);

    90 // 	bfs_queue.push(G.template first<OutEdgeIt>(w));

    91 // 	reached.set(w, true);

    92 //       } else {

    93 // 	visitor.at_previously_reached(e);

    94 //       }

    95 //     }

    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) {

    97 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

    98 //       valid();

    99 //     }

   100 //     bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {

   101 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   102 //       //if (bfs_queue.empty()) return *this;

   103 //       if (!valid()) return *this;

   104 //       ++(bfs_queue.front());

   105 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   106 //       valid();

   107 //       return *this;

   108 //     }

   109 //     //void next() {

   110 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   111 //     //  if (bfs_queue.empty()) return;

   112 //     //  ++(bfs_queue.front());

   113 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   114 //     //}

   115 //     bool valid() {

   116 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   117 //       if (bfs_queue.empty()) return false; else return true;

   118 //     }

   119 //     //bool finished() {

   120 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   121 //     //  if (bfs_queue.empty()) return true; else return false;

   122 //     //}

   123 //     operator Edge () { return bfs_queue.front(); }

   125 //   };

   127 //   template <typename Graph, typename ReachedMap>

   128 //   struct bfs_iterator1 {

   129 //     typedef typename Graph::Node Node;

   130 //     typedef typename Graph::Edge Edge;

   131 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   132 //     Graph& G;

   133 //     std::queue<OutEdgeIt>& bfs_queue;

   134 //     ReachedMap& reached;

   135 //     bool _newly_reached;

   136 //     bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   137 //       valid();

   138 //       if (!bfs_queue.empty() && bfs_queue.front().valid()) {

   139 // 	OutEdgeIt e=bfs_queue.front();

   140 // 	Node w=G.bNode(e);

   141 // 	if (!reached.get(w)) {

   142 // 	  bfs_queue.push(G.template first<OutEdgeIt>(w));

   143 // 	  reached.set(w, true);

   144 // 	  _newly_reached=true;

   145 // 	} else {

   146 // 	  _newly_reached=false;

   147 // 	}

   148 //       }

   149 //     }

   150 //     bfs_iterator1<Graph, ReachedMap>& operator++() {

   151 //       if (!valid()) return *this;

   152 //       ++(bfs_queue.front());

   153 //       valid();

   154 //       if (!bfs_queue.empty() && bfs_queue.front().valid()) {

   155 // 	OutEdgeIt e=bfs_queue.front();

   156 // 	Node w=G.bNode(e);

   157 // 	if (!reached.get(w)) {

   158 // 	  bfs_queue.push(G.template first<OutEdgeIt>(w));

   159 // 	  reached.set(w, true);

   160 // 	  _newly_reached=true;

   161 // 	} else {

   162 // 	  _newly_reached=false;

   163 // 	}

   164 //       }

   165 //       return *this;

   166 //     }

   167 //     bool valid() {

   168 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   169 //       if (bfs_queue.empty()) return false; else return true;

   170 //     }

   171 //     operator OutEdgeIt() { return bfs_queue.front(); }

   172 //     //ize

   173 //     bool newly_reached() { return _newly_reached; }

   175 //   };

   177 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   178 //   struct BfsIterator {

   179 //     typedef typename Graph::Node Node;

   180 //     Graph& G;

   181 //     std::queue<OutEdgeIt>& bfs_queue;

   182 //     ReachedMap& reached;

   183 //     bool b_node_newly_reached;

   184 //     OutEdgeIt actual_edge;

   185 //     BfsIterator(Graph& _G,

   186 // 		std::queue<OutEdgeIt>& _bfs_queue,

   187 // 		ReachedMap& _reached) :

   188 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   189 //       actual_edge=bfs_queue.front();

   190 //       if (actual_edge.valid()) {

   191 // 	Node w=G.bNode(actual_edge);

   192 // 	if (!reached.get(w)) {

   193 // 	  bfs_queue.push(G.firstOutEdge(w));

   194 // 	  reached.set(w, true);

   195 // 	  b_node_newly_reached=true;

   196 // 	} else {

   197 // 	  b_node_newly_reached=false;

   198 // 	}

   199 //       }

   200 //     }

   201 //     BfsIterator<Graph, OutEdgeIt, ReachedMap>&

   202 //     operator++() {

   203 //       if (bfs_queue.front().valid()) {

   204 // 	++(bfs_queue.front());

   205 // 	actual_edge=bfs_queue.front();

   206 // 	if (actual_edge.valid()) {

   207 // 	  Node w=G.bNode(actual_edge);

   208 // 	  if (!reached.get(w)) {

   209 // 	    bfs_queue.push(G.firstOutEdge(w));

   210 // 	    reached.set(w, true);

   211 // 	    b_node_newly_reached=true;

   212 // 	  } else {

   213 // 	    b_node_newly_reached=false;

   214 // 	  }

   215 // 	}

   216 //       } else {

   217 // 	bfs_queue.pop();

   218 // 	actual_edge=bfs_queue.front();

   219 // 	if (actual_edge.valid()) {

   220 // 	  Node w=G.bNode(actual_edge);

   221 // 	  if (!reached.get(w)) {

   222 // 	    bfs_queue.push(G.firstOutEdge(w));

   223 // 	    reached.set(w, true);

   224 // 	    b_node_newly_reached=true;

   225 // 	  } else {

   226 // 	    b_node_newly_reached=false;

   227 // 	  }

   228 // 	}

   229 //       }

   230 //       return *this;

   231 //     }

   232 //     bool finished() { return bfs_queue.empty(); }

   233 //     operator OutEdgeIt () { return actual_edge; }

   234 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   235 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }

   236 //   };

   239 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   240 //   struct DfsIterator {

   241 //     typedef typename Graph::Node Node;

   242 //     Graph& G;

   243 //     std::stack<OutEdgeIt>& bfs_queue;

   244 //     ReachedMap& reached;

   245 //     bool b_node_newly_reached;

   246 //     OutEdgeIt actual_edge;

   247 //     DfsIterator(Graph& _G,

   248 // 		std::stack<OutEdgeIt>& _bfs_queue,

   249 // 		ReachedMap& _reached) :

   250 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   251 //       actual_edge=bfs_queue.top();

   252 //       if (actual_edge.valid()) {

   253 // 	Node w=G.bNode(actual_edge);

   254 // 	if (!reached.get(w)) {

   255 // 	  bfs_queue.push(G.firstOutEdge(w));

   256 // 	  reached.set(w, true);

   257 // 	  b_node_newly_reached=true;

   258 // 	} else {

   259 // 	  ++(bfs_queue.top());

   260 // 	  b_node_newly_reached=false;

   261 // 	}

   262 //       } else {

   263 // 	bfs_queue.pop();

   264 //       }

   265 //     }

   266 //     DfsIterator<Graph, OutEdgeIt, ReachedMap>&

   267 //     operator++() {

   268 //       actual_edge=bfs_queue.top();

   269 //       if (actual_edge.valid()) {

   270 // 	Node w=G.bNode(actual_edge);

   271 // 	if (!reached.get(w)) {

   272 // 	  bfs_queue.push(G.firstOutEdge(w));

   273 // 	  reached.set(w, true);

   274 // 	  b_node_newly_reached=true;

   275 // 	} else {

   276 // 	  ++(bfs_queue.top());

   277 // 	  b_node_newly_reached=false;

   278 // 	}

   279 //       } else {

   280 // 	bfs_queue.pop();

   281 //       }

   282 //       return *this;

   283 //     }

   284 //     bool finished() { return bfs_queue.empty(); }

   285 //     operator OutEdgeIt () { return actual_edge; }

   286 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   287 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }

   288 //   };

   290 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   291 //   struct BfsIterator1 {

   292 //     typedef typename Graph::Node Node;

   293 //     Graph& G;

   294 //     std::queue<OutEdgeIt>& bfs_queue;

   295 //     ReachedMap& reached;

   296 //     bool b_node_newly_reached;

   297 //     OutEdgeIt actual_edge;

   298 //     BfsIterator1(Graph& _G,

   299 // 		std::queue<OutEdgeIt>& _bfs_queue,

   300 // 		ReachedMap& _reached) :

   301 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   302 //       actual_edge=bfs_queue.front();

   303 //       if (actual_edge.valid()) {

   304 //       	Node w=G.bNode(actual_edge);

   305 // 	if (!reached.get(w)) {

   306 // 	  bfs_queue.push(OutEdgeIt(G, w));

   307 // 	  reached.set(w, true);

   308 // 	  b_node_newly_reached=true;

   309 // 	} else {

   310 // 	  b_node_newly_reached=false;

   311 // 	}

   312 //       }

   313 //     }

   314 //     void next() {

   315 //       if (bfs_queue.front().valid()) {

   316 // 	++(bfs_queue.front());

   317 // 	actual_edge=bfs_queue.front();

   318 // 	if (actual_edge.valid()) {

   319 // 	  Node w=G.bNode(actual_edge);

   320 // 	  if (!reached.get(w)) {

   321 // 	    bfs_queue.push(OutEdgeIt(G, w));

   322 // 	    reached.set(w, true);

   323 // 	    b_node_newly_reached=true;

   324 // 	  } else {

   325 // 	    b_node_newly_reached=false;

   326 // 	  }

   327 // 	}

   328 //       } else {

   329 // 	bfs_queue.pop();

   330 // 	actual_edge=bfs_queue.front();

   331 // 	if (actual_edge.valid()) {

   332 // 	  Node w=G.bNode(actual_edge);

   333 // 	  if (!reached.get(w)) {

   334 // 	    bfs_queue.push(OutEdgeIt(G, w));

   335 // 	    reached.set(w, true);

   336 // 	    b_node_newly_reached=true;

   337 // 	  } else {

   338 // 	    b_node_newly_reached=false;

   339 // 	  }

   340 // 	}

   341 //       }

   342 //       //return *this;

   343 //     }

   344 //     bool finished() { return bfs_queue.empty(); }

   345 //     operator OutEdgeIt () { return actual_edge; }

   346 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   347 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }

   348 //   };

   351 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   352 //   struct DfsIterator1 {

   353 //     typedef typename Graph::Node Node;

   354 //     Graph& G;

   355 //     std::stack<OutEdgeIt>& bfs_queue;

   356 //     ReachedMap& reached;

   357 //     bool b_node_newly_reached;

   358 //     OutEdgeIt actual_edge;

   359 //     DfsIterator1(Graph& _G,

   360 // 		std::stack<OutEdgeIt>& _bfs_queue,

   361 // 		ReachedMap& _reached) :

   362 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   363 //       //actual_edge=bfs_queue.top();

   364 //       //if (actual_edge.valid()) {

   365 //       //	Node w=G.bNode(actual_edge);

   366 //       //if (!reached.get(w)) {

   367 //       //  bfs_queue.push(OutEdgeIt(G, w));

   368 //       //  reached.set(w, true);

   369 //       //  b_node_newly_reached=true;

   370 //       //} else {

   371 //       //  ++(bfs_queue.top());

   372 //       //  b_node_newly_reached=false;

   373 //       //}

   374 //       //} else {

   375 //       //	bfs_queue.pop();

   376 //       //}

   377 //     }

   378 //     void next() {

   379 //       actual_edge=bfs_queue.top();

   380 //       if (actual_edge.valid()) {

   381 // 	Node w=G.bNode(actual_edge);

   382 // 	if (!reached.get(w)) {

   383 // 	  bfs_queue.push(OutEdgeIt(G, w));

   384 // 	  reached.set(w, true);

   385 // 	  b_node_newly_reached=true;

   386 // 	} else {

   387 // 	  ++(bfs_queue.top());

   388 // 	  b_node_newly_reached=false;

   389 // 	}

   390 //       } else {

   391 // 	bfs_queue.pop();

   392 //       }

   393 //       //return *this;

   394 //     }

   395 //     bool finished() { return bfs_queue.empty(); }

   396 //     operator OutEdgeIt () { return actual_edge; }

   397 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   398 //     bool aNodeIsLeaved() { return !(actual_edge.valid()); }

   399 //   };

   401 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   402 //   class BfsIterator2 {

   403 //     typedef typename Graph::Node Node;

   404 //     const Graph& G;

   405 //     std::queue<OutEdgeIt> bfs_queue;

   406 //     ReachedMap reached;

   407 //     bool b_node_newly_reached;

   408 //     OutEdgeIt actual_edge;

   409 //   public:

   410 //     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }

   411 //     void pushAndSetReached(Node s) {

   412 //       reached.set(s, true);

   413 //       if (bfs_queue.empty()) {

   414 // 	bfs_queue.push(G.template first<OutEdgeIt>(s));

   415 // 	actual_edge=bfs_queue.front();

   416 // 	if (actual_edge.valid()) {

   417 // 	  Node w=G.bNode(actual_edge);

   418 // 	  if (!reached.get(w)) {

   419 // 	    bfs_queue.push(G.template first<OutEdgeIt>(w));

   420 // 	    reached.set(w, true);

   421 // 	    b_node_newly_reached=true;

   422 // 	  } else {

   423 // 	    b_node_newly_reached=false;

   424 // 	  }

   425 // 	} //else {

   426 // 	//}

   427 //       } else {

   428 // 	bfs_queue.push(G.template first<OutEdgeIt>(s));

   429 //       }

   430 //     }

   431 //     BfsIterator2<Graph, OutEdgeIt, ReachedMap>&

   432 //     operator++() {

   433 //       if (bfs_queue.front().valid()) {

   434 // 	++(bfs_queue.front());

   435 // 	actual_edge=bfs_queue.front();

   436 // 	if (actual_edge.valid()) {

   437 // 	  Node w=G.bNode(actual_edge);

   438 // 	  if (!reached.get(w)) {

   439 // 	    bfs_queue.push(G.template first<OutEdgeIt>(w));

   440 // 	    reached.set(w, true);

   441 // 	    b_node_newly_reached=true;

   442 // 	  } else {

   443 // 	    b_node_newly_reached=false;

   444 // 	  }

   445 // 	}

   446 //       } else {

   447 // 	bfs_queue.pop();

   448 // 	if (!bfs_queue.empty()) {

   449 // 	  actual_edge=bfs_queue.front();

   450 // 	  if (actual_edge.valid()) {

   451 // 	    Node w=G.bNode(actual_edge);

   452 // 	    if (!reached.get(w)) {

   453 // 	      bfs_queue.push(G.template first<OutEdgeIt>(w));

   454 // 	      reached.set(w, true);

   455 // 	      b_node_newly_reached=true;

   456 // 	    } else {

   457 // 	      b_node_newly_reached=false;

   458 // 	    }

   459 // 	  }

   460 // 	}

   461 //       }

   462 //       return *this;

   463 //     }

   464 //     bool finished() const { return bfs_queue.empty(); }

   465 //     operator OutEdgeIt () const { return actual_edge; }

   466 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   467 //     bool isANodeExamined() const { return !(actual_edge.valid()); }

   468 //     const ReachedMap& getReachedMap() const { return reached; }

   469 //     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }

   470 //  };

   473 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   474 //   class BfsIterator3 {

   475 //     typedef typename Graph::Node Node;

   476 //     const Graph& G;

   477 //     std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;

   478 //     ReachedMap reached;

   479 //     bool b_node_newly_reached;

   480 //     OutEdgeIt actual_edge;

   481 //   public:

   482 //     BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }

   483 //     void pushAndSetReached(Node s) {

   484 //       reached.set(s, true);

   485 //       if (bfs_queue.empty()) {

   486 // 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));

   487 // 	actual_edge=bfs_queue.front().second;

   488 // 	if (actual_edge.valid()) {

   489 // 	  Node w=G.bNode(actual_edge);

   490 // 	  if (!reached.get(w)) {

   491 // 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));

   492 // 	    reached.set(w, true);

   493 // 	    b_node_newly_reached=true;

   494 // 	  } else {

   495 // 	    b_node_newly_reached=false;

   496 // 	  }

   497 // 	} //else {

   498 // 	//}

   499 //       } else {

   500 // 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));

   501 //       }

   502 //     }

   503 //     BfsIterator3<Graph, OutEdgeIt, ReachedMap>&

   504 //     operator++() {

   505 //       if (bfs_queue.front().second.valid()) {

   506 // 	++(bfs_queue.front().second);

   507 // 	actual_edge=bfs_queue.front().second;

   508 // 	if (actual_edge.valid()) {

   509 // 	  Node w=G.bNode(actual_edge);

   510 // 	  if (!reached.get(w)) {

   511 // 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));

   512 // 	    reached.set(w, true);

   513 // 	    b_node_newly_reached=true;

   514 // 	  } else {

   515 // 	    b_node_newly_reached=false;

   516 // 	  }

   517 // 	}

   518 //       } else {

   519 // 	bfs_queue.pop();

   520 // 	if (!bfs_queue.empty()) {

   521 // 	  actual_edge=bfs_queue.front().second;

   522 // 	  if (actual_edge.valid()) {

   523 // 	    Node w=G.bNode(actual_edge);

   524 // 	    if (!reached.get(w)) {

   525 // 	      bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));

   526 // 	      reached.set(w, true);

   527 // 	      b_node_newly_reached=true;

   528 // 	    } else {

   529 // 	      b_node_newly_reached=false;

   530 // 	    }

   531 // 	  }

   532 // 	}

   533 //       }

   534 //       return *this;

   535 //     }

   536 //     bool finished() const { return bfs_queue.empty(); }

   537 //     operator OutEdgeIt () const { return actual_edge; }

   538 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   539 //     bool isANodeExamined() const { return !(actual_edge.valid()); }

   540 //     Node aNode() const { return bfs_queue.front().first; }

   541 //     Node bNode() const { return G.bNode(actual_edge); }

   542 //     const ReachedMap& getReachedMap() const { return reached; }

   543 //     //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }

   544 //  };

   547   template <typename Graph, typename OutEdgeIt,

   548 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   549   class BfsIterator4 {

   550     typedef typename Graph::Node Node;

   551     const Graph& G;

   552     std::queue<Node> bfs_queue;

   553     ReachedMap& reached;

   554     bool b_node_newly_reached;

   555     OutEdgeIt actual_edge;

   556     bool own_reached_map;

   557   public:

   558     BfsIterator4(const Graph& _G, ReachedMap& _reached) :

   559       G(_G), reached(_reached),

   560       own_reached_map(false) { }

   561     BfsIterator4(const Graph& _G) :

   562       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   563       own_reached_map(true) { }

   564     ~BfsIterator4() { if (own_reached_map) delete &reached; }

   565     void pushAndSetReached(Node s) {

   566       //std::cout << "mimi" << &reached << std::endl;

   567       reached.set(s, true);

   568       //std::cout << "mumus" << std::endl;

   569       if (bfs_queue.empty()) {

   570 	//std::cout << "bibi1" << std::endl;

   571 	bfs_queue.push(s);

   572 	//std::cout << "zizi" << std::endl;

   573 	G./*getF*/first(actual_edge, s);

   574 	//std::cout << "kiki" << std::endl;

   575 	if (G.valid(actual_edge)/*.valid()*/) {

   576 	  Node w=G.bNode(actual_edge);

   577 	  if (!reached.get(w)) {

   578 	    bfs_queue.push(w);

   579 	    reached.set(w, true);

   580 	    b_node_newly_reached=true;

   581 	  } else {

   582 	    b_node_newly_reached=false;

   583 	  }

   584 	}

   585       } else {

   586 	//std::cout << "bibi2" << std::endl;

   587 	bfs_queue.push(s);

   588       }

   589     }

   590     BfsIterator4<Graph, OutEdgeIt, ReachedMap>&

   591     operator++() {

   592       if (G.valid(actual_edge)/*.valid()*/) {

   593 	/*++*/G.next(actual_edge);

   594 	if (G.valid(actual_edge)/*.valid()*/) {

   595 	  Node w=G.bNode(actual_edge);

   596 	  if (!reached.get(w)) {

   597 	    bfs_queue.push(w);

   598 	    reached.set(w, true);

   599 	    b_node_newly_reached=true;

   600 	  } else {

   601 	    b_node_newly_reached=false;

   602 	  }

   603 	}

   604       } else {

   605 	bfs_queue.pop();

   606 	if (!bfs_queue.empty()) {

   607 	  G./*getF*/first(actual_edge, bfs_queue.front());

   608 	  if (G.valid(actual_edge)/*.valid()*/) {

   609 	    Node w=G.bNode(actual_edge);

   610 	    if (!reached.get(w)) {

   611 	      bfs_queue.push(w);

   612 	      reached.set(w, true);

   613 	      b_node_newly_reached=true;

   614 	    } else {

   615 	      b_node_newly_reached=false;

   616 	    }

   617 	  }

   618 	}

   619       }

   620       return *this;

   621     }

   622     bool finished() const { return bfs_queue.empty(); }

   623     operator OutEdgeIt () const { return actual_edge; }

   624     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   625     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }

   626     Node aNode() const { return bfs_queue.front(); }

   627     Node bNode() const { return G.bNode(actual_edge); }

   628     const ReachedMap& getReachedMap() const { return reached; }

   629     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }

   630  };

   633   template <typename GraphWrapper, /*typename OutEdgeIt,*/

   634 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >

   635   class BfsIterator5 {

   636     typedef typename GraphWrapper::Node Node;

   637     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   638     GraphWrapper G;

   639     std::queue<Node> bfs_queue;

   640     ReachedMap& reached;

   641     bool b_node_newly_reached;

   642     OutEdgeIt actual_edge;

   643     bool own_reached_map;

   644   public:

   645     BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :

   646       G(_G), reached(_reached),

   647       own_reached_map(false) { }

   648     BfsIterator5(const GraphWrapper& _G) :

   649       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   650       own_reached_map(true) { }

   651 //     BfsIterator5(const typename GraphWrapper::BaseGraph& _G,

   652 // 		 ReachedMap& _reached) :

   653 //       G(_G), reached(_reached),

   654 //       own_reached_map(false) { }

   655 //     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :

   656 //       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   657 //       own_reached_map(true) { }

   658     ~BfsIterator5() { if (own_reached_map) delete &reached; }

   659     void pushAndSetReached(Node s) {

   660       reached.set(s, true);

   661       if (bfs_queue.empty()) {

   662 	bfs_queue.push(s);

   663 	G./*getF*/first(actual_edge, s);

   664 	if (G.valid(actual_edge)/*.valid()*/) {

   665 	  Node w=G.bNode(actual_edge);

   666 	  if (!reached.get(w)) {

   667 	    bfs_queue.push(w);

   668 	    reached.set(w, true);

   669 	    b_node_newly_reached=true;

   670 	  } else {

   671 	    b_node_newly_reached=false;

   672 	  }

   673 	}

   674       } else {

   675 	bfs_queue.push(s);

   676       }

   677     }

   678     BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&

   679     operator++() {

   680       if (G.valid(actual_edge)/*.valid()*/) {

   681 	/*++*/G.next(actual_edge);

   682 	if (G.valid(actual_edge)/*.valid()*/) {

   683 	  Node w=G.bNode(actual_edge);

   684 	  if (!reached.get(w)) {

   685 	    bfs_queue.push(w);

   686 	    reached.set(w, true);

   687 	    b_node_newly_reached=true;

   688 	  } else {

   689 	    b_node_newly_reached=false;

   690 	  }

   691 	}

   692       } else {

   693 	bfs_queue.pop();

   694 	if (!bfs_queue.empty()) {

   695 	  G./*getF*/first(actual_edge, bfs_queue.front());

   696 	  if (G.valid(actual_edge)/*.valid()*/) {

   697 	    Node w=G.bNode(actual_edge);

   698 	    if (!reached.get(w)) {

   699 	      bfs_queue.push(w);

   700 	      reached.set(w, true);

   701 	      b_node_newly_reached=true;

   702 	    } else {

   703 	      b_node_newly_reached=false;

   704 	    }

   705 	  }

   706 	}

   707       }

   708       return *this;

   709     }

   710     bool finished() const { return bfs_queue.empty(); }

   711     operator OutEdgeIt () const { return actual_edge; }

   712     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   713     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }

   714     Node aNode() const { return bfs_queue.front(); }

   715     Node bNode() const { return G.bNode(actual_edge); }

   716     const ReachedMap& getReachedMap() const { return reached; }

   717     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }

   718   };

   720   template <typename Graph, typename OutEdgeIt,

   721 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   722   class DfsIterator4 {

   723     typedef typename Graph::Node Node;

   724     const Graph& G;

   725     std::stack<OutEdgeIt> dfs_stack;

   726     bool b_node_newly_reached;

   727     OutEdgeIt actual_edge;

   728     Node actual_node;

   729     ReachedMap& reached;

   730     bool own_reached_map;

   731   public:

   732     DfsIterator4(const Graph& _G, ReachedMap& _reached) :

   733       G(_G), reached(_reached),

   734       own_reached_map(false) { }

   735     DfsIterator4(const Graph& _G) :

   736       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   737       own_reached_map(true) { }

   738     ~DfsIterator4() { if (own_reached_map) delete &reached; }

   739     void pushAndSetReached(Node s) {

   740       actual_node=s;

   741       reached.set(s, true);

   742       dfs_stack.push(G.template first<OutEdgeIt>(s));

   743     }

   744     DfsIterator4<Graph, OutEdgeIt, ReachedMap>&

   745     operator++() {

   746       actual_edge=dfs_stack.top();

   747       //actual_node=G.aNode(actual_edge);

   748       if (G.valid(actual_edge)/*.valid()*/) {

   749 	Node w=G.bNode(actual_edge);

   750 	actual_node=w;

   751 	if (!reached.get(w)) {

   752 	  dfs_stack.push(G.template first<OutEdgeIt>(w));

   753 	  reached.set(w, true);

   754 	  b_node_newly_reached=true;

   755 	} else {

   756 	  actual_node=G.aNode(actual_edge);

   757 	  /*++*/G.next(dfs_stack.top());

   758 	  b_node_newly_reached=false;

   759 	}

   760       } else {

   761 	//actual_node=G.aNode(dfs_stack.top());

   762 	dfs_stack.pop();

   763       }

   764       return *this;

   765     }

   766     bool finished() const { return dfs_stack.empty(); }

   767     operator OutEdgeIt () const { return actual_edge; }

   768     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   769     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }

   770     Node aNode() const { return actual_node; /*FIXME*/}

   771     Node bNode() const { return G.bNode(actual_edge); }

   772     const ReachedMap& getReachedMap() const { return reached; }

   773     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }

   774   };

   776   template <typename GraphWrapper, /*typename OutEdgeIt,*/

   777 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >

   778   class DfsIterator5 {

   779     typedef typename GraphWrapper::Node Node;

   780     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   781     GraphWrapper G;

   782     std::stack<OutEdgeIt> dfs_stack;

   783     bool b_node_newly_reached;

   784     OutEdgeIt actual_edge;

   785     Node actual_node;

   786     ReachedMap& reached;

   787     bool own_reached_map;

   788   public:

   789     DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :

   790       G(_G), reached(_reached),

   791       own_reached_map(false) { }

   792     DfsIterator5(const GraphWrapper& _G) :

   793       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   794       own_reached_map(true) { }

   795     ~DfsIterator5() { if (own_reached_map) delete &reached; }

   796     void pushAndSetReached(Node s) {

   797       actual_node=s;

   798       reached.set(s, true);

   799       dfs_stack.push(G.template first<OutEdgeIt>(s));

   800     }

   801     DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&

   802     operator++() {

   803       actual_edge=dfs_stack.top();

   804       //actual_node=G.aNode(actual_edge);

   805       if (G.valid(actual_edge)/*.valid()*/) {

   806 	Node w=G.bNode(actual_edge);

   807 	actual_node=w;

   808 	if (!reached.get(w)) {

   809 	  dfs_stack.push(G.template first<OutEdgeIt>(w));

   810 	  reached.set(w, true);

   811 	  b_node_newly_reached=true;

   812 	} else {

   813 	  actual_node=G.aNode(actual_edge);

   814 	  /*++*/G.next(dfs_stack.top());

   815 	  b_node_newly_reached=false;

   816 	}

   817       } else {

   818 	//actual_node=G.aNode(dfs_stack.top());

   819 	dfs_stack.pop();

   820       }

   821       return *this;

   822     }

   823     bool finished() const { return dfs_stack.empty(); }

   824     operator OutEdgeIt () const { return actual_edge; }

   825     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   826     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }

   827     Node aNode() const { return actual_node; /*FIXME*/}

   828     Node bNode() const { return G.bNode(actual_edge); }

   829     const ReachedMap& getReachedMap() const { return reached; }

   830     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }

   831   };

   835 } // namespace hugo

   837 #endif //BFS_ITERATOR_H

author	marci
	Wed, 17 Mar 2004 18:18:26 +0000
changeset 198	5cec393baade
child 243	a85fd87460e3
permissions	-rw-r--r--