Changeset 1218:5331168bbb18 in lemon-0.x for src/lemon/bfs.h

Timestamp:

03/16/05 08:56:25 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1638

Message:

• Several updates and clarifications on dijkstra.h
• bfs.h and dfs.h is synchronized with dijkstra.h

File:

• src/lemon/bfs.h (modified) (6 diffs)

src/lemon/bfs.h

@@ -21 +21 @@
 ///\file
 ///\brief Bfs algorithm.
-///
-///\todo Revise Manual.
-
-#include <lemon/bin_heap.h>
+
+#include <lemon/list_graph.h>
+#include <lemon/graph_utils.h>
 #include <lemon/invalid.h>
-#include <lemon/graph_utils.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
 
 namespace lemon {
 
-/// \addtogroup flowalgs
-/// @{
-
+
+  
+  ///Default traits class of Bfs class.
+
+  ///Default traits class of Bfs class.
+  ///\param GR Graph type.
+  template<class GR>
+  struct BfsDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the shortest paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G) 
+    {
+      return new PredMap(G);
+    }
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///
+//     ///The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+//     ///
+//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
+//     ///Instantiates a PredNodeMap.
+    
+//     ///This function instantiates a \ref PredNodeMap. 
+//     ///\param G is the graph, to which
+//     ///we would like to define the \ref PredNodeMap
+//     static PredNodeMap *createPredNodeMap(const GR &G)
+//     {
+//       return new PredNodeMap();
+//     }
+
+    ///The type of the map that indicates which nodes are processed.
+ 
+    ///The type of the map that indicates which nodes are processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///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 concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef typename Graph::template NodeMap<bool> ReachedMap;
+    ///Instantiates a ReachedMap.
+ 
+    ///This function instantiates a \ref ReachedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const GR &G)
+    {
+      return new ReachedMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<int> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap(G);
+    }
+  };
+  
   ///%BFS algorithm class.
-
-  ///This class provides an efficient implementation of %BFS algorithm.
-  ///\param GR The graph type the algorithm runs on.
-  ///This class does the same as Dijkstra does with constant 1 edge length,
-  ///but it is faster.
+  
+  ///\ingroup flowalgs
+  ///This class provides an efficient implementation of the %BFS algorithm.
   ///
-  ///\author Alpar Juttner
+  ///\param GR The graph type the algorithm runs on. The default value is
+  ///\ref ListGraph. The value of GR is not used directly by Bfs, it
+  ///is only passed to \ref BfsDefaultTraits.
+  ///\param TR Traits class to set various data types used by the algorithm.
+  ///The default traits class is
+  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
+  ///See \ref BfsDefaultTraits for the documentation of
+  ///a Bfs traits class.
+  ///
+  ///\author Jacint Szabo and Alpar Juttner
+  ///\todo A compare object would be nice.
 
 #ifdef DOXYGEN
-  template <typename GR>
+  template <typename GR,
+            typename TR>
 #else
-  template <typename GR>
+  template <typename GR=ListGraph,
+            typename TR=BfsDefaultTraits<GR> >
 #endif
