///

     ///

     ///The type of the map that stores the predecessor

     ///The type of the map that stores the predecessor

     ///arcs of the shortest paths.

     ///arcs of the shortest paths.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

     ///\param g is the digraph, to which we would like to define the

     ///\param g is the digraph, to which we would like to define the

     static PredMap *createPredMap(const Digraph &g)

     static PredMap *createPredMap(const Digraph &g)

     {

     {

       return new PredMap(g);

       return new PredMap(g);

     }

     }

     ///The type of the map that indicates which nodes are processed.

     ///The type of the map that indicates which nodes are processed.

     ///The type of the map that indicates which nodes are processed.

     ///The type of the map that indicates which nodes are processed.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

     ///\param g is the digraph, to which

     ///\param g is the digraph, to which

 #ifdef DOXYGEN

 #ifdef DOXYGEN

     static ProcessedMap *createProcessedMap(const Digraph &g)

     static ProcessedMap *createProcessedMap(const Digraph &g)

 #else

 #else

     static ProcessedMap *createProcessedMap(const Digraph &)

     static ProcessedMap *createProcessedMap(const Digraph &)

 #endif

 #endif

     ///The type of the map that indicates which nodes are reached.

     ///The type of the map that indicates which nodes are reached.

     ///The type of the map that indicates which nodes are reached.

     ///The type of the map that indicates which nodes are reached.

     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

     typedef typename Digraph::template NodeMap<bool> ReachedMap;

     typedef typename Digraph::template NodeMap<bool> ReachedMap;

     ///\param g is the digraph, to which

     ///\param g is the digraph, to which

     static ReachedMap *createReachedMap(const Digraph &g)

     static ReachedMap *createReachedMap(const Digraph &g)

     {

     {

       return new ReachedMap(g);

       return new ReachedMap(g);

     }

     }

     ///The type of the map that stores the distances of the nodes.

     ///The type of the map that stores the distances of the nodes.

     ///The type of the map that stores the distances of the nodes.

     ///The type of the map that stores the distances of the nodes.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     typedef typename Digraph::template NodeMap<int> DistMap;

     typedef typename Digraph::template NodeMap<int> DistMap;

     ///\param g is the digraph, to which we would like to define the

     ///\param g is the digraph, to which we would like to define the

     static DistMap *createDistMap(const Digraph &g)

     static DistMap *createDistMap(const Digraph &g)

     {

     {

       return new DistMap(g);

       return new DistMap(g);

     }

     }

   };

   };

         LEMON_ASSERT(false, "PredMap is not initialized");

         LEMON_ASSERT(false, "PredMap is not initialized");

         return 0; // ignore warnings

         return 0; // ignore warnings

       }

       }

     };

     };

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///

     ///

     ///\ref named-templ-param "Named parameter" for setting

     ///\ref named-templ-param "Named parameter" for setting

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     template <class T>

     template <class T>

     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {

     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {

       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;

       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;

     };

     };

         LEMON_ASSERT(false, "DistMap is not initialized");

         LEMON_ASSERT(false, "DistMap is not initialized");

         return 0; // ignore warnings

         return 0; // ignore warnings

       }

       }

     };

     };

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///

     ///

     ///\ref named-templ-param "Named parameter" for setting

     ///\ref named-templ-param "Named parameter" for setting

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     template <class T>

     template <class T>

     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {

     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {

       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;

       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;

     };

     };

         LEMON_ASSERT(false, "ReachedMap is not initialized");

         LEMON_ASSERT(false, "ReachedMap is not initialized");

         return 0; // ignore warnings

         return 0; // ignore warnings

       }

       }

     };

     };

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///

     ///

     ///\ref named-templ-param "Named parameter" for setting

     ///\ref named-templ-param "Named parameter" for setting

     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

     template <class T>

     template <class T>

     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {

     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {

       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;

       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;

     };

     };

         LEMON_ASSERT(false, "ProcessedMap is not initialized");

         LEMON_ASSERT(false, "ProcessedMap is not initialized");

         return 0; // ignore warnings

         return 0; // ignore warnings

       }

       }

     };

     };

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///

     ///

     ///\ref named-templ-param "Named parameter" for setting

     ///\ref named-templ-param "Named parameter" for setting

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

     template <class T>

     template <class T>

     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {

     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {

       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;

       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;

     };

     };

         return new ProcessedMap(g);

         return new ProcessedMap(g);

         return 0; // ignore warnings

         return 0; // ignore warnings

       }

       }

     };

     };

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///\brief \ref named-templ-param "Named parameter" for setting

     ///

     ///

     ///\ref named-templ-param "Named parameter" for setting

     ///\ref named-templ-param "Named parameter" for setting

     ///If you don't set it explicitly, it will be automatically allocated.

     ///If you don't set it explicitly, it will be automatically allocated.

     struct SetStandardProcessedMap :

     struct SetStandardProcessedMap :

       public Bfs< Digraph, SetStandardProcessedMapTraits > {

       public Bfs< Digraph, SetStandardProcessedMapTraits > {

       typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;

       typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;

     };

     };

 #ifdef DOXYGEN

 #ifdef DOXYGEN

   /// \brief Visitor class for BFS.

   /// \brief Visitor class for BFS.

   ///

   ///

   /// This class defines the interface of the BfsVisit events, and

   /// This class defines the interface of the BfsVisit events, and

   /// it could be the base of a real visitor class.

   /// it could be the base of a real visitor class.

   struct BfsVisitor {

   struct BfsVisitor {

     typedef typename Digraph::Arc Arc;

     typedef typename Digraph::Arc Arc;

     typedef typename Digraph::Node Node;

     typedef typename Digraph::Node Node;

     /// \brief Called for the source node(s) of the BFS.

     /// \brief Called for the source node(s) of the BFS.

     ///

     ///

     /// This function is called for the source node(s) of the BFS.

     /// This function is called for the source node(s) of the BFS.

     /// This function is called when an arc is examined but its target node is

     /// This function is called when an arc is examined but its target node is

     /// already discovered.

     /// already discovered.

     void examine(const Arc& arc) {}

     void examine(const Arc& arc) {}

   };

   };

 #else

 #else

   struct BfsVisitor {

   struct BfsVisitor {

     typedef typename Digraph::Arc Arc;

     typedef typename Digraph::Arc Arc;

     typedef typename Digraph::Node Node;

     typedef typename Digraph::Node Node;

     void start(const Node&) {}

     void start(const Node&) {}

     void reach(const Node&) {}

     void reach(const Node&) {}

     void process(const Node&) {}

     void process(const Node&) {}

 #endif

 #endif

   /// \brief Default traits class of BfsVisit class.

   /// \brief Default traits class of BfsVisit class.

   ///

   ///

   /// Default traits class of BfsVisit class.

   /// Default traits class of BfsVisit class.

   struct BfsVisitDefaultTraits {

   struct BfsVisitDefaultTraits {

     /// \brief The type of the digraph the algorithm runs on.

     /// \brief The type of the digraph the algorithm runs on.

     /// \brief The type of the map that indicates which nodes are reached.

     /// \brief The type of the map that indicates which nodes are reached.

     ///

     ///

     /// The type of the map that indicates which nodes are reached.

     /// The type of the map that indicates which nodes are reached.

     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

   };

   };

   /// \ingroup search

   /// \ingroup search

   ///

   ///

   ///

   ///

   /// with visitor interface.

   /// with visitor interface.

   ///

   ///

   /// class. It works with callback mechanism, the BfsVisit object calls

   /// class. It works with callback mechanism, the BfsVisit object calls

   /// the member functions of the \c Visitor class on every BFS event.

   /// the member functions of the \c Visitor class on every BFS event.

   ///

   ///

   /// This interface of the BFS algorithm should be used in special cases

   /// This interface of the BFS algorithm should be used in special cases

   /// when extra actions have to be performed in connection with certain

   /// when extra actions have to be performed in connection with certain

   /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()

   /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()

   /// instead.

   /// instead.

   ///

   ///

   /// does not observe the BFS events. If you want to observe the BFS

   /// does not observe the BFS events. If you want to observe the BFS

   /// events, you should implement your own visitor class.

   /// events, you should implement your own visitor class.

   /// algorithm. The default traits class is

   /// algorithm. The default traits class is

   /// See \ref BfsVisitDefaultTraits for the documentation of

   /// See \ref BfsVisitDefaultTraits for the documentation of

   /// a BFS visit traits class.

   /// a BFS visit traits class.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

 #else

 #else

 #endif

 #endif

   class BfsVisit {

   class BfsVisit {

   public:

   public:

     ///The traits class.

     ///The traits class.

     ///The type of the digraph the algorithm runs on.

     ///The type of the digraph the algorithm runs on.

     typedef typename Traits::Digraph Digraph;

     typedef typename Traits::Digraph Digraph;

     ///The visitor type used by the algorithm.

     ///The visitor type used by the algorithm.

     ///The type of the map that indicates which nodes are reached.

     ///The type of the map that indicates which nodes are reached.

     typedef typename Traits::ReachedMap ReachedMap;

     typedef typename Traits::ReachedMap ReachedMap;

   private:

   private: