lemon/bfs.h
changeset 249 f0b89f242745
parent 220 a5d8c039f218
parent 244 c30731a37f91
child 252 66644b9cd9eb
child 257 8d76a7bf9961
equal deleted inserted replaced
5:36d492ef02ac 7:023ea2581bd0
    19 #ifndef LEMON_BFS_H
    19 #ifndef LEMON_BFS_H
    20 #define LEMON_BFS_H
    20 #define LEMON_BFS_H
    21 
    21 
    22 ///\ingroup search
    22 ///\ingroup search
    23 ///\file
    23 ///\file
    24 ///\brief Bfs algorithm.
    24 ///\brief BFS algorithm.
    25 
    25 
    26 #include <lemon/list_graph.h>
    26 #include <lemon/list_graph.h>
    27 #include <lemon/bits/path_dump.h>
    27 #include <lemon/bits/path_dump.h>
    28 #include <lemon/core.h>
    28 #include <lemon/core.h>
    29 #include <lemon/error.h>
    29 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    30 #include <lemon/maps.h>
    31 
    31 
    32 namespace lemon {
    32 namespace lemon {
    33 
    33 
    34 
       
    35 
       
    36   ///Default traits class of Bfs class.
    34   ///Default traits class of Bfs class.
    37 
    35 
    38   ///Default traits class of Bfs class.
    36   ///Default traits class of Bfs class.
    39   ///\tparam GR Digraph type.
    37   ///\tparam GR Digraph type.
    40   template<class GR>
    38   template<class GR>
    41   struct BfsDefaultTraits
    39   struct BfsDefaultTraits
    42   {
    40   {
    43     ///The digraph type the algorithm runs on.
    41     ///The type of the digraph the algorithm runs on.
    44     typedef GR Digraph;
    42     typedef GR Digraph;
    45     ///\brief The type of the map that stores the last
    43 
       
    44     ///\brief The type of the map that stores the predecessor
    46     ///arcs of the shortest paths.
    45     ///arcs of the shortest paths.
    47     ///
    46     ///
    48     ///The type of the map that stores the last
    47     ///The type of the map that stores the predecessor
    49     ///arcs of the shortest paths.
    48     ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    49     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    51     ///
    50     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    51     ///Instantiates a \ref PredMap.
    53     ///Instantiates a PredMap.
       
    54 
    52 
    55     ///This function instantiates a \ref PredMap.
    53     ///This function instantiates a \ref PredMap.
    56     ///\param G is the digraph, to which we would like to define the PredMap.
    54     ///\param g is the digraph, to which we would like to define the
       
    55     ///\ref PredMap.
    57     ///\todo The digraph alone may be insufficient to initialize
    56     ///\todo The digraph alone may be insufficient to initialize
    58     static PredMap *createPredMap(const GR &G)
    57     static PredMap *createPredMap(const Digraph &g)
    59     {
    58     {
    60       return new PredMap(G);
    59       return new PredMap(g);
    61     }
    60     }
       
    61 
    62     ///The type of the map that indicates which nodes are processed.
    62     ///The type of the map that indicates which nodes are processed.
    63 
    63 
    64     ///The type of the map that indicates which nodes are processed.
    64     ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    66     ///\todo named parameter to set this type, function to read and write.
    66     ///By default it is a NullMap.
    67     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a ProcessedMap.
    68     ///Instantiates a \ref ProcessedMap.
    69 
    69 
    70     ///This function instantiates a \ref ProcessedMap.
    70     ///This function instantiates a \ref ProcessedMap.
    71     ///\param g is the digraph, to which
    71     ///\param g is the digraph, to which
    72     ///we would like to define the \ref ProcessedMap
    72     ///we would like to define the \ref ProcessedMap
    73 #ifdef DOXYGEN
    73 #ifdef DOXYGEN
    74     static ProcessedMap *createProcessedMap(const GR &g)
    74     static ProcessedMap *createProcessedMap(const Digraph &g)
    75 #else
    75 #else
    76     static ProcessedMap *createProcessedMap(const GR &)
    76     static ProcessedMap *createProcessedMap(const Digraph &)
    77 #endif
    77 #endif
    78     {
    78     {
    79       return new ProcessedMap();
    79       return new ProcessedMap();
    80     }
    80     }
       
    81 
    81     ///The type of the map that indicates which nodes are reached.
    82     ///The type of the map that indicates which nodes are reached.
    82 
    83 
    83     ///The type of the map that indicates which nodes are reached.
    84     ///The type of the map that indicates which nodes are reached.
       
    85     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
       
    86     typedef typename Digraph::template NodeMap<bool> ReachedMap;
       
    87     ///Instantiates a \ref ReachedMap.
       
    88 
       
    89     ///This function instantiates a \ref ReachedMap.
       
    90     ///\param g is the digraph, to which
       
    91     ///we would like to define the \ref ReachedMap.
       
    92     static ReachedMap *createReachedMap(const Digraph &g)
       
    93     {
       
    94       return new ReachedMap(g);
       
    95     }
       
    96 
       
    97     ///The type of the map that stores the distances of the nodes.
       
    98 
       
    99     ///The type of the map that stores the distances of the nodes.
    84     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   100     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    85     ///\todo named parameter to set this type, function to read and write.
       
    86     typedef typename Digraph::template NodeMap<bool> ReachedMap;
       
    87     ///Instantiates a ReachedMap.
       
    88 
       
    89     ///This function instantiates a \ref ReachedMap.
       
    90     ///\param G is the digraph, to which
       
    91     ///we would like to define the \ref ReachedMap.
       
    92     static ReachedMap *createReachedMap(const GR &G)
       
    93     {
       
    94       return new ReachedMap(G);
       
    95     }
       
    96     ///The type of the map that stores the dists of the nodes.
       
    97 
       
    98     ///The type of the map that stores the dists of the nodes.
       
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   100     ///
       
   101     typedef typename Digraph::template NodeMap<int> DistMap;
   101     typedef typename Digraph::template NodeMap<int> DistMap;
   102     ///Instantiates a DistMap.
   102     ///Instantiates a \ref DistMap.
   103 
   103 
   104     ///This function instantiates a \ref DistMap.
   104     ///This function instantiates a \ref DistMap.
   105     ///\param G is the digraph, to which we would like to define
   105     ///\param g is the digraph, to which we would like to define the
   106     ///the \ref DistMap
   106     ///\ref DistMap.
   107     static DistMap *createDistMap(const GR &G)
   107     static DistMap *createDistMap(const Digraph &g)
   108     {
   108     {
   109       return new DistMap(G);
   109       return new DistMap(g);
   110     }
   110     }
   111   };
   111   };
   112 
   112 
   113   ///%BFS algorithm class.
   113   ///%BFS algorithm class.
   114 
   114 
   115   ///\ingroup search
   115   ///\ingroup search
   116   ///This class provides an efficient implementation of the %BFS algorithm.
   116   ///This class provides an efficient implementation of the %BFS algorithm.
   117   ///
   117   ///
   118   ///\tparam GR The digraph type the algorithm runs on. The default value is
   118   ///There is also a \ref bfs() "function type interface" for the BFS
   119   ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
   119   ///algorithm, which is convenient in the simplier cases and it can be
   120   ///is only passed to \ref BfsDefaultTraits.
   120   ///used easier.
       
   121   ///
       
   122   ///\tparam GR The type of the digraph the algorithm runs on.
       
   123   ///The default value is \ref ListDigraph. The value of GR is not used
       
   124   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
   121   ///\tparam TR Traits class to set various data types used by the algorithm.
   125   ///\tparam TR Traits class to set various data types used by the algorithm.
   122   ///The default traits class is
   126   ///The default traits class is
   123   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
   127   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
   124   ///See \ref BfsDefaultTraits for the documentation of
   128   ///See \ref BfsDefaultTraits for the documentation of
   125   ///a Bfs traits class.
   129   ///a Bfs traits class.
   126 
       
   127 #ifdef DOXYGEN
   130 #ifdef DOXYGEN
   128   template <typename GR,
   131   template <typename GR,
   129             typename TR>
   132             typename TR>
   130 #else
   133 #else
   131   template <typename GR=ListDigraph,
   134   template <typename GR=ListDigraph,
   132             typename TR=BfsDefaultTraits<GR> >
   135             typename TR=BfsDefaultTraits<GR> >
   133 #endif
   136 #endif
   134   class Bfs {
   137   class Bfs {
   135   public:
   138   public:
   136     /**
   139     ///\ref Exception for uninitialized parameters.
   137      * \brief \ref Exception for uninitialized parameters.
   140 
   138      *
   141     ///This error represents problems in the initialization of the
   139      * This error represents problems in the initialization
   142     ///parameters of the algorithm.
   140      * of the parameters of the algorithms.
       
   141      */
       
   142     class UninitializedParameter : public lemon::UninitializedParameter {
   143     class UninitializedParameter : public lemon::UninitializedParameter {
   143     public:
   144     public:
   144       virtual const char* what() const throw() {
   145       virtual const char* what() const throw() {
   145         return "lemon::Bfs::UninitializedParameter";
   146         return "lemon::Bfs::UninitializedParameter";
   146       }
   147       }
   147     };
   148     };
   148 
   149 
       
   150     ///The type of the digraph the algorithm runs on.
       
   151     typedef typename TR::Digraph Digraph;
       
   152 
       
   153     ///\brief The type of the map that stores the predecessor arcs of the
       
   154     ///shortest paths.
       
   155     typedef typename TR::PredMap PredMap;
       
   156     ///The type of the map that stores the distances of the nodes.
       
   157     typedef typename TR::DistMap DistMap;
       
   158     ///The type of the map that indicates which nodes are reached.
       
   159     typedef typename TR::ReachedMap ReachedMap;
       
   160     ///The type of the map that indicates which nodes are processed.
       
   161     typedef typename TR::ProcessedMap ProcessedMap;
       
   162     ///The type of the paths.
       
   163     typedef PredMapPath<Digraph, PredMap> Path;
       
   164 
       
   165     ///The traits class.
   149     typedef TR Traits;
   166     typedef TR Traits;
   150     ///The type of the underlying digraph.
   167 
   151     typedef typename TR::Digraph Digraph;
       
   152 
       
   153     ///\brief The type of the map that stores the last
       
   154     ///arcs of the shortest paths.
       
   155     typedef typename TR::PredMap PredMap;
       
   156     ///The type of the map indicating which nodes are reached.
       
   157     typedef typename TR::ReachedMap ReachedMap;
       
   158     ///The type of the map indicating which nodes are processed.
       
   159     typedef typename TR::ProcessedMap ProcessedMap;
       
   160     ///The type of the map that stores the dists of the nodes.
       
   161     typedef typename TR::DistMap DistMap;
       
   162   private:
   168   private:
   163 
   169 
   164     typedef typename Digraph::Node Node;
   170     typedef typename Digraph::Node Node;
   165     typedef typename Digraph::NodeIt NodeIt;
   171     typedef typename Digraph::NodeIt NodeIt;
   166     typedef typename Digraph::Arc Arc;
   172     typedef typename Digraph::Arc Arc;
   167     typedef typename Digraph::OutArcIt OutArcIt;
   173     typedef typename Digraph::OutArcIt OutArcIt;
   168 
   174 
   169     /// Pointer to the underlying digraph.
   175     //Pointer to the underlying digraph.
   170     const Digraph *G;
   176     const Digraph *G;
   171     ///Pointer to the map of predecessors arcs.
   177     //Pointer to the map of predecessor arcs.
   172     PredMap *_pred;
   178     PredMap *_pred;
   173     ///Indicates if \ref _pred is locally allocated (\c true) or not.
   179     //Indicates if _pred is locally allocated (true) or not.
   174     bool local_pred;
   180     bool local_pred;
   175     ///Pointer to the map of distances.
   181     //Pointer to the map of distances.
   176     DistMap *_dist;
   182     DistMap *_dist;
   177     ///Indicates if \ref _dist is locally allocated (\c true) or not.
   183     //Indicates if _dist is locally allocated (true) or not.
   178     bool local_dist;
   184     bool local_dist;
   179     ///Pointer to the map of reached status of the nodes.
   185     //Pointer to the map of reached status of the nodes.
   180     ReachedMap *_reached;
   186     ReachedMap *_reached;
   181     ///Indicates if \ref _reached is locally allocated (\c true) or not.
   187     //Indicates if _reached is locally allocated (true) or not.
   182     bool local_reached;
   188     bool local_reached;
   183     ///Pointer to the map of processed status of the nodes.
   189     //Pointer to the map of processed status of the nodes.
   184     ProcessedMap *_processed;
   190     ProcessedMap *_processed;
   185     ///Indicates if \ref _processed is locally allocated (\c true) or not.
   191     //Indicates if _processed is locally allocated (true) or not.
   186     bool local_processed;
   192     bool local_processed;
   187 
   193 
   188     std::vector<typename Digraph::Node> _queue;
   194     std::vector<typename Digraph::Node> _queue;
   189     int _queue_head,_queue_tail,_queue_next_dist;
   195     int _queue_head,_queue_tail,_queue_next_dist;
   190     int _curr_dist;
   196     int _curr_dist;
   191 
   197 
   192     ///Creates the maps if necessary.
   198     ///Creates the maps if necessary.
   193 
       
   194     ///\todo Better memory allocation (instead of new).
   199     ///\todo Better memory allocation (instead of new).
   195     void create_maps()
   200     void create_maps()
   196     {
   201     {
   197       if(!_pred) {
   202       if(!_pred) {
   198         local_pred = true;
   203         local_pred = true;
   231       {
   236       {
   232         throw UninitializedParameter();
   237         throw UninitializedParameter();
   233       }
   238       }
   234     };
   239     };
   235     ///\brief \ref named-templ-param "Named parameter" for setting
   240     ///\brief \ref named-templ-param "Named parameter" for setting
   236     ///PredMap type
   241     ///\ref PredMap type.
   237     ///
   242     ///
   238     ///\ref named-templ-param "Named parameter" for setting PredMap type
   243     ///\ref named-templ-param "Named parameter" for setting
   239     ///
   244     ///\ref PredMap type.
   240     template <class T>
   245     template <class T>
   241     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
   246     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
   242       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
   247       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
   243     };
   248     };
   244 
   249 
   249       {
   254       {
   250         throw UninitializedParameter();
   255         throw UninitializedParameter();
   251       }
   256       }
   252     };
   257     };
   253     ///\brief \ref named-templ-param "Named parameter" for setting
   258     ///\brief \ref named-templ-param "Named parameter" for setting
   254     ///DistMap type
   259     ///\ref DistMap type.
   255     ///
   260     ///
   256     ///\ref named-templ-param "Named parameter" for setting DistMap type
   261     ///\ref named-templ-param "Named parameter" for setting
   257     ///
   262     ///\ref DistMap type.
   258     template <class T>
   263     template <class T>
   259     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
   264     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
   260       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
   265       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
   261     };
   266     };
   262 
   267 
   267       {
   272       {
   268         throw UninitializedParameter();
   273         throw UninitializedParameter();
   269       }
   274       }
   270     };
   275     };
   271     ///\brief \ref named-templ-param "Named parameter" for setting
   276     ///\brief \ref named-templ-param "Named parameter" for setting
   272     ///ReachedMap type
   277     ///\ref ReachedMap type.
   273     ///
   278     ///
   274     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   279     ///\ref named-templ-param "Named parameter" for setting
   275     ///
   280     ///\ref ReachedMap type.
   276     template <class T>
   281     template <class T>
   277     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
   282     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
   278       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
   283       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
   279     };
   284     };
   280 
   285 
   285       {
   290       {
   286         throw UninitializedParameter();
   291         throw UninitializedParameter();
   287       }
   292       }
   288     };
   293     };
   289     ///\brief \ref named-templ-param "Named parameter" for setting
   294     ///\brief \ref named-templ-param "Named parameter" for setting
   290     ///ProcessedMap type
   295     ///\ref ProcessedMap type.
   291     ///
   296     ///
   292     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   297     ///\ref named-templ-param "Named parameter" for setting
   293     ///
   298     ///\ref ProcessedMap type.
   294     template <class T>
   299     template <class T>
   295     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
   300     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
   296       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
   301       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
   297     };
   302     };
   298 
   303 
   299     struct DefDigraphProcessedMapTraits : public Traits {
   304     struct DefDigraphProcessedMapTraits : public Traits {
   300       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   305       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   301       static ProcessedMap *createProcessedMap(const Digraph &G)
   306       static ProcessedMap *createProcessedMap(const Digraph &g)
   302       {
   307       {
   303         return new ProcessedMap(G);
   308         return new ProcessedMap(g);
   304       }
   309       }
   305     };
   310     };
   306     ///\brief \ref named-templ-param "Named parameter"
   311     ///\brief \ref named-templ-param "Named parameter" for setting
   307     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   312     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   308     ///
   313     ///
   309     ///\ref named-templ-param "Named parameter"
   314     ///\ref named-templ-param "Named parameter" for setting
   310     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   315     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   311     ///If you don't set it explicitly, it will be automatically allocated.
   316     ///If you don't set it explicitly, it will be automatically allocated.
   312     template <class T>
   317     template <class T>
   313     struct DefProcessedMapToBeDefaultMap :
   318     struct DefProcessedMapToBeDefaultMap :
   314       public Bfs< Digraph, DefDigraphProcessedMapTraits> {
   319       public Bfs< Digraph, DefDigraphProcessedMapTraits> {
   315       typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
   320       typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
   319 
   324 
   320   public:
   325   public:
   321 
   326 
   322     ///Constructor.
   327     ///Constructor.
   323 
   328 
   324     ///\param _G the digraph the algorithm will run on.
   329     ///Constructor.
   325     ///
   330     ///\param g The digraph the algorithm runs on.
   326     Bfs(const Digraph& _G) :
   331     Bfs(const Digraph &g) :
   327       G(&_G),
   332       G(&g),
   328       _pred(NULL), local_pred(false),
   333       _pred(NULL), local_pred(false),
   329       _dist(NULL), local_dist(false),
   334       _dist(NULL), local_dist(false),
   330       _reached(NULL), local_reached(false),
   335       _reached(NULL), local_reached(false),
   331       _processed(NULL), local_processed(false)
   336       _processed(NULL), local_processed(false)
   332     { }
   337     { }
   338       if(local_dist) delete _dist;
   343       if(local_dist) delete _dist;
   339       if(local_reached) delete _reached;
   344       if(local_reached) delete _reached;
   340       if(local_processed) delete _processed;
   345       if(local_processed) delete _processed;
   341     }
   346     }
   342 
   347 
   343     ///Sets the map storing the predecessor arcs.
   348     ///Sets the map that stores the predecessor arcs.
   344 
   349 
   345     ///Sets the map storing the predecessor arcs.
   350     ///Sets the map that stores the predecessor arcs.
   346     ///If you don't use this function before calling \ref run(),
   351     ///If you don't use this function before calling \ref run(),
   347     ///it will allocate one. The destructor deallocates this
   352     ///it will allocate one. The destructor deallocates this
   348     ///automatically allocated map, of course.
   353     ///automatically allocated map, of course.
   349     ///\return <tt> (*this) </tt>
   354     ///\return <tt> (*this) </tt>
   350     Bfs &predMap(PredMap &m)
   355     Bfs &predMap(PredMap &m)
   355       }
   360       }
   356       _pred = &m;
   361       _pred = &m;
   357       return *this;
   362       return *this;
   358     }
   363     }
   359 
   364 
   360     ///Sets the map indicating the reached nodes.
   365     ///Sets the map that indicates which nodes are reached.
   361 
   366 
   362     ///Sets the map indicating the reached nodes.
   367     ///Sets the map that indicates which nodes are reached.
   363     ///If you don't use this function before calling \ref run(),
   368     ///If you don't use this function before calling \ref run(),
   364     ///it will allocate one. The destructor deallocates this
   369     ///it will allocate one. The destructor deallocates this
   365     ///automatically allocated map, of course.
   370     ///automatically allocated map, of course.
   366     ///\return <tt> (*this) </tt>
   371     ///\return <tt> (*this) </tt>
   367     Bfs &reachedMap(ReachedMap &m)
   372     Bfs &reachedMap(ReachedMap &m)
   372       }
   377       }
   373       _reached = &m;
   378       _reached = &m;
   374       return *this;
   379       return *this;
   375     }
   380     }
   376 
   381 
   377     ///Sets the map indicating the processed nodes.
   382     ///Sets the map that indicates which nodes are processed.
   378 
   383 
   379     ///Sets the map indicating the processed nodes.
   384     ///Sets the map that indicates which nodes are processed.
   380     ///If you don't use this function before calling \ref run(),
   385     ///If you don't use this function before calling \ref run(),
   381     ///it will allocate one. The destructor deallocates this
   386     ///it will allocate one. The destructor deallocates this
   382     ///automatically allocated map, of course.
   387     ///automatically allocated map, of course.
   383     ///\return <tt> (*this) </tt>
   388     ///\return <tt> (*this) </tt>
   384     Bfs &processedMap(ProcessedMap &m)
   389     Bfs &processedMap(ProcessedMap &m)
   389       }
   394       }
   390       _processed = &m;
   395       _processed = &m;
   391       return *this;
   396       return *this;
   392     }
   397     }
   393 
   398 
   394     ///Sets the map storing the distances calculated by the algorithm.
   399     ///Sets the map that stores the distances of the nodes.
   395 
   400 
   396     ///Sets the map storing the distances calculated by the algorithm.
   401     ///Sets the map that stores the distances of the nodes calculated by
       
   402     ///the algorithm.
   397     ///If you don't use this function before calling \ref run(),
   403     ///If you don't use this function before calling \ref run(),
   398     ///it will allocate one. The destructor deallocates this
   404     ///it will allocate one. The destructor deallocates this
   399     ///automatically allocated map, of course.
   405     ///automatically allocated map, of course.
   400     ///\return <tt> (*this) </tt>
   406     ///\return <tt> (*this) </tt>
   401     Bfs &distMap(DistMap &m)
   407     Bfs &distMap(DistMap &m)
   407       _dist = &m;
   413       _dist = &m;
   408       return *this;
   414       return *this;
   409     }
   415     }
   410 
   416 
   411   public:
   417   public:
       
   418 
   412     ///\name Execution control
   419     ///\name Execution control
   413     ///The simplest way to execute the algorithm is to use
   420     ///The simplest way to execute the algorithm is to use
   414     ///one of the member functions called \c run(...).
   421     ///one of the member functions called \ref lemon::Bfs::run() "run()".
   415     ///\n
   422     ///\n
   416     ///If you need more control on the execution,
   423     ///If you need more control on the execution, first you must call
   417     ///first you must call \ref init(), then you can add several source nodes
   424     ///\ref lemon::Bfs::init() "init()", then you can add several source
   418     ///with \ref addSource().
   425     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
   419     ///Finally \ref start() will perform the actual path
   426     ///Finally \ref lemon::Bfs::start() "start()" will perform the
   420     ///computation.
   427     ///actual path computation.
   421 
   428 
   422     ///@{
   429     ///@{
   423 
   430 
   424     ///\brief Initializes the internal data structures.
   431     ///Initializes the internal data structures.
   425     ///
   432 
   426     ///Initializes the internal data structures.
   433     ///Initializes the internal data structures.
   427     ///
   434     ///
   428     void init()
   435     void init()
   429     {
   436     {
   430       create_maps();
   437       create_maps();
   458 
   465 
   459     ///Processes the next node.
   466     ///Processes the next node.
   460     ///
   467     ///
   461     ///\return The processed node.
   468     ///\return The processed node.
   462     ///
   469     ///
   463     ///\warning The queue must not be empty!
   470     ///\pre The queue must not be empty.
   464     Node processNextNode()
   471     Node processNextNode()
   465     {
   472     {
   466       if(_queue_tail==_queue_next_dist) {
   473       if(_queue_tail==_queue_next_dist) {
   467         _curr_dist++;
   474         _curr_dist++;
   468         _queue_next_dist=_queue_head;
   475         _queue_next_dist=_queue_head;
   480       return n;
   487       return n;
   481     }
   488     }
   482 
   489 
   483     ///Processes the next node.
   490     ///Processes the next node.
   484 
   491 
   485     ///Processes the next node. And checks that the given target node
   492     ///Processes the next node and checks if the given target node
   486     ///is reached. If the target node is reachable from the processed
   493     ///is reached. If the target node is reachable from the processed
   487     ///node then the reached parameter will be set true. The reached
   494     ///node, then the \c reach parameter will be set to \c true.
   488     ///parameter should be initially false.
       
   489     ///
   495     ///
   490     ///\param target The target node.
   496     ///\param target The target node.
   491     ///\retval reach Indicates that the target node is reached.
   497     ///\retval reach Indicates if the target node is reached.
       
   498     ///It should be initially \c false.
       
   499     ///
   492     ///\return The processed node.
   500     ///\return The processed node.
   493     ///
   501     ///
   494     ///\warning The queue must not be empty!
   502     ///\pre The queue must not be empty.
   495     Node processNextNode(Node target, bool& reach)
   503     Node processNextNode(Node target, bool& reach)
   496     {
   504     {
   497       if(_queue_tail==_queue_next_dist) {
   505       if(_queue_tail==_queue_next_dist) {
   498         _curr_dist++;
   506         _curr_dist++;
   499         _queue_next_dist=_queue_head;
   507         _queue_next_dist=_queue_head;
   512       return n;
   520       return n;
   513     }
   521     }
   514 
   522 
   515     ///Processes the next node.
   523     ///Processes the next node.
   516 
   524 
   517     ///Processes the next node. And checks that at least one of
   525     ///Processes the next node and checks if at least one of reached
   518     ///reached node has true value in the \c nm node map. If one node
   526     ///nodes has \c true value in the \c nm node map. If one node
   519     ///with true value is reachable from the processed node then the
   527     ///with \c true value is reachable from the processed node, then the
   520     ///rnode parameter will be set to the first of such nodes.
   528     ///\c rnode parameter will be set to the first of such nodes.
   521     ///
   529     ///
   522     ///\param nm The node map of possible targets.
   530     ///\param nm A \c bool (or convertible) node map that indicates the
       
   531     ///possible targets.
   523     ///\retval rnode The reached target node.
   532     ///\retval rnode The reached target node.
       
   533     ///It should be initially \c INVALID.
       
   534     ///
   524     ///\return The processed node.
   535     ///\return The processed node.
   525     ///
   536     ///
   526     ///\warning The queue must not be empty!
   537     ///\pre The queue must not be empty.
   527     template<class NM>
   538     template<class NM>
   528     Node processNextNode(const NM& nm, Node& rnode)
   539     Node processNextNode(const NM& nm, Node& rnode)
   529     {
   540     {
   530       if(_queue_tail==_queue_next_dist) {
   541       if(_queue_tail==_queue_next_dist) {
   531         _curr_dist++;
   542         _curr_dist++;
   543           if (nm[m] && rnode == INVALID) rnode = m;
   554           if (nm[m] && rnode == INVALID) rnode = m;
   544         }
   555         }
   545       return n;
   556       return n;
   546     }
   557     }
   547 
   558 
   548     ///Next node to be processed.
   559     ///The next node to be processed.
   549 
   560 
   550     ///Next node to be processed.
   561     ///Returns the next node to be processed or \c INVALID if the queue
   551     ///
   562     ///is empty.
   552     ///\return The next node to be processed or INVALID if the queue is
   563     Node nextNode() const
   553     /// empty.
       
   554     Node nextNode()
       
   555     {
   564     {
   556       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   565       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   557     }
   566     }
   558 
   567 
   559     ///\brief Returns \c false if there are nodes
   568     ///\brief Returns \c false if there are nodes
   560     ///to be processed in the queue
   569     ///to be processed.
   561     ///
   570     ///
   562     ///Returns \c false if there are nodes
   571     ///Returns \c false if there are nodes
   563     ///to be processed in the queue
   572     ///to be processed in the queue.
   564     bool emptyQueue() { return _queue_tail==_queue_head; }
   573     bool emptyQueue() const { return _queue_tail==_queue_head; }
       
   574 
   565     ///Returns the number of the nodes to be processed.
   575     ///Returns the number of the nodes to be processed.
   566 
   576 
   567     ///Returns the number of the nodes to be processed in the queue.
   577     ///Returns the number of the nodes to be processed in the queue.
   568     int queueSize() { return _queue_head-_queue_tail; }
   578     int queueSize() const { return _queue_head-_queue_tail; }
   569 
   579 
   570     ///Executes the algorithm.
   580     ///Executes the algorithm.
   571 
   581 
   572     ///Executes the algorithm.
   582     ///Executes the algorithm.
   573     ///
   583     ///
   574     ///\pre init() must be called and at least one node should be added
       
   575     ///with addSource() before using this function.
       
   576     ///
       
   577     ///This method runs the %BFS algorithm from the root node(s)
   584     ///This method runs the %BFS algorithm from the root node(s)
   578     ///in order to
   585     ///in order to compute the shortest path to each node.
   579     ///compute the
   586     ///
   580     ///shortest path to each node. The algorithm computes
   587     ///The algorithm computes
   581     ///- The shortest path tree.
   588     ///- the shortest path tree (forest),
   582     ///- The distance of each node from the root(s).
   589     ///- the distance of each node from the root(s).
       
   590     ///
       
   591     ///\pre init() must be called and at least one root node should be
       
   592     ///added with addSource() before using this function.
       
   593     ///
       
   594     ///\note <tt>b.start()</tt> is just a shortcut of the following code.
       
   595     ///\code
       
   596     ///  while ( !b.emptyQueue() ) {
       
   597     ///    b.processNextNode();
       
   598     ///  }
       
   599     ///\endcode
   583     void start()
   600     void start()
   584     {
   601     {
   585       while ( !emptyQueue() ) processNextNode();
   602       while ( !emptyQueue() ) processNextNode();
   586     }
   603     }
   587 
   604 
   588     ///Executes the algorithm until \c dest is reached.
   605     ///Executes the algorithm until the given target node is reached.
   589 
   606 
   590     ///Executes the algorithm until \c dest is reached.
   607     ///Executes the algorithm until the given target node is reached.
   591     ///
       
   592     ///\pre init() must be called and at least one node should be added
       
   593     ///with addSource() before using this function.
       
   594     ///
   608     ///
   595     ///This method runs the %BFS algorithm from the root node(s)
   609     ///This method runs the %BFS algorithm from the root node(s)
   596     ///in order to compute the shortest path to \c dest.
   610     ///in order to compute the shortest path to \c dest.
       
   611     ///
   597     ///The algorithm computes
   612     ///The algorithm computes
   598     ///- The shortest path to \c  dest.
   613     ///- the shortest path to \c dest,
   599     ///- The distance of \c dest from the root(s).
   614     ///- the distance of \c dest from the root(s).
       
   615     ///
       
   616     ///\pre init() must be called and at least one root node should be
       
   617     ///added with addSource() before using this function.
       
   618     ///
       
   619     ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
       
   620     ///\code
       
   621     ///  bool reach = false;
       
   622     ///  while ( !b.emptyQueue() && !reach ) {
       
   623     ///    b.processNextNode(t, reach);
       
   624     ///  }
       
   625     ///\endcode
   600     void start(Node dest)
   626     void start(Node dest)
   601     {
   627     {
   602       bool reach = false;
   628       bool reach = false;
   603       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
   629       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
   604     }
   630     }
   605 
   631 
   606     ///Executes the algorithm until a condition is met.
   632     ///Executes the algorithm until a condition is met.
   607 
   633 
   608     ///Executes the algorithm until a condition is met.
   634     ///Executes the algorithm until a condition is met.
   609     ///
   635     ///
   610     ///\pre init() must be called and at least one node should be added
   636     ///This method runs the %BFS algorithm from the root node(s) in
   611     ///with addSource() before using this function.
   637     ///order to compute the shortest path to a node \c v with
   612     ///
   638     /// <tt>nm[v]</tt> true, if such a node can be found.
   613     ///\param nm must be a bool (or convertible) node map. The
   639     ///
   614     ///algorithm will stop when it reaches a node \c v with
   640     ///\param nm A \c bool (or convertible) node map. The algorithm
   615     /// <tt>nm[v]</tt> true.
   641     ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
   616     ///
   642     ///
   617     ///\return The reached node \c v with <tt>nm[v]</tt> true or
   643     ///\return The reached node \c v with <tt>nm[v]</tt> true or
   618     ///\c INVALID if no such node was found.
   644     ///\c INVALID if no such node was found.
   619     template<class NM>
   645     ///
   620     Node start(const NM &nm)
   646     ///\pre init() must be called and at least one root node should be
       
   647     ///added with addSource() before using this function.
       
   648     ///
       
   649     ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
       
   650     ///\code
       
   651     ///  Node rnode = INVALID;
       
   652     ///  while ( !b.emptyQueue() && rnode == INVALID ) {
       
   653     ///    b.processNextNode(nm, rnode);
       
   654     ///  }
       
   655     ///  return rnode;
       
   656     ///\endcode
       
   657     template<class NodeBoolMap>
       
   658     Node start(const NodeBoolMap &nm)
   621     {
   659     {
   622       Node rnode = INVALID;
   660       Node rnode = INVALID;
   623       while ( !emptyQueue() && rnode == INVALID ) {
   661       while ( !emptyQueue() && rnode == INVALID ) {
   624         processNextNode(nm, rnode);
   662         processNextNode(nm, rnode);
   625       }
   663       }
   626       return rnode;
   664       return rnode;
   627     }
   665     }
   628 
   666 
   629     ///Runs %BFS algorithm from node \c s.
   667     ///Runs the algorithm from the given node.
   630 
   668 
   631     ///This method runs the %BFS algorithm from a root node \c s
   669     ///This method runs the %BFS algorithm from node \c s
   632     ///in order to
   670     ///in order to compute the shortest path to each node.
   633     ///compute the
   671     ///
   634     ///shortest path to each node. The algorithm computes
   672     ///The algorithm computes
   635     ///- The shortest path tree.
   673     ///- the shortest path tree,
   636     ///- The distance of each node from the root.
   674     ///- the distance of each node from the root.
   637     ///
   675     ///
   638     ///\note b.run(s) is just a shortcut of the following code.
   676     ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
   639     ///\code
   677     ///\code
   640     ///  b.init();
   678     ///  b.init();
   641     ///  b.addSource(s);
   679     ///  b.addSource(s);
   642     ///  b.start();
   680     ///  b.start();
   643     ///\endcode
   681     ///\endcode
   647       start();
   685       start();
   648     }
   686     }
   649 
   687 
   650     ///Finds the shortest path between \c s and \c t.
   688     ///Finds the shortest path between \c s and \c t.
   651 
   689 
   652     ///Finds the shortest path between \c s and \c t.
   690     ///This method runs the %BFS algorithm from node \c s
   653     ///
   691     ///in order to compute the shortest path to \c t.
   654     ///\return The length of the shortest s---t path if there exists one,
   692     ///
   655     ///0 otherwise.
   693     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
   656     ///\note Apart from the return value, b.run(s) is
   694     ///if \c t is reachable form \c s, \c 0 otherwise.
   657     ///just a shortcut of the following code.
   695     ///
       
   696     ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
       
   697     ///shortcut of the following code.
   658     ///\code
   698     ///\code
   659     ///  b.init();
   699     ///  b.init();
   660     ///  b.addSource(s);
   700     ///  b.addSource(s);
   661     ///  b.start(t);
   701     ///  b.start(t);
   662     ///\endcode
   702     ///\endcode
   665       addSource(s);
   705       addSource(s);
   666       start(t);
   706       start(t);
   667       return reached(t) ? _curr_dist : 0;
   707       return reached(t) ? _curr_dist : 0;
   668     }
   708     }
   669 
   709 
       
   710     ///Runs the algorithm to visit all nodes in the digraph.
       
   711 
       
   712     ///This method runs the %BFS algorithm in order to
       
   713     ///compute the shortest path to each node.
       
   714     ///
       
   715     ///The algorithm computes
       
   716     ///- the shortest path tree (forest),
       
   717     ///- the distance of each node from the root(s).
       
   718     ///
       
   719     ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
       
   720     ///\code
       
   721     ///  b.init();
       
   722     ///  for (NodeIt n(gr); n != INVALID; ++n) {
       
   723     ///    if (!b.reached(n)) {
       
   724     ///      b.addSource(n);
       
   725     ///      b.start();
       
   726     ///    }
       
   727     ///  }
       
   728     ///\endcode
       
   729     void run() {
       
   730       init();
       
   731       for (NodeIt n(*G); n != INVALID; ++n) {
       
   732         if (!reached(n)) {
       
   733           addSource(n);
       
   734           start();
       
   735         }
       
   736       }
       
   737     }
       
   738 
   670     ///@}
   739     ///@}
   671 
   740 
   672     ///\name Query Functions
   741     ///\name Query Functions
   673     ///The result of the %BFS algorithm can be obtained using these
   742     ///The result of the %BFS algorithm can be obtained using these
   674     ///functions.\n
   743     ///functions.\n
   675     ///Before the use of these functions,
   744     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
   676     ///either run() or start() must be calleb.
   745     ///"start()" must be called before using them.
   677 
   746 
   678     ///@{
   747     ///@{
   679 
   748 
   680     typedef PredMapPath<Digraph, PredMap> Path;
   749     ///The shortest path to a node.
   681 
   750 
   682     ///Gives back the shortest path.
   751     ///Returns the shortest path to a node.
   683 
   752     ///
   684     ///Gives back the shortest path.
   753     ///\warning \c t should be reachable from the root(s).
   685     ///\pre The \c t should be reachable from the source.
   754     ///
   686     Path path(Node t)
   755     ///\pre Either \ref run() or \ref start() must be called before
   687     {
   756     ///using this function.
   688       return Path(*G, *_pred, t);
   757     Path path(Node t) const { return Path(*G, *_pred, t); }
   689     }
       
   690 
   758 
   691     ///The distance of a node from the root(s).
   759     ///The distance of a node from the root(s).
   692 
   760 
   693     ///Returns the distance of a node from the root(s).
   761     ///Returns the distance of a node from the root(s).
   694     ///\pre \ref run() must be called before using this function.
   762     ///
   695     ///\warning If node \c v in unreachable from the root(s) the return value
   763     ///\warning If node \c v is not reachable from the root(s), then
   696     ///of this function is undefined.
   764     ///the return value of this function is undefined.
       
   765     ///
       
   766     ///\pre Either \ref run() or \ref start() must be called before
       
   767     ///using this function.
   697     int dist(Node v) const { return (*_dist)[v]; }
   768     int dist(Node v) const { return (*_dist)[v]; }
   698 
   769 
   699     ///Returns the 'previous arc' of the shortest path tree.
   770     ///Returns the 'previous arc' of the shortest path tree for a node.
   700 
   771 
   701     ///For a node \c v it returns the 'previous arc'
   772     ///This function returns the 'previous arc' of the shortest path
   702     ///of the shortest path tree,
   773     ///tree for the node \c v, i.e. it returns the last arc of a
   703     ///i.e. it returns the last arc of a shortest path from the root(s) to \c
   774     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   704     ///v. It is \ref INVALID
   775     ///is not reachable from the root(s) or if \c v is a root.
   705     ///if \c v is unreachable from the root(s) or \c v is a root. The
   776     ///
   706     ///shortest path tree used here is equal to the shortest path tree used in
   777     ///The shortest path tree used here is equal to the shortest path
   707     ///\ref predNode().
   778     ///tree used in \ref predNode().
   708     ///\pre Either \ref run() or \ref start() must be called before using
   779     ///
   709     ///this function.
   780     ///\pre Either \ref run() or \ref start() must be called before
       
   781     ///using this function.
   710     Arc predArc(Node v) const { return (*_pred)[v];}
   782     Arc predArc(Node v) const { return (*_pred)[v];}
   711 
   783 
   712     ///Returns the 'previous node' of the shortest path tree.
   784     ///Returns the 'previous node' of the shortest path tree for a node.
   713 
   785 
   714     ///For a node \c v it returns the 'previous node'
   786     ///This function returns the 'previous node' of the shortest path
   715     ///of the shortest path tree,
   787     ///tree for the node \c v, i.e. it returns the last but one node
   716     ///i.e. it returns the last but one node from a shortest path from the
   788     ///from a shortest path from the root(s) to \c v. It is \c INVALID
   717     ///root(a) to \c /v.
   789     ///if \c v is not reachable from the root(s) or if \c v is a root.
   718     ///It is INVALID if \c v is unreachable from the root(s) or
   790     ///
   719     ///if \c v itself a root.
       
   720     ///The shortest path tree used here is equal to the shortest path
   791     ///The shortest path tree used here is equal to the shortest path
   721     ///tree used in \ref predArc().
   792     ///tree used in \ref predArc().
       
   793     ///
   722     ///\pre Either \ref run() or \ref start() must be called before
   794     ///\pre Either \ref run() or \ref start() must be called before
   723     ///using this function.
   795     ///using this function.
   724     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   796     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   725                                   G->source((*_pred)[v]); }
   797                                   G->source((*_pred)[v]); }
   726 
   798 
   727     ///Returns a reference to the NodeMap of distances.
   799     ///\brief Returns a const reference to the node map that stores the
   728 
   800     /// distances of the nodes.
   729     ///Returns a reference to the NodeMap of distances.
   801     ///
   730     ///\pre Either \ref run() or \ref init() must
   802     ///Returns a const reference to the node map that stores the distances
   731     ///be called before using this function.
   803     ///of the nodes calculated by the algorithm.
       
   804     ///
       
   805     ///\pre Either \ref run() or \ref init()
       
   806     ///must be called before using this function.
   732     const DistMap &distMap() const { return *_dist;}
   807     const DistMap &distMap() const { return *_dist;}
   733 
   808 
   734     ///Returns a reference to the shortest path tree map.
   809     ///\brief Returns a const reference to the node map that stores the
   735 
   810     ///predecessor arcs.
   736     ///Returns a reference to the NodeMap of the arcs of the
   811     ///
   737     ///shortest path tree.
   812     ///Returns a const reference to the node map that stores the predecessor
       
   813     ///arcs, which form the shortest path tree.
       
   814     ///
   738     ///\pre Either \ref run() or \ref init()
   815     ///\pre Either \ref run() or \ref init()
   739     ///must be called before using this function.
   816     ///must be called before using this function.
   740     const PredMap &predMap() const { return *_pred;}
   817     const PredMap &predMap() const { return *_pred;}
   741 
   818 
   742     ///Checks if a node is reachable from the root.
   819     ///Checks if a node is reachable from the root(s).
   743 
   820 
   744     ///Returns \c true if \c v is reachable from the root.
   821     ///Returns \c true if \c v is reachable from the root(s).
   745     ///\warning The source nodes are indicated as unreached.
       
   746     ///\pre Either \ref run() or \ref start()
   822     ///\pre Either \ref run() or \ref start()
   747     ///must be called before using this function.
   823     ///must be called before using this function.
   748     ///
   824     bool reached(Node v) const { return (*_reached)[v]; }
   749     bool reached(Node v) { return (*_reached)[v]; }
       
   750 
   825 
   751     ///@}
   826     ///@}
   752   };
   827   };
   753 
   828 
   754   ///Default traits class of Bfs function.
   829   ///Default traits class of bfs() function.
   755 
   830 
   756   ///Default traits class of Bfs function.
   831   ///Default traits class of bfs() function.
   757   ///\tparam GR Digraph type.
   832   ///\tparam GR Digraph type.
   758   template<class GR>
   833   template<class GR>
   759   struct BfsWizardDefaultTraits
   834   struct BfsWizardDefaultTraits
   760   {
   835   {
   761     ///The digraph type the algorithm runs on.
   836     ///The type of the digraph the algorithm runs on.
   762     typedef GR Digraph;
   837     typedef GR Digraph;
   763     ///\brief The type of the map that stores the last
   838 
       
   839     ///\brief The type of the map that stores the predecessor
   764     ///arcs of the shortest paths.
   840     ///arcs of the shortest paths.
   765     ///
   841     ///
   766     ///The type of the map that stores the last
   842     ///The type of the map that stores the predecessor
   767     ///arcs of the shortest paths.
   843     ///arcs of the shortest paths.
   768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   844     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   769     ///
   845     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
   770     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
   846     ///Instantiates a \ref PredMap.
   771     ///Instantiates a PredMap.
       
   772 
   847 
   773     ///This function instantiates a \ref PredMap.
   848     ///This function instantiates a \ref PredMap.
   774     ///\param g is the digraph, to which we would like to define the PredMap.
   849     ///\param g is the digraph, to which we would like to define the
       
   850     ///\ref PredMap.
   775     ///\todo The digraph alone may be insufficient to initialize
   851     ///\todo The digraph alone may be insufficient to initialize
   776 #ifdef DOXYGEN
   852 #ifdef DOXYGEN
   777     static PredMap *createPredMap(const GR &g)
   853     static PredMap *createPredMap(const Digraph &g)
   778 #else
   854 #else
   779     static PredMap *createPredMap(const GR &)
   855     static PredMap *createPredMap(const Digraph &)
   780 #endif
   856 #endif
   781     {
   857     {
   782       return new PredMap();
   858       return new PredMap();
   783     }
   859     }
   784 
   860 
   785     ///The type of the map that indicates which nodes are processed.
   861     ///The type of the map that indicates which nodes are processed.
   786 
   862 
   787     ///The type of the map that indicates which nodes are processed.
   863     ///The type of the map that indicates which nodes are processed.
   788     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   864     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   789     ///\todo named parameter to set this type, function to read and write.
       
   790     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   865     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   791     ///Instantiates a ProcessedMap.
   866     ///Instantiates a \ref ProcessedMap.
   792 
   867 
   793     ///This function instantiates a \ref ProcessedMap.
   868     ///This function instantiates a \ref ProcessedMap.
   794     ///\param g is the digraph, to which
   869     ///\param g is the digraph, to which
   795     ///we would like to define the \ref ProcessedMap
   870     ///we would like to define the \ref ProcessedMap.
   796 #ifdef DOXYGEN
   871 #ifdef DOXYGEN
   797     static ProcessedMap *createProcessedMap(const GR &g)
   872     static ProcessedMap *createProcessedMap(const Digraph &g)
   798 #else
   873 #else
   799     static ProcessedMap *createProcessedMap(const GR &)
   874     static ProcessedMap *createProcessedMap(const Digraph &)
   800 #endif
   875 #endif
   801     {
   876     {
   802       return new ProcessedMap();
   877       return new ProcessedMap();
   803     }
   878     }
       
   879 
   804     ///The type of the map that indicates which nodes are reached.
   880     ///The type of the map that indicates which nodes are reached.
   805 
   881 
   806     ///The type of the map that indicates which nodes are reached.
   882     ///The type of the map that indicates which nodes are reached.
       
   883     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
       
   884     typedef typename Digraph::template NodeMap<bool> ReachedMap;
       
   885     ///Instantiates a \ref ReachedMap.
       
   886 
       
   887     ///This function instantiates a \ref ReachedMap.
       
   888     ///\param g is the digraph, to which
       
   889     ///we would like to define the \ref ReachedMap.
       
   890     static ReachedMap *createReachedMap(const Digraph &g)
       
   891     {
       
   892       return new ReachedMap(g);
       
   893     }
       
   894 
       
   895     ///The type of the map that stores the distances of the nodes.
       
   896 
       
   897     ///The type of the map that stores the distances of the nodes.
   807     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   898     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   808     ///\todo named parameter to set this type, function to read and write.
       
   809     typedef typename Digraph::template NodeMap<bool> ReachedMap;
       
   810     ///Instantiates a ReachedMap.
       
   811 
       
   812     ///This function instantiates a \ref ReachedMap.
       
   813     ///\param G is the digraph, to which
       
   814     ///we would like to define the \ref ReachedMap.
       
   815     static ReachedMap *createReachedMap(const GR &G)
       
   816     {
       
   817       return new ReachedMap(G);
       
   818     }
       
   819     ///The type of the map that stores the dists of the nodes.
       
   820 
       
   821     ///The type of the map that stores the dists of the nodes.
       
   822     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   823     ///
   899     ///
   824     typedef NullMap<typename Digraph::Node,int> DistMap;
   900     typedef NullMap<typename Digraph::Node,int> DistMap;
   825     ///Instantiates a DistMap.
   901     ///Instantiates a \ref DistMap.
   826 
   902 
   827     ///This function instantiates a \ref DistMap.
   903     ///This function instantiates a \ref DistMap.
   828     ///\param g is the digraph, to which we would like to define
   904     ///\param g is the digraph, to which we would like to define
   829     ///the \ref DistMap
   905     ///the \ref DistMap
   830 #ifdef DOXYGEN
   906 #ifdef DOXYGEN
   831     static DistMap *createDistMap(const GR &g)
   907     static DistMap *createDistMap(const Digraph &g)
   832 #else
   908 #else
   833     static DistMap *createDistMap(const GR &)
   909     static DistMap *createDistMap(const Digraph &)
   834 #endif
   910 #endif
   835     {
   911     {
   836       return new DistMap();
   912       return new DistMap();
   837     }
   913     }
   838   };
   914   };
   839 
   915 
   840   /// Default traits used by \ref BfsWizard
   916   /// Default traits class used by \ref BfsWizard
   841 
   917 
   842   /// To make it easier to use Bfs algorithm
   918   /// To make it easier to use Bfs algorithm
   843   ///we have created a wizard class.
   919   /// we have created a wizard class.
   844   /// This \ref BfsWizard class needs default traits,
   920   /// This \ref BfsWizard class needs default traits,
   845   ///as well as the \ref Bfs class.
   921   /// as well as the \ref Bfs class.
   846   /// The \ref BfsWizardBase is a class to be the default traits of the
   922   /// The \ref BfsWizardBase is a class to be the default traits of the
   847   /// \ref BfsWizard class.
   923   /// \ref BfsWizard class.
   848   template<class GR>
   924   template<class GR>
   849   class BfsWizardBase : public BfsWizardDefaultTraits<GR>
   925   class BfsWizardBase : public BfsWizardDefaultTraits<GR>
   850   {
   926   {
   851 
   927 
   852     typedef BfsWizardDefaultTraits<GR> Base;
   928     typedef BfsWizardDefaultTraits<GR> Base;
   853   protected:
   929   protected:
   854     /// Type of the nodes in the digraph.
   930     //The type of the nodes in the digraph.
   855     typedef typename Base::Digraph::Node Node;
   931     typedef typename Base::Digraph::Node Node;
   856 
   932 
   857     /// Pointer to the underlying digraph.
   933     //Pointer to the digraph the algorithm runs on.
   858     void *_g;
   934     void *_g;
   859     ///Pointer to the map of reached nodes.
   935     //Pointer to the map of reached nodes.
   860     void *_reached;
   936     void *_reached;
   861     ///Pointer to the map of processed nodes.
   937     //Pointer to the map of processed nodes.
   862     void *_processed;
   938     void *_processed;
   863     ///Pointer to the map of predecessors arcs.
   939     //Pointer to the map of predecessors arcs.
   864     void *_pred;
   940     void *_pred;
   865     ///Pointer to the map of distances.
   941     //Pointer to the map of distances.
   866     void *_dist;
   942     void *_dist;
   867     ///Pointer to the source node.
   943     //Pointer to the source node.
   868     Node _source;
   944     Node _source;
   869 
   945 
   870     public:
   946     public:
   871     /// Constructor.
   947     /// Constructor.
   872 
   948 
   873     /// This constructor does not require parameters, therefore it initiates
   949     /// This constructor does not require parameters, therefore it initiates
   874     /// all of the attributes to default values (0, INVALID).
   950     /// all of the attributes to default values (0, INVALID).
   875     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   951     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   876                            _dist(0), _source(INVALID) {}
   952                       _dist(0), _source(INVALID) {}
   877 
   953 
   878     /// Constructor.
   954     /// Constructor.
   879 
   955 
   880     /// This constructor requires some parameters,
   956     /// This constructor requires some parameters,
   881     /// listed in the parameters list.
   957     /// listed in the parameters list.
   882     /// Others are initiated to 0.
   958     /// Others are initiated to 0.
   883     /// \param g is the initial value of  \ref _g
   959     /// \param g The digraph the algorithm runs on.
   884     /// \param s is the initial value of  \ref _source
   960     /// \param s The source node.
   885     BfsWizardBase(const GR &g, Node s=INVALID) :
   961     BfsWizardBase(const GR &g, Node s=INVALID) :
   886       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   962       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   887       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   963       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   888 
   964 
   889   };
   965   };
   890 
   966 
   891   /// A class to make the usage of Bfs algorithm easier
   967   /// Auxiliary class for the function type interface of BFS algorithm.
   892 
   968 
   893   /// This class is created to make it easier to use Bfs algorithm.
   969   /// This auxiliary class is created to implement the function type
   894   /// It uses the functions and features of the plain \ref Bfs,
   970   /// interface of \ref Bfs algorithm. It uses the functions and features
   895   /// but it is much simpler to use it.
   971   /// of the plain \ref Bfs, but it is much simpler to use it.
       
   972   /// It should only be used through the \ref bfs() function, which makes
       
   973   /// it easier to use the algorithm.
   896   ///
   974   ///
   897   /// Simplicity means that the way to change the types defined
   975   /// Simplicity means that the way to change the types defined
   898   /// in the traits class is based on functions that returns the new class
   976   /// in the traits class is based on functions that returns the new class
   899   /// and not on templatable built-in classes.
   977   /// and not on templatable built-in classes.
   900   /// When using the plain \ref Bfs
   978   /// When using the plain \ref Bfs
   901   /// the new class with the modified type comes from
   979   /// the new class with the modified type comes from
   902   /// the original class by using the ::
   980   /// the original class by using the ::
   903   /// operator. In the case of \ref BfsWizard only
   981   /// operator. In the case of \ref BfsWizard only
   904   /// a function have to be called and it will
   982   /// a function have to be called, and it will
   905   /// return the needed class.
   983   /// return the needed class.
   906   ///
   984   ///
   907   /// It does not have own \ref run method. When its \ref run method is called
   985   /// It does not have own \ref run() method. When its \ref run() method
   908   /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
   986   /// is called, it initiates a plain \ref Bfs object, and calls the
   909   /// method of it.
   987   /// \ref Bfs::run() method of it.
   910   template<class TR>
   988   template<class TR>
   911   class BfsWizard : public TR
   989   class BfsWizard : public TR
   912   {
   990   {
   913     typedef TR Base;
   991     typedef TR Base;
   914 
   992 
   915     ///The type of the underlying digraph.
   993     ///The type of the digraph the algorithm runs on.
   916     typedef typename TR::Digraph Digraph;
   994     typedef typename TR::Digraph Digraph;
   917     //\e
   995 
   918     typedef typename Digraph::Node Node;
   996     typedef typename Digraph::Node Node;
   919     //\e
       
   920     typedef typename Digraph::NodeIt NodeIt;
   997     typedef typename Digraph::NodeIt NodeIt;
   921     //\e
       
   922     typedef typename Digraph::Arc Arc;
   998     typedef typename Digraph::Arc Arc;
   923     //\e
       
   924     typedef typename Digraph::OutArcIt OutArcIt;
   999     typedef typename Digraph::OutArcIt OutArcIt;
   925 
  1000 
   926     ///\brief The type of the map that stores
  1001     ///\brief The type of the map that stores the predecessor
   927     ///the reached nodes
       
   928     typedef typename TR::ReachedMap ReachedMap;
       
   929     ///\brief The type of the map that stores
       
   930     ///the processed nodes
       
   931     typedef typename TR::ProcessedMap ProcessedMap;
       
   932     ///\brief The type of the map that stores the last
       
   933     ///arcs of the shortest paths.
  1002     ///arcs of the shortest paths.
   934     typedef typename TR::PredMap PredMap;
  1003     typedef typename TR::PredMap PredMap;
   935     ///The type of the map that stores the dists of the nodes.
  1004     ///\brief The type of the map that stores the distances of the nodes.
   936     typedef typename TR::DistMap DistMap;
  1005     typedef typename TR::DistMap DistMap;
       
  1006     ///\brief The type of the map that indicates which nodes are reached.
       
  1007     typedef typename TR::ReachedMap ReachedMap;
       
  1008     ///\brief The type of the map that indicates which nodes are processed.
       
  1009     typedef typename TR::ProcessedMap ProcessedMap;
   937 
  1010 
   938   public:
  1011   public:
       
  1012 
   939     /// Constructor.
  1013     /// Constructor.
   940     BfsWizard() : TR() {}
  1014     BfsWizard() : TR() {}
   941 
  1015 
   942     /// Constructor that requires parameters.
  1016     /// Constructor that requires parameters.
   943 
  1017 
   949     ///Copy constructor
  1023     ///Copy constructor
   950     BfsWizard(const TR &b) : TR(b) {}
  1024     BfsWizard(const TR &b) : TR(b) {}
   951 
  1025 
   952     ~BfsWizard() {}
  1026     ~BfsWizard() {}
   953 
  1027 
   954     ///Runs Bfs algorithm from a given node.
  1028     ///Runs BFS algorithm from a source node.
   955 
  1029 
   956     ///Runs Bfs algorithm from a given node.
  1030     ///Runs BFS algorithm from a source node.
   957     ///The node can be given by the \ref source function.
  1031     ///The node can be given with the \ref source() function.
   958     void run()
  1032     void run()
   959     {
  1033     {
   960       if(Base::_source==INVALID) throw UninitializedParameter();
  1034       if(Base::_source==INVALID) throw UninitializedParameter();
   961       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
  1035       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
   962       if(Base::_reached)
  1036       if(Base::_reached)
   968       if(Base::_dist)
  1042       if(Base::_dist)
   969         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1043         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   970       alg.run(Base::_source);
  1044       alg.run(Base::_source);
   971     }
  1045     }
   972 
  1046 
   973     ///Runs Bfs algorithm from the given node.
  1047     ///Runs BFS algorithm from the given node.
   974 
  1048 
   975     ///Runs Bfs algorithm from the given node.
  1049     ///Runs BFS algorithm from the given node.
   976     ///\param s is the given source.
  1050     ///\param s is the given source.
   977     void run(Node s)
  1051     void run(Node s)
   978     {
  1052     {
   979       Base::_source=s;
  1053       Base::_source=s;
   980       run();
  1054       run();
       
  1055     }
       
  1056 
       
  1057     /// Sets the source node, from which the Bfs algorithm runs.
       
  1058 
       
  1059     /// Sets the source node, from which the Bfs algorithm runs.
       
  1060     /// \param s is the source node.
       
  1061     BfsWizard<TR> &source(Node s)
       
  1062     {
       
  1063       Base::_source=s;
       
  1064       return *this;
   981     }
  1065     }
   982 
  1066 
   983     template<class T>
  1067     template<class T>
   984     struct DefPredMapBase : public Base {
  1068     struct DefPredMapBase : public Base {
   985       typedef T PredMap;
  1069       typedef T PredMap;
   986       static PredMap *createPredMap(const Digraph &) { return 0; };
  1070       static PredMap *createPredMap(const Digraph &) { return 0; };
   987       DefPredMapBase(const TR &b) : TR(b) {}
  1071       DefPredMapBase(const TR &b) : TR(b) {}
   988     };
  1072     };
   989 
       
   990     ///\brief \ref named-templ-param "Named parameter"
  1073     ///\brief \ref named-templ-param "Named parameter"
   991     ///function for setting PredMap
  1074     ///for setting \ref PredMap object.
   992     ///
  1075     ///
   993     /// \ref named-templ-param "Named parameter"
  1076     /// \ref named-templ-param "Named parameter"
   994     ///function for setting PredMap
  1077     ///for setting \ref PredMap object.
   995     ///
       
   996     template<class T>
  1078     template<class T>
   997     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
  1079     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
   998     {
  1080     {
   999       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1081       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1000       return BfsWizard<DefPredMapBase<T> >(*this);
  1082       return BfsWizard<DefPredMapBase<T> >(*this);
  1001     }
  1083     }
  1002 
       
  1003 
  1084 
  1004     template<class T>
  1085     template<class T>
  1005     struct DefReachedMapBase : public Base {
  1086     struct DefReachedMapBase : public Base {
  1006       typedef T ReachedMap;
  1087       typedef T ReachedMap;
  1007       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1088       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1008       DefReachedMapBase(const TR &b) : TR(b) {}
  1089       DefReachedMapBase(const TR &b) : TR(b) {}
  1009     };
  1090     };
  1010 
       
  1011     ///\brief \ref named-templ-param "Named parameter"
  1091     ///\brief \ref named-templ-param "Named parameter"
  1012     ///function for setting ReachedMap
  1092     ///for setting \ref ReachedMap object.
  1013     ///
  1093     ///
  1014     /// \ref named-templ-param "Named parameter"
  1094     /// \ref named-templ-param "Named parameter"
  1015     ///function for setting ReachedMap
  1095     ///for setting \ref ReachedMap object.
  1016     ///
       
  1017     template<class T>
  1096     template<class T>
  1018     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
  1097     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
  1019     {
  1098     {
  1020       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1099       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1021       return BfsWizard<DefReachedMapBase<T> >(*this);
  1100       return BfsWizard<DefReachedMapBase<T> >(*this);
  1022     }
  1101     }
  1023 
       
  1024 
  1102 
  1025     template<class T>
  1103     template<class T>
  1026     struct DefProcessedMapBase : public Base {
  1104     struct DefProcessedMapBase : public Base {
  1027       typedef T ProcessedMap;
  1105       typedef T ProcessedMap;
  1028       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1106       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1029       DefProcessedMapBase(const TR &b) : TR(b) {}
  1107       DefProcessedMapBase(const TR &b) : TR(b) {}
  1030     };
  1108     };
  1031 
       
  1032     ///\brief \ref named-templ-param "Named parameter"
  1109     ///\brief \ref named-templ-param "Named parameter"
  1033     ///function for setting ProcessedMap
  1110     ///for setting \ref ProcessedMap object.
  1034     ///
  1111     ///
  1035     /// \ref named-templ-param "Named parameter"
  1112     /// \ref named-templ-param "Named parameter"
  1036     ///function for setting ProcessedMap
  1113     ///for setting \ref ProcessedMap object.
  1037     ///
       
  1038     template<class T>
  1114     template<class T>
  1039     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  1115     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  1040     {
  1116     {
  1041       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1117       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1042       return BfsWizard<DefProcessedMapBase<T> >(*this);
  1118       return BfsWizard<DefProcessedMapBase<T> >(*this);
  1043     }
  1119     }
  1044 
       
  1045 
  1120 
  1046     template<class T>
  1121     template<class T>
  1047     struct DefDistMapBase : public Base {
  1122     struct DefDistMapBase : public Base {
  1048       typedef T DistMap;
  1123       typedef T DistMap;
  1049       static DistMap *createDistMap(const Digraph &) { return 0; };
  1124       static DistMap *createDistMap(const Digraph &) { return 0; };
  1050       DefDistMapBase(const TR &b) : TR(b) {}
  1125       DefDistMapBase(const TR &b) : TR(b) {}
  1051     };
  1126     };
  1052 
       
  1053     ///\brief \ref named-templ-param "Named parameter"
  1127     ///\brief \ref named-templ-param "Named parameter"
  1054     ///function for setting DistMap type
  1128     ///for setting \ref DistMap object.
  1055     ///
  1129     ///
  1056     /// \ref named-templ-param "Named parameter"
  1130     /// \ref named-templ-param "Named parameter"
  1057     ///function for setting DistMap type
  1131     ///for setting \ref DistMap object.
  1058     ///
       
  1059     template<class T>
  1132     template<class T>
  1060     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
  1133     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
  1061     {
  1134     {
  1062       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1135       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1063       return BfsWizard<DefDistMapBase<T> >(*this);
  1136       return BfsWizard<DefDistMapBase<T> >(*this);
  1064     }
       
  1065 
       
  1066     /// Sets the source node, from which the Bfs algorithm runs.
       
  1067 
       
  1068     /// Sets the source node, from which the Bfs algorithm runs.
       
  1069     /// \param s is the source node.
       
  1070     BfsWizard<TR> &source(Node s)
       
  1071     {
       
  1072       Base::_source=s;
       
  1073       return *this;
       
  1074     }
  1137     }
  1075 
  1138 
  1076   };
  1139   };
  1077 
  1140 
  1078   ///Function type interface for Bfs algorithm.
  1141   ///Function type interface for Bfs algorithm.
  1098   {
  1161   {
  1099     return BfsWizard<BfsWizardBase<GR> >(g,s);
  1162     return BfsWizard<BfsWizardBase<GR> >(g,s);
  1100   }
  1163   }
  1101 
  1164 
  1102 #ifdef DOXYGEN
  1165 #ifdef DOXYGEN
  1103   /// \brief Visitor class for bfs.
  1166   /// \brief Visitor class for BFS.
  1104   ///
  1167   ///
  1105   /// This class defines the interface of the BfsVisit events, and
  1168   /// This class defines the interface of the BfsVisit events, and
  1106   /// it could be the base of a real Visitor class.
  1169   /// it could be the base of a real visitor class.
  1107   template <typename _Digraph>
  1170   template <typename _Digraph>
  1108   struct BfsVisitor {
  1171   struct BfsVisitor {
  1109     typedef _Digraph Digraph;
  1172     typedef _Digraph Digraph;
  1110     typedef typename Digraph::Arc Arc;
  1173     typedef typename Digraph::Arc Arc;
  1111     typedef typename Digraph::Node Node;
  1174     typedef typename Digraph::Node Node;
  1112     /// \brief Called when the arc reach a node.
  1175     /// \brief Called for the source node(s) of the BFS.
  1113     ///
  1176     ///
  1114     /// It is called when the bfs find an arc which target is not
  1177     /// This function is called for the source node(s) of the BFS.
  1115     /// reached yet.
  1178     void start(const Node& node) {}
       
  1179     /// \brief Called when a node is reached first time.
       
  1180     ///
       
  1181     /// This function is called when a node is reached first time.
       
  1182     void reach(const Node& node) {}
       
  1183     /// \brief Called when a node is processed.
       
  1184     ///
       
  1185     /// This function is called when a node is processed.
       
  1186     void process(const Node& node) {}
       
  1187     /// \brief Called when an arc reaches a new node.
       
  1188     ///
       
  1189     /// This function is called when the BFS finds an arc whose target node
       
  1190     /// is not reached yet.
  1116     void discover(const Arc& arc) {}
  1191     void discover(const Arc& arc) {}
  1117     /// \brief Called when the node reached first time.
  1192     /// \brief Called when an arc is examined but its target node is
  1118     ///
       
  1119     /// It is Called when the node reached first time.
       
  1120     void reach(const Node& node) {}
       
  1121     /// \brief Called when the arc examined but target of the arc
       
  1122     /// already discovered.
  1193     /// already discovered.
  1123     ///
  1194     ///
  1124     /// It called when the arc examined but the target of the arc
  1195     /// This function is called when an arc is examined but its target node is
  1125     /// already discovered.
  1196     /// already discovered.
  1126     void examine(const Arc& arc) {}
  1197     void examine(const Arc& arc) {}
  1127     /// \brief Called for the source node of the bfs.
       
  1128     ///
       
  1129     /// It is called for the source node of the bfs.
       
  1130     void start(const Node& node) {}
       
  1131     /// \brief Called when the node processed.
       
  1132     ///
       
  1133     /// It is Called when the node processed.
       
  1134     void process(const Node& node) {}
       
  1135   };
  1198   };
  1136 #else
  1199 #else
  1137   template <typename _Digraph>
  1200   template <typename _Digraph>
  1138   struct BfsVisitor {
  1201   struct BfsVisitor {
  1139     typedef _Digraph Digraph;
  1202     typedef _Digraph Digraph;
  1140     typedef typename Digraph::Arc Arc;
  1203     typedef typename Digraph::Arc Arc;
  1141     typedef typename Digraph::Node Node;
  1204     typedef typename Digraph::Node Node;
       
  1205     void start(const Node&) {}
       
  1206     void reach(const Node&) {}
       
  1207     void process(const Node&) {}
  1142     void discover(const Arc&) {}
  1208     void discover(const Arc&) {}
  1143     void reach(const Node&) {}
       
  1144     void examine(const Arc&) {}
  1209     void examine(const Arc&) {}
  1145     void start(const Node&) {}
       
  1146     void process(const Node&) {}
       
  1147 
  1210 
  1148     template <typename _Visitor>
  1211     template <typename _Visitor>
  1149     struct Constraints {
  1212     struct Constraints {
  1150       void constraints() {
  1213       void constraints() {
  1151         Arc arc;
  1214         Arc arc;
  1152         Node node;
  1215         Node node;
       
  1216         visitor.start(node);
       
  1217         visitor.reach(node);
       
  1218         visitor.process(node);
  1153         visitor.discover(arc);
  1219         visitor.discover(arc);
  1154         visitor.reach(node);
       
  1155         visitor.examine(arc);
  1220         visitor.examine(arc);
  1156         visitor.start(node);
       
  1157         visitor.process(node);
       
  1158       }
  1221       }
  1159       _Visitor& visitor;
  1222       _Visitor& visitor;
  1160     };
  1223     };
  1161   };
  1224   };
  1162 #endif
  1225 #endif
  1163 
  1226 
  1164   /// \brief Default traits class of BfsVisit class.
  1227   /// \brief Default traits class of BfsVisit class.
  1165   ///
  1228   ///
  1166   /// Default traits class of BfsVisit class.
  1229   /// Default traits class of BfsVisit class.
  1167   /// \tparam _Digraph Digraph type.
  1230   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1168   template<class _Digraph>
  1231   template<class _Digraph>
  1169   struct BfsVisitDefaultTraits {
  1232   struct BfsVisitDefaultTraits {
  1170 
  1233 
  1171     /// \brief The digraph type the algorithm runs on.
  1234     /// \brief The type of the digraph the algorithm runs on.
  1172     typedef _Digraph Digraph;
  1235     typedef _Digraph Digraph;
  1173 
  1236 
  1174     /// \brief The type of the map that indicates which nodes are reached.
  1237     /// \brief The type of the map that indicates which nodes are reached.
  1175     ///
  1238     ///
  1176     /// The type of the map that indicates which nodes are reached.
  1239     /// The type of the map that indicates which nodes are reached.
  1177     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1240     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1178     /// \todo named parameter to set this type, function to read and write.
       
  1179     typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1241     typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1180 
  1242 
  1181     /// \brief Instantiates a ReachedMap.
  1243     /// \brief Instantiates a \ref ReachedMap.
  1182     ///
  1244     ///
  1183     /// This function instantiates a \ref ReachedMap.
  1245     /// This function instantiates a \ref ReachedMap.
  1184     /// \param digraph is the digraph, to which
  1246     /// \param digraph is the digraph, to which
  1185     /// we would like to define the \ref ReachedMap.
  1247     /// we would like to define the \ref ReachedMap.
  1186     static ReachedMap *createReachedMap(const Digraph &digraph) {
  1248     static ReachedMap *createReachedMap(const Digraph &digraph) {
  1189 
  1251 
  1190   };
  1252   };
  1191 
  1253 
  1192   /// \ingroup search
  1254   /// \ingroup search
  1193   ///
  1255   ///
  1194   /// \brief %BFS Visit algorithm class.
  1256   /// \brief %BFS algorithm class with visitor interface.
  1195   ///
  1257   ///
  1196   /// This class provides an efficient implementation of the %BFS algorithm
  1258   /// This class provides an efficient implementation of the %BFS algorithm
  1197   /// with visitor interface.
  1259   /// with visitor interface.
  1198   ///
  1260   ///
  1199   /// The %BfsVisit class provides an alternative interface to the Bfs
  1261   /// The %BfsVisit class provides an alternative interface to the Bfs
  1200   /// class. It works with callback mechanism, the BfsVisit object calls
  1262   /// class. It works with callback mechanism, the BfsVisit object calls
  1201   /// on every bfs event the \c Visitor class member functions.
  1263   /// the member functions of the \c Visitor class on every BFS event.
  1202   ///
  1264   ///
  1203   /// \tparam _Digraph The digraph type the algorithm runs on.
  1265   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1204   /// The default value is
  1266   /// The default value is
  1205   /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
  1267   /// \ref ListDigraph. The value of _Digraph is not used directly by
  1206   /// is only passed to \ref BfsDefaultTraits.
  1268   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
  1207   /// \tparam _Visitor The Visitor object for the algorithm. The
  1269   /// \tparam _Visitor The Visitor type that is used by the algorithm.
  1208   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
  1270   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
  1209   /// does not observe the Bfs events. If you want to observe the bfs
  1271   /// does not observe the BFS events. If you want to observe the BFS
  1210   /// events you should implement your own Visitor class.
  1272   /// events, you should implement your own visitor class.
  1211   /// \tparam _Traits Traits class to set various data types used by the
  1273   /// \tparam _Traits Traits class to set various data types used by the
  1212   /// algorithm. The default traits class is
  1274   /// algorithm. The default traits class is
  1213   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
  1275   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
  1214   /// See \ref BfsVisitDefaultTraits for the documentation of
  1276   /// See \ref BfsVisitDefaultTraits for the documentation of
  1215   /// a Bfs visit traits class.
  1277   /// a BFS visit traits class.
  1216 #ifdef DOXYGEN
  1278 #ifdef DOXYGEN
  1217   template <typename _Digraph, typename _Visitor, typename _Traits>
  1279   template <typename _Digraph, typename _Visitor, typename _Traits>
  1218 #else
  1280 #else
  1219   template <typename _Digraph = ListDigraph,
  1281   template <typename _Digraph = ListDigraph,
  1220             typename _Visitor = BfsVisitor<_Digraph>,
  1282             typename _Visitor = BfsVisitor<_Digraph>,
  1224   public:
  1286   public:
  1225 
  1287 
  1226     /// \brief \ref Exception for uninitialized parameters.
  1288     /// \brief \ref Exception for uninitialized parameters.
  1227     ///
  1289     ///
  1228     /// This error represents problems in the initialization
  1290     /// This error represents problems in the initialization
  1229     /// of the parameters of the algorithms.
  1291     /// of the parameters of the algorithm.
  1230     class UninitializedParameter : public lemon::UninitializedParameter {
  1292     class UninitializedParameter : public lemon::UninitializedParameter {
  1231     public:
  1293     public:
  1232       virtual const char* what() const throw()
  1294       virtual const char* what() const throw()
  1233       {
  1295       {
  1234         return "lemon::BfsVisit::UninitializedParameter";
  1296         return "lemon::BfsVisit::UninitializedParameter";
  1235       }
  1297       }
  1236     };
  1298     };
  1237 
  1299 
       
  1300     ///The traits class.
  1238     typedef _Traits Traits;
  1301     typedef _Traits Traits;
  1239 
  1302 
       
  1303     ///The type of the digraph the algorithm runs on.
  1240     typedef typename Traits::Digraph Digraph;
  1304     typedef typename Traits::Digraph Digraph;
  1241 
  1305 
       
  1306     ///The visitor type used by the algorithm.
  1242     typedef _Visitor Visitor;
  1307     typedef _Visitor Visitor;
  1243 
  1308 
  1244     ///The type of the map indicating which nodes are reached.
  1309     ///The type of the map that indicates which nodes are reached.
  1245     typedef typename Traits::ReachedMap ReachedMap;
  1310     typedef typename Traits::ReachedMap ReachedMap;
  1246 
  1311 
  1247   private:
  1312   private:
  1248 
  1313 
  1249     typedef typename Digraph::Node Node;
  1314     typedef typename Digraph::Node Node;
  1250     typedef typename Digraph::NodeIt NodeIt;
  1315     typedef typename Digraph::NodeIt NodeIt;
  1251     typedef typename Digraph::Arc Arc;
  1316     typedef typename Digraph::Arc Arc;
  1252     typedef typename Digraph::OutArcIt OutArcIt;
  1317     typedef typename Digraph::OutArcIt OutArcIt;
  1253 
  1318 
  1254     /// Pointer to the underlying digraph.
  1319     //Pointer to the underlying digraph.
  1255     const Digraph *_digraph;
  1320     const Digraph *_digraph;
  1256     /// Pointer to the visitor object.
  1321     //Pointer to the visitor object.
  1257     Visitor *_visitor;
  1322     Visitor *_visitor;
  1258     ///Pointer to the map of reached status of the nodes.
  1323     //Pointer to the map of reached status of the nodes.
  1259     ReachedMap *_reached;
  1324     ReachedMap *_reached;
  1260     ///Indicates if \ref _reached is locally allocated (\c true) or not.
  1325     //Indicates if _reached is locally allocated (true) or not.
  1261     bool local_reached;
  1326     bool local_reached;
  1262 
  1327 
  1263     std::vector<typename Digraph::Node> _list;
  1328     std::vector<typename Digraph::Node> _list;
  1264     int _list_front, _list_back;
  1329     int _list_front, _list_back;
  1265 
  1330 
  1266     /// \brief Creates the maps if necessary.
  1331     ///Creates the maps if necessary.
  1267     ///
  1332     ///\todo Better memory allocation (instead of new).
  1268     /// Creates the maps if necessary.
       
  1269     void create_maps() {
  1333     void create_maps() {
  1270       if(!_reached) {
  1334       if(!_reached) {
  1271         local_reached = true;
  1335         local_reached = true;
  1272         _reached = Traits::createReachedMap(*_digraph);
  1336         _reached = Traits::createReachedMap(*_digraph);
  1273       }
  1337       }
  1290       static ReachedMap *createReachedMap(const Digraph &digraph) {
  1354       static ReachedMap *createReachedMap(const Digraph &digraph) {
  1291         throw UninitializedParameter();
  1355         throw UninitializedParameter();
  1292       }
  1356       }
  1293     };
  1357     };
  1294     /// \brief \ref named-templ-param "Named parameter" for setting
  1358     /// \brief \ref named-templ-param "Named parameter" for setting
  1295     /// ReachedMap type
  1359     /// ReachedMap type.
  1296     ///
  1360     ///
  1297     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
  1361     /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
  1298     template <class T>
  1362     template <class T>
  1299     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
  1363     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
  1300                                             DefReachedMapTraits<T> > {
  1364                                             DefReachedMapTraits<T> > {
  1301       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
  1365       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
  1302     };
  1366     };
  1306 
  1370 
  1307     /// \brief Constructor.
  1371     /// \brief Constructor.
  1308     ///
  1372     ///
  1309     /// Constructor.
  1373     /// Constructor.
  1310     ///
  1374     ///
  1311     /// \param digraph the digraph the algorithm will run on.
  1375     /// \param digraph The digraph the algorithm runs on.
  1312     /// \param visitor The visitor of the algorithm.
  1376     /// \param visitor The visitor object of the algorithm.
  1313     ///
       
  1314     BfsVisit(const Digraph& digraph, Visitor& visitor)
  1377     BfsVisit(const Digraph& digraph, Visitor& visitor)
  1315       : _digraph(&digraph), _visitor(&visitor),
  1378       : _digraph(&digraph), _visitor(&visitor),
  1316         _reached(0), local_reached(false) {}
  1379         _reached(0), local_reached(false) {}
  1317 
  1380 
  1318     /// \brief Destructor.
  1381     /// \brief Destructor.
  1319     ///
       
  1320     /// Destructor.
       
  1321     ~BfsVisit() {
  1382     ~BfsVisit() {
  1322       if(local_reached) delete _reached;
  1383       if(local_reached) delete _reached;
  1323     }
  1384     }
  1324 
  1385 
  1325     /// \brief Sets the map indicating if a node is reached.
  1386     /// \brief Sets the map that indicates which nodes are reached.
  1326     ///
  1387     ///
  1327     /// Sets the map indicating if a node is reached.
  1388     /// Sets the map that indicates which nodes are reached.
  1328     /// If you don't use this function before calling \ref run(),
  1389     /// If you don't use this function before calling \ref run(),
  1329     /// it will allocate one. The destuctor deallocates this
  1390     /// it will allocate one. The destructor deallocates this
  1330     /// automatically allocated map, of course.
  1391     /// automatically allocated map, of course.
  1331     /// \return <tt> (*this) </tt>
  1392     /// \return <tt> (*this) </tt>
  1332     BfsVisit &reachedMap(ReachedMap &m) {
  1393     BfsVisit &reachedMap(ReachedMap &m) {
  1333       if(local_reached) {
  1394       if(local_reached) {
  1334         delete _reached;
  1395         delete _reached;
  1337       _reached = &m;
  1398       _reached = &m;
  1338       return *this;
  1399       return *this;
  1339     }
  1400     }
  1340 
  1401 
  1341   public:
  1402   public:
       
  1403 
  1342     /// \name Execution control
  1404     /// \name Execution control
  1343     /// The simplest way to execute the algorithm is to use
  1405     /// The simplest way to execute the algorithm is to use
  1344     /// one of the member functions called \c run(...).
  1406     /// one of the member functions called \ref lemon::BfsVisit::run()
       
  1407     /// "run()".
  1345     /// \n
  1408     /// \n
  1346     /// If you need more control on the execution,
  1409     /// If you need more control on the execution, first you must call
  1347     /// first you must call \ref init(), then you can adda source node
  1410     /// \ref lemon::BfsVisit::init() "init()", then you can add several
  1348     /// with \ref addSource().
  1411     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
  1349     /// Finally \ref start() will perform the actual path
  1412     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
  1350     /// computation.
  1413     /// actual path computation.
  1351 
  1414 
  1352     /// @{
  1415     /// @{
       
  1416 
  1353     /// \brief Initializes the internal data structures.
  1417     /// \brief Initializes the internal data structures.
  1354     ///
  1418     ///
  1355     /// Initializes the internal data structures.
  1419     /// Initializes the internal data structures.
  1356     ///
       
  1357     void init() {
  1420     void init() {
  1358       create_maps();
  1421       create_maps();
  1359       _list.resize(countNodes(*_digraph));
  1422       _list.resize(countNodes(*_digraph));
  1360       _list_front = _list_back = -1;
  1423       _list_front = _list_back = -1;
  1361       for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
  1424       for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
  1379     ///
  1442     ///
  1380     /// Processes the next node.
  1443     /// Processes the next node.
  1381     ///
  1444     ///
  1382     /// \return The processed node.
  1445     /// \return The processed node.
  1383     ///
  1446     ///
  1384     /// \pre The queue must not be empty!
  1447     /// \pre The queue must not be empty.
  1385     Node processNextNode() {
  1448     Node processNextNode() {
  1386       Node n = _list[++_list_front];
  1449       Node n = _list[++_list_front];
  1387       _visitor->process(n);
  1450       _visitor->process(n);
  1388       Arc e;
  1451       Arc e;
  1389       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1452       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1400       return n;
  1463       return n;
  1401     }
  1464     }
  1402 
  1465 
  1403     /// \brief Processes the next node.
  1466     /// \brief Processes the next node.
  1404     ///
  1467     ///
  1405     /// Processes the next node. And checks that the given target node
  1468     /// Processes the next node and checks if the given target node
  1406     /// is reached. If the target node is reachable from the processed
  1469     /// is reached. If the target node is reachable from the processed
  1407     /// node then the reached parameter will be set true. The reached
  1470     /// node, then the \c reach parameter will be set to \c true.
  1408     /// parameter should be initially false.
       
  1409     ///
  1471     ///
  1410     /// \param target The target node.
  1472     /// \param target The target node.
  1411     /// \retval reach Indicates that the target node is reached.
  1473     /// \retval reach Indicates if the target node is reached.
       
  1474     /// It should be initially \c false.
       
  1475     ///
  1412     /// \return The processed node.
  1476     /// \return The processed node.
  1413     ///
  1477     ///
  1414     /// \warning The queue must not be empty!
  1478     /// \pre The queue must not be empty.
  1415     Node processNextNode(Node target, bool& reach) {
  1479     Node processNextNode(Node target, bool& reach) {
  1416       Node n = _list[++_list_front];
  1480       Node n = _list[++_list_front];
  1417       _visitor->process(n);
  1481       _visitor->process(n);
  1418       Arc e;
  1482       Arc e;
  1419       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1483       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1431       return n;
  1495       return n;
  1432     }
  1496     }
  1433 
  1497 
  1434     /// \brief Processes the next node.
  1498     /// \brief Processes the next node.
  1435     ///
  1499     ///
  1436     /// Processes the next node. And checks that at least one of
  1500     /// Processes the next node and checks if at least one of reached
  1437     /// reached node has true value in the \c nm node map. If one node
  1501     /// nodes has \c true value in the \c nm node map. If one node
  1438     /// with true value is reachable from the processed node then the
  1502     /// with \c true value is reachable from the processed node, then the
  1439     /// rnode parameter will be set to the first of such nodes.
  1503     /// \c rnode parameter will be set to the first of such nodes.
  1440     ///
  1504     ///
  1441     /// \param nm The node map of possible targets.
  1505     /// \param nm A \c bool (or convertible) node map that indicates the
       
  1506     /// possible targets.
  1442     /// \retval rnode The reached target node.
  1507     /// \retval rnode The reached target node.
       
  1508     /// It should be initially \c INVALID.
       
  1509     ///
  1443     /// \return The processed node.
  1510     /// \return The processed node.
  1444     ///
  1511     ///
  1445     /// \warning The queue must not be empty!
  1512     /// \pre The queue must not be empty.
  1446     template <typename NM>
  1513     template <typename NM>
  1447     Node processNextNode(const NM& nm, Node& rnode) {
  1514     Node processNextNode(const NM& nm, Node& rnode) {
  1448       Node n = _list[++_list_front];
  1515       Node n = _list[++_list_front];
  1449       _visitor->process(n);
  1516       _visitor->process(n);
  1450       Arc e;
  1517       Arc e;
  1461         }
  1528         }
  1462       }
  1529       }
  1463       return n;
  1530       return n;
  1464     }
  1531     }
  1465 
  1532 
  1466     /// \brief Next node to be processed.
  1533     /// \brief The next node to be processed.
  1467     ///
  1534     ///
  1468     /// Next node to be processed.
  1535     /// Returns the next node to be processed or \c INVALID if the queue
  1469     ///
  1536     /// is empty.
  1470     /// \return The next node to be processed or INVALID if the stack is
  1537     Node nextNode() const {
  1471     /// empty.
       
  1472     Node nextNode() {
       
  1473       return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
  1538       return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
  1474     }
  1539     }
  1475 
  1540 
  1476     /// \brief Returns \c false if there are nodes
  1541     /// \brief Returns \c false if there are nodes
  1477     /// to be processed in the queue
  1542     /// to be processed.
  1478     ///
  1543     ///
  1479     /// Returns \c false if there are nodes
  1544     /// Returns \c false if there are nodes
  1480     /// to be processed in the queue
  1545     /// to be processed in the queue.
  1481     bool emptyQueue() { return _list_front == _list_back; }
  1546     bool emptyQueue() const { return _list_front == _list_back; }
  1482 
  1547 
  1483     /// \brief Returns the number of the nodes to be processed.
  1548     /// \brief Returns the number of the nodes to be processed.
  1484     ///
  1549     ///
  1485     /// Returns the number of the nodes to be processed in the queue.
  1550     /// Returns the number of the nodes to be processed in the queue.
  1486     int queueSize() { return _list_back - _list_front; }
  1551     int queueSize() const { return _list_back - _list_front; }
  1487 
  1552 
  1488     /// \brief Executes the algorithm.
  1553     /// \brief Executes the algorithm.
  1489     ///
  1554     ///
  1490     /// Executes the algorithm.
  1555     /// Executes the algorithm.
  1491     ///
  1556     ///
  1492     /// \pre init() must be called and at least one node should be added
  1557     /// This method runs the %BFS algorithm from the root node(s)
       
  1558     /// in order to compute the shortest path to each node.
       
  1559     ///
       
  1560     /// The algorithm computes
       
  1561     /// - the shortest path tree (forest),
       
  1562     /// - the distance of each node from the root(s).
       
  1563     ///
       
  1564     /// \pre init() must be called and at least one root node should be added
  1493     /// with addSource() before using this function.
  1565     /// with addSource() before using this function.
       
  1566     ///
       
  1567     /// \note <tt>b.start()</tt> is just a shortcut of the following code.
       
  1568     /// \code
       
  1569     ///   while ( !b.emptyQueue() ) {
       
  1570     ///     b.processNextNode();
       
  1571     ///   }
       
  1572     /// \endcode
  1494     void start() {
  1573     void start() {
  1495       while ( !emptyQueue() ) processNextNode();
  1574       while ( !emptyQueue() ) processNextNode();
  1496     }
  1575     }
  1497 
  1576 
  1498     /// \brief Executes the algorithm until \c dest is reached.
  1577     /// \brief Executes the algorithm until the given target node is reached.
  1499     ///
  1578     ///
  1500     /// Executes the algorithm until \c dest is reached.
  1579     /// Executes the algorithm until the given target node is reached.
  1501     ///
  1580     ///
  1502     /// \pre init() must be called and at least one node should be added
  1581     /// This method runs the %BFS algorithm from the root node(s)
  1503     /// with addSource() before using this function.
  1582     /// in order to compute the shortest path to \c dest.
       
  1583     ///
       
  1584     /// The algorithm computes
       
  1585     /// - the shortest path to \c dest,
       
  1586     /// - the distance of \c dest from the root(s).
       
  1587     ///
       
  1588     /// \pre init() must be called and at least one root node should be
       
  1589     /// added with addSource() before using this function.
       
  1590     ///
       
  1591     /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
       
  1592     /// \code
       
  1593     ///   bool reach = false;
       
  1594     ///   while ( !b.emptyQueue() && !reach ) {
       
  1595     ///     b.processNextNode(t, reach);
       
  1596     ///   }
       
  1597     /// \endcode
  1504     void start(Node dest) {
  1598     void start(Node dest) {
  1505       bool reach = false;
  1599       bool reach = false;
  1506       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
  1600       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
  1507     }
  1601     }
  1508 
  1602 
  1509     /// \brief Executes the algorithm until a condition is met.
  1603     /// \brief Executes the algorithm until a condition is met.
  1510     ///
  1604     ///
  1511     /// Executes the algorithm until a condition is met.
  1605     /// Executes the algorithm until a condition is met.
  1512     ///
  1606     ///
  1513     /// \pre init() must be called and at least one node should be added
  1607     /// This method runs the %BFS algorithm from the root node(s) in
  1514     /// with addSource() before using this function.
  1608     /// order to compute the shortest path to a node \c v with
  1515     ///
  1609     /// <tt>nm[v]</tt> true, if such a node can be found.
  1516     ///\param nm must be a bool (or convertible) node map. The
  1610     ///
  1517     ///algorithm will stop when it reaches a node \c v with
  1611     /// \param nm must be a bool (or convertible) node map. The
       
  1612     /// algorithm will stop when it reaches a node \c v with
  1518     /// <tt>nm[v]</tt> true.
  1613     /// <tt>nm[v]</tt> true.
  1519     ///
  1614     ///
  1520     ///\return The reached node \c v with <tt>nm[v]</tt> true or
  1615     /// \return The reached node \c v with <tt>nm[v]</tt> true or
  1521     ///\c INVALID if no such node was found.
  1616     /// \c INVALID if no such node was found.
       
  1617     ///
       
  1618     /// \pre init() must be called and at least one root node should be
       
  1619     /// added with addSource() before using this function.
       
  1620     ///
       
  1621     /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
       
  1622     /// \code
       
  1623     ///   Node rnode = INVALID;
       
  1624     ///   while ( !b.emptyQueue() && rnode == INVALID ) {
       
  1625     ///     b.processNextNode(nm, rnode);
       
  1626     ///   }
       
  1627     ///   return rnode;
       
  1628     /// \endcode
  1522     template <typename NM>
  1629     template <typename NM>
  1523     Node start(const NM &nm) {
  1630     Node start(const NM &nm) {
  1524       Node rnode = INVALID;
  1631       Node rnode = INVALID;
  1525       while ( !emptyQueue() && rnode == INVALID ) {
  1632       while ( !emptyQueue() && rnode == INVALID ) {
  1526         processNextNode(nm, rnode);
  1633         processNextNode(nm, rnode);
  1527       }
  1634       }
  1528       return rnode;
  1635       return rnode;
  1529     }
  1636     }
  1530 
  1637 
  1531     /// \brief Runs %BFSVisit algorithm from node \c s.
  1638     /// \brief Runs the algorithm from the given node.
  1532     ///
  1639     ///
  1533     /// This method runs the %BFS algorithm from a root node \c s.
  1640     /// This method runs the %BFS algorithm from node \c s
  1534     /// \note b.run(s) is just a shortcut of the following code.
  1641     /// in order to compute the shortest path to each node.
       
  1642     ///
       
  1643     /// The algorithm computes
       
  1644     /// - the shortest path tree,
       
  1645     /// - the distance of each node from the root.
       
  1646     ///
       
  1647     /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  1535     ///\code
  1648     ///\code
  1536     ///   b.init();
  1649     ///   b.init();
  1537     ///   b.addSource(s);
  1650     ///   b.addSource(s);
  1538     ///   b.start();
  1651     ///   b.start();
  1539     ///\endcode
  1652     ///\endcode
  1541       init();
  1654       init();
  1542       addSource(s);
  1655       addSource(s);
  1543       start();
  1656       start();
  1544     }
  1657     }
  1545 
  1658 
  1546     /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
  1659     /// \brief Runs the algorithm to visit all nodes in the digraph.
  1547     ///
  1660     ///
  1548     /// This method runs the %BFS algorithm in order to
  1661     /// This method runs the %BFS algorithm in order to
  1549     /// compute the %BFS path to each node. The algorithm computes
  1662     /// compute the shortest path to each node.
  1550     /// - The %BFS tree.
  1663     ///
  1551     /// - The distance of each node from the root in the %BFS tree.
  1664     /// The algorithm computes
  1552     ///
  1665     /// - the shortest path tree (forest),
  1553     ///\note b.run() is just a shortcut of the following code.
  1666     /// - the distance of each node from the root(s).
       
  1667     ///
       
  1668     /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  1554     ///\code
  1669     ///\code
  1555     ///  b.init();
  1670     ///  b.init();
  1556     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
  1671     ///  for (NodeIt n(gr); n != INVALID; ++n) {
  1557     ///    if (!b.reached(it)) {
  1672     ///    if (!b.reached(n)) {
  1558     ///      b.addSource(it);
  1673     ///      b.addSource(n);
  1559     ///      b.start();
  1674     ///      b.start();
  1560     ///    }
  1675     ///    }
  1561     ///  }
  1676     ///  }
  1562     ///\endcode
  1677     ///\endcode
  1563     void run() {
  1678     void run() {
  1567           addSource(it);
  1682           addSource(it);
  1568           start();
  1683           start();
  1569         }
  1684         }
  1570       }
  1685       }
  1571     }
  1686     }
       
  1687 
  1572     ///@}
  1688     ///@}
  1573 
  1689 
  1574     /// \name Query Functions
  1690     /// \name Query Functions
  1575     /// The result of the %BFS algorithm can be obtained using these
  1691     /// The result of the %BFS algorithm can be obtained using these
  1576     /// functions.\n
  1692     /// functions.\n
  1577     /// Before the use of these functions,
  1693     /// Either \ref lemon::BfsVisit::run() "run()" or
  1578     /// either run() or start() must be called.
  1694     /// \ref lemon::BfsVisit::start() "start()" must be called before
       
  1695     /// using them.
  1579     ///@{
  1696     ///@{
  1580 
  1697 
  1581     /// \brief Checks if a node is reachable from the root.
  1698     /// \brief Checks if a node is reachable from the root(s).
  1582     ///
  1699     ///
  1583     /// Returns \c true if \c v is reachable from the root(s).
  1700     /// Returns \c true if \c v is reachable from the root(s).
  1584     /// \warning The source nodes are inditated as unreachable.
       
  1585     /// \pre Either \ref run() or \ref start()
  1701     /// \pre Either \ref run() or \ref start()
  1586     /// must be called before using this function.
  1702     /// must be called before using this function.
  1587     ///
       
  1588     bool reached(Node v) { return (*_reached)[v]; }
  1703     bool reached(Node v) { return (*_reached)[v]; }
       
  1704 
  1589     ///@}
  1705     ///@}
       
  1706 
  1590   };
  1707   };
  1591 
  1708 
  1592 } //END OF NAMESPACE LEMON
  1709 } //END OF NAMESPACE LEMON
  1593 
  1710 
  1594 #endif
  1711 #endif
  1595