-  class Bfs{
+  class Bfs {
   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* exceptionName() const {
+        return "lemon::Bfs::UninitializedParameter";
+      }
+    };
+
+    typedef TR Traits;
     ///The type of the underlying graph.
-    typedef GR Graph;
+    typedef typename TR::Graph Graph;
     ///\e
     typedef typename Graph::Node Node;
@@ -62 +175 @@
     ///\brief The type of the map that stores the last
     ///edges of the shortest paths.
-    typedef typename Graph::template NodeMap<Edge> PredMap;
-    ///\brief The type of the map that stores the last but one
-    ///nodes of the shortest paths.
-    typedef typename Graph::template NodeMap<Node> PredNodeMap;
+    typedef typename TR::PredMap PredMap;
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map indicating which nodes are reached.
+    typedef typename TR::ReachedMap ReachedMap;
+    ///The type of the map indicating which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
     ///The type of the map that stores the dists of the nodes.
-    typedef typename Graph::template NodeMap<int> DistMap;
-
+    typedef typename TR::DistMap DistMap;
   private:
     /// Pointer to the underlying graph.
     const Graph *G;
     ///Pointer to the map of predecessors edges.
-    PredMap *predecessor;
-    ///Indicates if \ref predecessor is locally allocated (\c true) or not.
-    bool local_predecessor;
-    ///Pointer to the map of predecessors nodes.
-    PredNodeMap *pred_node;
-    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
-    bool local_pred_node;
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    bool local_pred;
+//     ///Pointer to the map of predecessors nodes.
+//     PredNodeMap *_predNode;
+//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
+//     bool local_predNode;
     ///Pointer to the map of distances.
-    DistMap *distance;
-    ///Indicates if \ref distance is locally allocated (\c true) or not.
-    bool local_distance;
-
-    ///The source node of the last execution.
-    Node source;
-
-
-    ///Initializes the maps.
-    void init_maps() 
-    {
-      if(!predecessor) {
-        local_predecessor = true;
-        predecessor = new PredMap(*G);
-      }
-      if(!pred_node) {
-        local_pred_node = true;
-        pred_node = new PredNodeMap(*G);
-      }
-      if(!distance) {
-        local_distance = true;
-        distance = new DistMap(*G);
-      }
-    }
-    
-  public :    
+    DistMap *_dist;
+    ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    bool local_dist;
+    ///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;
+    ///Pointer to the map of processed status of the nodes.
+    ProcessedMap *_processed;
+    ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    bool local_processed;
+
+    std::vector<typename Graph::Node> _queue;
+    int _queue_head,_queue_tail,_queue_next_dist;
+    int _curr_dist;
+//     ///The source node of the last execution.
+//     Node source;
+
+    ///Creates the maps if necessary.
+    
+    ///\todo Error if \c G are \c NULL.
+    ///\todo Better memory allocation (instead of new).
+    void create_maps() 
+    {
+      if(!_pred) {
+        local_pred = true;
+        _pred = Traits::createPredMap(*G);
+      }
+//       if(!_predNode) {
+//      local_predNode = true;
+//      _predNode = Traits::createPredNodeMap(*G);
+//       }
+      if(!_dist) {
+        local_dist = true;
+        _dist = Traits::createDistMap(*G);
+      }
+      if(!_reached) {
+        local_reached = true;
+        _reached = Traits::createReachedMap(*G);
+      }
+      if(!_processed) {
+        local_processed = true;
+        _processed = Traits::createProcessedMap(*G);
+      }
+    }
+    
+  public :
+ 
+    ///\name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    template <class T>
+    class DefPredMap : public Bfs< Graph,
+                                        DefPredMapTraits<T> > { };
+    
+//     template <class T>
+//     struct DefPredNodeMapTraits : public Traits {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) 
+//       {
+//      throw UninitializedParameter();
+//       }
+//     };
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+//     ///
+//     template <class T>
+//     class DefPredNodeMap : public Bfs< Graph,
+//                                          LengthMap,
+//                                          DefPredNodeMapTraits<T> > { };
+    
+    template <class T>
+    struct DefDistMapTraits : public Traits {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+    ///
+    template <class T>
+    class DefDistMap : public Bfs< Graph,
+                                   DefDistMapTraits<T> > { };
+    
+    template <class T>
+    struct DefReachedMapTraits : public Traits {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+    ///
+    template <class T>
+    class DefReachedMap : public Bfs< Graph,
+                                      DefReachedMapTraits<T> > { };
+    
+    struct DefGraphReachedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        return new ReachedMap(G);
+      }
+    };
+    template <class T>
+    struct DefProcessedMapTraits : public Traits {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+    ///
+    template <class T>
+    class DefProcessedMap : public Bfs< Graph,
+                                        DefProcessedMapTraits<T> > { };
+    
+    struct DefGraphProcessedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
+      {
+        return new ProcessedMap(G);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter"
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
+    ///If you don't set it explicitely, it will be automatically allocated.
+    template <class T>
+    class DefProcessedMapToBeDefaultMap :
+      public Bfs< Graph,
+                  DefGraphProcessedMapTraits> { };
+    
+    ///@}
+
+  public:      
+    
     ///Constructor.
     
@@ -113 +365 @@
     Bfs(const Graph& _G) :
       G(&_G),
-      predecessor(NULL), local_predecessor(false),
-      pred_node(NULL), local_pred_node(false),
-      distance(NULL), local_distance(false)
+      _pred(NULL), local_pred(false),
+//       _predNode(NULL), local_predNode(false),
+      _dist(NULL), local_dist(false),
+      _reached(NULL), local_reached(false),
+      _processed(NULL), local_processed(false)
     { }
     
@@ -121 +375 @@
     ~Bfs() 
     {
-      if(local_predecessor) delete predecessor;
-      if(local_pred_node) delete pred_node;
-      if(local_distance) delete distance;
+      if(local_pred) delete _pred;
+//       if(local_predNode) delete _predNode;
+      if(local_dist) delete _dist;
+      if(local_reached) delete _reached;
+      if(local_processed) delete _processed;
     }
 
@@ -133 +389 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Bfs &setPredMap(PredMap &m) 
-    {
-      if(local_predecessor) {
-        delete predecessor;
-        local_predecessor=false;
-      }
-      predecessor = &m;
+    Bfs &predMap(PredMap &m) 
+    {
+      if(local_pred) {
+        delete _pred;
+        local_pred=false;
+      }
+      _pred = &m;
       return *this;
     }
 
-    ///Sets the map storing the predecessor nodes.
-
-    ///Sets the map storing the predecessor nodes.
+    ///Sets the map indicating the reached nodes.
+
+    ///Sets the map indicating the reached nodes.
     ///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>
-    Bfs &setPredNodeMap(PredNodeMap &m) 
-    {
-      if(local_pred_node) {
-        delete pred_node;
-        local_pred_node=false;
-      }
-      pred_node = &m;
+    Bfs &reachedMap(ReachedMap &m) 
+    {
+      if(local_reached) {
+        delete _reached;
+        local_reached=false;
+      }
+      _reached = &m;
       return *this;
     }
+
+    ///Sets the map indicating the processed nodes.
+
+    ///Sets the map indicating the processed nodes.
+    ///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>
+    Bfs &processedMap(ProcessedMap &m) 
+    {
+      if(local_processed) {
+        delete _processed;
+        local_processed=false;
+      }
+      _processed = &m;
+      return *this;
+    }
+
+//     ///Sets the map storing the predecessor nodes.
+
+//     ///Sets the map storing the predecessor nodes.
+//     ///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>
+//     Bfs &predNodeMap(PredNodeMap &m) 
+//     {
+//       if(local_predNode) {
+//      delete _predNode;
+//      local_predNode=false;
+//       }
+//       _predNode = &m;
+//       return *this;
+//     }
 
     ///Sets the map storing the distances calculated by the algorithm.
@@ -167 +457 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Bfs &setDistMap(DistMap &m) 
-    {
-      if(local_distance) {
-        delete distance;
-        local_distance=false;
-      }
-      distance = &m;
+    Bfs &distMap(DistMap &m) 
+    {
+      if(local_dist) {
+        delete _dist;
+        local_dist=false;
+      }
+      _dist = &m;
       return *this;
     }
-    
-  ///Runs %BFS algorithm from node \c s.
-
-  ///This method runs the %BFS algorithm from a root node \c s
-  ///in order to
-  ///compute a
-  ///shortest path to each node. The algorithm computes
-  ///- The %BFS tree.
-  ///- The distance of each node from the root.
- 
+
+  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 add several source nodes
+    ///with \ref addSource().
+    ///Finally \ref start() will perform the actual path
+    ///computation.
+
+    ///@{
+
+    ///Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
+    void init()
+    {
+      create_maps();
+      _queue.resize(countNodes(*G));
+      _queue_head=_queue_tail=0;
+      _curr_dist=1;
+      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
+        _pred->set(u,INVALID);
+//      _predNode->set(u,INVALID);
+        _reached->set(u,false);
+        _processed->set(u,false);
+      }
+    }
+    
+    ///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);
+          _pred->set(s,INVALID);
+          _dist->set(s,0);
+          _queue[_queue_head++]=s;
+          _queue_next_dist=_queue_head;
+        }
+    }
+    
+    ///Processes the next node.
+
+    ///Processes the next node.
+    ///
+    ///\warning The queue must not be empty!
+    void processNextNode()
+    {
+      if(_queue_tail==_queue_next_dist) {
+        _curr_dist++;
+        _queue_next_dist=_queue_head;
+      }
+      Node n=_queue[_queue_tail++];
+      _processed->set(n,true);
+      Node m;
+      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
+        if(!(*_reached)[m=G->target(e)]) {
+          _queue[_queue_head++]=m;
+          _reached->set(m,true);
+          _pred->set(m,e);
+//        _pred_node->set(m,n);
+          _dist->set(m,_curr_dist);
+        }
+    }
+      
+    ///\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 _queue_tail==_queue_head; }
+    ///Returns the number of the nodes to be processed.
+    
+    ///Returns the number of the nodes to be processed in the queue.
+    ///
+    int queueSize() { return _queue_head-_queue_tail; }
+    
+    ///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.
+    ///
+    ///This method runs the %BFS algorithm from the root node(s)
+    ///in order to
+    ///compute the
+    ///shortest path to each node. The algorithm computes
+    ///- The shortest path tree.
+    ///- The distance of each node from the root(s).
+    ///
+    void start()
+    {
+      while ( !emptyQueue() ) processNextNode();
+    }
+    
+    ///Executes the algorithm until \c dest is reached.
+
+    ///Executes the algorithm until \c dest is reached.
+    ///
+    ///\pre init() must be called and at least one node should be added
+    ///with addSource() before using this function.
+    ///
+    ///This method runs the %BFS algorithm from the root node(s)
+    ///in order to
+    ///compute the
+    ///shortest path to \c dest. The algorithm computes
+    ///- The shortest path to \c  dest.
+    ///- The distance of \c dest from the root(s).
+    ///
+    void start(Node dest)
+    {
+      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
+    }
+    
+    ///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]==true</tt>.
+    template<class NM>
+      void start(const NM &nm)
+      {
+        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
+      }
+    
+    ///Runs %BFS algorithm from node \c s.
+    
+    ///This method runs the %BFS algorithm from a root node \c s
+    ///in order to
+    ///compute the
+    ///shortest path to each node. The algorithm computes
+    ///- The shortest path tree.
+    ///- The distance of each node from the root.
+    ///
+    ///\note d.run(s) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start();
+    ///\endcode
     void run(Node s) {
-      
-      init_maps();
-      
-      source = s;
-      
-      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
-        predecessor->set(u,INVALID);
-        pred_node->set(u,INVALID);
-      }
-      
-      int N = countNodes(*G);
-      std::vector<typename Graph::Node> Q(N);
-      int Qh=0;
-      int Qt=0;
-      
-      Q[Qh++]=source;
-      distance->set(s, 0);
-      do {
-        Node m;
-        Node n=Q[Qt++];
-        int d= (*distance)[n]+1;
-        
-        for(OutEdgeIt e(*G,n);e!=INVALID;++e)
-          if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
-            Q[Qh++]=m;
-            predecessor->set(m,e);
-            pred_node->set(m,n);
-            distance->set(m,d);
-          }
-      } while(Qt!=Qh);
-    }
-    
-    ///The distance of a node from the root.
-
-    ///Returns the distance of a node from the root.
+      init();
+      addSource(s);
+      start();
+    }
+    
+    ///Finds the shortest path between \c s and \c t.
+    
+    ///Finds the shortest path between \c s and \c t.
+    ///
+    ///\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
+    ///just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start(t);
+    ///\endcode
+    int run(Node s,Node t) {
+      init();
+      addSource(s);
+      start(t);
+      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
+    }
+    
+    ///@}
+
+    ///\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.
+    
+    ///@{
+
+    ///The distance of a node from the root(s).
+
+    ///Returns the distance of a node from the root(s).
     ///\pre \ref run() must be called before using this function.
