src/work/bfs_iterator.hh
author klao
Thu, 26 Feb 2004 16:07:40 +0000
changeset 132 1ac27e476e25
parent 99 f26897fb91fd
child 133 0631992fe7a1
permissions -rw-r--r--
makefile: tobb include konyvtar, jobb depend keszites
flow_test.cc: torolve, mert a depend-et megakasztja, igy gondolom nem is fordul
     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   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   546   class BfsIterator4 {
   547     typedef typename Graph::NodeIt NodeIt;
   548     const Graph& G;
   549     std::queue<NodeIt> bfs_queue;
   550     ReachedMap reached;
   551     bool b_node_newly_reached;
   552     OutEdgeIt actual_edge;
   553   public:
   554     BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
   555     void pushAndSetReached(NodeIt s) { 
   556       reached.set(s, true);
   557       if (bfs_queue.empty()) {
   558 	bfs_queue.push(s);
   559 	G.getFirst(actual_edge, s);
   560 	if (actual_edge.valid()) { 
   561 	  NodeIt w=G.bNode(actual_edge);
   562 	  if (!reached.get(w)) {
   563 	    bfs_queue.push(w);
   564 	    reached.set(w, true);
   565 	    b_node_newly_reached=true;
   566 	  } else {
   567 	    b_node_newly_reached=false;
   568 	  }
   569 	} 
   570       } else {
   571 	bfs_queue.push(s);
   572       }
   573     }
   574     BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
   575     operator++() { 
   576       if (actual_edge.valid()) { 
   577 	++actual_edge;
   578 	if (actual_edge.valid()) {
   579 	  NodeIt w=G.bNode(actual_edge);
   580 	  if (!reached.get(w)) {
   581 	    bfs_queue.push(w);
   582 	    reached.set(w, true);
   583 	    b_node_newly_reached=true;
   584 	  } else {
   585 	    b_node_newly_reached=false;
   586 	  }
   587 	}
   588       } else {
   589 	bfs_queue.pop(); 
   590 	if (!bfs_queue.empty()) {
   591 	  G.getFirst(actual_edge, bfs_queue.front());
   592 	  if (actual_edge.valid()) {
   593 	    NodeIt w=G.bNode(actual_edge);
   594 	    if (!reached.get(w)) {
   595 	      bfs_queue.push(w);
   596 	      reached.set(w, true);
   597 	      b_node_newly_reached=true;
   598 	    } else {
   599 	      b_node_newly_reached=false;
   600 	    }
   601 	  }
   602 	}
   603       }
   604       return *this;
   605     }
   606     bool finished() const { return bfs_queue.empty(); }
   607     operator OutEdgeIt () const { return actual_edge; }
   608     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   609     bool isANodeExamined() const { return !(actual_edge.valid()); }
   610     NodeIt aNode() const { return bfs_queue.front(); }
   611     NodeIt bNode() const { return G.bNode(actual_edge); }
   612     const ReachedMap& getReachedMap() const { return reached; }
   613     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
   614  };
   615 
   616 
   617   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   618   struct DfsIterator4 {
   619     typedef typename Graph::NodeIt NodeIt;
   620     const Graph& G;
   621     std::stack<OutEdgeIt> dfs_stack;
   622     //ReachedMap& reached;
   623     bool b_node_newly_reached;
   624     OutEdgeIt actual_edge;
   625     NodeIt actual_node;
   626     ReachedMap reached;
   627     DfsIterator4(const Graph& _G 
   628 		 /*, std::stack<OutEdgeIt>& _bfs_queue, 
   629 		   ReachedMap& _reached*/) : 
   630       G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { 
   631       //actual_edge=bfs_queue.top();
   632       //if (actual_edge.valid()) { 
   633       //	NodeIt w=G.bNode(actual_edge);
   634       //if (!reached.get(w)) {
   635       //  bfs_queue.push(OutEdgeIt(G, w));
   636       //  reached.set(w, true);
   637       //  b_node_newly_reached=true;
   638       //} else {
   639       //  ++(bfs_queue.top());
   640       //  b_node_newly_reached=false;
   641       //}
   642       //} else {
   643       //	bfs_queue.pop();
   644       //}
   645     }
   646     void pushAndSetReached(NodeIt s) { 
   647       reached.set(s, true);
   648       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
   649     }
   650     DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
   651     operator++() { 
   652       actual_edge=dfs_stack.top();
   653       //actual_node=G.aNode(actual_edge);
   654       if (actual_edge.valid()) { 
   655 	NodeIt w=G.bNode(actual_edge);
   656 	actual_node=w;
   657 	if (!reached.get(w)) {
   658 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
   659 	  reached.set(w, true);
   660 	  b_node_newly_reached=true;
   661 	} else {
   662 	  ++(dfs_stack.top());
   663 	  b_node_newly_reached=false;
   664 	}
   665       } else {
   666 	//actual_node=G.aNode(dfs_stack.top());
   667 	dfs_stack.pop();
   668       }
   669       return *this;
   670     }
   671     bool finished() const { return dfs_stack.empty(); }
   672     operator OutEdgeIt () const { return actual_edge; }
   673     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   674     bool isANodeExamined() const { return !(actual_edge.valid()); }
   675     NodeIt aNode() const { return actual_node; }
   676     NodeIt bNode() const { return G.bNode(actual_edge); }
   677     const ReachedMap& getReachedMap() const { return reached; }
   678     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   679   };
   680 
   681 
   682 
   683   template <typename GraphWrapper, typename ReachedMap>
   684   class BfsIterator5 {
   685     typedef typename GraphWrapper::NodeIt NodeIt;
   686     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
   687     GraphWrapper gw;
   688     std::queue<NodeIt> bfs_queue;
   689     ReachedMap reached;
   690     bool b_node_newly_reached;
   691     OutEdgeIt actual_edge;
   692   public:
   693     BfsIterator5(GraphWrapper _gw) : 
   694       gw(_gw), reached(_gw.getGraph()) { }
   695     void pushAndSetReached(NodeIt s) { 
   696       reached.set(s, true);
   697       if (bfs_queue.empty()) {
   698 	bfs_queue.push(s);
   699 	gw.getFirst(actual_edge, s);
   700 	if (actual_edge.valid()) { 
   701 	  NodeIt w=gw.bNode(actual_edge);
   702 	  if (!reached.get(w)) {
   703 	    bfs_queue.push(w);
   704 	    reached.set(w, true);
   705 	    b_node_newly_reached=true;
   706 	  } else {
   707 	    b_node_newly_reached=false;
   708 	  }
   709 	} 
   710       } else {
   711 	bfs_queue.push(s);
   712       }
   713     }
   714     BfsIterator5<GraphWrapper, ReachedMap>& 
   715     operator++() { 
   716       if (actual_edge.valid()) { 
   717 	++actual_edge;
   718 	if (actual_edge.valid()) {
   719 	  NodeIt w=gw.bNode(actual_edge);
   720 	  if (!reached.get(w)) {
   721 	    bfs_queue.push(w);
   722 	    reached.set(w, true);
   723 	    b_node_newly_reached=true;
   724 	  } else {
   725 	    b_node_newly_reached=false;
   726 	  }
   727 	}
   728       } else {
   729 	bfs_queue.pop(); 
   730 	if (!bfs_queue.empty()) {
   731 	  gw.getFirst(actual_edge, bfs_queue.front());
   732 	  if (actual_edge.valid()) {
   733 	    NodeIt w=gw.bNode(actual_edge);
   734 	    if (!reached.get(w)) {
   735 	      bfs_queue.push(w);
   736 	      reached.set(w, true);
   737 	      b_node_newly_reached=true;
   738 	    } else {
   739 	      b_node_newly_reached=false;
   740 	    }
   741 	  }
   742 	}
   743       }
   744       return *this;
   745     }
   746     bool finished() const { return bfs_queue.empty(); }
   747     operator OutEdgeIt () const { return actual_edge; }
   748     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   749     bool isANodeExamined() const { return !(actual_edge.valid()); }
   750     NodeIt aNode() const { return bfs_queue.front(); }
   751     NodeIt bNode() const { return gw.bNode(actual_edge); }
   752     const ReachedMap& getReachedMap() const { return reached; }
   753     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
   754  };
   755 
   756 
   757 
   758 } // namespace hugo
   759 
   760 #endif //BFS_ITERATOR_HH