# HG changeset patch
# User marci
# Date 1084208360 0
# Node ID 580b329c2a0cd1c8d44a744e049e3727fcb6338d
# Parent  6c6c0eb89b475c5238152805a6bb9a4e337d0c2e
bfs_iterator -> bfs_dfs.h, some docs

diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/jacint/max_flow.h
--- a/src/work/jacint/max_flow.h	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/jacint/max_flow.h	Mon May 10 16:59:20 2004 +0000
@@ -44,7 +44,7 @@
 #include <stack>
 
 #include <hugo/graph_wrapper.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
 #include <for_each_macros.h>
@@ -55,7 +55,7 @@
 namespace hugo {
 
 
-//  ///\author Marton Makai, Jacint Szabo
+  //  ///\author Marton Makai, Jacint Szabo
   /// A class for computing max flows and related quantities.
   template <typename Graph, typename Num, 
 	    typename CapMap=typename Graph::template EdgeMap<Num>, 
@@ -88,20 +88,20 @@
     //In preflow, it shows levels of nodes.
     //typename Graph::template NodeMap<int> level;    
     typename Graph::template NodeMap<Num> excess; 
-//   protected:
-//     MaxFlow() { }
-//     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
-// 	     FlowMap& _flow) 
-//       {
-// 	g=&_G; 
-// 	s=_s; 
-// 	t=_t; 
-// 	capacity=&_capacity;
-// 	flow=&_flow;
-// 	n=_G.nodeNum;
-// 	level.set (_G); //kellene vmi ilyesmi fv 
-// 	excess(_G,0); //itt is
-//       }
+    //   protected:
+    //     MaxFlow() { }
+    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
+    // 	     FlowMap& _flow) 
+    //       {
+    // 	g=&_G; 
+    // 	s=_s; 
+    // 	t=_t; 
+    // 	capacity=&_capacity;
+    // 	flow=&_flow;
+    // 	n=_G.nodeNum;
+    // 	level.set (_G); //kellene vmi ilyesmi fv 
+    // 	excess(_G,0); //itt is
+    //       }
 
   public:
  
@@ -362,126 +362,127 @@
 
 
     void preflowPreproc ( flowEnum fe, VecStack& active, 
-			  VecNode& level_list, NNMap& left, NNMap& right ) {
+			  VecNode& level_list, NNMap& left, NNMap& right ) 
+    {
 
-			    std::queue<Node> bfs_queue;
+      std::queue<Node> bfs_queue;
       
-			    switch ( fe ) {
-			    case ZERO_FLOW: 
-			      {
-				//Reverse_bfs from t, to find the starting level.
-				level.set(t,0);
-				bfs_queue.push(t);
+      switch ( fe ) {
+      case ZERO_FLOW: 
+	{
+	  //Reverse_bfs from t, to find the starting level.
+	  level.set(t,0);
+	  bfs_queue.push(t);
 	
-				while (!bfs_queue.empty()) {
+	  while (!bfs_queue.empty()) {
 	    
-				  Node v=bfs_queue.front();	
-				  bfs_queue.pop();
-				  int l=level[v]+1;
+	    Node v=bfs_queue.front();	
+	    bfs_queue.pop();
+	    int l=level[v]+1;
 	    
-				  InEdgeIt e;
-				  for(g->first(e,v); g->valid(e); g->next(e)) {
-				    Node w=g->tail(e);
-				    if ( level[w] == n && w != s ) {
-				      bfs_queue.push(w);
-				      Node first=level_list[l];
-				      if ( g->valid(first) ) left.set(first,w);
-				      right.set(w,first);
-				      level_list[l]=w;
-				      level.set(w, l);
-				    }
-				  }
-				}
+	    InEdgeIt e;
+	    for(g->first(e,v); g->valid(e); g->next(e)) {
+	      Node w=g->tail(e);
+	      if ( level[w] == n && w != s ) {
+		bfs_queue.push(w);
+		Node first=level_list[l];
+		if ( g->valid(first) ) left.set(first,w);
+		right.set(w,first);
+		level_list[l]=w;
+		level.set(w, l);
+	      }
+	    }
+	  }
 	  
-				//the starting flow
-				OutEdgeIt e;
-				for(g->first(e,s); g->valid(e); g->next(e)) 
-				  {
-				    Num c=(*capacity)[e];
-				    if ( c <= 0 ) continue;
-				    Node w=g->head(e);
-				    if ( level[w] < n ) {	  
-				      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-				      flow->set(e, c); 
-				      excess.set(w, excess[w]+c);
-				    }
-				  }
-				break;
-			      }
+	  //the starting flow
+	  OutEdgeIt e;
+	  for(g->first(e,s); g->valid(e); g->next(e)) 
+	    {
+	      Num c=(*capacity)[e];
+	      if ( c <= 0 ) continue;
+	      Node w=g->head(e);
+	      if ( level[w] < n ) {	  
+		if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
+		flow->set(e, c); 
+		excess.set(w, excess[w]+c);
+	      }
+	    }
+	  break;
+	}
 	
-			    case GEN_FLOW:
-			    case PREFLOW:
-			      {
-				//Reverse_bfs from t in the residual graph, 
-				//to find the starting level.
-				level.set(t,0);
-				bfs_queue.push(t);
+      case GEN_FLOW:
+      case PREFLOW:
+	{
+	  //Reverse_bfs from t in the residual graph, 
+	  //to find the starting level.
+	  level.set(t,0);
+	  bfs_queue.push(t);
 	  
-				while (!bfs_queue.empty()) {
+	  while (!bfs_queue.empty()) {
 	    
-				  Node v=bfs_queue.front();	
-				  bfs_queue.pop();
-				  int l=level[v]+1;
+	    Node v=bfs_queue.front();	
+	    bfs_queue.pop();
+	    int l=level[v]+1;
 	    
-				  InEdgeIt e;
-				  for(g->first(e,v); g->valid(e); g->next(e)) {
-				    if ( (*capacity)[e] <= (*flow)[e] ) continue;
-				    Node w=g->tail(e);
-				    if ( level[w] == n && w != s ) {
-				      bfs_queue.push(w);
-				      Node first=level_list[l];
-				      if ( g->valid(first) ) left.set(first,w);
-				      right.set(w,first);
-				      level_list[l]=w;
-				      level.set(w, l);
-				    }
-				  }
+	    InEdgeIt e;
+	    for(g->first(e,v); g->valid(e); g->next(e)) {
+	      if ( (*capacity)[e] <= (*flow)[e] ) continue;
+	      Node w=g->tail(e);
+	      if ( level[w] == n && w != s ) {
+		bfs_queue.push(w);
+		Node first=level_list[l];
+		if ( g->valid(first) ) left.set(first,w);
+		right.set(w,first);
+		level_list[l]=w;
+		level.set(w, l);
+	      }
+	    }
 	    
-				  OutEdgeIt f;
-				  for(g->first(f,v); g->valid(f); g->next(f)) {
-				    if ( 0 >= (*flow)[f] ) continue;
-				    Node w=g->head(f);
-				    if ( level[w] == n && w != s ) {
-				      bfs_queue.push(w);
-				      Node first=level_list[l];
-				      if ( g->valid(first) ) left.set(first,w);
-				      right.set(w,first);
-				      level_list[l]=w;
-				      level.set(w, l);
-				    }
-				  }
-				}
+	    OutEdgeIt f;
+	    for(g->first(f,v); g->valid(f); g->next(f)) {
+	      if ( 0 >= (*flow)[f] ) continue;
+	      Node w=g->head(f);
+	      if ( level[w] == n && w != s ) {
+		bfs_queue.push(w);
+		Node first=level_list[l];
+		if ( g->valid(first) ) left.set(first,w);
+		right.set(w,first);
+		level_list[l]=w;
+		level.set(w, l);
+	      }
+	    }
+	  }
 	  
 	  
-				//the starting flow
-				OutEdgeIt e;
-				for(g->first(e,s); g->valid(e); g->next(e)) 
-				  {
-				    Num rem=(*capacity)[e]-(*flow)[e];
-				    if ( rem <= 0 ) continue;
-				    Node w=g->head(e);
-				    if ( level[w] < n ) {	  
-				      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-				      flow->set(e, (*capacity)[e]); 
-				      excess.set(w, excess[w]+rem);
-				    }
-				  }
+	  //the starting flow
+	  OutEdgeIt e;
+	  for(g->first(e,s); g->valid(e); g->next(e)) 
+	    {
+	      Num rem=(*capacity)[e]-(*flow)[e];
+	      if ( rem <= 0 ) continue;
+	      Node w=g->head(e);
+	      if ( level[w] < n ) {	  
+		if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
+		flow->set(e, (*capacity)[e]); 
+		excess.set(w, excess[w]+rem);
+	      }
+	    }
 	  
-				InEdgeIt f;
-				for(g->first(f,s); g->valid(f); g->next(f)) 
-				  {
-				    if ( (*flow)[f] <= 0 ) continue;
-				    Node w=g->tail(f);
-				    if ( level[w] < n ) {	  
-				      if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-				      excess.set(w, excess[w]+(*flow)[f]);
-				      flow->set(f, 0); 
-				    }
-				  }  
-				break;
-			      } //case PREFLOW
-			    }
-			  } //preflowPreproc
+	  InEdgeIt f;
+	  for(g->first(f,s); g->valid(f); g->next(f)) 
+	    {
+	      if ( (*flow)[f] <= 0 ) continue;
+	      Node w=g->tail(f);
+	      if ( level[w] < n ) {	  
+		if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
+		excess.set(w, excess[w]+(*flow)[f]);
+		flow->set(f, 0); 
+	      }
+	    }  
+	  break;
+	} //case PREFLOW
+      }
+    } //preflowPreproc
 
 
 
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bfs_dfs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/bfs_dfs.h	Mon May 10 16:59:20 2004 +0000
@@ -0,0 +1,314 @@
+// -*- c++ -*-
+#ifndef HUGO_BFS_DFS_H
+#define HUGO_BFS_DFS_H
+
+#include <queue>
+#include <stack>
+#include <utility>
+
+#include <hugo/invalid.h>
+
+namespace hugo {
+
+  /// Bfs searches for the nodes wich are not marked in 
+  /// \c reached_map
+  /// Reached have to work as read-write bool Node-map.
+  template <typename Graph, /*typename OutEdgeIt,*/ 
+	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
+  class BfsIterator {
+  protected:
+    typedef typename Graph::Node Node;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    const Graph* graph;
+    std::queue<Node> bfs_queue;
+    ReachedMap& reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+    bool own_reached_map;
+  public:
+    /// In that constructor \c _reached have to be a reference 
+    /// for a bool Node-map. The algorithm will search in a bfs order for 
+    /// the nodes which are \c false initially
+    BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
+      graph(&_graph), reached(_reached), 
+      own_reached_map(false) { }
+    /// The same as above, but the map storing the reached nodes 
+    /// is constructed dynamically to everywhere false.
+    BfsIterator(const Graph& _graph) : 
+      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
+      own_reached_map(true) { }
+    /// The storing the reached nodes have to be destroyed if 
+    /// it was constructed dynamically
+    ~BfsIterator() { if (own_reached_map) delete &reached; }
+    /// This method markes \c s reached.
+    /// If the queue is empty, then \c s is pushed in the bfs queue 
+    /// and the first out-edge is processed.
+    /// If the queue is not empty, then \c s is simply pushed.
+    void pushAndSetReached(Node s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+	bfs_queue.push(s);
+	graph->first(actual_edge, s);
+	if (graph->valid(actual_edge)) { 
+	  Node w=graph->bNode(actual_edge);
+	  if (!reached[w]) {
+	    bfs_queue.push(w);
+	    reached.set(w, true);
+	    b_node_newly_reached=true;
+	  } else {
+	    b_node_newly_reached=false;
+	  }
+	} 
+      } else {
+	bfs_queue.push(s);
+      }
+    }
+    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
+    /// its \c operator++() iterates on the edges in a bfs order.
+    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
+    operator++() { 
+      if (graph->valid(actual_edge)) { 
+	graph->next(actual_edge);
+	if (graph->valid(actual_edge)) {
+	  Node w=graph->bNode(actual_edge);
+	  if (!reached[w]) {
+	    bfs_queue.push(w);
+	    reached.set(w, true);
+	    b_node_newly_reached=true;
+	  } else {
+	    b_node_newly_reached=false;
+	  }
+	}
+      } else {
+	bfs_queue.pop(); 
+	if (!bfs_queue.empty()) {
+	  graph->first(actual_edge, bfs_queue.front());
+	  if (graph->valid(actual_edge)) {
+	    Node w=graph->bNode(actual_edge);
+	    if (!reached[w]) {
+	      bfs_queue.push(w);
+	      reached.set(w, true);
+	      b_node_newly_reached=true;
+	    } else {
+	      b_node_newly_reached=false;
+	    }
+	  }
+	}
+      }
+      return *this;
+    }
+    ///
+    bool finished() const { return bfs_queue.empty(); }
+    /// The conversion operator makes for converting the bfs-iterator 
+    /// to an \c out-edge-iterator.
+    ///\bug Edge have to be in HUGO 0.2
+    operator OutEdgeIt() const { return actual_edge; }
+    ///
+    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+    ///
+    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
+    ///
+    Node aNode() const { return bfs_queue.front(); }
+    ///
+    Node bNode() const { return graph->bNode(actual_edge); }
+    ///
+    const ReachedMap& getReachedMap() const { return reached; }
+    ///
+    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
+  };  
+
+  /// Bfs searches for the nodes wich are not marked in 
+  /// \c reached_map
+  /// Reached have to work as a read-write bool Node-map, 
+  /// Pred is a write Edge Node-map and
+  /// Dist is a read-write int Node-map, have to be. 
+  ///\todo In fact onsly simple operations requirement are needed for 
+  /// Dist::Value.
+  template <typename Graph, 
+	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
+	    typename PredMap
+	    =typename Graph::template NodeMap<typename Graph::Edge>, 
+	    typename DistMap=typename Graph::template NodeMap<int> > 
+  class Bfs : public BfsIterator<Graph, ReachedMap> {
+    typedef BfsIterator<Graph, ReachedMap> Parent;
+  protected:
+    typedef typename Parent::Node Node;
+    PredMap& pred;
+    DistMap& dist;
+  public:
+    /// The algorithm will search in a bfs order for 
+    /// the nodes which are \c false initially. 
+    /// The constructor makes no initial changes on the maps.
+    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
+    /// \c s is marked to be reached and pushed in the bfs queue.
+    /// If the queue is empty, then the first out-edge is processed.
+    /// If \c s was not marked previously, then 
+    /// in addition its pred is set to be \c INVALID, and dist to \c 0. 
+    /// if \c s was marked previuosly, then it is simply pushed.
+    void push(Node s) { 
+      if (this->reached[s]) {
+	Parent::pushAndSetReached(s);
+      } else {
+	Parent::pushAndSetReached(s);
+	pred.set(s, INVALID);
+	dist.set(s, 0);
+      }
+    }
+    /// A bfs is processed from \c s.
+    void run(Node s) {
+      push(s);
+      while (!this->finished()) this->operator++();
+    }
+    /// Beside the bfs iteration, \c pred and \dist are saved in a 
+    /// newly reached node. 
+    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
+      Parent::operator++();
+      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
+      {
+	pred.set(this->bNode(), this->actual_edge);
+	dist.set(this->bNode(), dist[this->aNode()]);
+      }
+      return *this;
+    }
+    ///
+    const PredMap& getPredMap() const { return pred; }
+    ///
+    const DistMap& getDistMap() const { return dist; }
+  };
+
+  /// Dfs searches for the nodes wich are not marked in 
+  /// \c reached_map
+  /// Reached have to be a read-write bool Node-map.
+  template <typename Graph, /*typename OutEdgeIt,*/ 
+	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
+  class DfsIterator {
+  protected:
+    typedef typename Graph::Node Node;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    const Graph* graph;
+    std::stack<OutEdgeIt> dfs_stack;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+    Node actual_node;
+    ReachedMap& reached;
+    bool own_reached_map;
+  public:
+    /// In that constructor \c _reached have to be a reference 
+    /// for a bool Node-map. The algorithm will search in a dfs order for 
+    /// the nodes which are \c false initially
+    DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
+      graph(&_graph), reached(_reached), 
+      own_reached_map(false) { }
+    /// The same as above, but the map of reached nodes is 
+    /// constructed dynamically 
+    /// to everywhere false.
+    DfsIterator(const Graph& _graph) : 
+      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
+      own_reached_map(true) { }
+    ~DfsIterator() { if (own_reached_map) delete &reached; }
+    /// This method markes s reached and first out-edge is processed.
+    void pushAndSetReached(Node s) { 
+      actual_node=s;
+      reached.set(s, true);
+      OutEdgeIt e;
+      graph->first(e, s);
+      dfs_stack.push(e); 
+    }
+    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, 
+    /// its \c operator++() iterates on the edges in a dfs order.
+    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
+    operator++() { 
+      actual_edge=dfs_stack.top();
+      //actual_node=G.aNode(actual_edge);
+      if (graph->valid(actual_edge)/*.valid()*/) { 
+	Node w=graph->bNode(actual_edge);
+	actual_node=w;
+	if (!reached[w]) {
+	  OutEdgeIt e;
+	  graph->first(e, w);
+	  dfs_stack.push(e);
+	  reached.set(w, true);
+	  b_node_newly_reached=true;
+	} else {
+	  actual_node=graph->aNode(actual_edge);
+	  graph->next(dfs_stack.top());
+	  b_node_newly_reached=false;
+	}
+      } else {
+	//actual_node=G.aNode(dfs_stack.top());
+	dfs_stack.pop();
+      }
+      return *this;
+    }
+    ///
+    bool finished() const { return dfs_stack.empty(); }
+    ///
+    operator OutEdgeIt() const { return actual_edge; }
+    ///
+    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+    ///
+    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
+    ///
+    Node aNode() const { return actual_node; /*FIXME*/}
+    ///
+    Node bNode() const { return graph->bNode(actual_edge); }
+    ///
+    const ReachedMap& getReachedMap() const { return reached; }
+    ///
+    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
+  };
+
+  /// Dfs searches for the nodes wich are not marked in 
+  /// \c reached_map
+  /// Reached is a read-write bool Node-map, 
+  /// Pred is a write Node-map, have to be.
+  template <typename Graph, 
+	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
+	    typename PredMap
+	    =typename Graph::template NodeMap<typename Graph::Edge> > 
+  class Dfs : public DfsIterator<Graph, ReachedMap> {
+    typedef DfsIterator<Graph, ReachedMap> Parent;
+  protected:
+    typedef typename Parent::Node Node;
+    PredMap& pred;
+  public:
+    /// The algorithm will search in a dfs order for 
+    /// the nodes which are \c false initially. 
+    /// The constructor makes no initial changes on the maps.
+    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
+    /// \c s is marked to be reached and pushed in the bfs queue.
+    /// If the queue is empty, then the first out-edge is processed.
+    /// If \c s was not marked previously, then 
+    /// in addition its pred is set to be \c INVALID. 
+    /// if \c s was marked previuosly, then it is simply pushed.
+    void push(Node s) { 
+      if (this->reached[s]) {
+	Parent::pushAndSetReached(s);
+      } else {
+	Parent::pushAndSetReached(s);
+	pred.set(s, INVALID);
+      }
+    }
+    /// A bfs is processed from \c s.
+    void run(Node s) {
+      push(s);
+      while (!this->finished()) this->operator++();
+    }
+    /// Beside the dfs iteration, \c pred is saved in a 
+    /// newly reached node. 
+    Dfs<Graph, ReachedMap, PredMap> operator++() {
+      Parent::operator++();
+      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
+      {
+	pred.set(this->bNode(), this->actual_edge);
+      }
+      return *this;
+    }
+    ///
+    const PredMap& getPredMap() const { return pred; }
+  };
+
+
+} // namespace hugo
+
+#endif //HUGO_BFS_DFS_H
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bfs_dfs_misc.h
--- a/src/work/marci/bfs_dfs_misc.h	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/bfs_dfs_misc.h	Mon May 10 16:59:20 2004 +0000
@@ -2,7 +2,7 @@
 #ifndef HUGO_BFS_DFS_MISC_H
 #define HUGO_BFS_DFS_MISC_H
 
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <for_each_macros.h>
 
 namespace hugo {
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bfs_iterator.h
--- a/src/work/marci/bfs_iterator.h	Mon May 10 16:52:51 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,314 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_BFS_ITERATOR_H
-#define HUGO_BFS_ITERATOR_H
-
-#include <queue>
-#include <stack>
-#include <utility>
-
-#include <hugo/invalid.h>
-
-namespace hugo {
-
-  /// Bfs searches for the nodes wich are not marked in 
-  /// \c reached_map
-  /// Reached have to work as read-write bool Node-map.
-  template <typename Graph, /*typename OutEdgeIt,*/ 
-	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
-  class BfsIterator {
-  protected:
-    typedef typename Graph::Node Node;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    const Graph* graph;
-    std::queue<Node> bfs_queue;
-    ReachedMap& reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    bool own_reached_map;
-  public:
-    /// In that constructor \c _reached have to be a reference 
-    /// for a bool Node-map. The algorithm will search in a bfs order for 
-    /// the nodes which are \c false initially
-    BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
-      graph(&_graph), reached(_reached), 
-      own_reached_map(false) { }
-    /// The same as above, but the map storing the reached nodes 
-    /// is constructed dynamically to everywhere false.
-    BfsIterator(const Graph& _graph) : 
-      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
-      own_reached_map(true) { }
-    /// The storing the reached nodes have to be destroyed if 
-    /// it was constructed dynamically
-    ~BfsIterator() { if (own_reached_map) delete &reached; }
-    /// This method markes \c s reached.
-    /// If the queue is empty, then \c s is pushed in the bfs queue 
-    /// and the first out-edge is processed.
-    /// If the queue is not empty, then \c s is simply pushed.
-    void pushAndSetReached(Node s) { 
-      reached.set(s, true);
-      if (bfs_queue.empty()) {
-	bfs_queue.push(s);
-	graph->first(actual_edge, s);
-	if (graph->valid(actual_edge)) { 
-	  Node w=graph->bNode(actual_edge);
-	  if (!reached[w]) {
-	    bfs_queue.push(w);
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	} 
-      } else {
-	bfs_queue.push(s);
-      }
-    }
-    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
-    /// its \c operator++() iterates on the edges in a bfs order.
-    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
-    operator++() { 
-      if (graph->valid(actual_edge)) { 
-	graph->next(actual_edge);
-	if (graph->valid(actual_edge)) {
-	  Node w=graph->bNode(actual_edge);
-	  if (!reached[w]) {
-	    bfs_queue.push(w);
-	    reached.set(w, true);
-	    b_node_newly_reached=true;
-	  } else {
-	    b_node_newly_reached=false;
-	  }
-	}
-      } else {
-	bfs_queue.pop(); 
-	if (!bfs_queue.empty()) {
-	  graph->first(actual_edge, bfs_queue.front());
-	  if (graph->valid(actual_edge)) {
-	    Node w=graph->bNode(actual_edge);
-	    if (!reached[w]) {
-	      bfs_queue.push(w);
-	      reached.set(w, true);
-	      b_node_newly_reached=true;
-	    } else {
-	      b_node_newly_reached=false;
-	    }
-	  }
-	}
-      }
-      return *this;
-    }
-    ///
-    bool finished() const { return bfs_queue.empty(); }
-    /// The conversion operator makes for converting the bfs-iterator 
-    /// to an \c out-edge-iterator.
-    ///\bug Edge have to be in HUGO 0.2
-    operator OutEdgeIt() const { return actual_edge; }
-    ///
-    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    ///
-    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    ///
-    Node aNode() const { return bfs_queue.front(); }
-    ///
-    Node bNode() const { return graph->bNode(actual_edge); }
-    ///
-    const ReachedMap& getReachedMap() const { return reached; }
-    ///
-    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
-  };  
-
-  /// Bfs searches for the nodes wich are not marked in 
-  /// \c reached_map
-  /// Reached have to work as a read-write bool Node-map, 
-  /// Pred is a write Edge Node-map and
-  /// Dist is a read-write int Node-map, have to be. 
-  ///\todo In fact onsly simple operations requirement are needed for 
-  /// Dist::Value.
-  template <typename Graph, 
-	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
-	    typename PredMap
-	    =typename Graph::template NodeMap<typename Graph::Edge>, 
-	    typename DistMap=typename Graph::template NodeMap<int> > 
-  class Bfs : public BfsIterator<Graph, ReachedMap> {
-    typedef BfsIterator<Graph, ReachedMap> Parent;
-  protected:
-    typedef typename Parent::Node Node;
-    PredMap& pred;
-    DistMap& dist;
-  public:
-    /// The algorithm will search in a bfs order for 
-    /// the nodes which are \c false initially. 
-    /// The constructor makes no initial changes on the maps.
-    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
-    /// \c s is marked to be reached and pushed in the bfs queue.
-    /// If the queue is empty, then the first out-edge is processed.
-    /// If \c s was not marked previously, then 
-    /// in addition its pred is set to be \c INVALID, and dist to \c 0. 
-    /// if \c s was marked previuosly, then it is simply pushed.
-    void push(Node s) { 
-      if (this->reached[s]) {
-	Parent::pushAndSetReached(s);
-      } else {
-	Parent::pushAndSetReached(s);
-	pred.set(s, INVALID);
-	dist.set(s, 0);
-      }
-    }
-    /// A bfs is processed from \c s.
-    void run(Node s) {
-      push(s);
-      while (!this->finished()) this->operator++();
-    }
-    /// Beside the bfs iteration, \c pred and \dist are saved in a 
-    /// newly reached node. 
-    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
-      Parent::operator++();
-      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
-      {
-	pred.set(this->bNode(), this->actual_edge);
-	dist.set(this->bNode(), dist[this->aNode()]);
-      }
-      return *this;
-    }
-    ///
-    const PredMap& getPredMap() const { return pred; }
-    ///
-    const DistMap& getDistMap() const { return dist; }
-  };
-
-  /// Dfs searches for the nodes wich are not marked in 
-  /// \c reached_map
-  /// Reached have to be a read-write bool Node-map.
-  template <typename Graph, /*typename OutEdgeIt,*/ 
-	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
-  class DfsIterator {
-  protected:
-    typedef typename Graph::Node Node;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    const Graph* graph;
-    std::stack<OutEdgeIt> dfs_stack;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
-    Node actual_node;
-    ReachedMap& reached;
-    bool own_reached_map;
-  public:
-    /// In that constructor \c _reached have to be a reference 
-    /// for a bool Node-map. The algorithm will search in a dfs order for 
-    /// the nodes which are \c false initially
-    DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
-      graph(&_graph), reached(_reached), 
-      own_reached_map(false) { }
-    /// The same as above, but the map of reached nodes is 
-    /// constructed dynamically 
-    /// to everywhere false.
-    DfsIterator(const Graph& _graph) : 
-      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
-      own_reached_map(true) { }
-    ~DfsIterator() { if (own_reached_map) delete &reached; }
-    /// This method markes s reached and first out-edge is processed.
-    void pushAndSetReached(Node s) { 
-      actual_node=s;
-      reached.set(s, true);
-      OutEdgeIt e;
-      graph->first(e, s);
-      dfs_stack.push(e); 
-    }
-    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, 
-    /// its \c operator++() iterates on the edges in a dfs order.
-    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
-    operator++() { 
-      actual_edge=dfs_stack.top();
-      //actual_node=G.aNode(actual_edge);
-      if (graph->valid(actual_edge)/*.valid()*/) { 
-	Node w=graph->bNode(actual_edge);
-	actual_node=w;
-	if (!reached[w]) {
-	  OutEdgeIt e;
-	  graph->first(e, w);
-	  dfs_stack.push(e);
-	  reached.set(w, true);
-	  b_node_newly_reached=true;
-	} else {
-	  actual_node=graph->aNode(actual_edge);
-	  graph->next(dfs_stack.top());
-	  b_node_newly_reached=false;
-	}
-      } else {
-	//actual_node=G.aNode(dfs_stack.top());
-	dfs_stack.pop();
-      }
-      return *this;
-    }
-    ///
-    bool finished() const { return dfs_stack.empty(); }
-    ///
-    operator OutEdgeIt() const { return actual_edge; }
-    ///
-    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    ///
-    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    ///
-    Node aNode() const { return actual_node; /*FIXME*/}
-    ///
-    Node bNode() const { return graph->bNode(actual_edge); }
-    ///
-    const ReachedMap& getReachedMap() const { return reached; }
-    ///
-    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
-  };
-
-  /// Dfs searches for the nodes wich are not marked in 
-  /// \c reached_map
-  /// Reached is a read-write bool Node-map, 
-  /// Pred is a write Node-map, have to be.
-  template <typename Graph, 
-	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
-	    typename PredMap
-	    =typename Graph::template NodeMap<typename Graph::Edge> > 
-  class Dfs : public DfsIterator<Graph, ReachedMap> {
-    typedef DfsIterator<Graph, ReachedMap> Parent;
-  protected:
-    typedef typename Parent::Node Node;
-    PredMap& pred;
-  public:
-    /// The algorithm will search in a dfs order for 
-    /// the nodes which are \c false initially. 
-    /// The constructor makes no initial changes on the maps.
-    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
-    /// \c s is marked to be reached and pushed in the bfs queue.
-    /// If the queue is empty, then the first out-edge is processed.
-    /// If \c s was not marked previously, then 
-    /// in addition its pred is set to be \c INVALID. 
-    /// if \c s was marked previuosly, then it is simply pushed.
-    void push(Node s) { 
-      if (this->reached[s]) {
-	Parent::pushAndSetReached(s);
-      } else {
-	Parent::pushAndSetReached(s);
-	pred.set(s, INVALID);
-      }
-    }
-    /// A bfs is processed from \c s.
-    void run(Node s) {
-      push(s);
-      while (!this->finished()) this->operator++();
-    }
-    /// Beside the dfs iteration, \c pred is saved in a 
-    /// newly reached node. 
-    Dfs<Graph, ReachedMap, PredMap> operator++() {
-      Parent::operator++();
-      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
-      {
-	pred.set(this->bNode(), this->actual_edge);
-      }
-      return *this;
-    }
-    ///
-    const PredMap& getPredMap() const { return pred; }
-  };
-
-
-} // namespace hugo
-
-#endif //HUGO_BFS_ITERATOR_H
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bfsit_vs_byhand.cc
--- a/src/work/marci/bfsit_vs_byhand.cc	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/bfsit_vs_byhand.cc	Mon May 10 16:59:20 2004 +0000
@@ -7,7 +7,7 @@
 #include <hugo/dimacs.h>
 #include <hugo/time_measure.h>
 #include <for_each_macros.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 
 using namespace hugo;
 
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bipartite_graph_wrapper_test.cc
--- a/src/work/marci/bipartite_graph_wrapper_test.cc	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Mon May 10 16:59:20 2004 +0000
@@ -8,7 +8,7 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
 #include <for_each_macros.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <hugo/graph_wrapper.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bipartite_matching_try.cc
--- a/src/work/marci/bipartite_matching_try.cc	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/bipartite_matching_try.cc	Mon May 10 16:59:20 2004 +0000
@@ -9,7 +9,7 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
 #include <for_each_macros.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <hugo/graph_wrapper.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bipartite_matching_try_2.cc
--- a/src/work/marci/bipartite_matching_try_2.cc	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/bipartite_matching_try_2.cc	Mon May 10 16:59:20 2004 +0000
@@ -9,7 +9,7 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
 #include <for_each_macros.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
 #include <max_flow.h>
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/bipartite_matching_try_3.cc
--- a/src/work/marci/bipartite_matching_try_3.cc	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/bipartite_matching_try_3.cc	Mon May 10 16:59:20 2004 +0000
@@ -8,7 +8,7 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
 #include <for_each_macros.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
 #include <max_flow.h>
diff -r 6c6c0eb89b47 -r 580b329c2a0c src/work/marci/iterator_bfs_demo.cc
--- a/src/work/marci/iterator_bfs_demo.cc	Mon May 10 16:52:51 2004 +0000
+++ b/src/work/marci/iterator_bfs_demo.cc	Mon May 10 16:59:20 2004 +0000
@@ -5,7 +5,7 @@
 
 #include <list_graph.h>
 //#include <smart_graph.h>
-#include <bfs_iterator.h>
+#include <bfs_dfs.h>
 #include <hugo/graph_wrapper.h>
 
 using namespace hugo;