diff -r 4a2236cc98a0 -r 42cce226b87b lemon/bfs.h
--- a/lemon/bfs.h	Tue Nov 21 17:28:08 2006 +0000
+++ b/lemon/bfs.h	Tue Nov 21 18:22:08 2006 +0000
@@ -587,9 +587,9 @@
       while ( !emptyQueue() ) processNextNode();
     }
     
-    ///Executes the algorithm until \c dest is reached.
+    ///Executes the algorithm until \c dest is the next node to processed.
 
-    ///Executes the algorithm until \c dest is reached.
+    ///Executes the algorithm until \c dest is the next node to processed.
     ///
     ///\pre init() must be called and at least one node should be added
     ///with addSource() before using this function.
@@ -614,8 +614,9 @@
     ///\pre init() must be called and at least one node should be added
     ///with addSource() before using this function.
     ///
-    ///\param nm must be a bool (or convertible) node map. The algorithm
-    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
+    ///\param nm must be a bool (or convertible) node map. The
+    ///algorithm will stop when for the next processable node \c v is
+    ///<tt>nm[v]</tt> true.
     ///\todo query the reached target
     template<class NM>
     void start(const NM &nm)
@@ -633,11 +634,11 @@
     ///- The shortest path tree.
     ///- The distance of each node from the root.
     ///
-    ///\note d.run(s) is just a shortcut of the following code.
+    ///\note b.run(s) is just a shortcut of the following code.
     ///\code
