lemon/dfs.h
 changeset 281 e9b4fbe163f5 parent 280 e7f8647ce760 parent 278 931190050520 child 287 bb40b6db0a58
equal inserted replaced
12:0c70c82d512e 13:bd0229ea5f63
    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/assert.h>
    30 #include <lemon/assert.h>
    31 #include <lemon/maps.h>
    31 #include <lemon/maps.h>

    32 #include <lemon/path.h>
    32
    33
    33 namespace lemon {
    34 namespace lemon {
    34
    35
    35   ///Default traits class of Dfs class.
    36   ///Default traits class of Dfs class.
    36
    37
   112   ///%DFS algorithm class.
   113   ///%DFS algorithm class.
   113
   114
   114   ///\ingroup search
   115   ///\ingroup search
   115   ///This class provides an efficient implementation of the %DFS algorithm.
   116   ///This class provides an efficient implementation of the %DFS algorithm.
   116   ///
   117   ///
   117   ///There is also a \ref dfs() "function type interface" for the DFS
   118   ///There is also a \ref dfs() "function-type interface" for the DFS
   118   ///algorithm, which is convenient in the simplier cases and it can be
   119   ///algorithm, which is convenient in the simplier cases and it can be
   119   ///used easier.
   120   ///used easier.
   120   ///
   121   ///
   121   ///\tparam GR The type of the digraph the algorithm runs on.
   122   ///\tparam GR The type of the digraph the algorithm runs on.
   122   ///The default value is \ref ListDigraph. The value of GR is not used
   123   ///The default value is \ref ListDigraph. The value of GR is not used
   770     ///arcs of the %DFS paths.
   771     ///arcs of the %DFS paths.
   771     ///
   772     ///
   772     ///The type of the map that stores the predecessor
   773     ///The type of the map that stores the predecessor
   773     ///arcs of the %DFS paths.
   774     ///arcs of the %DFS paths.
   774     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   775     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   775     ///
   776     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   776     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;

   777     ///Instantiates a \ref PredMap.
   777     ///Instantiates a \ref PredMap.
   778
   778
   779     ///This function instantiates a \ref PredMap.
   779     ///This function instantiates a \ref PredMap.
   780     ///\param g is the digraph, to which we would like to define the
   780     ///\param g is the digraph, to which we would like to define the
   781     ///\ref PredMap.
   781     ///\ref PredMap.
   783     static PredMap *createPredMap(const Digraph &g)
   782     static PredMap *createPredMap(const Digraph &g)
   784 #else
   783     {
   785     static PredMap *createPredMap(const Digraph &)
   784       return new PredMap(g);
   786 #endif

   787     {

   788       return new PredMap();

   789     }
   785     }
   790
   786
   791     ///The type of the map that indicates which nodes are processed.
   787     ///The type of the map that indicates which nodes are processed.
   792
   788
   793     ///The type of the map that indicates which nodes are processed.
   789     ///The type of the map that indicates which nodes are processed.
   794     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   790     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

   791     ///By default it is a NullMap.
   795     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   792     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   796     ///Instantiates a \ref ProcessedMap.
   793     ///Instantiates a \ref ProcessedMap.
   797
   794
   798     ///This function instantiates a \ref ProcessedMap.
   795     ///This function instantiates a \ref ProcessedMap.
   799     ///\param g is the digraph, to which
   796     ///\param g is the digraph, to which
   824
   821
   825     ///The type of the map that stores the distances of the nodes.
   822     ///The type of the map that stores the distances of the nodes.
   826
   823
   827     ///The type of the map that stores the distances of the nodes.
   824     ///The type of the map that stores the distances of the nodes.
   828     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   825     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   829     ///
   826     typedef typename Digraph::template NodeMap<int> DistMap;
   830     typedef NullMap<typename Digraph::Node,int> DistMap;

   831     ///Instantiates a \ref DistMap.
   827     ///Instantiates a \ref DistMap.
   832
   828
   833     ///This function instantiates a \ref DistMap.
   829     ///This function instantiates a \ref DistMap.
   834     ///\param g is the digraph, to which we would like to define
   830     ///\param g is the digraph, to which we would like to define
   835     ///the \ref DistMap
   831     ///the \ref DistMap
   837     static DistMap *createDistMap(const Digraph &g)
   832     static DistMap *createDistMap(const Digraph &g)
   838 #else
   833     {
   839     static DistMap *createDistMap(const Digraph &)
   834       return new DistMap(g);
   840 #endif
   835     }
   841     {
   836
   842       return new DistMap();
   837     ///The type of the DFS paths.
   843     }
   838

   839     ///The type of the DFS paths.

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

   841     typedef lemon::Path<Digraph> Path;
   844   };
   842   };
   845
   843
   846   /// Default traits class used by \ref DfsWizard
   844   /// Default traits class used by \ref DfsWizard
   847
   845
   848   /// To make it easier to use Dfs algorithm
   846   /// To make it easier to use Dfs algorithm
   868     void *_processed;
   866     void *_processed;
   869     //Pointer to the map of predecessors arcs.
   867     //Pointer to the map of predecessors arcs.
   870     void *_pred;
   868     void *_pred;
   871     //Pointer to the map of distances.
   869     //Pointer to the map of distances.
   872     void *_dist;
   870     void *_dist;
   873     //Pointer to the source node.
   871     //Pointer to the DFS path to the target node.
   874     Node _source;
   872     void *_path;

   873     //Pointer to the distance of the target node.

   874     int *_di;
   875
   875
   876     public:
   876     public:
   877     /// Constructor.
   877     /// Constructor.
   878
   878
   879     /// This constructor does not require parameters, therefore it initiates
   879     /// This constructor does not require parameters, therefore it initiates
   880     /// all of the attributes to default values (0, INVALID).
   880     /// all of the attributes to \c 0.
   881     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   881     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   882                       _dist(0), _source(INVALID) {}
   882                       _dist(0), _path(0), _di(0) {}
   883
   883
   884     /// Constructor.
   884     /// Constructor.
   885
   885
   886     /// This constructor requires some parameters,
   886     /// This constructor requires one parameter,
   887     /// listed in the parameters list.
   887     /// others are initiated to \c 0.
   888     /// Others are initiated to 0.

   889     /// \param g The digraph the algorithm runs on.
   888     /// \param g The digraph the algorithm runs on.
   890     /// \param s The source node.
   889     DfsWizardBase(const GR &g) :
   891     DfsWizardBase(const GR &g, Node s=INVALID) :

   892       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   890       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   893       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   891       _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
   894
   892
   895   };
   893   };
   896
   894
   897   /// Auxiliary class for the function type interface of DFS algorithm.
   895   /// Auxiliary class for the function-type interface of DFS algorithm.
   898
   896
   899   /// This auxiliary class is created to implement the function type
   897   /// This auxiliary class is created to implement the
   900   /// interface of \ref Dfs algorithm. It uses the functions and features
   898   /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
   901   /// of the plain \ref Dfs, but it is much simpler to use it.
   899   /// It does not have own \ref run() method, it uses the functions
   902   /// It should only be used through the \ref dfs() function, which makes
   900   /// and features of the plain \ref Dfs.
   903   /// it easier to use the algorithm.

   904   ///
   901   ///
   905   /// Simplicity means that the way to change the types defined
   902   /// This class should only be used through the \ref dfs() function,
   906   /// in the traits class is based on functions that returns the new class
   903   /// which makes it easier to use the algorithm.
   907   /// and not on templatable built-in classes.

   908   /// When using the plain \ref Dfs

   909   /// the new class with the modified type comes from

   910   /// the original class by using the ::

   911   /// operator. In the case of \ref DfsWizard only

   912   /// a function have to be called, and it will

   913   /// return the needed class.

   914   ///

   915   /// It does not have own \ref run() method. When its \ref run() method

   916   /// is called, it initiates a plain \ref Dfs object, and calls the

   917   /// \ref Dfs::run() method of it.

   918   template<class TR>
   904   template<class TR>
   919   class DfsWizard : public TR
   905   class DfsWizard : public TR
   920   {
   906   {
   921     typedef TR Base;
   907     typedef TR Base;
   922
   908
   927     typedef typename Digraph::NodeIt NodeIt;
   913     typedef typename Digraph::NodeIt NodeIt;
   928     typedef typename Digraph::Arc Arc;
   914     typedef typename Digraph::Arc Arc;
   929     typedef typename Digraph::OutArcIt OutArcIt;
   915     typedef typename Digraph::OutArcIt OutArcIt;
   930
   916
   931     ///\brief The type of the map that stores the predecessor
   917     ///\brief The type of the map that stores the predecessor
   932     ///arcs of the shortest paths.
   918     ///arcs of the DFS paths.
   933     typedef typename TR::PredMap PredMap;
   919     typedef typename TR::PredMap PredMap;
   934     ///\brief The type of the map that stores the distances of the nodes.
   920     ///\brief The type of the map that stores the distances of the nodes.
   935     typedef typename TR::DistMap DistMap;
   921     typedef typename TR::DistMap DistMap;
   936     ///\brief The type of the map that indicates which nodes are reached.
   922     ///\brief The type of the map that indicates which nodes are reached.
   937     typedef typename TR::ReachedMap ReachedMap;
   923     typedef typename TR::ReachedMap ReachedMap;
   938     ///\brief The type of the map that indicates which nodes are processed.
   924     ///\brief The type of the map that indicates which nodes are processed.
   939     typedef typename TR::ProcessedMap ProcessedMap;
   925     typedef typename TR::ProcessedMap ProcessedMap;

   926     ///The type of the DFS paths

   927     typedef typename TR::Path Path;
   940
   928
   941   public:
   929   public:
   942
   930
   943     /// Constructor.
   931     /// Constructor.
   944     DfsWizard() : TR() {}
   932     DfsWizard() : TR() {}
   945
   933
   946     /// Constructor that requires parameters.
   934     /// Constructor that requires parameters.
   947
   935
   948     /// Constructor that requires parameters.
   936     /// Constructor that requires parameters.
   949     /// These parameters will be the default values for the traits class.
   937     /// These parameters will be the default values for the traits class.
   950     DfsWizard(const Digraph &g, Node s=INVALID) :
   938     /// \param g The digraph the algorithm runs on.
   951       TR(g,s) {}
   939     DfsWizard(const Digraph &g) :

   940       TR(g) {}
   952
   941
   953     ///Copy constructor
   942     ///Copy constructor
   954     DfsWizard(const TR &b) : TR(b) {}
   943     DfsWizard(const TR &b) : TR(b) {}
   955
   944
   956     ~DfsWizard() {}
   945     ~DfsWizard() {}
   957
   946
   958     ///Runs DFS algorithm from a source node.
   947     ///Runs DFS algorithm from the given source node.
   959
   948
   960     ///Runs DFS algorithm from a source node.
   949     ///This method runs DFS algorithm from node \c s
   961     ///The node can be given with the \ref source() function.
   950     ///in order to compute the DFS path to each node.

   951     void run(Node s)

   952     {

   953       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));

   954       if (Base::_pred)

   955         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

   956       if (Base::_dist)

   957         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

   958       if (Base::_reached)

   959         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));

   960       if (Base::_processed)

   961         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));

   962       if (s!=INVALID)

   963         alg.run(s);

   964       else

   965         alg.run();

   966     }

   967

   968     ///Finds the DFS path between \c s and \c t.

   969

   970     ///This method runs DFS algorithm from node \c s

   971     ///in order to compute the DFS path to node \c t

   972     ///(it stops searching when \c t is processed).

   973     ///

   974     ///\return \c true if \c t is reachable form \c s.

   975     bool run(Node s, Node t)

   976     {

   977       if (s==INVALID || t==INVALID) throw UninitializedParameter();

   978       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));

   979       if (Base::_pred)

   980         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

   981       if (Base::_dist)

   982         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

   983       if (Base::_reached)

   984         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));

   985       if (Base::_processed)

   986         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));

   987       alg.run(s,t);

   988       if (Base::_path)

   989         *reinterpret_cast<Path*>(Base::_path) = alg.path(t);

   990       if (Base::_di)

   991         *Base::_di = alg.dist(t);

   992       return alg.reached(t);

   993       }

   994

   995     ///Runs DFS algorithm to visit all nodes in the digraph.

   996

   997     ///This method runs DFS algorithm in order to compute

   998     ///the DFS path to each node.
   962     void run()
   999     void run()
   963     {
  1000     {
   964       if(Base::_source==INVALID) throw UninitializedParameter();
  1001       run(INVALID);
   965       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));

   966       if(Base::_reached)

   967         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));

   968       if(Base::_processed)

   969         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));

   970       if(Base::_pred)

   971         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

   972       if(Base::_dist)

   973         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

   974       alg.run(Base::_source);

   975     }

   976

   977     ///Runs DFS algorithm from the given node.

   978

   979     ///Runs DFS algorithm from the given node.

   980     ///\param s is the given source.

   981     void run(Node s)

   982     {

   983       Base::_source=s;

   984       run();

   985     }

   986

   987     /// Sets the source node, from which the Dfs algorithm runs.

   988

   989     /// Sets the source node, from which the Dfs algorithm runs.

   990     /// \param s is the source node.

   991     DfsWizard<TR> &source(Node s)

   992     {

   993       Base::_source=s;

   994       return *this;

   995     }
  1002     }
   996
  1003
   997     template<class T>
  1004     template<class T>
   998     struct SetPredMapBase : public Base {
  1005     struct SetPredMapBase : public Base {
   999       typedef T PredMap;
  1006       typedef T PredMap;
  1000       static PredMap *createPredMap(const Digraph &) { return 0; };
  1007       static PredMap *createPredMap(const Digraph &) { return 0; };
  1001       SetPredMapBase(const TR &b) : TR(b) {}
  1008       SetPredMapBase(const TR &b) : TR(b) {}
  1002     };
  1009     };
  1003     ///\brief \ref named-templ-param "Named parameter"
  1010     ///\brief \ref named-func-param "Named parameter"
  1004     ///for setting \ref PredMap object.
  1011     ///for setting \ref PredMap object.
  1005     ///
  1012     ///
  1006     ///\ref named-templ-param "Named parameter"
  1013     ///\ref named-func-param "Named parameter"
  1007     ///for setting \ref PredMap object.
  1014     ///for setting \ref PredMap object.
  1008     template<class T>
  1015     template<class T>
  1009     DfsWizard<SetPredMapBase<T> > predMap(const T &t)
  1016     DfsWizard<SetPredMapBase<T> > predMap(const T &t)
  1010     {
  1017     {
  1011       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1018       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1016     struct SetReachedMapBase : public Base {
  1023     struct SetReachedMapBase : public Base {
  1017       typedef T ReachedMap;
  1024       typedef T ReachedMap;
  1018       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1025       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1019       SetReachedMapBase(const TR &b) : TR(b) {}
  1026       SetReachedMapBase(const TR &b) : TR(b) {}
  1020     };
  1027     };
  1021     ///\brief \ref named-templ-param "Named parameter"
  1028     ///\brief \ref named-func-param "Named parameter"
  1022     ///for setting \ref ReachedMap object.
  1029     ///for setting \ref ReachedMap object.
  1023     ///
  1030     ///
  1024     /// \ref named-templ-param "Named parameter"
  1031     /// \ref named-func-param "Named parameter"
  1025     ///for setting \ref ReachedMap object.
  1032     ///for setting \ref ReachedMap object.
  1026     template<class T>
  1033     template<class T>
  1027     DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
  1034     DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
  1028     {
  1035     {
  1029       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1036       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1030       return DfsWizard<SetReachedMapBase<T> >(*this);
  1037       return DfsWizard<SetReachedMapBase<T> >(*this);

  1038     }

  1039

  1040     template<class T>

  1041     struct SetDistMapBase : public Base {

  1042       typedef T DistMap;

  1043       static DistMap *createDistMap(const Digraph &) { return 0; };

  1044       SetDistMapBase(const TR &b) : TR(b) {}

  1045     };

  1046     ///\brief \ref named-func-param "Named parameter"

  1047     ///for setting \ref DistMap object.

  1048     ///

  1049     /// \ref named-func-param "Named parameter"

  1050     ///for setting \ref DistMap object.

  1051     template<class T>

  1052     DfsWizard<SetDistMapBase<T> > distMap(const T &t)

  1053     {

  1054       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));

  1055       return DfsWizard<SetDistMapBase<T> >(*this);
  1031     }
  1056     }
  1032
  1057
  1033     template<class T>
  1058     template<class T>
  1034     struct SetProcessedMapBase : public Base {
  1059     struct SetProcessedMapBase : public Base {
  1035       typedef T ProcessedMap;
  1060       typedef T ProcessedMap;
  1036       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1061       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1037       SetProcessedMapBase(const TR &b) : TR(b) {}
  1062       SetProcessedMapBase(const TR &b) : TR(b) {}
  1038     };
  1063     };
  1039     ///\brief \ref named-templ-param "Named parameter"
  1064     ///\brief \ref named-func-param "Named parameter"
  1040     ///for setting \ref ProcessedMap object.
  1065     ///for setting \ref ProcessedMap object.
  1041     ///
  1066     ///
  1042     /// \ref named-templ-param "Named parameter"
  1067     /// \ref named-func-param "Named parameter"
  1043     ///for setting \ref ProcessedMap object.
  1068     ///for setting \ref ProcessedMap object.
  1044     template<class T>
  1069     template<class T>
  1045     DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1070     DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1046     {
  1071     {
  1047       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1072       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1048       return DfsWizard<SetProcessedMapBase<T> >(*this);
  1073       return DfsWizard<SetProcessedMapBase<T> >(*this);
  1049     }
  1074     }
  1050
  1075
  1051     template<class T>
  1076     template<class T>
  1052     struct SetDistMapBase : public Base {
  1077     struct SetPathBase : public Base {
  1053       typedef T DistMap;
  1078       typedef T Path;
  1054       static DistMap *createDistMap(const Digraph &) { return 0; };
  1079       SetPathBase(const TR &b) : TR(b) {}
  1055       SetDistMapBase(const TR &b) : TR(b) {}
  1080     };
  1056     };
  1081     ///\brief \ref named-func-param "Named parameter"
  1057     ///\brief \ref named-templ-param "Named parameter"
  1082     ///for getting the DFS path to the target node.
  1058     ///for setting \ref DistMap object.
  1083     ///
  1059     ///
  1084     ///\ref named-func-param "Named parameter"
  1060     ///\ref named-templ-param "Named parameter"
  1085     ///for getting the DFS path to the target node.
  1061     ///for setting \ref DistMap object.

  1062     template<class T>
  1086     template<class T>
  1063     DfsWizard<SetDistMapBase<T> > distMap(const T &t)
  1087     DfsWizard<SetPathBase<T> > path(const T &t)
  1064     {
  1088     {
  1065       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1089       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1066       return DfsWizard<SetDistMapBase<T> >(*this);
  1090       return DfsWizard<SetPathBase<T> >(*this);

  1091     }

  1092

  1093     ///\brief \ref named-func-param "Named parameter"

  1094     ///for getting the distance of the target node.

  1095     ///

  1096     ///\ref named-func-param "Named parameter"

  1097     ///for getting the distance of the target node.

  1098     DfsWizard dist(const int &d)

  1099     {

  1100       Base::_di=const_cast<int*>(&d);

  1101       return *this;
  1067     }
  1102     }
  1068
  1103
  1069   };
  1104   };
  1070
  1105
  1071   ///Function type interface for Dfs algorithm.
  1106   ///Function-type interface for DFS algorithm.
  1072
  1107
  1073   ///\ingroup search
  1108   ///\ingroup search
  1074   ///Function type interface for Dfs algorithm.
  1109   ///Function-type interface for DFS algorithm.
  1075   ///
  1110   ///
  1076   ///This function also has several
  1111   ///This function also has several \ref named-func-param "named parameters",
  1077   ///\ref named-templ-func-param "named parameters",

  1078   ///they are declared as the members of class \ref DfsWizard.
  1112   ///they are declared as the members of class \ref DfsWizard.
  1079   ///The following
  1113   ///The following examples show how to use these parameters.
  1080   ///example shows how to use these parameters.

  1081   ///\code
  1114   ///\code
  1082   ///  dfs(g,source).predMap(preds).run();
  1115   ///  // Compute the DFS tree

  1116   ///  dfs(g).predMap(preds).distMap(dists).run(s);

  1117   ///

  1118   ///  // Compute the DFS path from s to t

  1119   ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
  1083   ///\endcode
  1120   ///\endcode

  1121
  1084   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
  1122   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
  1085   ///to the end of the parameter list.
  1123   ///to the end of the parameter list.
  1086   ///\sa DfsWizard
  1124   ///\sa DfsWizard
  1087   ///\sa Dfs
  1125   ///\sa Dfs
  1088   template<class GR>
  1126   template<class GR>
  1089   DfsWizard<DfsWizardBase<GR> >
  1127   DfsWizard<DfsWizardBase<GR> >
  1090   dfs(const GR &g,typename GR::Node s=INVALID)
  1128   dfs(const GR &digraph)
  1091   {
  1129   {
  1092     return DfsWizard<DfsWizardBase<GR> >(g,s);
  1130     return DfsWizard<DfsWizardBase<GR> >(digraph);
  1093   }
  1131   }
  1094
  1132
  1095 #ifdef DOXYGEN
  1133 #ifdef DOXYGEN
  1096   /// \brief Visitor class for DFS.
  1134   /// \brief Visitor class for DFS.
  1097   ///
  1135   ///