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