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