-    ///  d.init();
-    ///  d.addSource(s);
-    ///  d.start();
+    ///  b.init();
+    ///  b.addSource(s);
+    ///  b.start();
     ///\endcode
     void run(Node s) {
       init();
@@ -651,12 +652,12 @@
     ///
     ///\return The length of the shortest s---t path if there exists one,
     ///0 otherwise.
-    ///\note Apart from the return value, d.run(s) is
+    ///\note Apart from the return value, b.run(s) is
     ///just a shortcut of the following code.
     ///\code
-    ///  d.init();
-    ///  d.addSource(s);
-    ///  d.start(t);
+    ///  b.init();
+    ///  b.addSource(s);
+    ///  b.start(t);
     ///\endcode
     int run(Node s,Node t) {
       init();
@@ -671,7 +672,7 @@
     ///The result of the %BFS algorithm can be obtained using these
     ///functions.\n
     ///Before the use of these functions,
-    ///either run() or start() must be called.
+    ///either run() or start() must be calleb.
     
     ///@{
 
@@ -943,7 +944,7 @@
     ///The type of the map that stores the dists of the nodes.
     typedef typename TR::DistMap DistMap;
 
-public:
+  public:
     /// Constructor.
     BfsWizard() : TR() {}
 
@@ -1104,6 +1105,495 @@
     return BfsWizard<BfsWizardBase<GR> >(g,s);
   }
 
+#ifdef DOXYGEN
+  /// \brief Visitor class for bfs.
+  ///  
+  /// It gives a simple interface for a functional interface for bfs 
+  /// traversal. The traversal on a linear data structure. 
+  template <typename _Graph>
+  struct BfsVisitor {
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::Node Node;
+    /// \brief Called when the edge reach a node.
+    /// 
+    /// It is called when the bfs find an edge which target is not
+    /// reached yet.
+    void discover(const Edge& edge) {}
+    /// \brief Called when the node reached first time.
+    /// 
+    /// It is Called when the node reached first time.
+    void reach(const Node& node) {}
+    /// \brief Called when the edge examined but target of the edge 
+    /// already discovered.
+    /// 
+    /// It called when the edge examined but the target of the edge 
+    /// already discovered.
+    void examine(const Edge& edge) {}
+    /// \brief Called for the source node of the bfs.
+    /// 
+    /// It is called for the source node of the bfs.
+    void start(const Node& node) {}
+    /// \brief Called when the node processed.
+    /// 
+    /// It is Called when the node processed.
+    void process(const Node& node) {}
+  };
+#else
+  template <typename _Graph>
+  struct BfsVisitor {
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::Node Node;
+    void discover(const Edge&) {}
+    void reach(const Node&) {}
+    void examine(const Edge&) {}
+    void start(const Node&) {}
+    void process(const Node&) {}
+
+    template <typename _Visitor>
+    struct Constraints {
+      void constraints() {
+	Edge edge;
+	Node node;
+	visitor.discover(edge);
+	visitor.reach(node);
+	visitor.examine(edge);
+	visitor.start(node);
+        visitor.process(node);
+      }
+      _Visitor& visitor;
+    };
+  };
+#endif
+
+  /// \brief Default traits class of BfsVisit class.
+  ///
+  /// Default traits class of BfsVisit class.
+  /// \param _Graph Graph type.
+  template<class _Graph>
+  struct BfsVisitDefaultTraits {
+
+    /// \brief The graph type the algorithm runs on. 
+    typedef _Graph Graph;
+
+    /// \brief The type of the map that indicates which nodes are reached.
+    /// 
+    /// The type of the map that indicates which nodes are reached.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    /// \todo named parameter to set this type, function to read and write.
+    typedef typename Graph::template NodeMap<bool> ReachedMap;
+
+    /// \brief Instantiates a ReachedMap.
+    ///
+    /// This function instantiates a \ref ReachedMap. 
+    /// \param graph is the graph, to which
+    /// we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const Graph &graph) {
+      return new ReachedMap(graph);
+    }
+
+  };
+  
+  /// %BFS Visit algorithm class.
+  
+  /// \ingroup flowalgs
+  /// This class provides an efficient implementation of the %BFS algorithm
+  /// with visitor interface.
+  ///
+  /// The %BfsVisit class provides an alternative interface to the Bfs
+  /// class. It works with callback mechanism, the BfsVisit object calls
+  /// on every bfs event the \c Visitor class member functions. 
+  ///
+  /// \param _Graph The graph type the algorithm runs on. The default value is
+  /// \ref ListGraph. The value of _Graph is not used directly by Bfs, it
+  /// is only passed to \ref BfsDefaultTraits.
+  /// \param _Visitor The Visitor object for the algorithm. The 
+  /// \ref BfsVisitor "BfsVisitor<_Graph>" is an empty Visitor which
+  /// does not observe the Bfs events. If you want to observe the bfs
+  /// events you should implement your own Visitor class.
+  /// \param _Traits Traits class to set various data types used by the 
+  /// algorithm. The default traits class is
+  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Graph>".
+  /// See \ref BfsVisitDefaultTraits for the documentation of
+  /// a Bfs visit traits class.
+  ///
+  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
+#ifdef DOXYGEN
+  template <typename _Graph, typename _Visitor, typename _Traits>
+#else
+  template <typename _Graph = ListGraph,
+	    typename _Visitor = BfsVisitor<_Graph>,
+	    typename _Traits = BfsDefaultTraits<_Graph> >
+#endif
+  class BfsVisit {
+  public:
+    
+    /// \brief \ref Exception for uninitialized parameters.
+    ///
+    /// This error represents problems in the initialization
+    /// of the parameters of the algorithms.
+    class UninitializedParameter : public lemon::UninitializedParameter {
+    public:
+      virtual const char* what() const throw() 
+      {
+	return "lemon::BfsVisit::UninitializedParameter";
+      }
+    };
+
+    typedef _Traits Traits;
+
+    typedef typename Traits::Graph Graph;
+
+    typedef _Visitor Visitor;
+
+    ///The type of the map indicating which nodes are reached.
+    typedef typename Traits::ReachedMap ReachedMap;
+
+  private:
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+
+    /// Pointer to the underlying graph.
+    const Graph *_graph;
+    /// Pointer to the visitor object.
+    Visitor *_visitor;
+    ///Pointer to the map of reached status of the nodes.
+    ReachedMap *_reached;
+    ///Indicates if \ref _reached is locally allocated (\c true) or not.
+    bool local_reached;
+
+    std::vector<typename Graph::Node> _list;
+    int _list_front, _list_back;
+
+    /// \brief Creates the maps if necessary.
+    ///
+    /// Creates the maps if necessary.
+    void create_maps() {
+      if(!_reached) {
+	local_reached = true;
+	_reached = Traits::createReachedMap(*_graph);
+      }
+    }
+
+  protected:
+
+    BfsVisit() {}
+    
+  public:
+
+    typedef BfsVisit Create;
+
+    /// \name Named template parameters
+
+    ///@{
+    template <class T>
+    struct DefReachedMapTraits : public Traits {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &graph) {
+	throw UninitializedParameter();
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// ReachedMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
+    template <class T>
+    struct DefReachedMap : public BfsVisit< Graph, Visitor,
+					    DefReachedMapTraits<T> > {
+      typedef BfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
+    };
+    ///@}
+
+  public:      
+    
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    ///
+    /// \param graph the graph the algorithm will run on.
+    /// \param visitor The visitor of the algorithm.
+    ///
+    BfsVisit(const Graph& graph, Visitor& visitor) 
+      : _graph(&graph), _visitor(&visitor),
+	_reached(0), local_reached(false) {}
+    
+    /// \brief Destructor.
+    ///
+    /// Destructor.
+    ~BfsVisit() {
+      if(local_reached) delete _reached;
+    }
+
+    /// \brief Sets the map indicating if a node is reached.
+    ///
+    /// Sets the map indicating if a node is reached.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return <tt> (*this) </tt>
+    BfsVisit &reachedMap(ReachedMap &m) {
+      if(local_reached) {
+	delete _reached;
+	local_reached = false;
+      }
+      _reached = &m;
+      return *this;
+    }
+
+  public:
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// \n
+    /// If you need more control on the execution,
+    /// first you must call \ref init(), then you can adda source node
+    /// with \ref addSource().
+    /// Finally \ref start() will perform the actual path
+    /// computation.
+
+    /// @{
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures.
+    ///
+    void init() {
+      create_maps();
+      _list.resize(countNodes(*_graph));
+      _list_front = _list_back = -1;
+      for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
+	_reached->set(u, false);
+      }
+    }
+    
+    /// \brief Adds a new source node.
+    ///
+    /// Adds a new source node to the set of nodes to be processed.
+    void addSource(Node s) {
+      if(!(*_reached)[s]) {
+	  _reached->set(s,true);
+	  _visitor->start(s);
+	  _visitor->reach(s);
+          _list[++_list_back] = s;
+	}
+    }
+    
+    /// \brief Processes the next node.
+    ///
+    /// Processes the next node.
+    ///
+    /// \return The processed node.
+    ///
+    /// \pre The queue must not be empty!
+    Node processNextNode() { 
+      Node n = _list[++_list_front];
+      _visitor->process(n);
+      Edge e;
+      for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
+        Node m = _graph->target(e);
+        if (!(*_reached)[m]) {
+          _visitor->discover(e);
+          _visitor->reach(m);
+          _reached->set(m, true);
+          _list[++_list_back] = m;
+        } else {
+          _visitor->examine(e);
+        }
+      }
+      return n;
+    }
+
+    /// \brief Processes the next node.
+    ///
+    /// Processes the next node. And checks that the given target node
+    /// is reached. If the target node is reachable from the processed
+    /// node then the reached parameter will be set true. The reached
+    /// parameter should be initially false.
+    ///
+    /// \param target The target node.
+    /// \retval reached Indicates that the target node is reached.
+    /// \return The processed node.
+    ///
+    /// \warning The queue must not be empty!
+    Node processNextNode(Node target, bool& reached) {
+      Node n = _list[++_list_front];
+      _visitor->process(n);
+      Edge e;
+      for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
+        Node m = _graph->target(e);
+        if (!(*_reached)[m]) {
+          _visitor->discover(e);
+          _visitor->reach(m);
+          _reached->set(m, true);
+          _list[++_list_back] = m;
+          reached = reached || (target == m);
+        } else {
+          _visitor->examine(e);
+        }
+      }
+      return n;
+    }
+
+    /// \brief Processes the next node.
+    ///
+    /// Processes the next node. And checks that at least one of
+    /// reached node has true value in the \c nm nodemap. If one node
+    /// with true value is reachable from the processed node then the
+    /// reached parameter will be set true. The reached parameter
+    /// should be initially false.
+    ///
+    /// \param target The nodemaps of possible targets.
+    /// \retval reached Indicates that one of the target nodes is reached.
+    /// \return The processed node.
+    ///
+    /// \warning The queue must not be empty!
+    template <typename NM>
+    Node processNextNode(const NM& nm, bool& reached) {
+      Node n = _list[++_list_front];
+      _visitor->process(n);
+      Edge e;
+      for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
+        Node m = _graph->target(e);
+        if (!(*_reached)[m]) {
+          _visitor->discover(e);
+          _visitor->reach(m);
+          _reached->set(m, true);
+          _list[++_list_back] = m;
+          reached = reached || nm[m];
+        } else {
+          _visitor->examine(e);
+        }
+      }
+      return n;
+    }
+
+    /// \brief Next node to be processed.
+    ///
+    /// Next node to be processed.
+    ///
+    /// \return The next node to be processed or INVALID if the stack is
+    /// empty.
+    Node nextNode() { 
+      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
+    }
+
+    /// \brief Returns \c false if there are nodes
+    /// to be processed in the queue
+    ///
+    /// Returns \c false if there are nodes
+    /// to be processed in the queue
+    bool emptyQueue() { return _list_front == _list_back; }
+
+    /// \brief Returns the number of the nodes to be processed.
+    ///
+    /// Returns the number of the nodes to be processed in the queue.
+    int queueSize() { return _list_back - _list_front; }
+    
+    /// \brief Executes the algorithm.
+    ///
+    /// Executes the algorithm.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    void start() {
+      while ( !emptyQueue() ) processNextNode();
+    }
+    
+    /// \brief Executes the algorithm until \c dest will be next processed.
+    ///
+    /// Executes the algorithm until \c dest will be next processed.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    void start(Node dest) {
+      bool reached = false;
+      while (!emptyQueue() && !reached) { 
+	processNextNode(dest, reached);
+      }
+    }
+    
+    /// \brief Executes the algorithm until a condition is met.
+    ///
+    /// Executes the algorithm until a condition is met.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    ///\param nm must be a bool (or convertible) node map. The
+    ///algorithm will stop when it reaches a node \c v with
+    ///<tt>nm[v]</tt> true.
+    template <typename NM>
+    void start(const NM &nm) {
+      bool reached = false;
+      while (!emptyQueue() && !reached) {
+        processNextNode(nm, reached);
+      }
+    }
+
+    /// \brief Runs %BFSVisit algorithm from node \c s.
+    ///
+    /// This method runs the %BFS algorithm from a root node \c s.
+    /// \note b.run(s) is just a shortcut of the following code.
+    ///\code
+    ///   b.init();
+    ///   b.addSource(s);
+    ///   b.start();
+    ///\endcode
+    void run(Node s) {
+      init();
+      addSource(s);
+      start();
+    }
+
+    /// \brief Runs %BFSVisit algorithm to visit all nodes in the graph.
+    ///    
+    /// This method runs the %BFS algorithm in order to
+    /// compute the %BFS path to each node. The algorithm computes
+    /// - The %BFS tree.
+    /// - The distance of each node from the root in the %BFS tree.
+    ///
+    ///\note b.run() is just a shortcut of the following code.
+    ///\code
+    ///  b.init();
+    ///  for (NodeIt it(graph); it != INVALID; ++it) {
+    ///    if (!b.reached(it)) {
+    ///      b.addSource(it);
+    ///      b.start();
+    ///    }
+    ///  }
+    ///\endcode
+    void run() {
+      init();
+      for (NodeIt it(*_graph); it != INVALID; ++it) {
+        if (!reached(it)) {
+          addSource(it);
+          start();
+        }
+      }
+    }
+    ///@}
+
+    /// \name Query Functions
+    /// The result of the %BFS algorithm can be obtained using these
+    /// functions.\n
+    /// Before the use of these functions,
+    /// either run() or start() must be called.
+    ///@{
+
+    /// \brief Checks if a node is reachable from the root.
+    ///
+    /// Returns \c true if \c v is reachable from the root(s).
+    /// \warning The source nodes are inditated as unreachable.
+    /// \pre Either \ref run() or \ref start()
+    /// must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    ///@}
+  };
+
 } //END OF NAMESPACE LEMON
 
 #endif