-    ///\warning If node \c v in unreachable from the root the return value
+    ///\warning If node \c v in unreachable from the root(s) the return value
     ///of this funcion is undefined.
-    int dist(Node v) const { return (*distance)[v]; }
-
-    ///Returns the 'previous edge' of the %BFS path tree.
-
-    ///For a node \c v it returns the 'previous edge' of the %BFS tree,
-    ///i.e. it returns the last edge of a shortest path from the root to \c
+    int dist(Node v) const { return (*_dist)[v]; }
+
+    ///Returns the 'previous edge' of the shortest path tree.
+
+    ///For a node \c v it returns the 'previous edge'
+    ///of the shortest path tree,
+    ///i.e. it returns the last edge of a shortest path from the root(s) to \c
     ///v. It is \ref INVALID
-    ///if \c v is unreachable from the root or if \c v=s. The
-    ///%BFS tree used here is equal to the %BFS tree used in
-    ///\ref predNode(Node v).  \pre \ref run() must be called before using
+    ///if \c v is unreachable from the root(s) or \c v is a root. The
+    ///shortest path tree used here is equal to the shortest path tree used in
+    ///\ref predNode(Node v).
+    ///\pre Either \ref run() or \ref start() must be called before using
     ///this function.
-    Edge pred(Node v) const { return (*predecessor)[v]; }
-
-    ///Returns the 'previous node' of the %BFS tree.
-
-    ///For a node \c v it returns the 'previous node' on the %BFS tree,
+    ///\todo predEdge could be a better name.
+    Edge pred(Node v) const { return (*_pred)[v];}
+
+    ///Returns the 'previous node' of the shortest path tree.
+
+    ///For a node \c v it returns the 'previous node'
+    ///of the shortest path tree,
     ///i.e. it returns the last but one node from a shortest path from the
