1.1 --- a/src/lemon/dfs.h Wed Mar 16 07:52:16 2005 +0000
1.2 +++ b/src/lemon/dfs.h Wed Mar 16 07:56:25 2005 +0000
1.3 @@ -19,35 +19,150 @@
1.4
1.5 ///\ingroup flowalgs
1.6 ///\file
1.7 -///\brief %DFS algorithm.
1.8 -///
1.9 -///\todo Revise Manual.
1.10 +///\brief Dfs algorithm.
1.11
1.12 +#include <lemon/list_graph.h>
1.13 #include <lemon/graph_utils.h>
1.14 #include <lemon/invalid.h>
1.15 +#include <lemon/error.h>
1.16 +#include <lemon/maps.h>
1.17
1.18 namespace lemon {
1.19
1.20 -/// \addtogroup flowalgs
1.21 -/// @{
1.22
1.23 +
1.24 + ///Default traits class of Dfs class.
1.25 +
1.26 + ///Default traits class of Dfs class.
1.27 + ///\param GR Graph type.
1.28 + template<class GR>
1.29 + struct DfsDefaultTraits
1.30 + {
1.31 + ///The graph type the algorithm runs on.
1.32 + typedef GR Graph;
1.33 + ///\brief The type of the map that stores the last
1.34 + ///edges of the %DFS paths.
1.35 + ///
1.36 + ///The type of the map that stores the last
1.37 + ///edges of the %DFS paths.
1.38 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.39 + ///
1.40 + typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.41 + ///Instantiates a PredMap.
1.42 +
1.43 + ///This function instantiates a \ref PredMap.
1.44 + ///\param G is the graph, to which we would like to define the PredMap.
1.45 + ///\todo The graph alone may be insufficient to initialize
1.46 + static PredMap *createPredMap(const GR &G)
1.47 + {
1.48 + return new PredMap(G);
1.49 + }
1.50 +// ///\brief The type of the map that stores the last but one
1.51 +// ///nodes of the %DFS paths.
1.52 +// ///
1.53 +// ///The type of the map that stores the last but one
1.54 +// ///nodes of the %DFS paths.
1.55 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.56 +// ///
1.57 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.58 +// ///Instantiates a PredNodeMap.
1.59 +
1.60 +// ///This function instantiates a \ref PredNodeMap.
1.61 +// ///\param G is the graph, to which
1.62 +// ///we would like to define the \ref PredNodeMap
1.63 +// static PredNodeMap *createPredNodeMap(const GR &G)
1.64 +// {
1.65 +// return new PredNodeMap();
1.66 +// }
1.67 +
1.68 + ///The type of the map that indicates which nodes are processed.
1.69 +
1.70 + ///The type of the map that indicates which nodes are processed.
1.71 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.72 + ///\todo named parameter to set this type, function to read and write.
1.73 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.74 + ///Instantiates a ProcessedMap.
1.75 +
1.76 + ///This function instantiates a \ref ProcessedMap.
1.77 + ///\param G is the graph, to which
1.78 + ///we would like to define the \ref ProcessedMap
1.79 + static ProcessedMap *createProcessedMap(const GR &G)
1.80 + {
1.81 + return new ProcessedMap();
1.82 + }
1.83 + ///The type of the map that indicates which nodes are reached.
1.84 +
1.85 + ///The type of the map that indicates which nodes are reached.
1.86 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.87 + ///\todo named parameter to set this type, function to read and write.
1.88 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.89 + ///Instantiates a ReachedMap.
1.90 +
1.91 + ///This function instantiates a \ref ReachedMap.
1.92 + ///\param G is the graph, to which
1.93 + ///we would like to define the \ref ReachedMap.
1.94 + static ReachedMap *createReachedMap(const GR &G)
1.95 + {
1.96 + return new ReachedMap(G);
1.97 + }
1.98 + ///The type of the map that stores the dists of the nodes.
1.99 +
1.100 + ///The type of the map that stores the dists of the nodes.
1.101 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.102 + ///
1.103 + typedef typename Graph::template NodeMap<int> DistMap;
1.104 + ///Instantiates a DistMap.
1.105 +
1.106 + ///This function instantiates a \ref DistMap.
1.107 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.108 + static DistMap *createDistMap(const GR &G)
1.109 + {
1.110 + return new DistMap(G);
1.111 + }
1.112 + };
1.113 +
1.114 ///%DFS algorithm class.
1.115 -
1.116 - ///This class provides an efficient implementation of %DFS algorithm.
1.117 +
1.118 + ///\ingroup flowalgs
1.119 + ///This class provides an efficient implementation of the %DFS algorithm.
1.120 ///
1.121 - ///\param GR The graph type the algorithm runs on.
1.122 + ///\param GR The graph type the algorithm runs on. The default value is
1.123 + ///\ref ListGraph. The value of GR is not used directly by Dfs, it
1.124 + ///is only passed to \ref DfsDefaultTraits.
1.125 + ///\param TR Traits class to set various data types used by the algorithm.
1.126 + ///The default traits class is
1.127 + ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
1.128 + ///See \ref DfsDefaultTraits for the documentation of
1.129 + ///a Dfs traits class.
1.130 ///
1.131 - ///\author Alpar Juttner
1.132 + ///\author Jacint Szabo and Alpar Juttner
1.133 + ///\todo A compare object would be nice.
1.134
1.135 #ifdef DOXYGEN
1.136 - template <typename GR>
1.137 + template <typename GR,
1.138 + typename TR>
1.139 #else
1.140 - template <typename GR>
1.141 + template <typename GR=ListGraph,
1.142 + typename TR=DfsDefaultTraits<GR> >
1.143 #endif
1.144 - class Dfs{
1.145 + class Dfs {
1.146 public:
1.147 + /**
1.148 + * \brief \ref Exception for uninitialized parameters.
1.149 + *
1.150 + * This error represents problems in the initialization
1.151 + * of the parameters of the algorithms.
1.152 + */
1.153 + class UninitializedParameter : public lemon::UninitializedParameter {
1.154 + public:
1.155 + virtual const char* exceptionName() const {
1.156 + return "lemon::Dfs::UninitializedParameter";
1.157 + }
1.158 + };
1.159 +
1.160 + typedef TR Traits;
1.161 ///The type of the underlying graph.
1.162 - typedef GR Graph;
1.163 + typedef typename TR::Graph Graph;
1.164 ///\e
1.165 typedef typename Graph::Node Node;
1.166 ///\e
1.167 @@ -58,69 +173,211 @@
1.168 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.169
1.170 ///\brief The type of the map that stores the last
1.171 - ///edges of the paths on the %DFS tree.
1.172 - typedef typename Graph::template NodeMap<Edge> PredMap;
1.173 - ///\brief The type of the map that stores the last but one
1.174 - ///nodes of the paths on the %DFS tree.
1.175 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.176 - ///The type of the map that stores the dists of the nodes on the %DFS tree.
1.177 - typedef typename Graph::template NodeMap<int> DistMap;
1.178 -
1.179 + ///edges of the %DFS paths.
1.180 + typedef typename TR::PredMap PredMap;
1.181 +// ///\brief The type of the map that stores the last but one
1.182 +// ///nodes of the %DFS paths.
1.183 +// typedef typename TR::PredNodeMap PredNodeMap;
1.184 + ///The type of the map indicating which nodes are reached.
1.185 + typedef typename TR::ReachedMap ReachedMap;
1.186 + ///The type of the map indicating which nodes are processed.
1.187 + typedef typename TR::ProcessedMap ProcessedMap;
1.188 + ///The type of the map that stores the dists of the nodes.
1.189 + typedef typename TR::DistMap DistMap;
1.190 private:
1.191 /// Pointer to the underlying graph.
1.192 const Graph *G;
1.193 ///Pointer to the map of predecessors edges.
1.194 - PredMap *predecessor;
1.195 - ///Indicates if \ref predecessor is locally allocated (\c true) or not.
1.196 - bool local_predecessor;
1.197 - ///Pointer to the map of predecessors nodes.
1.198 - PredNodeMap *pred_node;
1.199 - ///Indicates if \ref pred_node is locally allocated (\c true) or not.
1.200 - bool local_pred_node;
1.201 + PredMap *_pred;
1.202 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.203 + bool local_pred;
1.204 +// ///Pointer to the map of predecessors nodes.
1.205 +// PredNodeMap *_predNode;
1.206 +// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.207 +// bool local_predNode;
1.208 ///Pointer to the map of distances.
1.209 - DistMap *distance;
1.210 - ///Indicates if \ref distance is locally allocated (\c true) or not.
1.211 - bool local_distance;
1.212 + DistMap *_dist;
1.213 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.214 + bool local_dist;
1.215 + ///Pointer to the map of reached status of the nodes.
1.216 + ReachedMap *_reached;
1.217 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.218 + bool local_reached;
1.219 + ///Pointer to the map of processed status of the nodes.
1.220 + ProcessedMap *_processed;
1.221 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.222 + bool local_processed;
1.223
1.224 - ///The source node of the last execution.
1.225 - Node source;
1.226 + std::vector<typename Graph::OutEdgeIt> _stack;
1.227 + int _stack_head;
1.228 +// ///The source node of the last execution.
1.229 +// Node source;
1.230
1.231 -
1.232 - ///Initializes the maps.
1.233 - void init_maps()
1.234 + ///Creates the maps if necessary.
1.235 +
1.236 + ///\todo Error if \c G are \c NULL.
1.237 + ///\todo Better memory allocation (instead of new).
1.238 + void create_maps()
1.239 {
1.240 - if(!predecessor) {
1.241 - local_predecessor = true;
1.242 - predecessor = new PredMap(*G);
1.243 + if(!_pred) {
1.244 + local_pred = true;
1.245 + _pred = Traits::createPredMap(*G);
1.246 }
1.247 - if(!pred_node) {
1.248 - local_pred_node = true;
1.249 - pred_node = new PredNodeMap(*G);
1.250 +// if(!_predNode) {
1.251 +// local_predNode = true;
1.252 +// _predNode = Traits::createPredNodeMap(*G);
1.253 +// }
1.254 + if(!_dist) {
1.255 + local_dist = true;
1.256 + _dist = Traits::createDistMap(*G);
1.257 }
1.258 - if(!distance) {
1.259 - local_distance = true;
1.260 - distance = new DistMap(*G);
1.261 + if(!_reached) {
1.262 + local_reached = true;
1.263 + _reached = Traits::createReachedMap(*G);
1.264 + }
1.265 + if(!_processed) {
1.266 + local_processed = true;
1.267 + _processed = Traits::createProcessedMap(*G);
1.268 }
1.269 }
1.270
1.271 - public :
1.272 + public :
1.273 +
1.274 + ///\name Named template parameters
1.275 +
1.276 + ///@{
1.277 +
1.278 + template <class T>
1.279 + struct DefPredMapTraits : public Traits {
1.280 + typedef T PredMap;
1.281 + static PredMap *createPredMap(const Graph &G)
1.282 + {
1.283 + throw UninitializedParameter();
1.284 + }
1.285 + };
1.286 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.287 +
1.288 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.289 + ///
1.290 + template <class T>
1.291 + class DefPredMap : public Dfs< Graph,
1.292 + DefPredMapTraits<T> > { };
1.293 +
1.294 +// template <class T>
1.295 +// struct DefPredNodeMapTraits : public Traits {
1.296 +// typedef T PredNodeMap;
1.297 +// static PredNodeMap *createPredNodeMap(const Graph &G)
1.298 +// {
1.299 +// throw UninitializedParameter();
1.300 +// }
1.301 +// };
1.302 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.303 +
1.304 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.305 +// ///
1.306 +// template <class T>
1.307 +// class DefPredNodeMap : public Dfs< Graph,
1.308 +// LengthMap,
1.309 +// DefPredNodeMapTraits<T> > { };
1.310 +
1.311 + template <class T>
1.312 + struct DefDistMapTraits : public Traits {
1.313 + typedef T DistMap;
1.314 + static DistMap *createDistMap(const Graph &G)
1.315 + {
1.316 + throw UninitializedParameter();
1.317 + }
1.318 + };
1.319 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.320 +
1.321 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.322 + ///
1.323 + template <class T>
1.324 + class DefDistMap : public Dfs< Graph,
1.325 + DefDistMapTraits<T> > { };
1.326 +
1.327 + template <class T>
1.328 + struct DefReachedMapTraits : public Traits {
1.329 + typedef T ReachedMap;
1.330 + static ReachedMap *createReachedMap(const Graph &G)
1.331 + {
1.332 + throw UninitializedParameter();
1.333 + }
1.334 + };
1.335 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.336 +
1.337 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.338 + ///
1.339 + template <class T>
1.340 + class DefReachedMap : public Dfs< Graph,
1.341 + DefReachedMapTraits<T> > { };
1.342 +
1.343 + struct DefGraphReachedMapTraits : public Traits {
1.344 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.345 + static ReachedMap *createReachedMap(const Graph &G)
1.346 + {
1.347 + return new ReachedMap(G);
1.348 + }
1.349 + };
1.350 + template <class T>
1.351 + struct DefProcessedMapTraits : public Traits {
1.352 + typedef T ProcessedMap;
1.353 + static ProcessedMap *createProcessedMap(const Graph &G)
1.354 + {
1.355 + throw UninitializedParameter();
1.356 + }
1.357 + };
1.358 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.359 +
1.360 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.361 + ///
1.362 + template <class T>
1.363 + class DefProcessedMap : public Dfs< Graph,
1.364 + DefProcessedMapTraits<T> > { };
1.365 +
1.366 + struct DefGraphProcessedMapTraits : public Traits {
1.367 + typedef typename Graph::template NodeMap<bool> ProcessedMap;
1.368 + static ProcessedMap *createProcessedMap(const Graph &G)
1.369 + {
1.370 + return new ProcessedMap(G);
1.371 + }
1.372 + };
1.373 + ///\brief \ref named-templ-param "Named parameter"
1.374 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.375 + ///
1.376 + ///\ref named-templ-param "Named parameter"
1.377 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.378 + ///If you don't set it explicitely, it will be automatically allocated.
1.379 + template <class T>
1.380 + class DefProcessedMapToBeDefaultMap :
1.381 + public Dfs< Graph,
1.382 + DefGraphProcessedMapTraits> { };
1.383 +
1.384 + ///@}
1.385 +
1.386 + public:
1.387 +
1.388 ///Constructor.
1.389
1.390 ///\param _G the graph the algorithm will run on.
1.391 ///
1.392 Dfs(const Graph& _G) :
1.393 G(&_G),
1.394 - predecessor(NULL), local_predecessor(false),
1.395 - pred_node(NULL), local_pred_node(false),
1.396 - distance(NULL), local_distance(false)
1.397 + _pred(NULL), local_pred(false),
1.398 +// _predNode(NULL), local_predNode(false),
1.399 + _dist(NULL), local_dist(false),
1.400 + _reached(NULL), local_reached(false),
1.401 + _processed(NULL), local_processed(false)
1.402 { }
1.403
1.404 ///Destructor.
1.405 ~Dfs()
1.406 {
1.407 - if(local_predecessor) delete predecessor;
1.408 - if(local_pred_node) delete pred_node;
1.409 - if(local_distance) delete distance;
1.410 + if(local_pred) delete _pred;
1.411 +// if(local_predNode) delete _predNode;
1.412 + if(local_dist) delete _dist;
1.413 + if(local_reached) delete _reached;
1.414 + if(local_processed) delete _processed;
1.415 }
1.416
1.417 ///Sets the map storing the predecessor edges.
1.418 @@ -130,32 +387,32 @@
1.419 ///it will allocate one. The destuctor deallocates this
1.420 ///automatically allocated map, of course.
1.421 ///\return <tt> (*this) </tt>
1.422 - Dfs &setPredMap(PredMap &m)
1.423 + Dfs &predMap(PredMap &m)
1.424 {
1.425 - if(local_predecessor) {
1.426 - delete predecessor;
1.427 - local_predecessor=false;
1.428 + if(local_pred) {
1.429 + delete _pred;
1.430 + local_pred=false;
1.431 }
1.432 - predecessor = &m;
1.433 + _pred = &m;
1.434 return *this;
1.435 }
1.436
1.437 - ///Sets the map storing the predecessor nodes.
1.438 +// ///Sets the map storing the predecessor nodes.
1.439
1.440 - ///Sets the map storing the predecessor nodes.
1.441 - ///If you don't use this function before calling \ref run(),
1.442 - ///it will allocate one. The destuctor deallocates this
1.443 - ///automatically allocated map, of course.
1.444 - ///\return <tt> (*this) </tt>
1.445 - Dfs &setPredNodeMap(PredNodeMap &m)
1.446 - {
1.447 - if(local_pred_node) {
1.448 - delete pred_node;
1.449 - local_pred_node=false;
1.450 - }
1.451 - pred_node = &m;
1.452 - return *this;
1.453 - }
1.454 +// ///Sets the map storing the predecessor nodes.
1.455 +// ///If you don't use this function before calling \ref run(),
1.456 +// ///it will allocate one. The destuctor deallocates this
1.457 +// ///automatically allocated map, of course.
1.458 +// ///\return <tt> (*this) </tt>
1.459 +// Dfs &predNodeMap(PredNodeMap &m)
1.460 +// {
1.461 +// if(local_predNode) {
1.462 +// delete _predNode;
1.463 +// local_predNode=false;
1.464 +// }
1.465 +// _predNode = &m;
1.466 +// return *this;
1.467 +// }
1.468
1.469 ///Sets the map storing the distances calculated by the algorithm.
1.470
1.471 @@ -164,127 +421,655 @@
1.472 ///it will allocate one. The destuctor deallocates this
1.473 ///automatically allocated map, of course.
1.474 ///\return <tt> (*this) </tt>
1.475 - Dfs &setDistMap(DistMap &m)
1.476 + Dfs &distMap(DistMap &m)
1.477 {
1.478 - if(local_distance) {
1.479 - delete distance;
1.480 - local_distance=false;
1.481 + if(local_dist) {
1.482 + delete _dist;
1.483 + local_dist=false;
1.484 }
1.485 - distance = &m;
1.486 + _dist = &m;
1.487 return *this;
1.488 }
1.489 -
1.490 - ///Runs %DFS algorithm from node \c s.
1.491
1.492 - ///This method runs the %DFS algorithm from a root node \c s
1.493 - ///in order to
1.494 - ///compute
1.495 - ///- a %DFS tree and
1.496 - ///- the distance of each node from the root on this tree.
1.497 -
1.498 - void run(Node s) {
1.499 -
1.500 - init_maps();
1.501 -
1.502 - source = s;
1.503 -
1.504 + public:
1.505 + ///\name Execution control
1.506 + ///The simplest way to execute the algorithm is to use
1.507 + ///one of the member functions called \c run(...).
1.508 + ///\n
1.509 + ///If you need more control on the execution,
1.510 + ///first you must call \ref init(), then you can add several source nodes
1.511 + ///with \ref addSource().
1.512 + ///Finally \ref start() will perform the actual path
1.513 + ///computation.
1.514 +
1.515 + ///@{
1.516 +
1.517 + ///Initializes the internal data structures.
1.518 +
1.519 + ///Initializes the internal data structures.
1.520 + ///
1.521 + void init()
1.522 + {
1.523 + create_maps();
1.524 + _stack.resize(countNodes(*G));
1.525 + _stack_head=-1;
1.526 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.527 - predecessor->set(u,INVALID);
1.528 - pred_node->set(u,INVALID);
1.529 + _pred->set(u,INVALID);
1.530 + // _predNode->set(u,INVALID);
1.531 + _reached->set(u,false);
1.532 + _processed->set(u,false);
1.533 }
1.534 -
1.535 - int N = countNodes(*G);
1.536 - std::vector<typename Graph::OutEdgeIt> Q(N);
1.537 -
1.538 - int Qh=0;
1.539 -
1.540 - Q[Qh] = OutEdgeIt(*G, s);
1.541 - distance->set(s, 0);
1.542 -
1.543 - Node n=s;
1.544 - Node m;
1.545 - OutEdgeIt e;
1.546 - do {
1.547 - if((e=Q[Qh])!=INVALID)
1.548 - if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) {
1.549 - predecessor->set(m,e);
1.550 - pred_node->set(m,n);
1.551 - Q[++Qh] = OutEdgeIt(*G, m);
1.552 - distance->set(m,Qh);
1.553 - n=m;
1.554 - }
1.555 - else ++Q[Qh];
1.556 - else if(--Qh>=0) n=G->source(Q[Qh]);
1.557 - } while(Qh>=0);
1.558 }
1.559
1.560 - ///The distance of a node from the root on the %DFS tree.
1.561 + ///Adds a new source node.
1.562
1.563 - ///Returns the distance of a node from the root on the %DFS tree.
1.564 + ///Adds a new source node to the set of nodes to be processed.
1.565 + ///
1.566 + ///\bug dist's are wrong (or at least strange) in case of multiple sources.
1.567 + void addSource(Node s)
1.568 + {
1.569 + if(!(*_reached)[s])
1.570 + {
1.571 + _reached->set(s,true);
1.572 + _pred->set(s,INVALID);
1.573 + // _predNode->set(u,INVALID);
1.574 + _stack[++_stack_head]=OutEdgeIt(*G,s);
1.575 + _dist->set(s,_stack_head);
1.576 + }
1.577 + }
1.578 +
1.579 + ///Processes the next node.
1.580 +
1.581 + ///Processes the next node.
1.582 + ///
1.583 + ///\warning The stack must not be empty!
1.584 + void processNextEdge()
1.585 + {
1.586 + Node m;
1.587 + Edge e=_stack[_stack_head];
1.588 + if(!(*_reached)[m=G->target(e)]) {
1.589 + _pred->set(m,e);
1.590 + _reached->set(m,true);
1.591 + // _pred_node->set(m,G->source(e));
1.592 + _stack[++_stack_head] = OutEdgeIt(*G, m);
1.593 + _dist->set(m,_stack_head);
1.594 + }
1.595 + else {
1.596 + Node n;
1.597 + while(_stack_head>=0 &&
1.598 + (n=G->source(_stack[_stack_head]),
1.599 + ++_stack[_stack_head]==INVALID))
1.600 + {
1.601 + _processed->set(n,true);
1.602 + --_stack_head;
1.603 + }
1.604 + }
1.605 + }
1.606 +
1.607 + ///\brief Returns \c false if there are nodes
1.608 + ///to be processed in the queue
1.609 + ///
1.610 + ///Returns \c false if there are nodes
1.611 + ///to be processed in the queue
1.612 + bool emptyQueue() { return _stack_head<0; }
1.613 + ///Returns the number of the nodes to be processed.
1.614 +
1.615 + ///Returns the number of the nodes to be processed in the queue.
1.616 + ///
1.617 + int queueSize() { return _stack_head+1; }
1.618 +
1.619 + ///Executes the algorithm.
1.620 +
1.621 + ///Executes the algorithm.
1.622 + ///
1.623 + ///\pre init() must be called and at least one node should be added
1.624 + ///with addSource() before using this function.
1.625 + ///
1.626 + ///This method runs the %DFS algorithm from the root node(s)
1.627 + ///in order to
1.628 + ///compute the
1.629 + ///%DFS path to each node. The algorithm computes
1.630 + ///- The %DFS tree.
1.631 + ///- The distance of each node from the root(s).
1.632 + ///
1.633 + void start()
1.634 + {
1.635 + while ( !emptyQueue() ) processNextEdge();
1.636 + }
1.637 +
1.638 + ///Executes the algorithm until \c dest is reached.
1.639 +
1.640 + ///Executes the algorithm until \c dest is reached.
1.641 + ///
1.642 + ///\pre init() must be called and at least one node should be added
1.643 + ///with addSource() before using this function.
1.644 + ///
1.645 + ///This method runs the %DFS algorithm from the root node(s)
1.646 + ///in order to
1.647 + ///compute the
1.648 + ///%DFS path to \c dest. The algorithm computes
1.649 + ///- The %DFS path to \c dest.
1.650 + ///- The distance of \c dest from the root(s).
1.651 + ///
1.652 + void start(Node dest)
1.653 + {
1.654 + while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
1.655 + }
1.656 +
1.657 + ///Executes the algorithm until a condition is met.
1.658 +
1.659 + ///Executes the algorithm until a condition is met.
1.660 + ///
1.661 + ///\pre init() must be called and at least one node should be added
1.662 + ///with addSource() before using this function.
1.663 + ///
1.664 + ///\param nm must be a bool (or convertible) node map. The algorithm
1.665 + ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
1.666 + template<class NM>
1.667 + void start(const NM &nm)
1.668 + {
1.669 + while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
1.670 + }
1.671 +
1.672 + ///Runs %DFS algorithm from node \c s.
1.673 +
1.674 + ///This method runs the %DFS algorithm from a root node \c s
1.675 + ///in order to
1.676 + ///compute the
1.677 + ///%DFS path to each node. The algorithm computes
1.678 + ///- The %DFS tree.
1.679 + ///- The distance of each node from the root.
1.680 + ///
1.681 + ///\note d.run(s) is just a shortcut of the following code.
1.682 + ///\code
1.683 + /// d.init();
1.684 + /// d.addSource(s);
1.685 + /// d.start();
1.686 + ///\endcode
1.687 + void run(Node s) {
1.688 + init();
1.689 + addSource(s);
1.690 + start();
1.691 + }
1.692 +
1.693 + ///Finds the %DFS path between \c s and \c t.
1.694 +
1.695 + ///Finds the %DFS path between \c s and \c t.
1.696 + ///
1.697 + ///\return The length of the %DFS s---t path if there exists one,
1.698 + ///0 otherwise.
1.699 + ///\note Apart from the return value, d.run(s) is
1.700 + ///just a shortcut of the following code.
1.701 + ///\code
1.702 + /// d.init();
1.703 + /// d.addSource(s);
1.704 + /// d.start(t);
1.705 + ///\endcode
1.706 + int run(Node s,Node t) {
1.707 + init();
1.708 + addSource(s);
1.709 + start(t);
1.710 + return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
1.711 + }
1.712 +
1.713 + ///@}
1.714 +
1.715 + ///\name Query Functions
1.716 + ///The result of the %DFS algorithm can be obtained using these
1.717 + ///functions.\n
1.718 + ///Before the use of these functions,
1.719 + ///either run() or start() must be called.
1.720 +
1.721 + ///@{
1.722 +
1.723 + ///The distance of a node from the root(s).
1.724 +
1.725 + ///Returns the distance of a node from the root(s).
1.726 ///\pre \ref run() must be called before using this function.
1.727 - ///\warning If node \c v in unreachable from the root the return value
1.728 + ///\warning If node \c v in unreachable from the root(s) the return value
1.729 ///of this funcion is undefined.
1.730 - int dist(Node v) const { return (*distance)[v]; }
1.731 + int dist(Node v) const { return (*_dist)[v]; }
1.732
1.733 - ///Returns the 'previous edge' of the %DFS path tree.
1.734 + ///Returns the 'previous edge' of the %DFS tree.
1.735
1.736 - ///For a node \c v it returns the last edge of the path on the %DFS tree
1.737 - ///from the root to \c
1.738 + ///For a node \c v it returns the 'previous edge'
1.739 + ///of the %DFS path,
1.740 + ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
1.741 ///v. It is \ref INVALID
1.742 - ///if \c v is unreachable from the root or if \c v=s. The
1.743 + ///if \c v is unreachable from the root(s) or \c v is a root. The
1.744 ///%DFS tree used here is equal to the %DFS tree used in
1.745 - ///\ref predNode(Node v). \pre \ref run() must be called before using
1.746 + ///\ref predNode(Node v).
1.747 + ///\pre Either \ref run() or \ref start() must be called before using
1.748 ///this function.
1.749 - Edge pred(Node v) const { return (*predecessor)[v]; }
1.750 + ///\todo predEdge could be a better name.
1.751 + Edge pred(Node v) const { return (*_pred)[v];}
1.752
1.753 ///Returns the 'previous node' of the %DFS tree.
1.754
1.755 - ///For a node \c v it returns the 'previous node' on the %DFS tree,
1.756 - ///i.e. it returns the last but one node of the path from the
1.757 - ///root to \c /v on the %DFS tree.
1.758 - ///It is INVALID if \c v is unreachable from the root or if
1.759 - ///\c v=s.
1.760 - ///\pre \ref run() must be called before
1.761 + ///For a node \c v it returns the 'previous node'
1.762 + ///of the %DFS tree,
1.763 + ///i.e. it returns the last but one node from a %DFS path from the
1.764 + ///root(a) to \c /v.
1.765 + ///It is INVALID if \c v is unreachable from the root(s) or
1.766 + ///if \c v itself a root.
1.767 + ///The %DFS tree used here is equal to the %DFS
1.768 + ///tree used in \ref pred(Node v).
1.769 + ///\pre Either \ref run() or \ref start() must be called before
1.770 ///using this function.
1.771 - Node predNode(Node v) const { return (*pred_node)[v]; }
1.772 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.773 + G->source((*_pred)[v]); }
1.774
1.775 - ///Returns a reference to the NodeMap of distances on the %DFS tree.
1.776 -
1.777 - ///Returns a reference to the NodeMap of distances on the %DFS tree.
1.778 - ///\pre \ref run() must
1.779 + ///Returns a reference to the NodeMap of distances.
1.780 +
1.781 + ///Returns a reference to the NodeMap of distances.
1.782 + ///\pre Either \ref run() or \ref init() must
1.783 ///be called before using this function.
1.784 - const DistMap &distMap() const { return *distance;}
1.785 + const DistMap &distMap() const { return *_dist;}
1.786
1.787 - ///Returns a reference to the %DFS tree map.
1.788 + ///Returns a reference to the %DFS edge-tree map.
1.789
1.790 ///Returns a reference to the NodeMap of the edges of the
1.791 ///%DFS tree.
1.792 - ///\pre \ref run() must be called before using this function.
1.793 - const PredMap &predMap() const { return *predecessor;}
1.794 + ///\pre Either \ref run() or \ref init()
1.795 + ///must be called before using this function.
1.796 + const PredMap &predMap() const { return *_pred;}
1.797
1.798 - ///Returns a reference to the map of last but one nodes of the %DFS tree.
1.799 +// ///Returns a reference to the map of nodes of %DFS paths.
1.800
1.801 - ///Returns a reference to the NodeMap of the last but one nodes of the paths
1.802 - ///on the
1.803 - ///%DFS tree.
1.804 - ///\pre \ref run() must be called before using this function.
1.805 - const PredNodeMap &predNodeMap() const { return *pred_node;}
1.806 +// ///Returns a reference to the NodeMap of the last but one nodes of the
1.807 +// ///%DFS tree.
1.808 +// ///\pre \ref run() must be called before using this function.
1.809 +// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.810
1.811 ///Checks if a node is reachable from the root.
1.812
1.813 ///Returns \c true if \c v is reachable from the root.
1.814 - ///\note The root node is reported to be reached!
1.815 + ///\warning The source nodes are inditated as unreached.
1.816 + ///\pre Either \ref run() or \ref start()
1.817 + ///must be called before using this function.
1.818 ///
1.819 - ///\pre \ref run() must be called before using this function.
1.820 + bool reached(Node v) { return (*_reached)[v]; }
1.821 +
1.822 + ///@}
1.823 + };
1.824 +
1.825 + ///Default traits class of Dfs function.
1.826 +
1.827 + ///Default traits class of Dfs function.
1.828 + ///\param GR Graph type.
1.829 + template<class GR>
1.830 + struct DfsWizardDefaultTraits
1.831 + {
1.832 + ///The graph type the algorithm runs on.
1.833 + typedef GR Graph;
1.834 + ///\brief The type of the map that stores the last
1.835 + ///edges of the %DFS paths.
1.836 + ///
1.837 + ///The type of the map that stores the last
1.838 + ///edges of the %DFS paths.
1.839 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.840 ///
1.841 - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.842 + typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
1.843 + ///Instantiates a PredMap.
1.844 +
1.845 + ///This function instantiates a \ref PredMap.
1.846 + ///\param G is the graph, to which we would like to define the PredMap.
1.847 + ///\todo The graph alone may be insufficient to initialize
1.848 + static PredMap *createPredMap(const GR &G)
1.849 + {
1.850 + return new PredMap();
1.851 + }
1.852 +// ///\brief The type of the map that stores the last but one
1.853 +// ///nodes of the %DFS paths.
1.854 +// ///
1.855 +// ///The type of the map that stores the last but one
1.856 +// ///nodes of the %DFS paths.
1.857 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.858 +// ///
1.859 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.860 +// ///Instantiates a PredNodeMap.
1.861 +
1.862 +// ///This function instantiates a \ref PredNodeMap.
1.863 +// ///\param G is the graph, to which
1.864 +// ///we would like to define the \ref PredNodeMap
1.865 +// static PredNodeMap *createPredNodeMap(const GR &G)
1.866 +// {
1.867 +// return new PredNodeMap();
1.868 +// }
1.869 +
1.870 + ///The type of the map that indicates which nodes are processed.
1.871 +
1.872 + ///The type of the map that indicates which nodes are processed.
1.873 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.874 + ///\todo named parameter to set this type, function to read and write.
1.875 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.876 + ///Instantiates a ProcessedMap.
1.877 +
1.878 + ///This function instantiates a \ref ProcessedMap.
1.879 + ///\param G is the graph, to which
1.880 + ///we would like to define the \ref ProcessedMap
1.881 + static ProcessedMap *createProcessedMap(const GR &G)
1.882 + {
1.883 + return new ProcessedMap();
1.884 + }
1.885 + ///The type of the map that indicates which nodes are reached.
1.886 +
1.887 + ///The type of the map that indicates which nodes are reached.
1.888 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.889 + ///\todo named parameter to set this type, function to read and write.
1.890 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.891 + ///Instantiates a ReachedMap.
1.892 +
1.893 + ///This function instantiates a \ref ReachedMap.
1.894 + ///\param G is the graph, to which
1.895 + ///we would like to define the \ref ReachedMap.
1.896 + static ReachedMap *createReachedMap(const GR &G)
1.897 + {
1.898 + return new ReachedMap(G);
1.899 + }
1.900 + ///The type of the map that stores the dists of the nodes.
1.901 +
1.902 + ///The type of the map that stores the dists of the nodes.
1.903 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.904 + ///
1.905 + typedef NullMap<typename Graph::Node,int> DistMap;
1.906 + ///Instantiates a DistMap.
1.907 +
1.908 + ///This function instantiates a \ref DistMap.
1.909 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.910 + static DistMap *createDistMap(const GR &G)
1.911 + {
1.912 + return new DistMap();
1.913 + }
1.914 + };
1.915 +
1.916 + /// Default traits used by \ref DfsWizard
1.917 +
1.918 + /// To make it easier to use Dfs algorithm
1.919 + ///we have created a wizard class.
1.920 + /// This \ref DfsWizard class needs default traits,
1.921 + ///as well as the \ref Dfs class.
1.922 + /// The \ref DfsWizardBase is a class to be the default traits of the
1.923 + /// \ref DfsWizard class.
1.924 + template<class GR>
1.925 + class DfsWizardBase : public DfsWizardDefaultTraits<GR>
1.926 + {
1.927 +
1.928 + typedef DfsWizardDefaultTraits<GR> Base;
1.929 + protected:
1.930 + /// Type of the nodes in the graph.
1.931 + typedef typename Base::Graph::Node Node;
1.932 +
1.933 + /// Pointer to the underlying graph.
1.934 + void *_g;
1.935 + ///Pointer to the map of reached nodes.
1.936 + void *_reached;
1.937 + ///Pointer to the map of processed nodes.
1.938 + void *_processed;
1.939 + ///Pointer to the map of predecessors edges.
1.940 + void *_pred;
1.941 +// ///Pointer to the map of predecessors nodes.
1.942 +// void *_predNode;
1.943 + ///Pointer to the map of distances.
1.944 + void *_dist;
1.945 + ///Pointer to the source node.
1.946 + Node _source;
1.947 +
1.948 + public:
1.949 + /// Constructor.
1.950 +
1.951 + /// This constructor does not require parameters, therefore it initiates
1.952 + /// all of the attributes to default values (0, INVALID).
1.953 + DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.954 +// _predNode(0),
1.955 + _dist(0), _source(INVALID) {}
1.956 +
1.957 + /// Constructor.
1.958 +
1.959 + /// This constructor requires some parameters,
1.960 + /// listed in the parameters list.
1.961 + /// Others are initiated to 0.
1.962 + /// \param g is the initial value of \ref _g
1.963 + /// \param s is the initial value of \ref _source
1.964 + DfsWizardBase(const GR &g, Node s=INVALID) :
1.965 + _g((void *)&g), _reached(0), _processed(0), _pred(0),
1.966 +// _predNode(0),
1.967 + _dist(0), _source(s) {}
1.968 +
1.969 + };
1.970 +
1.971 + /// A class to make the usage of Dfs algorithm easier
1.972 +
1.973 + /// This class is created to make it easier to use Dfs algorithm.
1.974 + /// It uses the functions and features of the plain \ref Dfs,
1.975 + /// but it is much simpler to use it.
1.976 + ///
1.977 + /// Simplicity means that the way to change the types defined
1.978 + /// in the traits class is based on functions that returns the new class
1.979 + /// and not on templatable built-in classes.
1.980 + /// When using the plain \ref Dfs
1.981 + /// the new class with the modified type comes from
1.982 + /// the original class by using the ::
1.983 + /// operator. In the case of \ref DfsWizard only
1.984 + /// a function have to be called and it will
1.985 + /// return the needed class.
1.986 + ///
1.987 + /// It does not have own \ref run method. When its \ref run method is called
1.988 + /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run
1.989 + /// method of it.
1.990 + template<class TR>
1.991 + class DfsWizard : public TR
1.992 + {
1.993 + typedef TR Base;
1.994 +
1.995 + ///The type of the underlying graph.
1.996 + typedef typename TR::Graph Graph;
1.997 + //\e
1.998 + typedef typename Graph::Node Node;
1.999 + //\e
1.1000 + typedef typename Graph::NodeIt NodeIt;
1.1001 + //\e
1.1002 + typedef typename Graph::Edge Edge;
1.1003 + //\e
1.1004 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1005 +
1.1006 + ///\brief The type of the map that stores
1.1007 + ///the reached nodes
1.1008 + typedef typename TR::ReachedMap ReachedMap;
1.1009 + ///\brief The type of the map that stores
1.1010 + ///the processed nodes
1.1011 + typedef typename TR::ProcessedMap ProcessedMap;
1.1012 + ///\brief The type of the map that stores the last
1.1013 + ///edges of the %DFS paths.
1.1014 + typedef typename TR::PredMap PredMap;
1.1015 +// ///\brief The type of the map that stores the last but one
1.1016 +// ///nodes of the %DFS paths.
1.1017 +// typedef typename TR::PredNodeMap PredNodeMap;
1.1018 + ///The type of the map that stores the dists of the nodes.
1.1019 + typedef typename TR::DistMap DistMap;
1.1020 +
1.1021 +public:
1.1022 + /// Constructor.
1.1023 + DfsWizard() : TR() {}
1.1024 +
1.1025 + /// Constructor that requires parameters.
1.1026 +
1.1027 + /// Constructor that requires parameters.
1.1028 + /// These parameters will be the default values for the traits class.
1.1029 + DfsWizard(const Graph &g, Node s=INVALID) :
1.1030 + TR(g,s) {}
1.1031 +
1.1032 + ///Copy constructor
1.1033 + DfsWizard(const TR &b) : TR(b) {}
1.1034 +
1.1035 + ~DfsWizard() {}
1.1036 +
1.1037 + ///Runs Dfs algorithm from a given node.
1.1038 +
1.1039 + ///Runs Dfs algorithm from a given node.
1.1040 + ///The node can be given by the \ref source function.
1.1041 + void run()
1.1042 + {
1.1043 + if(Base::_source==INVALID) throw UninitializedParameter();
1.1044 + Dfs<Graph,TR> alg(*(Graph*)Base::_g);
1.1045 + if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
1.1046 + if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1.1047 + if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1.1048 +// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.1049 + if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1.1050 + alg.run(Base::_source);
1.1051 + }
1.1052 +
1.1053 + ///Runs Dfs algorithm from the given node.
1.1054 +
1.1055 + ///Runs Dfs algorithm from the given node.
1.1056 + ///\param s is the given source.
1.1057 + void run(Node s)
1.1058 + {
1.1059 + Base::_source=s;
1.1060 + run();
1.1061 + }
1.1062 +
1.1063 + template<class T>
1.1064 + struct DefPredMapBase : public Base {
1.1065 + typedef T PredMap;
1.1066 + static PredMap *createPredMap(const Graph &G) { return 0; };
1.1067 + DefPredMapBase(const Base &b) : Base(b) {}
1.1068 + };
1.1069 +
1.1070 + ///\brief \ref named-templ-param "Named parameter"
1.1071 + ///function for setting PredMap type
1.1072 + ///
1.1073 + /// \ref named-templ-param "Named parameter"
1.1074 + ///function for setting PredMap type
1.1075 + ///
1.1076 + template<class T>
1.1077 + DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1078 + {
1.1079 + Base::_pred=(void *)&t;
1.1080 + return DfsWizard<DefPredMapBase<T> >(*this);
1.1081 + }
1.1082 +
1.1083 +
1.1084 + template<class T>
1.1085 + struct DefReachedMapBase : public Base {
1.1086 + typedef T ReachedMap;
1.1087 + static ReachedMap *createReachedMap(const Graph &G) { return 0; };
1.1088 + DefReachedMapBase(const Base &b) : Base(b) {}
1.1089 + };
1.1090 +
1.1091 + ///\brief \ref named-templ-param "Named parameter"
1.1092 + ///function for setting ReachedMap
1.1093 + ///
1.1094 + /// \ref named-templ-param "Named parameter"
1.1095 + ///function for setting ReachedMap
1.1096 + ///
1.1097 + template<class T>
1.1098 + DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1099 + {
1.1100 + Base::_pred=(void *)&t;
1.1101 + return DfsWizard<DefReachedMapBase<T> >(*this);
1.1102 + }
1.1103 +
1.1104 +
1.1105 + template<class T>
1.1106 + struct DefProcessedMapBase : public Base {
1.1107 + typedef T ProcessedMap;
1.1108 + static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
1.1109 + DefProcessedMapBase(const Base &b) : Base(b) {}
1.1110 + };
1.1111 +
1.1112 + ///\brief \ref named-templ-param "Named parameter"
1.1113 + ///function for setting ProcessedMap
1.1114 + ///
1.1115 + /// \ref named-templ-param "Named parameter"
1.1116 + ///function for setting ProcessedMap
1.1117 + ///
1.1118 + template<class T>
1.1119 + DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1120 + {
1.1121 + Base::_pred=(void *)&t;
1.1122 + return DfsWizard<DefProcessedMapBase<T> >(*this);
1.1123 + }
1.1124 +
1.1125 +
1.1126 +// template<class T>
1.1127 +// struct DefPredNodeMapBase : public Base {
1.1128 +// typedef T PredNodeMap;
1.1129 +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.1130 +// DefPredNodeMapBase(const Base &b) : Base(b) {}
1.1131 +// };
1.1132 +
1.1133 +// ///\brief \ref named-templ-param "Named parameter"
1.1134 +// ///function for setting PredNodeMap type
1.1135 +// ///
1.1136 +// /// \ref named-templ-param "Named parameter"
1.1137 +// ///function for setting PredNodeMap type
1.1138 +// ///
1.1139 +// template<class T>
1.1140 +// DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.1141 +// {
1.1142 +// Base::_predNode=(void *)&t;
1.1143 +// return DfsWizard<DefPredNodeMapBase<T> >(*this);
1.1144 +// }
1.1145 +
1.1146 + template<class T>
1.1147 + struct DefDistMapBase : public Base {
1.1148 + typedef T DistMap;
1.1149 + static DistMap *createDistMap(const Graph &G) { return 0; };
1.1150 + DefDistMapBase(const Base &b) : Base(b) {}
1.1151 + };
1.1152 +
1.1153 + ///\brief \ref named-templ-param "Named parameter"
1.1154 + ///function for setting DistMap type
1.1155 + ///
1.1156 + /// \ref named-templ-param "Named parameter"
1.1157 + ///function for setting DistMap type
1.1158 + ///
1.1159 + template<class T>
1.1160 + DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1161 + {
1.1162 + Base::_dist=(void *)&t;
1.1163 + return DfsWizard<DefDistMapBase<T> >(*this);
1.1164 + }
1.1165 +
1.1166 + /// Sets the source node, from which the Dfs algorithm runs.
1.1167 +
1.1168 + /// Sets the source node, from which the Dfs algorithm runs.
1.1169 + /// \param s is the source node.
1.1170 + DfsWizard<TR> &source(Node s)
1.1171 + {
1.1172 + Base::_source=s;
1.1173 + return *this;
1.1174 + }
1.1175
1.1176 };
1.1177
1.1178 -/// @}
1.1179 -
1.1180 + ///Function type interface for Dfs algorithm.
1.1181 +
1.1182 + /// \ingroup flowalgs
1.1183 + ///Function type interface for Dfs algorithm.
1.1184 + ///
1.1185 + ///This function also has several
1.1186 + ///\ref named-templ-func-param "named parameters",
1.1187 + ///they are declared as the members of class \ref DfsWizard.
1.1188 + ///The following
1.1189 + ///example shows how to use these parameters.
1.1190 + ///\code
1.1191 + /// dfs(g,source).predMap(preds).run();
1.1192 + ///\endcode
1.1193 + ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1.1194 + ///to the end of the parameter list.
1.1195 + ///\sa DfsWizard
1.1196 + ///\sa Dfs
1.1197 + template<class GR>
1.1198 + DfsWizard<DfsWizardBase<GR> >
1.1199 + dfs(const GR &g,typename GR::Node s=INVALID)
1.1200 + {
1.1201 + return DfsWizard<DfsWizardBase<GR> >(g,s);
1.1202 + }
1.1203 +
1.1204 } //END OF NAMESPACE LEMON
1.1205
1.1206 #endif
1.1207
1.1208 -