lemon/bfs.h
changeset 284 a16cc721259e
parent 280 e7f8647ce760
parent 278 931190050520
child 287 bb40b6db0a58
equal deleted inserted replaced
12:37f6b65014b8 13:0188b3dae1fd
    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 #include <lemon/path.h>
    31 
    32 
    32 namespace lemon {
    33 namespace lemon {
    33 
    34 
    34   ///Default traits class of Bfs class.
    35   ///Default traits class of Bfs class.
    35 
    36 
   111   ///%BFS algorithm class.
   112   ///%BFS algorithm class.
   112 
   113 
   113   ///\ingroup search
   114   ///\ingroup search
   114   ///This class provides an efficient implementation of the %BFS algorithm.
   115   ///This class provides an efficient implementation of the %BFS algorithm.
   115   ///
   116   ///
   116   ///There is also a \ref bfs() "function type interface" for the BFS
   117   ///There is also a \ref bfs() "function-type interface" for the BFS
   117   ///algorithm, which is convenient in the simplier cases and it can be
   118   ///algorithm, which is convenient in the simplier cases and it can be
   118   ///used easier.
   119   ///used easier.
   119   ///
   120   ///
   120   ///\tparam GR The type of the digraph the algorithm runs on.
   121   ///\tparam GR The type of the digraph the algorithm runs on.
   121   ///The default value is \ref ListDigraph. The value of GR is not used
   122   ///The default value is \ref ListDigraph. The value of GR is not used
   836     ///arcs of the shortest paths.
   837     ///arcs of the shortest paths.
   837     ///
   838     ///
   838     ///The type of the map that stores the predecessor
   839     ///The type of the map that stores the predecessor
   839     ///arcs of the shortest paths.
   840     ///arcs of the shortest paths.
   840     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   841     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   841     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
   842     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   842     ///Instantiates a \ref PredMap.
   843     ///Instantiates a \ref PredMap.
   843 
   844 
   844     ///This function instantiates a \ref PredMap.
   845     ///This function instantiates a \ref PredMap.
   845     ///\param g is the digraph, to which we would like to define the
   846     ///\param g is the digraph, to which we would like to define the
   846     ///\ref PredMap.
   847     ///\ref PredMap.
   847 #ifdef DOXYGEN
       
   848     static PredMap *createPredMap(const Digraph &g)
   848     static PredMap *createPredMap(const Digraph &g)
   849 #else
   849     {
   850     static PredMap *createPredMap(const Digraph &)
   850       return new PredMap(g);
   851 #endif
       
   852     {
       
   853       return new PredMap();
       
   854     }
   851     }
   855 
   852 
   856     ///The type of the map that indicates which nodes are processed.
   853     ///The type of the map that indicates which nodes are processed.
   857 
   854 
   858     ///The type of the map that indicates which nodes are processed.
   855     ///The type of the map that indicates which nodes are processed.
   859     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   856     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   857     ///By default it is a NullMap.
   860     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   858     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   861     ///Instantiates a \ref ProcessedMap.
   859     ///Instantiates a \ref ProcessedMap.
   862 
   860 
   863     ///This function instantiates a \ref ProcessedMap.
   861     ///This function instantiates a \ref ProcessedMap.
   864     ///\param g is the digraph, to which
   862     ///\param g is the digraph, to which
   889 
   887 
   890     ///The type of the map that stores the distances of the nodes.
   888     ///The type of the map that stores the distances of the nodes.
   891 
   889 
   892     ///The type of the map that stores the distances of the nodes.
   890     ///The type of the map that stores the distances of the nodes.
   893     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   891     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   894     ///
   892     typedef typename Digraph::template NodeMap<int> DistMap;
   895     typedef NullMap<typename Digraph::Node,int> DistMap;
       
   896     ///Instantiates a \ref DistMap.
   893     ///Instantiates a \ref DistMap.
   897 
   894 
   898     ///This function instantiates a \ref DistMap.
   895     ///This function instantiates a \ref DistMap.
   899     ///\param g is the digraph, to which we would like to define
   896     ///\param g is the digraph, to which we would like to define
   900     ///the \ref DistMap
   897     ///the \ref DistMap
   901 #ifdef DOXYGEN
       
   902     static DistMap *createDistMap(const Digraph &g)
   898     static DistMap *createDistMap(const Digraph &g)
   903 #else
   899     {
   904     static DistMap *createDistMap(const Digraph &)
   900       return new DistMap(g);
   905 #endif
   901     }
   906     {
   902 
   907       return new DistMap();
   903     ///The type of the shortest paths.
   908     }
   904 
       
   905     ///The type of the shortest paths.
       
   906     ///It must meet the \ref concepts::Path "Path" concept.
       
   907     typedef lemon::Path<Digraph> Path;
   909   };
   908   };
   910 
   909 
   911   /// Default traits class used by \ref BfsWizard
   910   /// Default traits class used by \ref BfsWizard
   912 
   911 
   913   /// To make it easier to use Bfs algorithm
   912   /// To make it easier to use Bfs algorithm
   933     void *_processed;
   932     void *_processed;
   934     //Pointer to the map of predecessors arcs.
   933     //Pointer to the map of predecessors arcs.
   935     void *_pred;
   934     void *_pred;
   936     //Pointer to the map of distances.
   935     //Pointer to the map of distances.
   937     void *_dist;
   936     void *_dist;
   938     //Pointer to the source node.
   937     //Pointer to the shortest path to the target node.
   939     Node _source;
   938     void *_path;
       
   939     //Pointer to the distance of the target node.
       
   940     int *_di;
   940 
   941 
   941     public:
   942     public:
   942     /// Constructor.
   943     /// Constructor.
   943 
   944 
   944     /// This constructor does not require parameters, therefore it initiates
   945     /// This constructor does not require parameters, therefore it initiates
   945     /// all of the attributes to default values (0, INVALID).
   946     /// all of the attributes to \c 0.
   946     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   947     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   947                       _dist(0), _source(INVALID) {}
   948                       _dist(0), _path(0), _di(0) {}
   948 
   949 
   949     /// Constructor.
   950     /// Constructor.
   950 
   951 
   951     /// This constructor requires some parameters,
   952     /// This constructor requires one parameter,
   952     /// listed in the parameters list.
   953     /// others are initiated to \c 0.
   953     /// Others are initiated to 0.
       
   954     /// \param g The digraph the algorithm runs on.
   954     /// \param g The digraph the algorithm runs on.
   955     /// \param s The source node.
   955     BfsWizardBase(const GR &g) :
   956     BfsWizardBase(const GR &g, Node s=INVALID) :
       
   957       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   956       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   958       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   957       _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
   959 
   958 
   960   };
   959   };
   961 
   960 
   962   /// Auxiliary class for the function type interface of BFS algorithm.
   961   /// Auxiliary class for the function-type interface of BFS algorithm.
   963 
   962 
   964   /// This auxiliary class is created to implement the function type
   963   /// This auxiliary class is created to implement the
   965   /// interface of \ref Bfs algorithm. It uses the functions and features
   964   /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
   966   /// of the plain \ref Bfs, but it is much simpler to use it.
   965   /// It does not have own \ref run() method, it uses the functions
   967   /// It should only be used through the \ref bfs() function, which makes
   966   /// and features of the plain \ref Bfs.
   968   /// it easier to use the algorithm.
       
   969   ///
   967   ///
   970   /// Simplicity means that the way to change the types defined
   968   /// This class should only be used through the \ref bfs() function,
   971   /// in the traits class is based on functions that returns the new class
   969   /// which makes it easier to use the algorithm.
   972   /// and not on templatable built-in classes.
       
   973   /// When using the plain \ref Bfs
       
   974   /// the new class with the modified type comes from
       
   975   /// the original class by using the ::
       
   976   /// operator. In the case of \ref BfsWizard only
       
   977   /// a function have to be called, and it will
       
   978   /// return the needed class.
       
   979   ///
       
   980   /// It does not have own \ref run() method. When its \ref run() method
       
   981   /// is called, it initiates a plain \ref Bfs object, and calls the
       
   982   /// \ref Bfs::run() method of it.
       
   983   template<class TR>
   970   template<class TR>
   984   class BfsWizard : public TR
   971   class BfsWizard : public TR
   985   {
   972   {
   986     typedef TR Base;
   973     typedef TR Base;
   987 
   974 
  1000     typedef typename TR::DistMap DistMap;
   987     typedef typename TR::DistMap DistMap;
  1001     ///\brief The type of the map that indicates which nodes are reached.
   988     ///\brief The type of the map that indicates which nodes are reached.
  1002     typedef typename TR::ReachedMap ReachedMap;
   989     typedef typename TR::ReachedMap ReachedMap;
  1003     ///\brief The type of the map that indicates which nodes are processed.
   990     ///\brief The type of the map that indicates which nodes are processed.
  1004     typedef typename TR::ProcessedMap ProcessedMap;
   991     typedef typename TR::ProcessedMap ProcessedMap;
       
   992     ///The type of the shortest paths
       
   993     typedef typename TR::Path Path;
  1005 
   994 
  1006   public:
   995   public:
  1007 
   996 
  1008     /// Constructor.
   997     /// Constructor.
  1009     BfsWizard() : TR() {}
   998     BfsWizard() : TR() {}
  1010 
   999 
  1011     /// Constructor that requires parameters.
  1000     /// Constructor that requires parameters.
  1012 
  1001 
  1013     /// Constructor that requires parameters.
  1002     /// Constructor that requires parameters.
  1014     /// These parameters will be the default values for the traits class.
  1003     /// These parameters will be the default values for the traits class.
  1015     BfsWizard(const Digraph &g, Node s=INVALID) :
  1004     /// \param g The digraph the algorithm runs on.
  1016       TR(g,s) {}
  1005     BfsWizard(const Digraph &g) :
       
  1006       TR(g) {}
  1017 
  1007 
  1018     ///Copy constructor
  1008     ///Copy constructor
  1019     BfsWizard(const TR &b) : TR(b) {}
  1009     BfsWizard(const TR &b) : TR(b) {}
  1020 
  1010 
  1021     ~BfsWizard() {}
  1011     ~BfsWizard() {}
  1022 
  1012 
  1023     ///Runs BFS algorithm from a source node.
  1013     ///Runs BFS algorithm from the given source node.
  1024 
  1014 
  1025     ///Runs BFS algorithm from a source node.
  1015     ///This method runs BFS algorithm from node \c s
  1026     ///The node can be given with the \ref source() function.
  1016     ///in order to compute the shortest path to each node.
       
  1017     void run(Node s)
       
  1018     {
       
  1019       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
       
  1020       if (Base::_pred)
       
  1021         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
       
  1022       if (Base::_dist)
       
  1023         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
       
  1024       if (Base::_reached)
       
  1025         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
       
  1026       if (Base::_processed)
       
  1027         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
       
  1028       if (s!=INVALID)
       
  1029         alg.run(s);
       
  1030       else
       
  1031         alg.run();
       
  1032     }
       
  1033 
       
  1034     ///Finds the shortest path between \c s and \c t.
       
  1035 
       
  1036     ///This method runs BFS algorithm from node \c s
       
  1037     ///in order to compute the shortest path to node \c t
       
  1038     ///(it stops searching when \c t is processed).
       
  1039     ///
       
  1040     ///\return \c true if \c t is reachable form \c s.
       
  1041     bool run(Node s, Node t)
       
  1042     {
       
  1043       if (s==INVALID || t==INVALID) throw UninitializedParameter();
       
  1044       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
       
  1045       if (Base::_pred)
       
  1046         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
       
  1047       if (Base::_dist)
       
  1048         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
       
  1049       if (Base::_reached)
       
  1050         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
       
  1051       if (Base::_processed)
       
  1052         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
       
  1053       alg.run(s,t);
       
  1054       if (Base::_path)
       
  1055         *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
       
  1056       if (Base::_di)
       
  1057         *Base::_di = alg.dist(t);
       
  1058       return alg.reached(t);
       
  1059     }
       
  1060 
       
  1061     ///Runs BFS algorithm to visit all nodes in the digraph.
       
  1062 
       
  1063     ///This method runs BFS algorithm in order to compute
       
  1064     ///the shortest path to each node.
  1027     void run()
  1065     void run()
  1028     {
  1066     {
  1029       if(Base::_source==INVALID) throw UninitializedParameter();
  1067       run(INVALID);
  1030       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
       
  1031       if(Base::_reached)
       
  1032         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
       
  1033       if(Base::_processed)
       
  1034         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
       
  1035       if(Base::_pred)
       
  1036         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
       
  1037       if(Base::_dist)
       
  1038         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
       
  1039       alg.run(Base::_source);
       
  1040     }
       
  1041 
       
  1042     ///Runs BFS algorithm from the given node.
       
  1043 
       
  1044     ///Runs BFS algorithm from the given node.
       
  1045     ///\param s is the given source.
       
  1046     void run(Node s)
       
  1047     {
       
  1048       Base::_source=s;
       
  1049       run();
       
  1050     }
       
  1051 
       
  1052     /// Sets the source node, from which the Bfs algorithm runs.
       
  1053 
       
  1054     /// Sets the source node, from which the Bfs algorithm runs.
       
  1055     /// \param s is the source node.
       
  1056     BfsWizard<TR> &source(Node s)
       
  1057     {
       
  1058       Base::_source=s;
       
  1059       return *this;
       
  1060     }
  1068     }
  1061 
  1069 
  1062     template<class T>
  1070     template<class T>
  1063     struct SetPredMapBase : public Base {
  1071     struct SetPredMapBase : public Base {
  1064       typedef T PredMap;
  1072       typedef T PredMap;
  1065       static PredMap *createPredMap(const Digraph &) { return 0; };
  1073       static PredMap *createPredMap(const Digraph &) { return 0; };
  1066       SetPredMapBase(const TR &b) : TR(b) {}
  1074       SetPredMapBase(const TR &b) : TR(b) {}
  1067     };
  1075     };
  1068     ///\brief \ref named-templ-param "Named parameter"
  1076     ///\brief \ref named-func-param "Named parameter"
  1069     ///for setting \ref PredMap object.
  1077     ///for setting \ref PredMap object.
  1070     ///
  1078     ///
  1071     /// \ref named-templ-param "Named parameter"
  1079     ///\ref named-func-param "Named parameter"
  1072     ///for setting \ref PredMap object.
  1080     ///for setting \ref PredMap object.
  1073     template<class T>
  1081     template<class T>
  1074     BfsWizard<SetPredMapBase<T> > predMap(const T &t)
  1082     BfsWizard<SetPredMapBase<T> > predMap(const T &t)
  1075     {
  1083     {
  1076       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1084       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1081     struct SetReachedMapBase : public Base {
  1089     struct SetReachedMapBase : public Base {
  1082       typedef T ReachedMap;
  1090       typedef T ReachedMap;
  1083       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1091       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1084       SetReachedMapBase(const TR &b) : TR(b) {}
  1092       SetReachedMapBase(const TR &b) : TR(b) {}
  1085     };
  1093     };
  1086     ///\brief \ref named-templ-param "Named parameter"
  1094     ///\brief \ref named-func-param "Named parameter"
  1087     ///for setting \ref ReachedMap object.
  1095     ///for setting \ref ReachedMap object.
  1088     ///
  1096     ///
  1089     /// \ref named-templ-param "Named parameter"
  1097     /// \ref named-func-param "Named parameter"
  1090     ///for setting \ref ReachedMap object.
  1098     ///for setting \ref ReachedMap object.
  1091     template<class T>
  1099     template<class T>
  1092     BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
  1100     BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
  1093     {
  1101     {
  1094       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1102       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1095       return BfsWizard<SetReachedMapBase<T> >(*this);
  1103       return BfsWizard<SetReachedMapBase<T> >(*this);
       
  1104     }
       
  1105 
       
  1106     template<class T>
       
  1107     struct SetDistMapBase : public Base {
       
  1108       typedef T DistMap;
       
  1109       static DistMap *createDistMap(const Digraph &) { return 0; };
       
  1110       SetDistMapBase(const TR &b) : TR(b) {}
       
  1111     };
       
  1112     ///\brief \ref named-func-param "Named parameter"
       
  1113     ///for setting \ref DistMap object.
       
  1114     ///
       
  1115     /// \ref named-func-param "Named parameter"
       
  1116     ///for setting \ref DistMap object.
       
  1117     template<class T>
       
  1118     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
       
  1119     {
       
  1120       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
       
  1121       return BfsWizard<SetDistMapBase<T> >(*this);
  1096     }
  1122     }
  1097 
  1123 
  1098     template<class T>
  1124     template<class T>
  1099     struct SetProcessedMapBase : public Base {
  1125     struct SetProcessedMapBase : public Base {
  1100       typedef T ProcessedMap;
  1126       typedef T ProcessedMap;
  1101       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1127       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1102       SetProcessedMapBase(const TR &b) : TR(b) {}
  1128       SetProcessedMapBase(const TR &b) : TR(b) {}
  1103     };
  1129     };
  1104     ///\brief \ref named-templ-param "Named parameter"
  1130     ///\brief \ref named-func-param "Named parameter"
  1105     ///for setting \ref ProcessedMap object.
  1131     ///for setting \ref ProcessedMap object.
  1106     ///
  1132     ///
  1107     /// \ref named-templ-param "Named parameter"
  1133     /// \ref named-func-param "Named parameter"
  1108     ///for setting \ref ProcessedMap object.
  1134     ///for setting \ref ProcessedMap object.
  1109     template<class T>
  1135     template<class T>
  1110     BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1136     BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1111     {
  1137     {
  1112       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1138       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1113       return BfsWizard<SetProcessedMapBase<T> >(*this);
  1139       return BfsWizard<SetProcessedMapBase<T> >(*this);
  1114     }
  1140     }
  1115 
  1141 
  1116     template<class T>
  1142     template<class T>
  1117     struct SetDistMapBase : public Base {
  1143     struct SetPathBase : public Base {
  1118       typedef T DistMap;
  1144       typedef T Path;
  1119       static DistMap *createDistMap(const Digraph &) { return 0; };
  1145       SetPathBase(const TR &b) : TR(b) {}
  1120       SetDistMapBase(const TR &b) : TR(b) {}
  1146     };
  1121     };
  1147     ///\brief \ref named-func-param "Named parameter"
  1122     ///\brief \ref named-templ-param "Named parameter"
  1148     ///for getting the shortest path to the target node.
  1123     ///for setting \ref DistMap object.
  1149     ///
  1124     ///
  1150     ///\ref named-func-param "Named parameter"
  1125     /// \ref named-templ-param "Named parameter"
  1151     ///for getting the shortest path to the target node.
  1126     ///for setting \ref DistMap object.
       
  1127     template<class T>
  1152     template<class T>
  1128     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
  1153     BfsWizard<SetPathBase<T> > path(const T &t)
  1129     {
  1154     {
  1130       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1155       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1131       return BfsWizard<SetDistMapBase<T> >(*this);
  1156       return BfsWizard<SetPathBase<T> >(*this);
       
  1157     }
       
  1158 
       
  1159     ///\brief \ref named-func-param "Named parameter"
       
  1160     ///for getting the distance of the target node.
       
  1161     ///
       
  1162     ///\ref named-func-param "Named parameter"
       
  1163     ///for getting the distance of the target node.
       
  1164     BfsWizard dist(const int &d)
       
  1165     {
       
  1166       Base::_di=const_cast<int*>(&d);
       
  1167       return *this;
  1132     }
  1168     }
  1133 
  1169 
  1134   };
  1170   };
  1135 
  1171 
  1136   ///Function type interface for Bfs algorithm.
  1172   ///Function-type interface for BFS algorithm.
  1137 
  1173 
  1138   /// \ingroup search
  1174   /// \ingroup search
  1139   ///Function type interface for Bfs algorithm.
  1175   ///Function-type interface for BFS algorithm.
  1140   ///
  1176   ///
  1141   ///This function also has several
  1177   ///This function also has several \ref named-func-param "named parameters",
  1142   ///\ref named-templ-func-param "named parameters",
       
  1143   ///they are declared as the members of class \ref BfsWizard.
  1178   ///they are declared as the members of class \ref BfsWizard.
  1144   ///The following
  1179   ///The following examples show how to use these parameters.
  1145   ///example shows how to use these parameters.
       
  1146   ///\code
  1180   ///\code
  1147   ///  bfs(g,source).predMap(preds).run();
  1181   ///  // Compute shortest path from node s to each node
       
  1182   ///  bfs(g).predMap(preds).distMap(dists).run(s);
       
  1183   ///
       
  1184   ///  // Compute shortest path from s to t
       
  1185   ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
  1148   ///\endcode
  1186   ///\endcode
  1149   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
  1187   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
  1150   ///to the end of the parameter list.
  1188   ///to the end of the parameter list.
  1151   ///\sa BfsWizard
  1189   ///\sa BfsWizard
  1152   ///\sa Bfs
  1190   ///\sa Bfs
  1153   template<class GR>
  1191   template<class GR>
  1154   BfsWizard<BfsWizardBase<GR> >
  1192   BfsWizard<BfsWizardBase<GR> >
  1155   bfs(const GR &g,typename GR::Node s=INVALID)
  1193   bfs(const GR &digraph)
  1156   {
  1194   {
  1157     return BfsWizard<BfsWizardBase<GR> >(g,s);
  1195     return BfsWizard<BfsWizardBase<GR> >(digraph);
  1158   }
  1196   }
  1159 
  1197 
  1160 #ifdef DOXYGEN
  1198 #ifdef DOXYGEN
  1161   /// \brief Visitor class for BFS.
  1199   /// \brief Visitor class for BFS.
  1162   ///
  1200   ///