-    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
-    ///\c v=s. The shortest path tree used here is equal to the %BFS
-    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
+    ///root(a) to \c /v.
+    ///It is INVALID if \c v is unreachable from the root(s) or
+    ///if \c v itself a root.
+    ///The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref pred(Node v).
+    ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
-    Node predNode(Node v) const { return (*pred_node)[v]; }
+    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
+                                  G->source((*_pred)[v]); }
     
     ///Returns a reference to the NodeMap of distances.
-    
-    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
+
+    ///Returns a reference to the NodeMap of distances.
+    ///\pre Either \ref run() or \ref init() must
     ///be called before using this function.
-    const DistMap &distMap() const { return *distance;}
- 
-    ///Returns a reference to the %BFS tree map.
+    const DistMap &distMap() const { return *_dist;}
+ 
+    ///Returns a reference to the shortest path tree map.
 
     ///Returns a reference to the NodeMap of the edges of the
-    ///%BFS tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return *predecessor;}
- 
-    ///Returns a reference to the map of last but one nodes of shortest paths.
-
-    ///Returns a reference to the NodeMap of the last but one nodes on the
-    ///%BFS tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredNodeMap &predNodeMap() const { return *pred_node;}
+    ///shortest path tree.
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
+    const PredMap &predMap() const { return *_pred;}
+ 
+//     ///Returns a reference to the map of nodes of shortest paths.
+
+//     ///Returns a reference to the NodeMap of the last but one nodes of the
+//     ///shortest path tree.
+//     ///\pre \ref run() must be called before using this function.
+//     const PredNodeMap &predNodeMap() const { return *_predNode;}
 
     ///Checks if a node is reachable from the root.
 
     ///Returns \c true if \c v is reachable from the root.
-    ///\note The root node is reported to be reached!
-    ///
-    ///\pre \ref run() must be called before using this function.
-    ///
-    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
-    
+    ///\warning The source nodes are inditated as unreached.
+    ///\pre Either \ref run() or \ref start()
+    ///must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    
+    ///@}
+  };
+
+  ///Default traits class of Bfs function.
+
+  ///Default traits class of Bfs function.
+  ///\param GR Graph type.
+  template<class GR>
+  struct BfsWizardDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the shortest paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G) 
+    {
+      return new PredMap();
+    }
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///
+//     ///The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+//     ///
+//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
+//     ///Instantiates a PredNodeMap.
+    
+//     ///This function instantiates a \ref PredNodeMap. 
+//     ///\param G is the graph, to which
+//     ///we would like to define the \ref PredNodeMap
+//     static PredNodeMap *createPredNodeMap(const GR &G)
+//     {
+//       return new PredNodeMap();
+//     }
+
+    ///The type of the map that indicates which nodes are processed.
+ 
+    ///The type of the map that indicates which nodes are processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///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 concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef typename Graph::template NodeMap<bool> ReachedMap;
+    ///Instantiates a ReachedMap.
+ 
+    ///This function instantiates a \ref ReachedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const GR &G)
+    {
+      return new ReachedMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,int> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap();
+    }
   };
   
