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