lemon/dfs.h
author alpar
Mon, 12 Sep 2005 05:35:36 +0000
changeset 1678 b7b7125a5fe8
parent 1665 fdeb961110ac
child 1694 6d81e6f7a88d
permissions -rw-r--r--
graph_orientation.cc: A thoroughly documented demo application.
     1 /* -*- C++ -*-
     2  * lemon/dfs.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_DFS_H
    18 #define LEMON_DFS_H
    19 
    20 ///\ingroup flowalgs
    21 ///\file
    22 ///\brief Dfs algorithm.
    23 
    24 #include <lemon/list_graph.h>
    25 #include <lemon/graph_utils.h>
    26 #include <lemon/invalid.h>
    27 #include <lemon/error.h>
    28 #include <lemon/maps.h>
    29 
    30 namespace lemon {
    31 
    32 
    33   
    34   ///Default traits class of Dfs class.
    35 
    36   ///Default traits class of Dfs class.
    37   ///\param GR Graph type.
    38   template<class GR>
    39   struct DfsDefaultTraits
    40   {
    41     ///The graph type the algorithm runs on. 
    42     typedef GR Graph;
    43     ///\brief The type of the map that stores the last
    44     ///edges of the %DFS paths.
    45     /// 
    46     ///The type of the map that stores the last
    47     ///edges of the %DFS paths.
    48     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    49     ///
    50     typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
    51     ///Instantiates a PredMap.
    52  
    53     ///This function instantiates a \ref PredMap. 
    54     ///\param G is the graph, to which we would like to define the PredMap.
    55     ///\todo The graph alone may be insufficient to initialize
    56     static PredMap *createPredMap(const GR &G) 
    57     {
    58       return new PredMap(G);
    59     }
    60 //     ///\brief The type of the map that stores the last but one
    61 //     ///nodes of the %DFS paths.
    62 //     ///
    63 //     ///The type of the map that stores the last but one
    64 //     ///nodes of the %DFS paths.
    65 //     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    66 //     ///
    67 //     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
    68 //     ///Instantiates a PredNodeMap.
    69     
    70 //     ///This function instantiates a \ref PredNodeMap. 
    71 //     ///\param G is the graph, to which
    72 //     ///we would like to define the \ref PredNodeMap
    73 //     static PredNodeMap *createPredNodeMap(const GR &G)
    74 //     {
    75 //       return new PredNodeMap();
    76 //     }
    77 
    78     ///The type of the map that indicates which nodes are processed.
    79  
    80     ///The type of the map that indicates which nodes are processed.
    81     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    82     ///\todo named parameter to set this type, function to read and write.
    83     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
    84     ///Instantiates a ProcessedMap.
    85  
    86     ///This function instantiates a \ref ProcessedMap. 
    87     ///\param g is the graph, to which
    88     ///we would like to define the \ref ProcessedMap
    89 #ifdef DOXYGEN
    90     static ProcessedMap *createProcessedMap(const GR &g)
    91 #else
    92     static ProcessedMap *createProcessedMap(const GR &)
    93 #endif
    94     {
    95       return new ProcessedMap();
    96     }
    97     ///The type of the map that indicates which nodes are reached.
    98  
    99     ///The type of the map that indicates which nodes are reached.
   100     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   101     ///\todo named parameter to set this type, function to read and write.
   102     typedef typename Graph::template NodeMap<bool> ReachedMap;
   103     ///Instantiates a ReachedMap.
   104  
   105     ///This function instantiates a \ref ReachedMap. 
   106     ///\param G is the graph, to which
   107     ///we would like to define the \ref ReachedMap.
   108     static ReachedMap *createReachedMap(const GR &G)
   109     {
   110       return new ReachedMap(G);
   111     }
   112     ///The type of the map that stores the dists of the nodes.
   113  
   114     ///The type of the map that stores the dists of the nodes.
   115     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   116     ///
   117     typedef typename Graph::template NodeMap<int> DistMap;
   118     ///Instantiates a DistMap.
   119  
   120     ///This function instantiates a \ref DistMap. 
   121     ///\param G is the graph, to which we would like to define the \ref DistMap
   122     static DistMap *createDistMap(const GR &G)
   123     {
   124       return new DistMap(G);
   125     }
   126   };
   127   
   128   ///%DFS algorithm class.
   129   
   130   ///\ingroup flowalgs
   131   ///This class provides an efficient implementation of the %DFS algorithm.
   132   ///
   133   ///\param GR The graph type the algorithm runs on. The default value is
   134   ///\ref ListGraph. The value of GR is not used directly by Dfs, it
   135   ///is only passed to \ref DfsDefaultTraits.
   136   ///\param TR Traits class to set various data types used by the algorithm.
   137   ///The default traits class is
   138   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
   139   ///See \ref DfsDefaultTraits for the documentation of
   140   ///a Dfs traits class.
   141   ///
   142   ///\author Jacint Szabo and Alpar Juttner
   143   ///\todo A compare object would be nice.
   144 
   145 #ifdef DOXYGEN
   146   template <typename GR,
   147 	    typename TR>
   148 #else
   149   template <typename GR=ListGraph,
   150 	    typename TR=DfsDefaultTraits<GR> >
   151 #endif
   152   class Dfs {
   153   public:
   154     /**
   155      * \brief \ref Exception for uninitialized parameters.
   156      *
   157      * This error represents problems in the initialization
   158      * of the parameters of the algorithms.
   159      */
   160     class UninitializedParameter : public lemon::UninitializedParameter {
   161     public:
   162       virtual const char* exceptionName() const {
   163 	return "lemon::Dfs::UninitializedParameter";
   164       }
   165     };
   166 
   167     typedef TR Traits;
   168     ///The type of the underlying graph.
   169     typedef typename TR::Graph Graph;
   170     ///\e
   171     typedef typename Graph::Node Node;
   172     ///\e
   173     typedef typename Graph::NodeIt NodeIt;
   174     ///\e
   175     typedef typename Graph::Edge Edge;
   176     ///\e
   177     typedef typename Graph::OutEdgeIt OutEdgeIt;
   178     
   179     ///\brief The type of the map that stores the last
   180     ///edges of the %DFS paths.
   181     typedef typename TR::PredMap PredMap;
   182 //     ///\brief The type of the map that stores the last but one
   183 //     ///nodes of the %DFS paths.
   184 //     typedef typename TR::PredNodeMap PredNodeMap;
   185     ///The type of the map indicating which nodes are reached.
   186     typedef typename TR::ReachedMap ReachedMap;
   187     ///The type of the map indicating which nodes are processed.
   188     typedef typename TR::ProcessedMap ProcessedMap;
   189     ///The type of the map that stores the dists of the nodes.
   190     typedef typename TR::DistMap DistMap;
   191   private:
   192     /// Pointer to the underlying graph.
   193     const Graph *G;
   194     ///Pointer to the map of predecessors edges.
   195     PredMap *_pred;
   196     ///Indicates if \ref _pred is locally allocated (\c true) or not.
   197     bool local_pred;
   198 //     ///Pointer to the map of predecessors nodes.
   199 //     PredNodeMap *_predNode;
   200 //     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
   201 //     bool local_predNode;
   202     ///Pointer to the map of distances.
   203     DistMap *_dist;
   204     ///Indicates if \ref _dist is locally allocated (\c true) or not.
   205     bool local_dist;
   206     ///Pointer to the map of reached status of the nodes.
   207     ReachedMap *_reached;
   208     ///Indicates if \ref _reached is locally allocated (\c true) or not.
   209     bool local_reached;
   210     ///Pointer to the map of processed status of the nodes.
   211     ProcessedMap *_processed;
   212     ///Indicates if \ref _processed is locally allocated (\c true) or not.
   213     bool local_processed;
   214 
   215     std::vector<typename Graph::OutEdgeIt> _stack;
   216     int _stack_head;
   217 //     ///The source node of the last execution.
   218 //     Node source;
   219 
   220     ///Creates the maps if necessary.
   221     
   222     ///\todo Error if \c G are \c NULL.
   223     ///\todo Better memory allocation (instead of new).
   224     void create_maps() 
   225     {
   226       if(!_pred) {
   227 	local_pred = true;
   228 	_pred = Traits::createPredMap(*G);
   229       }
   230 //       if(!_predNode) {
   231 // 	local_predNode = true;
   232 // 	_predNode = Traits::createPredNodeMap(*G);
   233 //       }
   234       if(!_dist) {
   235 	local_dist = true;
   236 	_dist = Traits::createDistMap(*G);
   237       }
   238       if(!_reached) {
   239 	local_reached = true;
   240 	_reached = Traits::createReachedMap(*G);
   241       }
   242       if(!_processed) {
   243 	local_processed = true;
   244 	_processed = Traits::createProcessedMap(*G);
   245       }
   246     }
   247     
   248   public :
   249  
   250     ///\name Named template parameters
   251 
   252     ///@{
   253 
   254     template <class T>
   255     struct DefPredMapTraits : public Traits {
   256       typedef T PredMap;
   257       static PredMap *createPredMap(const Graph &G) 
   258       {
   259 	throw UninitializedParameter();
   260       }
   261     };
   262     ///\ref named-templ-param "Named parameter" for setting PredMap type
   263 
   264     ///\ref named-templ-param "Named parameter" for setting PredMap type
   265     ///
   266     template <class T>
   267     class DefPredMap : public Dfs< Graph,
   268 					DefPredMapTraits<T> > { };
   269     
   270 //     template <class T>
   271 //     struct DefPredNodeMapTraits : public Traits {
   272 //       typedef T PredNodeMap;
   273 //       static PredNodeMap *createPredNodeMap(const Graph &G) 
   274 //       {
   275 // 	throw UninitializedParameter();
   276 //       }
   277 //     };
   278 //     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
   279 
   280 //     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
   281 //     ///
   282 //     template <class T>
   283 //     class DefPredNodeMap : public Dfs< Graph,
   284 // 					    LengthMap,
   285 // 					    DefPredNodeMapTraits<T> > { };
   286     
   287     template <class T>
   288     struct DefDistMapTraits : public Traits {
   289       typedef T DistMap;
   290       static DistMap *createDistMap(const Graph &G) 
   291       {
   292 	throw UninitializedParameter();
   293       }
   294     };
   295     ///\ref named-templ-param "Named parameter" for setting DistMap type
   296 
   297     ///\ref named-templ-param "Named parameter" for setting DistMap type
   298     ///
   299     template <class T>
   300     class DefDistMap : public Dfs< Graph,
   301 				   DefDistMapTraits<T> > { };
   302     
   303     template <class T>
   304     struct DefReachedMapTraits : public Traits {
   305       typedef T ReachedMap;
   306       static ReachedMap *createReachedMap(const Graph &G) 
   307       {
   308 	throw UninitializedParameter();
   309       }
   310     };
   311     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   312 
   313     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   314     ///
   315     template <class T>
   316     class DefReachedMap : public Dfs< Graph,
   317 				      DefReachedMapTraits<T> > { };
   318     
   319     struct DefGraphReachedMapTraits : public Traits {
   320       typedef typename Graph::template NodeMap<bool> ReachedMap;
   321       static ReachedMap *createReachedMap(const Graph &G) 
   322       {
   323 	return new ReachedMap(G);
   324       }
   325     };
   326     template <class T>
   327     struct DefProcessedMapTraits : public Traits {
   328       typedef T ProcessedMap;
   329       static ProcessedMap *createProcessedMap(const Graph &G) 
   330       {
   331 	throw UninitializedParameter();
   332       }
   333     };
   334     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   335 
   336     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   337     ///
   338     template <class T>
   339     class DefProcessedMap : public Dfs< Graph,
   340 					DefProcessedMapTraits<T> > { };
   341     
   342     struct DefGraphProcessedMapTraits : public Traits {
   343       typedef typename Graph::template NodeMap<bool> ProcessedMap;
   344       static ProcessedMap *createProcessedMap(const Graph &G) 
   345       {
   346 	return new ProcessedMap(G);
   347       }
   348     };
   349     ///\brief \ref named-templ-param "Named parameter"
   350     ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
   351     ///
   352     ///\ref named-templ-param "Named parameter"
   353     ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
   354     ///If you don't set it explicitely, it will be automatically allocated.
   355     template <class T>
   356     class DefProcessedMapToBeDefaultMap :
   357       public Dfs< Graph,
   358 		  DefGraphProcessedMapTraits> { };
   359     
   360     ///@}
   361 
   362   public:      
   363     
   364     ///Constructor.
   365     
   366     ///\param _G the graph the algorithm will run on.
   367     ///
   368     Dfs(const Graph& _G) :
   369       G(&_G),
   370       _pred(NULL), local_pred(false),
   371 //       _predNode(NULL), local_predNode(false),
   372       _dist(NULL), local_dist(false),
   373       _reached(NULL), local_reached(false),
   374       _processed(NULL), local_processed(false)
   375     { }
   376     
   377     ///Destructor.
   378     ~Dfs() 
   379     {
   380       if(local_pred) delete _pred;
   381 //       if(local_predNode) delete _predNode;
   382       if(local_dist) delete _dist;
   383       if(local_reached) delete _reached;
   384       if(local_processed) delete _processed;
   385     }
   386 
   387     ///Sets the map storing the predecessor edges.
   388 
   389     ///Sets the map storing the predecessor edges.
   390     ///If you don't use this function before calling \ref run(),
   391     ///it will allocate one. The destuctor deallocates this
   392     ///automatically allocated map, of course.
   393     ///\return <tt> (*this) </tt>
   394     Dfs &predMap(PredMap &m) 
   395     {
   396       if(local_pred) {
   397 	delete _pred;
   398 	local_pred=false;
   399       }
   400       _pred = &m;
   401       return *this;
   402     }
   403 
   404 //     ///Sets the map storing the predecessor nodes.
   405 
   406 //     ///Sets the map storing the predecessor nodes.
   407 //     ///If you don't use this function before calling \ref run(),
   408 //     ///it will allocate one. The destuctor deallocates this
   409 //     ///automatically allocated map, of course.
   410 //     ///\return <tt> (*this) </tt>
   411 //     Dfs &predNodeMap(PredNodeMap &m) 
   412 //     {
   413 //       if(local_predNode) {
   414 // 	delete _predNode;
   415 // 	local_predNode=false;
   416 //       }
   417 //       _predNode = &m;
   418 //       return *this;
   419 //     }
   420 
   421     ///Sets the map storing the distances calculated by the algorithm.
   422 
   423     ///Sets the map storing the distances calculated by the algorithm.
   424     ///If you don't use this function before calling \ref run(),
   425     ///it will allocate one. The destuctor deallocates this
   426     ///automatically allocated map, of course.
   427     ///\return <tt> (*this) </tt>
   428     Dfs &distMap(DistMap &m) 
   429     {
   430       if(local_dist) {
   431 	delete _dist;
   432 	local_dist=false;
   433       }
   434       _dist = &m;
   435       return *this;
   436     }
   437 
   438     ///Sets the map indicating if a node is reached.
   439 
   440     ///Sets the map indicating if a node is reached.
   441     ///If you don't use this function before calling \ref run(),
   442     ///it will allocate one. The destuctor deallocates this
   443     ///automatically allocated map, of course.
   444     ///\return <tt> (*this) </tt>
   445     Dfs &reachedMap(ReachedMap &m) 
   446     {
   447       if(local_reached) {
   448 	delete _reached;
   449 	local_reached=false;
   450       }
   451       _reached = &m;
   452       return *this;
   453     }
   454 
   455     ///Sets the map indicating if a node is processed.
   456 
   457     ///Sets the map indicating if a node is processed.
   458     ///If you don't use this function before calling \ref run(),
   459     ///it will allocate one. The destuctor deallocates this
   460     ///automatically allocated map, of course.
   461     ///\return <tt> (*this) </tt>
   462     Dfs &processedMap(ProcessedMap &m) 
   463     {
   464       if(local_processed) {
   465 	delete _processed;
   466 	local_processed=false;
   467       }
   468       _processed = &m;
   469       return *this;
   470     }
   471 
   472   public:
   473     ///\name Execution control
   474     ///The simplest way to execute the algorithm is to use
   475     ///one of the member functions called \c run(...).
   476     ///\n
   477     ///If you need more control on the execution,
   478     ///first you must call \ref init(), then you can add several source nodes
   479     ///with \ref addSource().
   480     ///Finally \ref start() will perform the actual path
   481     ///computation.
   482 
   483     ///@{
   484 
   485     ///Initializes the internal data structures.
   486 
   487     ///Initializes the internal data structures.
   488     ///
   489     void init()
   490     {
   491       create_maps();
   492       _stack.resize(countNodes(*G));
   493       _stack_head=-1;
   494       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   495 	_pred->set(u,INVALID);
   496 	// _predNode->set(u,INVALID);
   497 	_reached->set(u,false);
   498 	_processed->set(u,false);
   499       }
   500     }
   501     
   502     ///Adds a new source node.
   503 
   504     ///Adds a new source node to the set of nodes to be processed.
   505     ///
   506     ///\bug dists are wrong (or at least strange) in case of multiple sources.
   507     void addSource(Node s)
   508     {
   509       if(!(*_reached)[s])
   510 	{
   511 	  _reached->set(s,true);
   512 	  _pred->set(s,INVALID);
   513 	  // _predNode->set(u,INVALID);
   514 	  OutEdgeIt e(*G,s);
   515 	  if(e!=INVALID) {
   516 	    _stack[++_stack_head]=e;
   517 	    _dist->set(s,_stack_head);
   518 	  }
   519 	  else {
   520 	    _processed->set(s,true);
   521 	    _dist->set(s,0);
   522 	  }
   523 	}
   524     }
   525     
   526     ///Processes the next edge.
   527 
   528     ///Processes the next edge.
   529     ///
   530     ///\return The processed edge.
   531     ///
   532     ///\pre The stack must not be empty!
   533     Edge processNextEdge()
   534     { 
   535       Node m;
   536       Edge e=_stack[_stack_head];
   537       if(!(*_reached)[m=G->target(e)]) {
   538 	_pred->set(m,e);
   539 	_reached->set(m,true);
   540 	//	  _pred_node->set(m,G->source(e));
   541 	++_stack_head;
   542 	_stack[_stack_head] = OutEdgeIt(*G, m);
   543 	_dist->set(m,_stack_head);
   544       }
   545       else {
   546 	m=G->source(e);
   547 	++_stack[_stack_head];
   548       }
   549       //'m' is now the (original) source of the _stack[_stack_head] 
   550       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
   551 	_processed->set(m,true);
   552 	--_stack_head;
   553 	if(_stack_head>=0) {
   554 	  m=G->source(_stack[_stack_head]);
   555 	  ++_stack[_stack_head];
   556 	}
   557       }
   558       return e;
   559     }
   560     ///Next edge to be processed.
   561 
   562     ///Next edge to be processed.
   563     ///
   564     ///\return The next edge to be processed or INVALID if the stack is
   565     /// empty.
   566     OutEdgeIt NextEdge()
   567     { 
   568       return _stack_head>=0?_stack[_stack_head]:INVALID;
   569     }
   570       
   571     ///\brief Returns \c false if there are nodes
   572     ///to be processed in the queue
   573     ///
   574     ///Returns \c false if there are nodes
   575     ///to be processed in the queue
   576     ///
   577     ///\todo This should be called emptyStack() or some "neutral" name.
   578     bool emptyQueue() { return _stack_head<0; }
   579     ///Returns the number of the nodes to be processed.
   580     
   581     ///Returns the number of the nodes to be processed in the queue.
   582     ///
   583     ///\todo This should be called stackSize() or some "neutral" name.
   584     int queueSize() { return _stack_head+1; }
   585     
   586     ///Executes the algorithm.
   587 
   588     ///Executes the algorithm.
   589     ///
   590     ///\pre init() must be called and at least one node should be added
   591     ///with addSource() before using this function.
   592     ///
   593     ///This method runs the %DFS algorithm from the root node(s)
   594     ///in order to
   595     ///compute the
   596     ///%DFS path to each node. The algorithm computes
   597     ///- The %DFS tree.
   598     ///- The distance of each node from the root(s) in the %DFS tree.
   599     ///
   600     void start()
   601     {
   602       while ( !emptyQueue() ) processNextEdge();
   603     }
   604     
   605     ///Executes the algorithm until \c dest is reached.
   606 
   607     ///Executes the algorithm until \c dest is reached.
   608     ///
   609     ///\pre init() must be called and at least one node should be added
   610     ///with addSource() before using this function.
   611     ///
   612     ///This method runs the %DFS algorithm from the root node(s)
   613     ///in order to
   614     ///compute the
   615     ///%DFS path to \c dest. The algorithm computes
   616     ///- The %DFS path to \c  dest.
   617     ///- The distance of \c dest from the root(s) in the %DFS tree.
   618     ///
   619     void start(Node dest)
   620     {
   621       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
   622 	processNextEdge();
   623     }
   624     
   625     ///Executes the algorithm until a condition is met.
   626 
   627     ///Executes the algorithm until a condition is met.
   628     ///
   629     ///\pre init() must be called and at least one node should be added
   630     ///with addSource() before using this function.
   631     ///
   632     ///\param nm must be a bool (or convertible) edge map. The algorithm
   633     ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
   634     ///
   635     ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
   636     ///not a node map.
   637     template<class NM>
   638       void start(const NM &nm)
   639       {
   640 	while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
   641       }
   642     
   643     ///Runs %DFS algorithm from node \c s.
   644     
   645     ///This method runs the %DFS algorithm from a root node \c s
   646     ///in order to
   647     ///compute the
   648     ///%DFS path to each node. The algorithm computes
   649     ///- The %DFS tree.
   650     ///- The distance of each node from the root in the %DFS tree.
   651     ///
   652     ///\note d.run(s) is just a shortcut of the following code.
   653     ///\code
   654     ///  d.init();
   655     ///  d.addSource(s);
   656     ///  d.start();
   657     ///\endcode
   658     void run(Node s) {
   659       init();
   660       addSource(s);
   661       start();
   662     }
   663     
   664     ///Finds the %DFS path between \c s and \c t.
   665     
   666     ///Finds the %DFS path between \c s and \c t.
   667     ///
   668     ///\return The length of the %DFS s---t path if there exists one,
   669     ///0 otherwise.
   670     ///\note Apart from the return value, d.run(s,t) is
   671     ///just a shortcut of the following code.
   672     ///\code
   673     ///  d.init();
   674     ///  d.addSource(s);
   675     ///  d.start(t);
   676     ///\endcode
   677     int run(Node s,Node t) {
   678       init();
   679       addSource(s);
   680       start(t);
   681       return reached(t)?_stack_head+1:0;
   682     }
   683     
   684     ///@}
   685 
   686     ///\name Query Functions
   687     ///The result of the %DFS algorithm can be obtained using these
   688     ///functions.\n
   689     ///Before the use of these functions,
   690     ///either run() or start() must be called.
   691     
   692     ///@{
   693 
   694     ///Copies the path to \c t on the DFS tree into \c p
   695     
   696     ///This function copies the path to \c t on the DFS tree  into \c p.
   697     ///If \c t is a source itself or unreachable, then it does not
   698     ///alter \c p.
   699     ///\todo Is this the right way to handle unreachable nodes?
   700     ///
   701     ///\return Returns \c true if a path to \c t was actually copied to \c p,
   702     ///\c false otherwise.
   703     ///\sa DirPath
   704     template<class P>
   705     bool getPath(P &p,Node t) 
   706     {
   707       if(reached(t)) {
   708 	p.clear();
   709 	typename P::Builder b(p);
   710 	for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
   711 	  b.pushFront(pred(t));
   712 	b.commit();
   713 	return true;
   714       }
   715       return false;
   716     }
   717 
   718     ///The distance of a node from the root(s).
   719 
   720     ///Returns the distance of a node from the root(s).
   721     ///\pre \ref run() must be called before using this function.
   722     ///\warning If node \c v is unreachable from the root(s) then the return value
   723     ///of this funcion is undefined.
   724     int dist(Node v) const { return (*_dist)[v]; }
   725 
   726     ///Returns the 'previous edge' of the %DFS tree.
   727 
   728     ///For a node \c v it returns the 'previous edge'
   729     ///of the %DFS path,
   730     ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
   731     ///v. It is \ref INVALID
   732     ///if \c v is unreachable from the root(s) or \c v is a root. The
   733     ///%DFS tree used here is equal to the %DFS tree used in
   734     ///\ref predNode().
   735     ///\pre Either \ref run() or \ref start() must be called before using
   736     ///this function.
   737     ///\todo predEdge could be a better name.
   738     Edge pred(Node v) const { return (*_pred)[v];}
   739 
   740     ///Returns the 'previous node' of the %DFS tree.
   741 
   742     ///For a node \c v it returns the 'previous node'
   743     ///of the %DFS tree,
   744     ///i.e. it returns the last but one node from a %DFS path from the
   745     ///root(a) to \c /v.
   746     ///It is INVALID if \c v is unreachable from the root(s) or
   747     ///if \c v itself a root.
   748     ///The %DFS tree used here is equal to the %DFS
   749     ///tree used in \ref pred().
   750     ///\pre Either \ref run() or \ref start() must be called before
   751     ///using this function.
   752     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   753 				  G->source((*_pred)[v]); }
   754     
   755     ///Returns a reference to the NodeMap of distances.
   756 
   757     ///Returns a reference to the NodeMap of distances.
   758     ///\pre Either \ref run() or \ref init() must
   759     ///be called before using this function.
   760     const DistMap &distMap() const { return *_dist;}
   761  
   762     ///Returns a reference to the %DFS edge-tree map.
   763 
   764     ///Returns a reference to the NodeMap of the edges of the
   765     ///%DFS tree.
   766     ///\pre Either \ref run() or \ref init()
   767     ///must be called before using this function.
   768     const PredMap &predMap() const { return *_pred;}
   769  
   770 //     ///Returns a reference to the map of nodes of %DFS paths.
   771 
   772 //     ///Returns a reference to the NodeMap of the last but one nodes of the
   773 //     ///%DFS tree.
   774 //     ///\pre \ref run() must be called before using this function.
   775 //     const PredNodeMap &predNodeMap() const { return *_predNode;}
   776 
   777     ///Checks if a node is reachable from the root.
   778 
   779     ///Returns \c true if \c v is reachable from the root(s).
   780     ///\warning The source nodes are inditated as unreachable.
   781     ///\pre Either \ref run() or \ref start()
   782     ///must be called before using this function.
   783     ///
   784     bool reached(Node v) { return (*_reached)[v]; }
   785     
   786     ///@}
   787   };
   788 
   789   ///Default traits class of Dfs function.
   790 
   791   ///Default traits class of Dfs function.
   792   ///\param GR Graph type.
   793   template<class GR>
   794   struct DfsWizardDefaultTraits
   795   {
   796     ///The graph type the algorithm runs on. 
   797     typedef GR Graph;
   798     ///\brief The type of the map that stores the last
   799     ///edges of the %DFS paths.
   800     /// 
   801     ///The type of the map that stores the last
   802     ///edges of the %DFS paths.
   803     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   804     ///
   805     typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
   806     ///Instantiates a PredMap.
   807  
   808     ///This function instantiates a \ref PredMap. 
   809     ///\param g is the graph, to which we would like to define the PredMap.
   810     ///\todo The graph alone may be insufficient to initialize
   811 #ifdef DOXYGEN
   812     static PredMap *createPredMap(const GR &g) 
   813 #else
   814     static PredMap *createPredMap(const GR &) 
   815 #endif
   816     {
   817       return new PredMap();
   818     }
   819 //     ///\brief The type of the map that stores the last but one
   820 //     ///nodes of the %DFS paths.
   821 //     ///
   822 //     ///The type of the map that stores the last but one
   823 //     ///nodes of the %DFS paths.
   824 //     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   825 //     ///
   826 //     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
   827 //     ///Instantiates a PredNodeMap.
   828     
   829 //     ///This function instantiates a \ref PredNodeMap. 
   830 //     ///\param G is the graph, to which
   831 //     ///we would like to define the \ref PredNodeMap
   832 //     static PredNodeMap *createPredNodeMap(const GR &G)
   833 //     {
   834 //       return new PredNodeMap();
   835 //     }
   836 
   837     ///The type of the map that indicates which nodes are processed.
   838  
   839     ///The type of the map that indicates which nodes are processed.
   840     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   841     ///\todo named parameter to set this type, function to read and write.
   842     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
   843     ///Instantiates a ProcessedMap.
   844  
   845     ///This function instantiates a \ref ProcessedMap. 
   846     ///\param g is the graph, to which
   847     ///we would like to define the \ref ProcessedMap
   848 #ifdef DOXYGEN
   849     static ProcessedMap *createProcessedMap(const GR &g)
   850 #else
   851     static ProcessedMap *createProcessedMap(const GR &)
   852 #endif
   853     {
   854       return new ProcessedMap();
   855     }
   856     ///The type of the map that indicates which nodes are reached.
   857  
   858     ///The type of the map that indicates which nodes are reached.
   859     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   860     ///\todo named parameter to set this type, function to read and write.
   861     typedef typename Graph::template NodeMap<bool> ReachedMap;
   862     ///Instantiates a ReachedMap.
   863  
   864     ///This function instantiates a \ref ReachedMap. 
   865     ///\param G is the graph, to which
   866     ///we would like to define the \ref ReachedMap.
   867     static ReachedMap *createReachedMap(const GR &G)
   868     {
   869       return new ReachedMap(G);
   870     }
   871     ///The type of the map that stores the dists of the nodes.
   872  
   873     ///The type of the map that stores the dists of the nodes.
   874     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   875     ///
   876     typedef NullMap<typename Graph::Node,int> DistMap;
   877     ///Instantiates a DistMap.
   878  
   879     ///This function instantiates a \ref DistMap. 
   880     ///\param g is the graph, to which we would like to define the \ref DistMap
   881 #ifdef DOXYGEN
   882     static DistMap *createDistMap(const GR &g)
   883 #else
   884     static DistMap *createDistMap(const GR &)
   885 #endif
   886     {
   887       return new DistMap();
   888     }
   889   };
   890   
   891   /// Default traits used by \ref DfsWizard
   892 
   893   /// To make it easier to use Dfs algorithm
   894   ///we have created a wizard class.
   895   /// This \ref DfsWizard class needs default traits,
   896   ///as well as the \ref Dfs class.
   897   /// The \ref DfsWizardBase is a class to be the default traits of the
   898   /// \ref DfsWizard class.
   899   template<class GR>
   900   class DfsWizardBase : public DfsWizardDefaultTraits<GR>
   901   {
   902 
   903     typedef DfsWizardDefaultTraits<GR> Base;
   904   protected:
   905     /// Type of the nodes in the graph.
   906     typedef typename Base::Graph::Node Node;
   907 
   908     /// Pointer to the underlying graph.
   909     void *_g;
   910     ///Pointer to the map of reached nodes.
   911     void *_reached;
   912     ///Pointer to the map of processed nodes.
   913     void *_processed;
   914     ///Pointer to the map of predecessors edges.
   915     void *_pred;
   916 //     ///Pointer to the map of predecessors nodes.
   917 //     void *_predNode;
   918     ///Pointer to the map of distances.
   919     void *_dist;
   920     ///Pointer to the source node.
   921     Node _source;
   922     
   923     public:
   924     /// Constructor.
   925     
   926     /// This constructor does not require parameters, therefore it initiates
   927     /// all of the attributes to default values (0, INVALID).
   928     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   929 // 			   _predNode(0),
   930 			   _dist(0), _source(INVALID) {}
   931 
   932     /// Constructor.
   933     
   934     /// This constructor requires some parameters,
   935     /// listed in the parameters list.
   936     /// Others are initiated to 0.
   937     /// \param g is the initial value of  \ref _g
   938     /// \param s is the initial value of  \ref _source
   939     DfsWizardBase(const GR &g, Node s=INVALID) :
   940       _g((void *)&g), _reached(0), _processed(0), _pred(0),
   941 //       _predNode(0),
   942       _dist(0), _source(s) {}
   943 
   944   };
   945   
   946   /// A class to make the usage of the Dfs algorithm easier
   947 
   948   /// This class is created to make it easier to use the Dfs algorithm.
   949   /// It uses the functions and features of the plain \ref Dfs,
   950   /// but it is much simpler to use it.
   951   ///
   952   /// Simplicity means that the way to change the types defined
   953   /// in the traits class is based on functions that returns the new class
   954   /// and not on templatable built-in classes.
   955   /// When using the plain \ref Dfs
   956   /// the new class with the modified type comes from
   957   /// the original class by using the ::
   958   /// operator. In the case of \ref DfsWizard only
   959   /// a function have to be called and it will
   960   /// return the needed class.
   961   ///
   962   /// It does not have own \ref run method. When its \ref run method is called
   963   /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
   964   /// method of it.
   965   template<class TR>
   966   class DfsWizard : public TR
   967   {
   968     typedef TR Base;
   969 
   970     ///The type of the underlying graph.
   971     typedef typename TR::Graph Graph;
   972     //\e
   973     typedef typename Graph::Node Node;
   974     //\e
   975     typedef typename Graph::NodeIt NodeIt;
   976     //\e
   977     typedef typename Graph::Edge Edge;
   978     //\e
   979     typedef typename Graph::OutEdgeIt OutEdgeIt;
   980     
   981     ///\brief The type of the map that stores
   982     ///the reached nodes
   983     typedef typename TR::ReachedMap ReachedMap;
   984     ///\brief The type of the map that stores
   985     ///the processed nodes
   986     typedef typename TR::ProcessedMap ProcessedMap;
   987     ///\brief The type of the map that stores the last
   988     ///edges of the %DFS paths.
   989     typedef typename TR::PredMap PredMap;
   990 //     ///\brief The type of the map that stores the last but one
   991 //     ///nodes of the %DFS paths.
   992 //     typedef typename TR::PredNodeMap PredNodeMap;
   993     ///The type of the map that stores the distances of the nodes.
   994     typedef typename TR::DistMap DistMap;
   995 
   996 public:
   997     /// Constructor.
   998     DfsWizard() : TR() {}
   999 
  1000     /// Constructor that requires parameters.
  1001 
  1002     /// Constructor that requires parameters.
  1003     /// These parameters will be the default values for the traits class.
  1004     DfsWizard(const Graph &g, Node s=INVALID) :
  1005       TR(g,s) {}
  1006 
  1007     ///Copy constructor
  1008     DfsWizard(const TR &b) : TR(b) {}
  1009 
  1010     ~DfsWizard() {}
  1011 
  1012     ///Runs Dfs algorithm from a given node.
  1013     
  1014     ///Runs Dfs algorithm from a given node.
  1015     ///The node can be given by the \ref source function.
  1016     void run()
  1017     {
  1018       if(Base::_source==INVALID) throw UninitializedParameter();
  1019       Dfs<Graph,TR> alg(*(Graph*)Base::_g);
  1020       if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
  1021       if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
  1022       if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
  1023 //       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
  1024       if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
  1025       alg.run(Base::_source);
  1026     }
  1027 
  1028     ///Runs Dfs algorithm from the given node.
  1029 
  1030     ///Runs Dfs algorithm from the given node.
  1031     ///\param s is the given source.
  1032     void run(Node s)
  1033     {
  1034       Base::_source=s;
  1035       run();
  1036     }
  1037 
  1038     template<class T>
  1039     struct DefPredMapBase : public Base {
  1040       typedef T PredMap;
  1041       static PredMap *createPredMap(const Graph &) { return 0; };
  1042       DefPredMapBase(const TR &b) : TR(b) {}
  1043     };
  1044     
  1045     ///\brief \ref named-templ-param "Named parameter"
  1046     ///function for setting PredMap type
  1047     ///
  1048     /// \ref named-templ-param "Named parameter"
  1049     ///function for setting PredMap type
  1050     ///
  1051     template<class T>
  1052     DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
  1053     {
  1054       Base::_pred=(void *)&t;
  1055       return DfsWizard<DefPredMapBase<T> >(*this);
  1056     }
  1057     
  1058  
  1059     template<class T>
  1060     struct DefReachedMapBase : public Base {
  1061       typedef T ReachedMap;
  1062       static ReachedMap *createReachedMap(const Graph &) { return 0; };
  1063       DefReachedMapBase(const TR &b) : TR(b) {}
  1064     };
  1065     
  1066     ///\brief \ref named-templ-param "Named parameter"
  1067     ///function for setting ReachedMap
  1068     ///
  1069     /// \ref named-templ-param "Named parameter"
  1070     ///function for setting ReachedMap
  1071     ///
  1072     template<class T>
  1073     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
  1074     {
  1075       Base::_pred=(void *)&t;
  1076       return DfsWizard<DefReachedMapBase<T> >(*this);
  1077     }
  1078     
  1079 
  1080     template<class T>
  1081     struct DefProcessedMapBase : public Base {
  1082       typedef T ProcessedMap;
  1083       static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
  1084       DefProcessedMapBase(const TR &b) : TR(b) {}
  1085     };
  1086     
  1087     ///\brief \ref named-templ-param "Named parameter"
  1088     ///function for setting ProcessedMap
  1089     ///
  1090     /// \ref named-templ-param "Named parameter"
  1091     ///function for setting ProcessedMap
  1092     ///
  1093     template<class T>
  1094     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
  1095     {
  1096       Base::_pred=(void *)&t;
  1097       return DfsWizard<DefProcessedMapBase<T> >(*this);
  1098     }
  1099     
  1100 
  1101 //     template<class T>
  1102 //     struct DefPredNodeMapBase : public Base {
  1103 //       typedef T PredNodeMap;
  1104 //       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
  1105 //       DefPredNodeMapBase(const TR &b) : TR(b) {}
  1106 //     };
  1107     
  1108 //     ///\brief \ref named-templ-param "Named parameter"
  1109 //     ///function for setting PredNodeMap type
  1110 //     ///
  1111 //     /// \ref named-templ-param "Named parameter"
  1112 //     ///function for setting PredNodeMap type
  1113 //     ///
  1114 //     template<class T>
  1115 //     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
  1116 //     {
  1117 //       Base::_predNode=(void *)&t;
  1118 //       return DfsWizard<DefPredNodeMapBase<T> >(*this);
  1119 //     }
  1120    
  1121     template<class T>
  1122     struct DefDistMapBase : public Base {
  1123       typedef T DistMap;
  1124       static DistMap *createDistMap(const Graph &) { return 0; };
  1125       DefDistMapBase(const TR &b) : TR(b) {}
  1126     };
  1127     
  1128     ///\brief \ref named-templ-param "Named parameter"
  1129     ///function for setting DistMap type
  1130     ///
  1131     /// \ref named-templ-param "Named parameter"
  1132     ///function for setting DistMap type
  1133     ///
  1134     template<class T>
  1135     DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
  1136     {
  1137       Base::_dist=(void *)&t;
  1138       return DfsWizard<DefDistMapBase<T> >(*this);
  1139     }
  1140     
  1141     /// Sets the source node, from which the Dfs algorithm runs.
  1142 
  1143     /// Sets the source node, from which the Dfs algorithm runs.
  1144     /// \param s is the source node.
  1145     DfsWizard<TR> &source(Node s) 
  1146     {
  1147       Base::_source=s;
  1148       return *this;
  1149     }
  1150     
  1151   };
  1152   
  1153   ///Function type interface for Dfs algorithm.
  1154 
  1155   /// \ingroup flowalgs
  1156   ///Function type interface for Dfs algorithm.
  1157   ///
  1158   ///This function also has several
  1159   ///\ref named-templ-func-param "named parameters",
  1160   ///they are declared as the members of class \ref DfsWizard.
  1161   ///The following
  1162   ///example shows how to use these parameters.
  1163   ///\code
  1164   ///  dfs(g,source).predMap(preds).run();
  1165   ///\endcode
  1166   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
  1167   ///to the end of the parameter list.
  1168   ///\sa DfsWizard
  1169   ///\sa Dfs
  1170   template<class GR>
  1171   DfsWizard<DfsWizardBase<GR> >
  1172   dfs(const GR &g,typename GR::Node s=INVALID)
  1173   {
  1174     return DfsWizard<DfsWizardBase<GR> >(g,s);
  1175   }
  1176 
  1177 } //END OF NAMESPACE LEMON
  1178 
  1179 #endif
  1180