-/// @}
+  /// Default traits used by \ref BfsWizard
+
+  /// To make it easier to use Bfs algorithm
+  ///we have created a wizard class.
+  /// This \ref BfsWizard class needs default traits,
+  ///as well as the \ref Bfs class.
+  /// The \ref BfsWizardBase is a class to be the default traits of the
+  /// \ref BfsWizard class.
+  template<class GR>
+  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+  {
+
+    typedef BfsWizardDefaultTraits<GR> Base;
+  protected:
+    /// Type of the nodes in the graph.
+    typedef typename Base::Graph::Node Node;
+
+    /// Pointer to the underlying graph.
+    void *_g;
+    ///Pointer to the map of reached nodes.
+    void *_reached;
+    ///Pointer to the map of processed nodes.
+    void *_processed;
+    ///Pointer to the map of predecessors edges.
+    void *_pred;
+//     ///Pointer to the map of predecessors nodes.
+//     void *_predNode;
+    ///Pointer to the map of distances.
+    void *_dist;
+    ///Pointer to the source node.
+    Node _source;
+    
+    public:
+    /// Constructor.
+    
+    /// This constructor does not require parameters, therefore it initiates
+    /// all of the attributes to default values (0, INVALID).
+    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
+//                         _predNode(0),
+                           _dist(0), _source(INVALID) {}
+
+    /// Constructor.
+    
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
+    /// \param g is the initial value of  \ref _g
+    /// \param s is the initial value of  \ref _source
+    BfsWizardBase(const GR &g, Node s=INVALID) :
+      _g((void *)&g), _reached(0), _processed(0), _pred(0),
+//       _predNode(0),
+      _dist(0), _source(s) {}
+
+  };
   
