src/work/bfs_iterator.hh
author beckerjc
Wed, 03 Mar 2004 19:14:27 +0000
changeset 149 824c0438020c
parent 144 a1323efc5753
child 158 4f54d89fa9d2
permissions -rw-r--r--
Apr?bb jav?t?sok.
     1 #ifndef BFS_ITERATOR_HH
     2 #define BFS_ITERATOR_HH
     3 
     4 #include <queue>
     5 #include <stack>
     6 #include <utility>
     7 #include <graph_wrapper.h>
     8 
     9 namespace hugo {
    10 
    11   template <typename Graph>
    12   struct bfs {
    13     typedef typename Graph::NodeIt NodeIt;
    14     typedef typename Graph::EdgeIt EdgeIt;
    15     typedef typename Graph::EachNodeIt EachNodeIt;
    16     typedef typename Graph::OutEdgeIt OutEdgeIt;
    17     Graph& G;
    18     NodeIt s;
    19     typename Graph::NodeMap<bool> reached;
    20     typename Graph::NodeMap<EdgeIt> pred;
    21     typename Graph::NodeMap<int> dist;
    22     std::queue<NodeIt> bfs_queue;
    23     bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
    24       bfs_queue.push(s); 
    25       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) 
    26 	reached.set(i, false);
    27       reached.set(s, true);
    28       dist.set(s, 0); 
    29     }
    30     
    31     void run() {
    32       while (!bfs_queue.empty()) {
    33 	NodeIt v=bfs_queue.front();
    34 	OutEdgeIt e=G.template first<OutEdgeIt>(v);
    35 	bfs_queue.pop();
    36 	for( ; e.valid(); ++e) {
    37 	  NodeIt w=G.bNode(e);
    38 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
    39 	  if (!reached.get(w)) {
    40 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
    41 	    bfs_queue.push(w);
    42 	    dist.set(w, dist.get(v)+1);
    43 	    pred.set(w, e);
    44 	    reached.set(w, true);
    45 	  } else {
    46 	    std::cout << G.id(w) << " is already reached" << std::endl;
    47 	  }
    48 	}
    49       }
    50     }
    51   };
    52 
    53   template <typename Graph> 
    54   struct bfs_visitor {
    55     typedef typename Graph::NodeIt NodeIt;
    56     typedef typename Graph::EdgeIt EdgeIt;
    57     typedef typename Graph::OutEdgeIt OutEdgeIt;
    58     Graph& G;
    59     bfs_visitor(Graph& _G) : G(_G) { }
    60     void at_previously_reached(OutEdgeIt& e) { 
    61       //NodeIt v=G.aNode(e);
    62       NodeIt w=G.bNode(e);
    63       std::cout << G.id(w) << " is already reached" << std::endl;
    64    }
    65     void at_newly_reached(OutEdgeIt& e) { 
    66       //NodeIt v=G.aNode(e);
    67       NodeIt w=G.bNode(e);
    68       std::cout << G.id(w) << " is newly reached :-)" << std::endl;
    69     }
    70   };
    71 
    72   template <typename Graph, typename ReachedMap, typename visitor_type>
    73   struct bfs_iterator {
    74     typedef typename Graph::NodeIt NodeIt;
    75     typedef typename Graph::EdgeIt EdgeIt;
    76     typedef typename Graph::OutEdgeIt OutEdgeIt;
    77     Graph& G;
    78     std::queue<OutEdgeIt>& bfs_queue;
    79     ReachedMap& reached;
    80     visitor_type& visitor;
    81     void process() {
    82       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
    83       if (bfs_queue.empty()) return;
    84       OutEdgeIt e=bfs_queue.front();
    85       //NodeIt v=G.aNode(e);
    86       NodeIt w=G.bNode(e);
    87       if (!reached.get(w)) {
    88 	visitor.at_newly_reached(e);
    89 	bfs_queue.push(G.template first<OutEdgeIt>(w));
    90 	reached.set(w, true);
    91       } else {
    92 	visitor.at_previously_reached(e);
    93       }
    94     }
    95     bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 
    96       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
    97       valid();
    98     }
    99     bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { 
   100       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   101       //if (bfs_queue.empty()) return *this;
   102       if (!valid()) return *this;
   103       ++(bfs_queue.front());
   104       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   105       valid();
   106       return *this;
   107     }
   108     //void next() { 
   109     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   110     //  if (bfs_queue.empty()) return;
   111     //  ++(bfs_queue.front());
   112     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   113     //}
   114     bool valid() { 
   115       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   116       if (bfs_queue.empty()) return false; else return true;
   117     }
   118     //bool finished() { 
   119     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   120     //  if (bfs_queue.empty()) return true; else return false;
   121     //}
   122     operator EdgeIt () { return bfs_queue.front(); }
   123 
   124   };
   125 
   126   template <typename Graph, typename ReachedMap>
   127   struct bfs_iterator1 {
   128     typedef typename Graph::NodeIt NodeIt;
   129     typedef typename Graph::EdgeIt EdgeIt;
   130     typedef typename Graph::OutEdgeIt OutEdgeIt;
   131     Graph& G;
   132     std::queue<OutEdgeIt>& bfs_queue;
   133     ReachedMap& reached;
   134     bool _newly_reached;
   135     bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   136       valid();
   137       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
   138 	OutEdgeIt e=bfs_queue.front();
   139 	NodeIt w=G.bNode(e);
   140 	if (!reached.get(w)) {
   141 	  bfs_queue.push(G.template first<OutEdgeIt>(w));
   142 	  reached.set(w, true);
   143 	  _newly_reached=true;
   144 	} else {
   145 	  _newly_reached=false;
   146 	}
   147       }
   148     }
   149     bfs_iterator1<Graph, ReachedMap>& operator++() { 
   150       if (!valid()) return *this;
   151       ++(bfs_queue.front());
   152       valid();
   153       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
   154 	OutEdgeIt e=bfs_queue.front();
   155 	NodeIt w=G.bNode(e);
   156 	if (!reached.get(w)) {
   157 	  bfs_queue.push(G.template first<OutEdgeIt>(w));
   158 	  reached.set(w, true);
   159 	  _newly_reached=true;
   160 	} else {
   161 	  _newly_reached=false;
   162 	}
   163       }
   164       return *this;
   165     }
   166     bool valid() { 
   167       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   168       if (bfs_queue.empty()) return false; else return true;
   169     }
   170     operator OutEdgeIt() { return bfs_queue.front(); }
   171     //ize
   172     bool newly_reached() { return _newly_reached; }
   173 
   174   };
   175 
   176   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   177   struct BfsIterator {
   178     typedef typename Graph::NodeIt NodeIt;
   179     Graph& G;
   180     std::queue<OutEdgeIt>& bfs_queue;
   181     ReachedMap& reached;
   182     bool b_node_newly_reached;
   183     OutEdgeIt actual_edge;
   184     BfsIterator(Graph& _G, 
   185 		std::queue<OutEdgeIt>& _bfs_queue, 
   186 		ReachedMap& _reached) : 
   187       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   188       actual_edge=bfs_queue.front();
   189       if (actual_edge.valid()) { 
   190 	NodeIt w=G.bNode(actual_edge);
   191 	if (!reached.get(w)) {
   192 	  bfs_queue.push(G.firstOutEdge(w));
   193 	  reached.set(w, true);
   194 	  b_node_newly_reached=true;
   195 	} else {
   196 	  b_node_newly_reached=false;
   197 	}
   198       }
   199     }
   200     BfsIterator<Graph, OutEdgeIt, ReachedMap>& 
   201     operator++() { 
   202       if (bfs_queue.front().valid()) { 
   203 	++(bfs_queue.front());
   204 	actual_edge=bfs_queue.front();
   205 	if (actual_edge.valid()) {
   206 	  NodeIt w=G.bNode(actual_edge);
   207 	  if (!reached.get(w)) {
   208 	    bfs_queue.push(G.firstOutEdge(w));
   209 	    reached.set(w, true);
   210 	    b_node_newly_reached=true;
   211 	  } else {
   212 	    b_node_newly_reached=false;
   213 	  }
   214 	}
   215       } else {
   216 	bfs_queue.pop(); 
   217 	actual_edge=bfs_queue.front();
   218 	if (actual_edge.valid()) {
   219 	  NodeIt w=G.bNode(actual_edge);
   220 	  if (!reached.get(w)) {
   221 	    bfs_queue.push(G.firstOutEdge(w));
   222 	    reached.set(w, true);
   223 	    b_node_newly_reached=true;
   224 	  } else {
   225 	    b_node_newly_reached=false;
   226 	  }
   227 	}
   228       }
   229       return *this;
   230     }
   231     bool finished() { return bfs_queue.empty(); }
   232     operator OutEdgeIt () { return actual_edge; }
   233     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   234     bool aNodeIsExamined() { return !(actual_edge.valid()); }
   235   };
   236 
   237 
   238   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   239   struct DfsIterator {
   240     typedef typename Graph::NodeIt NodeIt;
   241     Graph& G;
   242     std::stack<OutEdgeIt>& bfs_queue;
   243     ReachedMap& reached;
   244     bool b_node_newly_reached;
   245     OutEdgeIt actual_edge;
   246     DfsIterator(Graph& _G, 
   247 		std::stack<OutEdgeIt>& _bfs_queue, 
   248 		ReachedMap& _reached) : 
   249       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   250       actual_edge=bfs_queue.top();
   251       if (actual_edge.valid()) { 
   252 	NodeIt w=G.bNode(actual_edge);
   253 	if (!reached.get(w)) {
   254 	  bfs_queue.push(G.firstOutEdge(w));
   255 	  reached.set(w, true);
   256 	  b_node_newly_reached=true;
   257 	} else {
   258 	  ++(bfs_queue.top());
   259 	  b_node_newly_reached=false;
   260 	}
   261       } else {
   262 	bfs_queue.pop();
   263       }
   264     }
   265     DfsIterator<Graph, OutEdgeIt, ReachedMap>& 
   266     operator++() { 
   267       actual_edge=bfs_queue.top();
   268       if (actual_edge.valid()) { 
   269 	NodeIt w=G.bNode(actual_edge);
   270 	if (!reached.get(w)) {
   271 	  bfs_queue.push(G.firstOutEdge(w));
   272 	  reached.set(w, true);
   273 	  b_node_newly_reached=true;
   274 	} else {
   275 	  ++(bfs_queue.top());
   276 	  b_node_newly_reached=false;
   277 	}
   278       } else {
   279 	bfs_queue.pop();
   280       }
   281       return *this;
   282     }
   283     bool finished() { return bfs_queue.empty(); }
   284     operator OutEdgeIt () { return actual_edge; }
   285     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   286     bool aNodeIsExamined() { return !(actual_edge.valid()); }
   287   };
   288 
   289   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   290   struct BfsIterator1 {
   291     typedef typename Graph::NodeIt NodeIt;
   292     Graph& G;
   293     std::queue<OutEdgeIt>& bfs_queue;
   294     ReachedMap& reached;
   295     bool b_node_newly_reached;
   296     OutEdgeIt actual_edge;
   297     BfsIterator1(Graph& _G, 
   298 		std::queue<OutEdgeIt>& _bfs_queue, 
   299 		ReachedMap& _reached) : 
   300       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   301       actual_edge=bfs_queue.front();
   302       if (actual_edge.valid()) { 
   303       	NodeIt w=G.bNode(actual_edge);
   304 	if (!reached.get(w)) {
   305 	  bfs_queue.push(OutEdgeIt(G, w));
   306 	  reached.set(w, true);
   307 	  b_node_newly_reached=true;
   308 	} else {
   309 	  b_node_newly_reached=false;
   310 	}
   311       }
   312     }
   313     void next() { 
   314       if (bfs_queue.front().valid()) { 
   315 	++(bfs_queue.front());
   316 	actual_edge=bfs_queue.front();
   317 	if (actual_edge.valid()) {
   318 	  NodeIt w=G.bNode(actual_edge);
   319 	  if (!reached.get(w)) {
   320 	    bfs_queue.push(OutEdgeIt(G, w));
   321 	    reached.set(w, true);
   322 	    b_node_newly_reached=true;
   323 	  } else {
   324 	    b_node_newly_reached=false;
   325 	  }
   326 	}
   327       } else {
   328 	bfs_queue.pop(); 
   329 	actual_edge=bfs_queue.front();
   330 	if (actual_edge.valid()) {
   331 	  NodeIt w=G.bNode(actual_edge);
   332 	  if (!reached.get(w)) {
   333 	    bfs_queue.push(OutEdgeIt(G, w));
   334 	    reached.set(w, true);
   335 	    b_node_newly_reached=true;
   336 	  } else {
   337 	    b_node_newly_reached=false;
   338 	  }
   339 	}
   340       }
   341       //return *this;
   342     }
   343     bool finished() { return bfs_queue.empty(); }
   344     operator OutEdgeIt () { return actual_edge; }
   345     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   346     bool aNodeIsExamined() { return !(actual_edge.valid()); }
   347   };
   348 
   349 
   350   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   351   struct DfsIterator1 {
   352     typedef typename Graph::NodeIt NodeIt;
   353     Graph& G;
   354     std::stack<OutEdgeIt>& bfs_queue;
   355     ReachedMap& reached;
   356     bool b_node_newly_reached;
   357     OutEdgeIt actual_edge;
   358     DfsIterator1(Graph& _G, 
   359 		std::stack<OutEdgeIt>& _bfs_queue, 
   360 		ReachedMap& _reached) : 
   361       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   362       //actual_edge=bfs_queue.top();
   363       //if (actual_edge.valid()) { 
   364       //	NodeIt w=G.bNode(actual_edge);
   365       //if (!reached.get(w)) {
   366       //  bfs_queue.push(OutEdgeIt(G, w));
   367       //  reached.set(w, true);
   368       //  b_node_newly_reached=true;
   369       //} else {
   370       //  ++(bfs_queue.top());
   371       //  b_node_newly_reached=false;
   372       //}
   373       //} else {
   374       //	bfs_queue.pop();
   375       //}
   376     }
   377     void next() { 
   378       actual_edge=bfs_queue.top();
   379       if (actual_edge.valid()) { 
   380 	NodeIt w=G.bNode(actual_edge);
   381 	if (!reached.get(w)) {
   382 	  bfs_queue.push(OutEdgeIt(G, w));
   383 	  reached.set(w, true);
   384 	  b_node_newly_reached=true;
   385 	} else {
   386 	  ++(bfs_queue.top());
   387 	  b_node_newly_reached=false;
   388 	}
   389       } else {
   390 	bfs_queue.pop();
   391       }
   392       //return *this;
   393     }
   394     bool finished() { return bfs_queue.empty(); }
   395     operator OutEdgeIt () { return actual_edge; }
   396     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   397     bool aNodeIsLeaved() { return !(actual_edge.valid()); }
   398   };
   399 
   400   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   401   class BfsIterator2 {
   402     typedef typename Graph::NodeIt NodeIt;
   403     const Graph& G;
   404     std::queue<OutEdgeIt> bfs_queue;
   405     ReachedMap reached;
   406     bool b_node_newly_reached;
   407     OutEdgeIt actual_edge;
   408   public:
   409     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
   410     void pushAndSetReached(NodeIt s) { 
   411       reached.set(s, true);
   412       if (bfs_queue.empty()) {
   413 	bfs_queue.push(G.template first<OutEdgeIt>(s));
   414 	actual_edge=bfs_queue.front();
   415 	if (actual_edge.valid()) { 
   416 	  NodeIt w=G.bNode(actual_edge);
   417 	  if (!reached.get(w)) {
   418 	    bfs_queue.push(G.template first<OutEdgeIt>(w));
   419 	    reached.set(w, true);
   420 	    b_node_newly_reached=true;
   421 	  } else {
   422 	    b_node_newly_reached=false;
   423 	  }
   424 	} //else {
   425 	//}
   426       } else {
   427 	bfs_queue.push(G.template first<OutEdgeIt>(s));
   428       }
   429     }
   430     BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
   431     operator++() { 
   432       if (bfs_queue.front().valid()) { 
   433 	++(bfs_queue.front());
   434 	actual_edge=bfs_queue.front();
   435 	if (actual_edge.valid()) {
   436 	  NodeIt w=G.bNode(actual_edge);
   437 	  if (!reached.get(w)) {
   438 	    bfs_queue.push(G.template first<OutEdgeIt>(w));
   439 	    reached.set(w, true);
   440 	    b_node_newly_reached=true;
   441 	  } else {
   442 	    b_node_newly_reached=false;
   443 	  }
   444 	}
   445       } else {
   446 	bfs_queue.pop(); 
   447 	if (!bfs_queue.empty()) {
   448 	  actual_edge=bfs_queue.front();
   449 	  if (actual_edge.valid()) {
   450 	    NodeIt w=G.bNode(actual_edge);
   451 	    if (!reached.get(w)) {
   452 	      bfs_queue.push(G.template first<OutEdgeIt>(w));
   453 	      reached.set(w, true);
   454 	      b_node_newly_reached=true;
   455 	    } else {
   456 	      b_node_newly_reached=false;
   457 	    }
   458 	  }
   459 	}
   460       }
   461       return *this;
   462     }
   463     bool finished() const { return bfs_queue.empty(); }
   464     operator OutEdgeIt () const { return actual_edge; }
   465     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   466     bool isANodeExamined() const { return !(actual_edge.valid()); }
   467     const ReachedMap& getReachedMap() const { return reached; }
   468     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
   469  };
   470 
   471 
   472   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   473   class BfsIterator3 {
   474     typedef typename Graph::NodeIt NodeIt;
   475     const Graph& G;
   476     std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
   477     ReachedMap reached;
   478     bool b_node_newly_reached;
   479     OutEdgeIt actual_edge;
   480   public:
   481     BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
   482     void pushAndSetReached(NodeIt s) { 
   483       reached.set(s, true);
   484       if (bfs_queue.empty()) {
   485 	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
   486 	actual_edge=bfs_queue.front().second;
   487 	if (actual_edge.valid()) { 
   488 	  NodeIt w=G.bNode(actual_edge);
   489 	  if (!reached.get(w)) {
   490 	    bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
   491 	    reached.set(w, true);
   492 	    b_node_newly_reached=true;
   493 	  } else {
   494 	    b_node_newly_reached=false;
   495 	  }
   496 	} //else {
   497 	//}
   498       } else {
   499 	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
   500       }
   501     }
   502     BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
   503     operator++() { 
   504       if (bfs_queue.front().second.valid()) { 
   505 	++(bfs_queue.front().second);
   506 	actual_edge=bfs_queue.front().second;
   507 	if (actual_edge.valid()) {
   508 	  NodeIt w=G.bNode(actual_edge);
   509 	  if (!reached.get(w)) {
   510 	    bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
   511 	    reached.set(w, true);
   512 	    b_node_newly_reached=true;
   513 	  } else {
   514 	    b_node_newly_reached=false;
   515 	  }
   516 	}
   517       } else {
   518 	bfs_queue.pop(); 
   519 	if (!bfs_queue.empty()) {
   520 	  actual_edge=bfs_queue.front().second;
   521 	  if (actual_edge.valid()) {
   522 	    NodeIt w=G.bNode(actual_edge);
   523 	    if (!reached.get(w)) {
   524 	      bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
   525 	      reached.set(w, true);
   526 	      b_node_newly_reached=true;
   527 	    } else {
   528 	      b_node_newly_reached=false;
   529 	    }
   530 	  }
   531 	}
   532       }
   533       return *this;
   534     }
   535     bool finished() const { return bfs_queue.empty(); }
   536     operator OutEdgeIt () const { return actual_edge; }
   537     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   538     bool isANodeExamined() const { return !(actual_edge.valid()); }
   539     NodeIt aNode() const { return bfs_queue.front().first; }
   540     NodeIt bNode() const { return G.bNode(actual_edge); }
   541     const ReachedMap& getReachedMap() const { return reached; }
   542     //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
   543  };
   544 
   545 
   546   template <typename Graph, typename OutEdgeIt, 
   547 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   548   class BfsIterator4 {
   549     typedef typename Graph::NodeIt NodeIt;
   550     const Graph& G;
   551     std::queue<NodeIt> bfs_queue;
   552     ReachedMap& reached;
   553     bool b_node_newly_reached;
   554     OutEdgeIt actual_edge;
   555     bool own_reached_map;
   556   public:
   557     BfsIterator4(const Graph& _G, ReachedMap& _reached) : 
   558       G(_G), reached(_reached), 
   559       own_reached_map(false) { }
   560     BfsIterator4(const Graph& _G) : 
   561       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
   562       own_reached_map(true) { }
   563     ~BfsIterator4() { if (own_reached_map) delete &reached; }
   564     void pushAndSetReached(NodeIt s) { 
   565       reached.set(s, true);
   566       if (bfs_queue.empty()) {
   567 	bfs_queue.push(s);
   568 	G.getFirst(actual_edge, s);
   569 	if (G.valid(actual_edge)/*.valid()*/) { 
   570 	  NodeIt w=G.bNode(actual_edge);
   571 	  if (!reached.get(w)) {
   572 	    bfs_queue.push(w);
   573 	    reached.set(w, true);
   574 	    b_node_newly_reached=true;
   575 	  } else {
   576 	    b_node_newly_reached=false;
   577 	  }
   578 	} 
   579       } else {
   580 	bfs_queue.push(s);
   581       }
   582     }
   583     BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
   584     operator++() { 
   585       if (G.valid(actual_edge)/*.valid()*/) { 
   586 	/*++*/G.next(actual_edge);
   587 	if (G.valid(actual_edge)/*.valid()*/) {
   588 	  NodeIt w=G.bNode(actual_edge);
   589 	  if (!reached.get(w)) {
   590 	    bfs_queue.push(w);
   591 	    reached.set(w, true);
   592 	    b_node_newly_reached=true;
   593 	  } else {
   594 	    b_node_newly_reached=false;
   595 	  }
   596 	}
   597       } else {
   598 	bfs_queue.pop(); 
   599 	if (!bfs_queue.empty()) {
   600 	  G.getFirst(actual_edge, bfs_queue.front());
   601 	  if (G.valid(actual_edge)/*.valid()*/) {
   602 	    NodeIt w=G.bNode(actual_edge);
   603 	    if (!reached.get(w)) {
   604 	      bfs_queue.push(w);
   605 	      reached.set(w, true);
   606 	      b_node_newly_reached=true;
   607 	    } else {
   608 	      b_node_newly_reached=false;
   609 	    }
   610 	  }
   611 	}
   612       }
   613       return *this;
   614     }
   615     bool finished() const { return bfs_queue.empty(); }
   616     operator OutEdgeIt () const { return actual_edge; }
   617     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   618     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
   619     NodeIt aNode() const { return bfs_queue.front(); }
   620     NodeIt bNode() const { return G.bNode(actual_edge); }
   621     const ReachedMap& getReachedMap() const { return reached; }
   622     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
   623  };  
   624 
   625 
   626   template <typename GraphWrapper, typename OutEdgeIt, 
   627 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
   628   class BfsIterator5 {
   629     typedef typename GraphWrapper::NodeIt NodeIt;
   630     GraphWrapper G;
   631     std::queue<NodeIt> bfs_queue;
   632     ReachedMap& reached;
   633     bool b_node_newly_reached;
   634     OutEdgeIt actual_edge;
   635     bool own_reached_map;
   636   public:
   637     BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
   638       G(_G), reached(_reached), 
   639       own_reached_map(false) { }
   640     BfsIterator5(const GraphWrapper& _G) : 
   641       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
   642       own_reached_map(true) { }
   643     ~BfsIterator5() { if (own_reached_map) delete &reached; }
   644     void pushAndSetReached(NodeIt s) { 
   645       reached.set(s, true);
   646       if (bfs_queue.empty()) {
   647 	bfs_queue.push(s);
   648 	G.getFirst(actual_edge, s);
   649 	if (G.valid(actual_edge)/*.valid()*/) { 
   650 	  NodeIt w=G.bNode(actual_edge);
   651 	  if (!reached.get(w)) {
   652 	    bfs_queue.push(w);
   653 	    reached.set(w, true);
   654 	    b_node_newly_reached=true;
   655 	  } else {
   656 	    b_node_newly_reached=false;
   657 	  }
   658 	} 
   659       } else {
   660 	bfs_queue.push(s);
   661       }
   662     }
   663     BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 
   664     operator++() { 
   665       if (G.valid(actual_edge)/*.valid()*/) { 
   666 	/*++*/G.next(actual_edge);
   667 	if (G.valid(actual_edge)/*.valid()*/) {
   668 	  NodeIt w=G.bNode(actual_edge);
   669 	  if (!reached.get(w)) {
   670 	    bfs_queue.push(w);
   671 	    reached.set(w, true);
   672 	    b_node_newly_reached=true;
   673 	  } else {
   674 	    b_node_newly_reached=false;
   675 	  }
   676 	}
   677       } else {
   678 	bfs_queue.pop(); 
   679 	if (!bfs_queue.empty()) {
   680 	  G.getFirst(actual_edge, bfs_queue.front());
   681 	  if (G.valid(actual_edge)/*.valid()*/) {
   682 	    NodeIt w=G.bNode(actual_edge);
   683 	    if (!reached.get(w)) {
   684 	      bfs_queue.push(w);
   685 	      reached.set(w, true);
   686 	      b_node_newly_reached=true;
   687 	    } else {
   688 	      b_node_newly_reached=false;
   689 	    }
   690 	  }
   691 	}
   692       }
   693       return *this;
   694     }
   695     bool finished() const { return bfs_queue.empty(); }
   696     operator OutEdgeIt () const { return actual_edge; }
   697     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   698     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
   699     NodeIt aNode() const { return bfs_queue.front(); }
   700     NodeIt bNode() const { return G.bNode(actual_edge); }
   701     const ReachedMap& getReachedMap() const { return reached; }
   702     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
   703   };  
   704 
   705   template <typename Graph, typename OutEdgeIt, 
   706 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   707   class DfsIterator4 {
   708     typedef typename Graph::NodeIt NodeIt;
   709     const Graph& G;
   710     std::stack<OutEdgeIt> dfs_stack;
   711     bool b_node_newly_reached;
   712     OutEdgeIt actual_edge;
   713     NodeIt actual_node;
   714     ReachedMap& reached;
   715     bool own_reached_map;
   716   public:
   717     DfsIterator4(const Graph& _G, ReachedMap& _reached) : 
   718       G(_G), reached(_reached), 
   719       own_reached_map(false) { }
   720     DfsIterator4(const Graph& _G) : 
   721       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
   722       own_reached_map(true) { }
   723     ~DfsIterator4() { if (own_reached_map) delete &reached; }
   724     void pushAndSetReached(NodeIt s) { 
   725       actual_node=s;
   726       reached.set(s, true);
   727       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
   728     }
   729     DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
   730     operator++() { 
   731       actual_edge=dfs_stack.top();
   732       //actual_node=G.aNode(actual_edge);
   733       if (G.valid(actual_edge)/*.valid()*/) { 
   734 	NodeIt w=G.bNode(actual_edge);
   735 	actual_node=w;
   736 	if (!reached.get(w)) {
   737 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
   738 	  reached.set(w, true);
   739 	  b_node_newly_reached=true;
   740 	} else {
   741 	  actual_node=G.aNode(actual_edge);
   742 	  /*++*/G.next(dfs_stack.top());
   743 	  b_node_newly_reached=false;
   744 	}
   745       } else {
   746 	//actual_node=G.aNode(dfs_stack.top());
   747 	dfs_stack.pop();
   748       }
   749       return *this;
   750     }
   751     bool finished() const { return dfs_stack.empty(); }
   752     operator OutEdgeIt () const { return actual_edge; }
   753     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   754     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
   755     NodeIt aNode() const { return actual_node; /*FIXME*/}
   756     NodeIt bNode() const { return G.bNode(actual_edge); }
   757     const ReachedMap& getReachedMap() const { return reached; }
   758     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   759   };
   760 
   761   template <typename GraphWrapper, typename OutEdgeIt, 
   762 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
   763   class DfsIterator5 {
   764     typedef typename GraphWrapper::NodeIt NodeIt;
   765     GraphWrapper G;
   766     std::stack<OutEdgeIt> dfs_stack;
   767     bool b_node_newly_reached;
   768     OutEdgeIt actual_edge;
   769     NodeIt actual_node;
   770     ReachedMap& reached;
   771     bool own_reached_map;
   772   public:
   773     DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
   774       G(_G), reached(_reached), 
   775       own_reached_map(false) { }
   776     DfsIterator5(const GraphWrapper& _G) : 
   777       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
   778       own_reached_map(true) { }
   779     ~DfsIterator5() { if (own_reached_map) delete &reached; }
   780     void pushAndSetReached(NodeIt s) { 
   781       actual_node=s;
   782       reached.set(s, true);
   783       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
   784     }
   785     DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 
   786     operator++() { 
   787       actual_edge=dfs_stack.top();
   788       //actual_node=G.aNode(actual_edge);
   789       if (G.valid(actual_edge)/*.valid()*/) { 
   790 	NodeIt w=G.bNode(actual_edge);
   791 	actual_node=w;
   792 	if (!reached.get(w)) {
   793 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
   794 	  reached.set(w, true);
   795 	  b_node_newly_reached=true;
   796 	} else {
   797 	  actual_node=G.aNode(actual_edge);
   798 	  /*++*/G.next(dfs_stack.top());
   799 	  b_node_newly_reached=false;
   800 	}
   801       } else {
   802 	//actual_node=G.aNode(dfs_stack.top());
   803 	dfs_stack.pop();
   804       }
   805       return *this;
   806     }
   807     bool finished() const { return dfs_stack.empty(); }
   808     operator OutEdgeIt () const { return actual_edge; }
   809     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   810     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
   811     NodeIt aNode() const { return actual_node; /*FIXME*/}
   812     NodeIt bNode() const { return G.bNode(actual_edge); }
   813     const ReachedMap& getReachedMap() const { return reached; }
   814     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   815   };
   816 
   817 
   818 
   819 } // namespace hugo
   820 
   821 #endif //BFS_ITERATOR_HH