+  /// A class to make the usage of Bfs algorithm easier
+
+  /// This class is created to make it easier to use Bfs algorithm.
+  /// It uses the functions and features of the plain \ref Bfs,
+  /// but it is much simpler to use it.
+  ///
+  /// Simplicity means that the way to change the types defined
+  /// in the traits class is based on functions that returns the new class
+  /// and not on templatable built-in classes.
+  /// When using the plain \ref Bfs
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref BfsWizard only
+  /// a function have to be called and it will
+  /// return the needed class.
+  ///
+  /// It does not have own \ref run method. When its \ref run method is called
+  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
+  /// method of it.
+  template<class TR>
+  class BfsWizard : public TR
+  {
+    typedef TR Base;
+
+    ///The type of the underlying graph.
+    typedef typename TR::Graph Graph;
+    //\e
+    typedef typename Graph::Node Node;
+    //\e
+    typedef typename Graph::NodeIt NodeIt;
+    //\e
+    typedef typename Graph::Edge Edge;
+    //\e
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    ///\brief The type of the map that stores
+    ///the reached nodes
+    typedef typename TR::ReachedMap ReachedMap;
+    ///\brief The type of the map that stores
+    ///the processed nodes
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    typedef typename TR::PredMap PredMap;
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename TR::DistMap DistMap;
+
+public:
+    /// Constructor.
+    BfsWizard() : TR() {}
+
+    /// Constructor that requires parameters.
+
+    /// Constructor that requires parameters.
+    /// These parameters will be the default values for the traits class.
+    BfsWizard(const Graph &g, Node s=INVALID) :
+      TR(g,s) {}
+
+    ///Copy constructor
+    BfsWizard(const TR &b) : TR(b) {}
+
+    ~BfsWizard() {}
+
+    ///Runs Bfs algorithm from a given node.
+    
+    ///Runs Bfs algorithm from a given node.
+    ///The node can be given by the \ref source function.
+    void run()
+    {
+      if(Base::_source==INVALID) throw UninitializedParameter();
+      Bfs<Graph,TR> alg(*(Graph*)Base::_g);
+      if(Base::_reached)
+        alg.reachedMap(*(ReachedMap*)Base::_reached);
+      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
+      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
+//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
+      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
+      alg.run(Base::_source);
+    }
+
+    ///Runs Bfs algorithm from the given node.
+
+    ///Runs Bfs algorithm from the given node.
+    ///\param s is the given source.
+    void run(Node s)
+    {
+      Base::_source=s;
+      run();
+    }
+
+    template<class T>
+    struct DefPredMapBase : public Base {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &G) { return 0; };
+      DefPredMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap
+    ///
+    template<class T>
+    BfsWizard<DefPredMapBase<T> > predMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return BfsWizard<DefPredMapBase<T> >(*this);
+    }
+    
+ 
+    template<class T>
+    struct DefReachedMapBase : public Base {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) { return 0; };
+      DefReachedMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    template<class T>
+    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return BfsWizard<DefReachedMapBase<T> >(*this);
+    }
+    
+
+    template<class T>
+    struct DefProcessedMapBase : public Base {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
+      DefProcessedMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    template<class T>
+    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return BfsWizard<DefProcessedMapBase<T> >(*this);
+    }
+    
+
+//     template<class T>
+//     struct DefPredNodeMapBase : public Base {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
+//       DefPredNodeMapBase(const Base &b) : Base(b) {}
+//     };
+    
+//     ///\brief \ref named-templ-param "Named parameter"
+//     ///function for setting PredNodeMap type
+//     ///
+//     /// \ref named-templ-param "Named parameter"
+//     ///function for setting PredNodeMap type
+//     ///
+//     template<class T>
+//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
+//     {
+//       Base::_predNode=(void *)&t;
+//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
+//     }
+   
+    template<class T>
+    struct DefDistMapBase : public Base {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &G) { return 0; };
+      DefDistMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    template<class T>
+    BfsWizard<DefDistMapBase<T> > distMap(const T &t) 
+    {
+      Base::_dist=(void *)&t;
+      return BfsWizard<DefDistMapBase<T> >(*this);
+    }
+    
+    /// Sets the source node, from which the Bfs algorithm runs.
+
+    /// Sets the source node, from which the Bfs algorithm runs.
+    /// \param s is the source node.
+    BfsWizard<TR> &source(Node s) 
+    {
+      Base::_source=s;
+      return *this;
+    }
+    
+  };
+  
+  ///Function type interface for Bfs algorithm.
+
+  /// \ingroup flowalgs
+  ///Function type interface for Bfs algorithm.
+  ///
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
+  ///they are declared as the members of class \ref BfsWizard.
+  ///The following
+  ///example shows how to use these parameters.
+  ///\code
+  ///  bfs(g,source).predMap(preds).run();
+  ///\endcode
+  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
+  ///to the end of the parameter list.
+  ///\sa BfsWizard
+  ///\sa Bfs
+  template<class GR>
+  BfsWizard<BfsWizardBase<GR> >
+  bfs(const GR &g,typename GR::Node s=INVALID)
+  {
+    return BfsWizard<BfsWizardBase<GR> >(g,s);
+  }
+
 } //END OF NAMESPACE LEMON
 
 #endif
 
-