32 |
32 |
33 #include <lemon/concept_check.h> |
33 #include <lemon/concept_check.h> |
34 |
34 |
35 namespace lemon { |
35 namespace lemon { |
36 |
36 |
37 |
37 |
38 ///Default traits class of Dfs class. |
38 ///Default traits class of Dfs class. |
39 |
39 |
40 ///Default traits class of Dfs class. |
40 ///Default traits class of Dfs class. |
41 ///\tparam GR Digraph type. |
41 ///\tparam GR Digraph type. |
42 template<class GR> |
42 template<class GR> |
43 struct DfsDefaultTraits |
43 struct DfsDefaultTraits |
44 { |
44 { |
45 ///The digraph type the algorithm runs on. |
45 ///The digraph type the algorithm runs on. |
46 typedef GR Digraph; |
46 typedef GR Digraph; |
47 ///\brief The type of the map that stores the last |
47 ///\brief The type of the map that stores the last |
48 ///arcs of the %DFS paths. |
48 ///arcs of the %DFS paths. |
49 /// |
49 /// |
50 ///The type of the map that stores the last |
50 ///The type of the map that stores the last |
51 ///arcs of the %DFS paths. |
51 ///arcs of the %DFS paths. |
52 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
52 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
53 /// |
53 /// |
54 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
54 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
55 ///Instantiates a PredMap. |
55 ///Instantiates a PredMap. |
56 |
56 |
57 ///This function instantiates a \ref PredMap. |
57 ///This function instantiates a \ref PredMap. |
58 ///\param G is the digraph, to which we would like to define the PredMap. |
58 ///\param G is the digraph, to which we would like to define the PredMap. |
59 ///\todo The digraph alone may be insufficient to initialize |
59 ///\todo The digraph alone may be insufficient to initialize |
60 static PredMap *createPredMap(const GR &G) |
60 static PredMap *createPredMap(const GR &G) |
61 { |
61 { |
62 return new PredMap(G); |
62 return new PredMap(G); |
63 } |
63 } |
64 |
64 |
65 ///The type of the map that indicates which nodes are processed. |
65 ///The type of the map that indicates which nodes are processed. |
66 |
66 |
67 ///The type of the map that indicates which nodes are processed. |
67 ///The type of the map that indicates which nodes are processed. |
68 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
68 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
69 ///\todo named parameter to set this type, function to read and write. |
69 ///\todo named parameter to set this type, function to read and write. |
70 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
70 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
71 ///Instantiates a ProcessedMap. |
71 ///Instantiates a ProcessedMap. |
72 |
72 |
73 ///This function instantiates a \ref ProcessedMap. |
73 ///This function instantiates a \ref ProcessedMap. |
74 ///\param g is the digraph, to which |
74 ///\param g is the digraph, to which |
75 ///we would like to define the \ref ProcessedMap |
75 ///we would like to define the \ref ProcessedMap |
76 #ifdef DOXYGEN |
76 #ifdef DOXYGEN |
77 static ProcessedMap *createProcessedMap(const GR &g) |
77 static ProcessedMap *createProcessedMap(const GR &g) |
78 #else |
78 #else |
80 #endif |
80 #endif |
81 { |
81 { |
82 return new ProcessedMap(); |
82 return new ProcessedMap(); |
83 } |
83 } |
84 ///The type of the map that indicates which nodes are reached. |
84 ///The type of the map that indicates which nodes are reached. |
85 |
85 |
86 ///The type of the map that indicates which nodes are reached. |
86 ///The type of the map that indicates which nodes are reached. |
87 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
87 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
88 ///\todo named parameter to set this type, function to read and write. |
88 ///\todo named parameter to set this type, function to read and write. |
89 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
89 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
90 ///Instantiates a ReachedMap. |
90 ///Instantiates a ReachedMap. |
91 |
91 |
92 ///This function instantiates a \ref ReachedMap. |
92 ///This function instantiates a \ref ReachedMap. |
93 ///\param G is the digraph, to which |
93 ///\param G is the digraph, to which |
94 ///we would like to define the \ref ReachedMap. |
94 ///we would like to define the \ref ReachedMap. |
95 static ReachedMap *createReachedMap(const GR &G) |
95 static ReachedMap *createReachedMap(const GR &G) |
96 { |
96 { |
97 return new ReachedMap(G); |
97 return new ReachedMap(G); |
98 } |
98 } |
99 ///The type of the map that stores the dists of the nodes. |
99 ///The type of the map that stores the dists of the nodes. |
100 |
100 |
101 ///The type of the map that stores the dists of the nodes. |
101 ///The type of the map that stores the dists of the nodes. |
102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
103 /// |
103 /// |
104 typedef typename Digraph::template NodeMap<int> DistMap; |
104 typedef typename Digraph::template NodeMap<int> DistMap; |
105 ///Instantiates a DistMap. |
105 ///Instantiates a DistMap. |
106 |
106 |
107 ///This function instantiates a \ref DistMap. |
107 ///This function instantiates a \ref DistMap. |
108 ///\param G is the digraph, to which we would like to define the \ref DistMap |
108 ///\param G is the digraph, to which we would like to define the \ref DistMap |
109 static DistMap *createDistMap(const GR &G) |
109 static DistMap *createDistMap(const GR &G) |
110 { |
110 { |
111 return new DistMap(G); |
111 return new DistMap(G); |
112 } |
112 } |
113 }; |
113 }; |
114 |
114 |
115 ///%DFS algorithm class. |
115 ///%DFS algorithm class. |
116 |
116 |
117 ///\ingroup search |
117 ///\ingroup search |
118 ///This class provides an efficient implementation of the %DFS algorithm. |
118 ///This class provides an efficient implementation of the %DFS algorithm. |
119 /// |
119 /// |
120 ///\tparam GR The digraph type the algorithm runs on. The default value is |
120 ///\tparam GR The digraph type the algorithm runs on. The default value is |
121 ///\ref ListDigraph. The value of GR is not used directly by Dfs, it |
121 ///\ref ListDigraph. The value of GR is not used directly by Dfs, it |
282 }; |
282 }; |
283 |
283 |
284 template <class T> |
284 template <class T> |
285 struct DefProcessedMapTraits : public Traits { |
285 struct DefProcessedMapTraits : public Traits { |
286 typedef T ProcessedMap; |
286 typedef T ProcessedMap; |
287 static ProcessedMap *createProcessedMap(const Digraph &) |
287 static ProcessedMap *createProcessedMap(const Digraph &) |
288 { |
288 { |
289 throw UninitializedParameter(); |
289 throw UninitializedParameter(); |
290 } |
290 } |
291 }; |
291 }; |
292 ///\brief \ref named-templ-param "Named parameter" for setting |
292 ///\brief \ref named-templ-param "Named parameter" for setting |
293 ///ProcessedMap type |
293 ///ProcessedMap type |
294 /// |
294 /// |
295 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
295 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
296 /// |
296 /// |
297 template <class T> |
297 template <class T> |
298 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { |
298 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { |
299 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create; |
299 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create; |
300 }; |
300 }; |
301 |
301 |
302 struct DefDigraphProcessedMapTraits : public Traits { |
302 struct DefDigraphProcessedMapTraits : public Traits { |
303 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
303 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
304 static ProcessedMap *createProcessedMap(const Digraph &G) |
304 static ProcessedMap *createProcessedMap(const Digraph &G) |
305 { |
305 { |
306 return new ProcessedMap(G); |
306 return new ProcessedMap(G); |
307 } |
307 } |
308 }; |
308 }; |
309 ///\brief \ref named-templ-param "Named parameter" |
309 ///\brief \ref named-templ-param "Named parameter" |
310 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
310 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
311 /// |
311 /// |
312 ///\ref named-templ-param "Named parameter" |
312 ///\ref named-templ-param "Named parameter" |
313 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
313 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
314 ///If you don't set it explicitely, it will be automatically allocated. |
314 ///If you don't set it explicitely, it will be automatically allocated. |
315 template <class T> |
315 template <class T> |
316 class DefProcessedMapToBeDefaultMap : |
316 class DefProcessedMapToBeDefaultMap : |
317 public Dfs< Digraph, DefDigraphProcessedMapTraits> { |
317 public Dfs< Digraph, DefDigraphProcessedMapTraits> { |
318 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; |
318 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; |
319 }; |
319 }; |
320 |
320 |
321 ///@} |
321 ///@} |
322 |
322 |
323 public: |
323 public: |
324 |
324 |
325 ///Constructor. |
325 ///Constructor. |
326 |
326 |
327 ///\param _G the digraph the algorithm will run on. |
327 ///\param _G the digraph the algorithm will run on. |
328 /// |
328 /// |
329 Dfs(const Digraph& _G) : |
329 Dfs(const Digraph& _G) : |
330 G(&_G), |
330 G(&_G), |
331 _pred(NULL), local_pred(false), |
331 _pred(NULL), local_pred(false), |
332 _dist(NULL), local_dist(false), |
332 _dist(NULL), local_dist(false), |
333 _reached(NULL), local_reached(false), |
333 _reached(NULL), local_reached(false), |
334 _processed(NULL), local_processed(false) |
334 _processed(NULL), local_processed(false) |
335 { } |
335 { } |
336 |
336 |
337 ///Destructor. |
337 ///Destructor. |
338 ~Dfs() |
338 ~Dfs() |
339 { |
339 { |
340 if(local_pred) delete _pred; |
340 if(local_pred) delete _pred; |
341 if(local_dist) delete _dist; |
341 if(local_dist) delete _dist; |
342 if(local_reached) delete _reached; |
342 if(local_reached) delete _reached; |
343 if(local_processed) delete _processed; |
343 if(local_processed) delete _processed; |
432 { |
432 { |
433 create_maps(); |
433 create_maps(); |
434 _stack.resize(countNodes(*G)); |
434 _stack.resize(countNodes(*G)); |
435 _stack_head=-1; |
435 _stack_head=-1; |
436 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
436 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
437 _pred->set(u,INVALID); |
437 _pred->set(u,INVALID); |
438 // _predNode->set(u,INVALID); |
438 // _predNode->set(u,INVALID); |
439 _reached->set(u,false); |
439 _reached->set(u,false); |
440 _processed->set(u,false); |
440 _processed->set(u,false); |
441 } |
441 } |
442 } |
442 } |
443 |
443 |
444 ///Adds a new source node. |
444 ///Adds a new source node. |
445 |
445 |
446 ///Adds a new source node to the set of nodes to be processed. |
446 ///Adds a new source node to the set of nodes to be processed. |
447 /// |
447 /// |
448 ///\warning dists are wrong (or at least strange) |
448 ///\warning dists are wrong (or at least strange) |
449 ///in case of multiple sources. |
449 ///in case of multiple sources. |
450 void addSource(Node s) |
450 void addSource(Node s) |
451 { |
451 { |
452 if(!(*_reached)[s]) |
452 if(!(*_reached)[s]) |
453 { |
453 { |
454 _reached->set(s,true); |
454 _reached->set(s,true); |
455 _pred->set(s,INVALID); |
455 _pred->set(s,INVALID); |
456 OutArcIt e(*G,s); |
456 OutArcIt e(*G,s); |
457 if(e!=INVALID) { |
457 if(e!=INVALID) { |
458 _stack[++_stack_head]=e; |
458 _stack[++_stack_head]=e; |
459 _dist->set(s,_stack_head); |
459 _dist->set(s,_stack_head); |
460 } |
460 } |
461 else { |
461 else { |
462 _processed->set(s,true); |
462 _processed->set(s,true); |
463 _dist->set(s,0); |
463 _dist->set(s,0); |
464 } |
464 } |
465 } |
465 } |
466 } |
466 } |
467 |
467 |
468 ///Processes the next arc. |
468 ///Processes the next arc. |
469 |
469 |
470 ///Processes the next arc. |
470 ///Processes the next arc. |
471 /// |
471 /// |
472 ///\return The processed arc. |
472 ///\return The processed arc. |
473 /// |
473 /// |
474 ///\pre The stack must not be empty! |
474 ///\pre The stack must not be empty! |
475 Arc processNextArc() |
475 Arc processNextArc() |
476 { |
476 { |
477 Node m; |
477 Node m; |
478 Arc e=_stack[_stack_head]; |
478 Arc e=_stack[_stack_head]; |
479 if(!(*_reached)[m=G->target(e)]) { |
479 if(!(*_reached)[m=G->target(e)]) { |
480 _pred->set(m,e); |
480 _pred->set(m,e); |
481 _reached->set(m,true); |
481 _reached->set(m,true); |
482 ++_stack_head; |
482 ++_stack_head; |
483 _stack[_stack_head] = OutArcIt(*G, m); |
483 _stack[_stack_head] = OutArcIt(*G, m); |
484 _dist->set(m,_stack_head); |
484 _dist->set(m,_stack_head); |
485 } |
485 } |
486 else { |
486 else { |
487 m=G->source(e); |
487 m=G->source(e); |
488 ++_stack[_stack_head]; |
488 ++_stack[_stack_head]; |
489 } |
489 } |
490 while(_stack_head>=0 && _stack[_stack_head]==INVALID) { |
490 while(_stack_head>=0 && _stack[_stack_head]==INVALID) { |
491 _processed->set(m,true); |
491 _processed->set(m,true); |
492 --_stack_head; |
492 --_stack_head; |
493 if(_stack_head>=0) { |
493 if(_stack_head>=0) { |
494 m=G->source(_stack[_stack_head]); |
494 m=G->source(_stack[_stack_head]); |
495 ++_stack[_stack_head]; |
495 ++_stack[_stack_head]; |
496 } |
496 } |
497 } |
497 } |
498 return e; |
498 return e; |
499 } |
499 } |
500 ///Next arc to be processed. |
500 ///Next arc to be processed. |
501 |
501 |
502 ///Next arc to be processed. |
502 ///Next arc to be processed. |
503 /// |
503 /// |
504 ///\return The next arc to be processed or INVALID if the stack is |
504 ///\return The next arc to be processed or INVALID if the stack is |
505 /// empty. |
505 /// empty. |
506 OutArcIt nextArc() |
506 OutArcIt nextArc() |
507 { |
507 { |
508 return _stack_head>=0?_stack[_stack_head]:INVALID; |
508 return _stack_head>=0?_stack[_stack_head]:INVALID; |
509 } |
509 } |
510 |
510 |
511 ///\brief Returns \c false if there are nodes |
511 ///\brief Returns \c false if there are nodes |
512 ///to be processed in the queue |
512 ///to be processed in the queue |
513 /// |
513 /// |
514 ///Returns \c false if there are nodes |
514 ///Returns \c false if there are nodes |
515 ///to be processed in the queue |
515 ///to be processed in the queue |
516 bool emptyQueue() { return _stack_head<0; } |
516 bool emptyQueue() { return _stack_head<0; } |
517 ///Returns the number of the nodes to be processed. |
517 ///Returns the number of the nodes to be processed. |
518 |
518 |
519 ///Returns the number of the nodes to be processed in the queue. |
519 ///Returns the number of the nodes to be processed in the queue. |
520 int queueSize() { return _stack_head+1; } |
520 int queueSize() { return _stack_head+1; } |
521 |
521 |
522 ///Executes the algorithm. |
522 ///Executes the algorithm. |
523 |
523 |
524 ///Executes the algorithm. |
524 ///Executes the algorithm. |
525 /// |
525 /// |
526 ///\pre init() must be called and at least one node should be added |
526 ///\pre init() must be called and at least one node should be added |
647 init(); |
647 init(); |
648 addSource(s); |
648 addSource(s); |
649 start(t); |
649 start(t); |
650 return reached(t)?_stack_head+1:0; |
650 return reached(t)?_stack_head+1:0; |
651 } |
651 } |
652 |
652 |
653 ///@} |
653 ///@} |
654 |
654 |
655 ///\name Query Functions |
655 ///\name Query Functions |
656 ///The result of the %DFS algorithm can be obtained using these |
656 ///The result of the %DFS algorithm can be obtained using these |
657 ///functions.\n |
657 ///functions.\n |
658 ///Before the use of these functions, |
658 ///Before the use of these functions, |
659 ///either run() or start() must be called. |
659 ///either run() or start() must be called. |
660 |
660 |
661 ///@{ |
661 ///@{ |
662 |
662 |
663 typedef PredMapPath<Digraph, PredMap> Path; |
663 typedef PredMapPath<Digraph, PredMap> Path; |
664 |
664 |
665 ///Gives back the shortest path. |
665 ///Gives back the shortest path. |
666 |
666 |
667 ///Gives back the shortest path. |
667 ///Gives back the shortest path. |
668 ///\pre The \c t should be reachable from the source. |
668 ///\pre The \c t should be reachable from the source. |
669 Path path(Node t) |
669 Path path(Node t) |
670 { |
670 { |
671 return Path(*G, *_pred, t); |
671 return Path(*G, *_pred, t); |
672 } |
672 } |
673 |
673 |
674 ///The distance of a node from the root(s). |
674 ///The distance of a node from the root(s). |
675 |
675 |
676 ///Returns the distance of a node from the root(s). |
676 ///Returns the distance of a node from the root(s). |
677 ///\pre \ref run() must be called before using this function. |
677 ///\pre \ref run() must be called before using this function. |
678 ///\warning If node \c v is unreachable from the root(s) then the return |
678 ///\warning If node \c v is unreachable from the root(s) then the return |
679 ///value of this funcion is undefined. |
679 ///value of this funcion is undefined. |
680 int dist(Node v) const { return (*_dist)[v]; } |
680 int dist(Node v) const { return (*_dist)[v]; } |
681 |
681 |
682 ///Returns the 'previous arc' of the %DFS tree. |
682 ///Returns the 'previous arc' of the %DFS tree. |
683 |
683 |
703 ///The %DFS tree used here is equal to the %DFS |
703 ///The %DFS tree used here is equal to the %DFS |
704 ///tree used in \ref predArc(). |
704 ///tree used in \ref predArc(). |
705 ///\pre Either \ref run() or \ref start() must be called before |
705 ///\pre Either \ref run() or \ref start() must be called before |
706 ///using this function. |
706 ///using this function. |
707 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
707 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
708 G->source((*_pred)[v]); } |
708 G->source((*_pred)[v]); } |
709 |
709 |
710 ///Returns a reference to the NodeMap of distances. |
710 ///Returns a reference to the NodeMap of distances. |
711 |
711 |
712 ///Returns a reference to the NodeMap of distances. |
712 ///Returns a reference to the NodeMap of distances. |
713 ///\pre Either \ref run() or \ref init() must |
713 ///\pre Either \ref run() or \ref init() must |
714 ///be called before using this function. |
714 ///be called before using this function. |
715 const DistMap &distMap() const { return *_dist;} |
715 const DistMap &distMap() const { return *_dist;} |
716 |
716 |
717 ///Returns a reference to the %DFS arc-tree map. |
717 ///Returns a reference to the %DFS arc-tree map. |
718 |
718 |
719 ///Returns a reference to the NodeMap of the arcs of the |
719 ///Returns a reference to the NodeMap of the arcs of the |
720 ///%DFS tree. |
720 ///%DFS tree. |
721 ///\pre Either \ref run() or \ref init() |
721 ///\pre Either \ref run() or \ref init() |
722 ///must be called before using this function. |
722 ///must be called before using this function. |
723 const PredMap &predMap() const { return *_pred;} |
723 const PredMap &predMap() const { return *_pred;} |
724 |
724 |
725 ///Checks if a node is reachable from the root. |
725 ///Checks if a node is reachable from the root. |
726 |
726 |
727 ///Returns \c true if \c v is reachable from the root(s). |
727 ///Returns \c true if \c v is reachable from the root(s). |
728 ///\warning The source nodes are inditated as unreachable. |
728 ///\warning The source nodes are inditated as unreachable. |
729 ///\pre Either \ref run() or \ref start() |
729 ///\pre Either \ref run() or \ref start() |
730 ///must be called before using this function. |
730 ///must be called before using this function. |
731 /// |
731 /// |
732 bool reached(Node v) { return (*_reached)[v]; } |
732 bool reached(Node v) { return (*_reached)[v]; } |
733 |
733 |
734 ///@} |
734 ///@} |
735 }; |
735 }; |
736 |
736 |
737 ///Default traits class of Dfs function. |
737 ///Default traits class of Dfs function. |
738 |
738 |
739 ///Default traits class of Dfs function. |
739 ///Default traits class of Dfs function. |
740 ///\tparam GR Digraph type. |
740 ///\tparam GR Digraph type. |
741 template<class GR> |
741 template<class GR> |
742 struct DfsWizardDefaultTraits |
742 struct DfsWizardDefaultTraits |
743 { |
743 { |
744 ///The digraph type the algorithm runs on. |
744 ///The digraph type the algorithm runs on. |
745 typedef GR Digraph; |
745 typedef GR Digraph; |
746 ///\brief The type of the map that stores the last |
746 ///\brief The type of the map that stores the last |
747 ///arcs of the %DFS paths. |
747 ///arcs of the %DFS paths. |
748 /// |
748 /// |
749 ///The type of the map that stores the last |
749 ///The type of the map that stores the last |
750 ///arcs of the %DFS paths. |
750 ///arcs of the %DFS paths. |
751 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
751 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
752 /// |
752 /// |
753 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; |
753 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; |
754 ///Instantiates a PredMap. |
754 ///Instantiates a PredMap. |
755 |
755 |
756 ///This function instantiates a \ref PredMap. |
756 ///This function instantiates a \ref PredMap. |
757 ///\param g is the digraph, to which we would like to define the PredMap. |
757 ///\param g is the digraph, to which we would like to define the PredMap. |
758 ///\todo The digraph alone may be insufficient to initialize |
758 ///\todo The digraph alone may be insufficient to initialize |
759 #ifdef DOXYGEN |
759 #ifdef DOXYGEN |
760 static PredMap *createPredMap(const GR &g) |
760 static PredMap *createPredMap(const GR &g) |
761 #else |
761 #else |
762 static PredMap *createPredMap(const GR &) |
762 static PredMap *createPredMap(const GR &) |
763 #endif |
763 #endif |
764 { |
764 { |
765 return new PredMap(); |
765 return new PredMap(); |
766 } |
766 } |
767 |
767 |
768 ///The type of the map that indicates which nodes are processed. |
768 ///The type of the map that indicates which nodes are processed. |
769 |
769 |
770 ///The type of the map that indicates which nodes are processed. |
770 ///The type of the map that indicates which nodes are processed. |
771 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
771 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
772 ///\todo named parameter to set this type, function to read and write. |
772 ///\todo named parameter to set this type, function to read and write. |
773 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
773 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
774 ///Instantiates a ProcessedMap. |
774 ///Instantiates a ProcessedMap. |
775 |
775 |
776 ///This function instantiates a \ref ProcessedMap. |
776 ///This function instantiates a \ref ProcessedMap. |
777 ///\param g is the digraph, to which |
777 ///\param g is the digraph, to which |
778 ///we would like to define the \ref ProcessedMap |
778 ///we would like to define the \ref ProcessedMap |
779 #ifdef DOXYGEN |
779 #ifdef DOXYGEN |
780 static ProcessedMap *createProcessedMap(const GR &g) |
780 static ProcessedMap *createProcessedMap(const GR &g) |
781 #else |
781 #else |
783 #endif |
783 #endif |
784 { |
784 { |
785 return new ProcessedMap(); |
785 return new ProcessedMap(); |
786 } |
786 } |
787 ///The type of the map that indicates which nodes are reached. |
787 ///The type of the map that indicates which nodes are reached. |
788 |
788 |
789 ///The type of the map that indicates which nodes are reached. |
789 ///The type of the map that indicates which nodes are reached. |
790 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
790 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
791 ///\todo named parameter to set this type, function to read and write. |
791 ///\todo named parameter to set this type, function to read and write. |
792 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
792 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
793 ///Instantiates a ReachedMap. |
793 ///Instantiates a ReachedMap. |
794 |
794 |
795 ///This function instantiates a \ref ReachedMap. |
795 ///This function instantiates a \ref ReachedMap. |
796 ///\param G is the digraph, to which |
796 ///\param G is the digraph, to which |
797 ///we would like to define the \ref ReachedMap. |
797 ///we would like to define the \ref ReachedMap. |
798 static ReachedMap *createReachedMap(const GR &G) |
798 static ReachedMap *createReachedMap(const GR &G) |
799 { |
799 { |
800 return new ReachedMap(G); |
800 return new ReachedMap(G); |
801 } |
801 } |
802 ///The type of the map that stores the dists of the nodes. |
802 ///The type of the map that stores the dists of the nodes. |
803 |
803 |
804 ///The type of the map that stores the dists of the nodes. |
804 ///The type of the map that stores the dists of the nodes. |
805 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
805 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
806 /// |
806 /// |
807 typedef NullMap<typename Digraph::Node,int> DistMap; |
807 typedef NullMap<typename Digraph::Node,int> DistMap; |
808 ///Instantiates a DistMap. |
808 ///Instantiates a DistMap. |
809 |
809 |
810 ///This function instantiates a \ref DistMap. |
810 ///This function instantiates a \ref DistMap. |
811 ///\param g is the digraph, to which we would like to define the \ref DistMap |
811 ///\param g is the digraph, to which we would like to define the \ref DistMap |
812 #ifdef DOXYGEN |
812 #ifdef DOXYGEN |
813 static DistMap *createDistMap(const GR &g) |
813 static DistMap *createDistMap(const GR &g) |
814 #else |
814 #else |
815 static DistMap *createDistMap(const GR &) |
815 static DistMap *createDistMap(const GR &) |
816 #endif |
816 #endif |
817 { |
817 { |
818 return new DistMap(); |
818 return new DistMap(); |
819 } |
819 } |
820 }; |
820 }; |
821 |
821 |
822 /// Default traits used by \ref DfsWizard |
822 /// Default traits used by \ref DfsWizard |
823 |
823 |
824 /// To make it easier to use Dfs algorithm |
824 /// To make it easier to use Dfs algorithm |
825 ///we have created a wizard class. |
825 ///we have created a wizard class. |
826 /// This \ref DfsWizard class needs default traits, |
826 /// This \ref DfsWizard class needs default traits, |
846 void *_pred; |
846 void *_pred; |
847 ///Pointer to the map of distances. |
847 ///Pointer to the map of distances. |
848 void *_dist; |
848 void *_dist; |
849 ///Pointer to the source node. |
849 ///Pointer to the source node. |
850 Node _source; |
850 Node _source; |
851 |
851 |
852 public: |
852 public: |
853 /// Constructor. |
853 /// Constructor. |
854 |
854 |
855 /// This constructor does not require parameters, therefore it initiates |
855 /// This constructor does not require parameters, therefore it initiates |
856 /// all of the attributes to default values (0, INVALID). |
856 /// all of the attributes to default values (0, INVALID). |
857 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
857 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
858 _dist(0), _source(INVALID) {} |
858 _dist(0), _source(INVALID) {} |
859 |
859 |
860 /// Constructor. |
860 /// Constructor. |
861 |
861 |
862 /// This constructor requires some parameters, |
862 /// This constructor requires some parameters, |
863 /// listed in the parameters list. |
863 /// listed in the parameters list. |
864 /// Others are initiated to 0. |
864 /// Others are initiated to 0. |
865 /// \param g is the initial value of \ref _g |
865 /// \param g is the initial value of \ref _g |
866 /// \param s is the initial value of \ref _source |
866 /// \param s is the initial value of \ref _source |
867 DfsWizardBase(const GR &g, Node s=INVALID) : |
867 DfsWizardBase(const GR &g, Node s=INVALID) : |
868 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
868 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
869 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
869 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
870 |
870 |
871 }; |
871 }; |
872 |
872 |
873 /// A class to make the usage of the Dfs algorithm easier |
873 /// A class to make the usage of the Dfs algorithm easier |
874 |
874 |
875 /// This class is created to make it easier to use the Dfs algorithm. |
875 /// This class is created to make it easier to use the Dfs algorithm. |
876 /// It uses the functions and features of the plain \ref Dfs, |
876 /// It uses the functions and features of the plain \ref Dfs, |
877 /// but it is much simpler to use it. |
877 /// but it is much simpler to use it. |
932 DfsWizard(const TR &b) : TR(b) {} |
932 DfsWizard(const TR &b) : TR(b) {} |
933 |
933 |
934 ~DfsWizard() {} |
934 ~DfsWizard() {} |
935 |
935 |
936 ///Runs Dfs algorithm from a given node. |
936 ///Runs Dfs algorithm from a given node. |
937 |
937 |
938 ///Runs Dfs algorithm from a given node. |
938 ///Runs Dfs algorithm from a given node. |
939 ///The node can be given by the \ref source function. |
939 ///The node can be given by the \ref source function. |
940 void run() |
940 void run() |
941 { |
941 { |
942 if(Base::_source==INVALID) throw UninitializedParameter(); |
942 if(Base::_source==INVALID) throw UninitializedParameter(); |
943 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
943 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
944 if(Base::_reached) |
944 if(Base::_reached) |
945 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); |
945 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); |
946 if(Base::_processed) |
946 if(Base::_processed) |
947 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
947 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
948 if(Base::_pred) |
948 if(Base::_pred) |
949 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
949 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
950 if(Base::_dist) |
950 if(Base::_dist) |
951 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
951 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
952 alg.run(Base::_source); |
952 alg.run(Base::_source); |
953 } |
953 } |
954 |
954 |
955 ///Runs Dfs algorithm from the given node. |
955 ///Runs Dfs algorithm from the given node. |
966 struct DefPredMapBase : public Base { |
966 struct DefPredMapBase : public Base { |
967 typedef T PredMap; |
967 typedef T PredMap; |
968 static PredMap *createPredMap(const Digraph &) { return 0; }; |
968 static PredMap *createPredMap(const Digraph &) { return 0; }; |
969 DefPredMapBase(const TR &b) : TR(b) {} |
969 DefPredMapBase(const TR &b) : TR(b) {} |
970 }; |
970 }; |
971 |
971 |
972 ///\brief \ref named-templ-param "Named parameter" |
972 ///\brief \ref named-templ-param "Named parameter" |
973 ///function for setting PredMap type |
973 ///function for setting PredMap type |
974 /// |
974 /// |
975 /// \ref named-templ-param "Named parameter" |
975 /// \ref named-templ-param "Named parameter" |
976 ///function for setting PredMap type |
976 ///function for setting PredMap type |
977 /// |
977 /// |
978 template<class T> |
978 template<class T> |
979 DfsWizard<DefPredMapBase<T> > predMap(const T &t) |
979 DfsWizard<DefPredMapBase<T> > predMap(const T &t) |
980 { |
980 { |
981 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
981 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
982 return DfsWizard<DefPredMapBase<T> >(*this); |
982 return DfsWizard<DefPredMapBase<T> >(*this); |
983 } |
983 } |
984 |
984 |
985 |
985 |
986 template<class T> |
986 template<class T> |
987 struct DefReachedMapBase : public Base { |
987 struct DefReachedMapBase : public Base { |
988 typedef T ReachedMap; |
988 typedef T ReachedMap; |
989 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
989 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
990 DefReachedMapBase(const TR &b) : TR(b) {} |
990 DefReachedMapBase(const TR &b) : TR(b) {} |
991 }; |
991 }; |
992 |
992 |
993 ///\brief \ref named-templ-param "Named parameter" |
993 ///\brief \ref named-templ-param "Named parameter" |
994 ///function for setting ReachedMap |
994 ///function for setting ReachedMap |
995 /// |
995 /// |
996 /// \ref named-templ-param "Named parameter" |
996 /// \ref named-templ-param "Named parameter" |
997 ///function for setting ReachedMap |
997 ///function for setting ReachedMap |
998 /// |
998 /// |
999 template<class T> |
999 template<class T> |
1000 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1000 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1001 { |
1001 { |
1002 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1002 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1003 return DfsWizard<DefReachedMapBase<T> >(*this); |
1003 return DfsWizard<DefReachedMapBase<T> >(*this); |
1004 } |
1004 } |
1005 |
1005 |
1006 |
1006 |
1007 template<class T> |
1007 template<class T> |
1008 struct DefProcessedMapBase : public Base { |
1008 struct DefProcessedMapBase : public Base { |
1009 typedef T ProcessedMap; |
1009 typedef T ProcessedMap; |
1010 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1010 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1011 DefProcessedMapBase(const TR &b) : TR(b) {} |
1011 DefProcessedMapBase(const TR &b) : TR(b) {} |
1012 }; |
1012 }; |
1013 |
1013 |
1014 ///\brief \ref named-templ-param "Named parameter" |
1014 ///\brief \ref named-templ-param "Named parameter" |
1015 ///function for setting ProcessedMap |
1015 ///function for setting ProcessedMap |
1016 /// |
1016 /// |
1017 /// \ref named-templ-param "Named parameter" |
1017 /// \ref named-templ-param "Named parameter" |
1018 ///function for setting ProcessedMap |
1018 ///function for setting ProcessedMap |
1019 /// |
1019 /// |
1020 template<class T> |
1020 template<class T> |
1021 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1021 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1022 { |
1022 { |
1023 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1023 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1024 return DfsWizard<DefProcessedMapBase<T> >(*this); |
1024 return DfsWizard<DefProcessedMapBase<T> >(*this); |
1025 } |
1025 } |
1026 |
1026 |
1027 template<class T> |
1027 template<class T> |
1028 struct DefDistMapBase : public Base { |
1028 struct DefDistMapBase : public Base { |
1029 typedef T DistMap; |
1029 typedef T DistMap; |
1030 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1030 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1031 DefDistMapBase(const TR &b) : TR(b) {} |
1031 DefDistMapBase(const TR &b) : TR(b) {} |
1032 }; |
1032 }; |
1033 |
1033 |
1034 ///\brief \ref named-templ-param "Named parameter" |
1034 ///\brief \ref named-templ-param "Named parameter" |
1035 ///function for setting DistMap type |
1035 ///function for setting DistMap type |
1036 /// |
1036 /// |
1037 /// \ref named-templ-param "Named parameter" |
1037 /// \ref named-templ-param "Named parameter" |
1038 ///function for setting DistMap type |
1038 ///function for setting DistMap type |
1039 /// |
1039 /// |
1040 template<class T> |
1040 template<class T> |
1041 DfsWizard<DefDistMapBase<T> > distMap(const T &t) |
1041 DfsWizard<DefDistMapBase<T> > distMap(const T &t) |
1042 { |
1042 { |
1043 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1043 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1044 return DfsWizard<DefDistMapBase<T> >(*this); |
1044 return DfsWizard<DefDistMapBase<T> >(*this); |
1045 } |
1045 } |
1046 |
1046 |
1047 /// Sets the source node, from which the Dfs algorithm runs. |
1047 /// Sets the source node, from which the Dfs algorithm runs. |
1048 |
1048 |
1049 /// Sets the source node, from which the Dfs algorithm runs. |
1049 /// Sets the source node, from which the Dfs algorithm runs. |
1050 /// \param s is the source node. |
1050 /// \param s is the source node. |
1051 DfsWizard<TR> &source(Node s) |
1051 DfsWizard<TR> &source(Node s) |
1052 { |
1052 { |
1053 Base::_source=s; |
1053 Base::_source=s; |
1054 return *this; |
1054 return *this; |
1055 } |
1055 } |
1056 |
1056 |
1057 }; |
1057 }; |
1058 |
1058 |
1059 ///Function type interface for Dfs algorithm. |
1059 ///Function type interface for Dfs algorithm. |
1060 |
1060 |
1061 ///\ingroup search |
1061 ///\ingroup search |
1062 ///Function type interface for Dfs algorithm. |
1062 ///Function type interface for Dfs algorithm. |
1063 /// |
1063 /// |
1080 return DfsWizard<DfsWizardBase<GR> >(g,s); |
1080 return DfsWizard<DfsWizardBase<GR> >(g,s); |
1081 } |
1081 } |
1082 |
1082 |
1083 #ifdef DOXYGEN |
1083 #ifdef DOXYGEN |
1084 /// \brief Visitor class for dfs. |
1084 /// \brief Visitor class for dfs. |
1085 /// |
1085 /// |
1086 /// It gives a simple interface for a functional interface for dfs |
1086 /// It gives a simple interface for a functional interface for dfs |
1087 /// traversal. The traversal on a linear data structure. |
1087 /// traversal. The traversal on a linear data structure. |
1088 template <typename _Digraph> |
1088 template <typename _Digraph> |
1089 struct DfsVisitor { |
1089 struct DfsVisitor { |
1090 typedef _Digraph Digraph; |
1090 typedef _Digraph Digraph; |
1091 typedef typename Digraph::Arc Arc; |
1091 typedef typename Digraph::Arc Arc; |
1092 typedef typename Digraph::Node Node; |
1092 typedef typename Digraph::Node Node; |
1093 /// \brief Called when the arc reach a node. |
1093 /// \brief Called when the arc reach a node. |
1094 /// |
1094 /// |
1095 /// It is called when the dfs find an arc which target is not |
1095 /// It is called when the dfs find an arc which target is not |
1096 /// reached yet. |
1096 /// reached yet. |
1097 void discover(const Arc& arc) {} |
1097 void discover(const Arc& arc) {} |
1098 /// \brief Called when the node reached first time. |
1098 /// \brief Called when the node reached first time. |
1099 /// |
1099 /// |
1100 /// It is Called when the node reached first time. |
1100 /// It is Called when the node reached first time. |
1101 void reach(const Node& node) {} |
1101 void reach(const Node& node) {} |
1102 /// \brief Called when we step back on an arc. |
1102 /// \brief Called when we step back on an arc. |
1103 /// |
1103 /// |
1104 /// It is called when the dfs should step back on the arc. |
1104 /// It is called when the dfs should step back on the arc. |
1105 void backtrack(const Arc& arc) {} |
1105 void backtrack(const Arc& arc) {} |
1106 /// \brief Called when we step back from the node. |
1106 /// \brief Called when we step back from the node. |
1107 /// |
1107 /// |
1108 /// It is called when we step back from the node. |
1108 /// It is called when we step back from the node. |
1109 void leave(const Node& node) {} |
1109 void leave(const Node& node) {} |
1110 /// \brief Called when the arc examined but target of the arc |
1110 /// \brief Called when the arc examined but target of the arc |
1111 /// already discovered. |
1111 /// already discovered. |
1112 /// |
1112 /// |
1113 /// It called when the arc examined but the target of the arc |
1113 /// It called when the arc examined but the target of the arc |
1114 /// already discovered. |
1114 /// already discovered. |
1115 void examine(const Arc& arc) {} |
1115 void examine(const Arc& arc) {} |
1116 /// \brief Called for the source node of the dfs. |
1116 /// \brief Called for the source node of the dfs. |
1117 /// |
1117 /// |
1118 /// It is called for the source node of the dfs. |
1118 /// It is called for the source node of the dfs. |
1119 void start(const Node& node) {} |
1119 void start(const Node& node) {} |
1120 /// \brief Called when we leave the source node of the dfs. |
1120 /// \brief Called when we leave the source node of the dfs. |
1121 /// |
1121 /// |
1122 /// It is called when we leave the source node of the dfs. |
1122 /// It is called when we leave the source node of the dfs. |
1123 void stop(const Node& node) {} |
1123 void stop(const Node& node) {} |
1124 |
1124 |
1125 }; |
1125 }; |
1126 #else |
1126 #else |
1160 /// Default traits class of DfsVisit class. |
1160 /// Default traits class of DfsVisit class. |
1161 /// \tparam _Digraph Digraph type. |
1161 /// \tparam _Digraph Digraph type. |
1162 template<class _Digraph> |
1162 template<class _Digraph> |
1163 struct DfsVisitDefaultTraits { |
1163 struct DfsVisitDefaultTraits { |
1164 |
1164 |
1165 /// \brief The digraph type the algorithm runs on. |
1165 /// \brief The digraph type the algorithm runs on. |
1166 typedef _Digraph Digraph; |
1166 typedef _Digraph Digraph; |
1167 |
1167 |
1168 /// \brief The type of the map that indicates which nodes are reached. |
1168 /// \brief The type of the map that indicates which nodes are reached. |
1169 /// |
1169 /// |
1170 /// The type of the map that indicates which nodes are reached. |
1170 /// The type of the map that indicates which nodes are reached. |
1171 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1171 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1172 /// \todo named parameter to set this type, function to read and write. |
1172 /// \todo named parameter to set this type, function to read and write. |
1173 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1173 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1174 |
1174 |
1175 /// \brief Instantiates a ReachedMap. |
1175 /// \brief Instantiates a ReachedMap. |
1176 /// |
1176 /// |
1177 /// This function instantiates a \ref ReachedMap. |
1177 /// This function instantiates a \ref ReachedMap. |
1178 /// \param digraph is the digraph, to which |
1178 /// \param digraph is the digraph, to which |
1179 /// we would like to define the \ref ReachedMap. |
1179 /// we would like to define the \ref ReachedMap. |
1180 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1180 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1181 return new ReachedMap(digraph); |
1181 return new ReachedMap(digraph); |
1182 } |
1182 } |
1183 |
1183 |
1184 }; |
1184 }; |
1185 |
1185 |
1186 /// %DFS Visit algorithm class. |
1186 /// %DFS Visit algorithm class. |
1187 |
1187 |
1188 /// \ingroup search |
1188 /// \ingroup search |
1189 /// This class provides an efficient implementation of the %DFS algorithm |
1189 /// This class provides an efficient implementation of the %DFS algorithm |
1190 /// with visitor interface. |
1190 /// with visitor interface. |
1191 /// |
1191 /// |
1192 /// The %DfsVisit class provides an alternative interface to the Dfs |
1192 /// The %DfsVisit class provides an alternative interface to the Dfs |
1193 /// class. It works with callback mechanism, the DfsVisit object calls |
1193 /// class. It works with callback mechanism, the DfsVisit object calls |
1194 /// on every dfs event the \c Visitor class member functions. |
1194 /// on every dfs event the \c Visitor class member functions. |
1195 /// |
1195 /// |
1196 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is |
1196 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is |
1197 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it |
1197 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it |
1198 /// is only passed to \ref DfsDefaultTraits. |
1198 /// is only passed to \ref DfsDefaultTraits. |
1199 /// \tparam _Visitor The Visitor object for the algorithm. The |
1199 /// \tparam _Visitor The Visitor object for the algorithm. The |
1200 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which |
1200 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which |
1201 /// does not observe the Dfs events. If you want to observe the dfs |
1201 /// does not observe the Dfs events. If you want to observe the dfs |
1202 /// events you should implement your own Visitor class. |
1202 /// events you should implement your own Visitor class. |
1203 /// \tparam _Traits Traits class to set various data types used by the |
1203 /// \tparam _Traits Traits class to set various data types used by the |
1204 /// algorithm. The default traits class is |
1204 /// algorithm. The default traits class is |
1205 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". |
1205 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". |
1206 /// See \ref DfsVisitDefaultTraits for the documentation of |
1206 /// See \ref DfsVisitDefaultTraits for the documentation of |
1207 /// a Dfs visit traits class. |
1207 /// a Dfs visit traits class. |
1208 /// |
1208 /// |
1209 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso |
1209 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso |
1210 #ifdef DOXYGEN |
1210 #ifdef DOXYGEN |
1211 template <typename _Digraph, typename _Visitor, typename _Traits> |
1211 template <typename _Digraph, typename _Visitor, typename _Traits> |
1212 #else |
1212 #else |
1213 template <typename _Digraph = ListDigraph, |
1213 template <typename _Digraph = ListDigraph, |
1214 typename _Visitor = DfsVisitor<_Digraph>, |
1214 typename _Visitor = DfsVisitor<_Digraph>, |
1215 typename _Traits = DfsDefaultTraits<_Digraph> > |
1215 typename _Traits = DfsDefaultTraits<_Digraph> > |
1216 #endif |
1216 #endif |
1217 class DfsVisit { |
1217 class DfsVisit { |
1218 public: |
1218 public: |
1219 |
1219 |
1220 /// \brief \ref Exception for uninitialized parameters. |
1220 /// \brief \ref Exception for uninitialized parameters. |
1221 /// |
1221 /// |
1222 /// This error represents problems in the initialization |
1222 /// This error represents problems in the initialization |
1223 /// of the parameters of the algorithms. |
1223 /// of the parameters of the algorithms. |
1224 class UninitializedParameter : public lemon::UninitializedParameter { |
1224 class UninitializedParameter : public lemon::UninitializedParameter { |
1225 public: |
1225 public: |
1226 virtual const char* what() const throw() |
1226 virtual const char* what() const throw() |
1227 { |
1227 { |
1228 return "lemon::DfsVisit::UninitializedParameter"; |
1228 return "lemon::DfsVisit::UninitializedParameter"; |
1229 } |
1229 } |
1230 }; |
1230 }; |
1231 |
1231 |
1232 typedef _Traits Traits; |
1232 typedef _Traits Traits; |
1233 |
1233 |
1280 ///@{ |
1280 ///@{ |
1281 template <class T> |
1281 template <class T> |
1282 struct DefReachedMapTraits : public Traits { |
1282 struct DefReachedMapTraits : public Traits { |
1283 typedef T ReachedMap; |
1283 typedef T ReachedMap; |
1284 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1284 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1285 throw UninitializedParameter(); |
1285 throw UninitializedParameter(); |
1286 } |
1286 } |
1287 }; |
1287 }; |
1288 /// \brief \ref named-templ-param "Named parameter" for setting |
1288 /// \brief \ref named-templ-param "Named parameter" for setting |
1289 /// ReachedMap type |
1289 /// ReachedMap type |
1290 /// |
1290 /// |
1291 /// \ref named-templ-param "Named parameter" for setting ReachedMap type |
1291 /// \ref named-templ-param "Named parameter" for setting ReachedMap type |
1292 template <class T> |
1292 template <class T> |
1293 struct DefReachedMap : public DfsVisit< Digraph, Visitor, |
1293 struct DefReachedMap : public DfsVisit< Digraph, Visitor, |
1294 DefReachedMapTraits<T> > { |
1294 DefReachedMapTraits<T> > { |
1295 typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create; |
1295 typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create; |
1296 }; |
1296 }; |
1297 ///@} |
1297 ///@} |
1298 |
1298 |
1299 public: |
1299 public: |
1300 |
1300 |
1301 /// \brief Constructor. |
1301 /// \brief Constructor. |
1302 /// |
1302 /// |
1303 /// Constructor. |
1303 /// Constructor. |
1304 /// |
1304 /// |
1305 /// \param digraph the digraph the algorithm will run on. |
1305 /// \param digraph the digraph the algorithm will run on. |
1306 /// \param visitor The visitor of the algorithm. |
1306 /// \param visitor The visitor of the algorithm. |
1307 /// |
1307 /// |
1308 DfsVisit(const Digraph& digraph, Visitor& visitor) |
1308 DfsVisit(const Digraph& digraph, Visitor& visitor) |
1309 : _digraph(&digraph), _visitor(&visitor), |
1309 : _digraph(&digraph), _visitor(&visitor), |
1310 _reached(0), local_reached(false) {} |
1310 _reached(0), local_reached(false) {} |
1311 |
1311 |
1312 /// \brief Destructor. |
1312 /// \brief Destructor. |
1313 /// |
1313 /// |
1314 /// Destructor. |
1314 /// Destructor. |
1315 ~DfsVisit() { |
1315 ~DfsVisit() { |
1316 if(local_reached) delete _reached; |
1316 if(local_reached) delete _reached; |
1351 void init() { |
1351 void init() { |
1352 create_maps(); |
1352 create_maps(); |
1353 _stack.resize(countNodes(*_digraph)); |
1353 _stack.resize(countNodes(*_digraph)); |
1354 _stack_head = -1; |
1354 _stack_head = -1; |
1355 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { |
1355 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { |
1356 _reached->set(u, false); |
1356 _reached->set(u, false); |
1357 } |
1357 } |
1358 } |
1358 } |
1359 |
1359 |
1360 /// \brief Adds a new source node. |
1360 /// \brief Adds a new source node. |
1361 /// |
1361 /// |
1362 /// Adds a new source node to the set of nodes to be processed. |
1362 /// Adds a new source node to the set of nodes to be processed. |
1363 void addSource(Node s) { |
1363 void addSource(Node s) { |
1364 if(!(*_reached)[s]) { |
1364 if(!(*_reached)[s]) { |
1365 _reached->set(s,true); |
1365 _reached->set(s,true); |
1366 _visitor->start(s); |
1366 _visitor->start(s); |
1367 _visitor->reach(s); |
1367 _visitor->reach(s); |
1368 Arc e; |
1368 Arc e; |
1369 _digraph->firstOut(e, s); |
1369 _digraph->firstOut(e, s); |
1370 if (e != INVALID) { |
1370 if (e != INVALID) { |
1371 _stack[++_stack_head] = e; |
1371 _stack[++_stack_head] = e; |
1372 } else { |
1372 } else { |
1373 _visitor->leave(s); |
1373 _visitor->leave(s); |
1374 } |
1374 } |
1375 } |
1375 } |
1376 } |
1376 } |
1377 |
1377 |
1378 /// \brief Processes the next arc. |
1378 /// \brief Processes the next arc. |
1379 /// |
1379 /// |
1380 /// Processes the next arc. |
1380 /// Processes the next arc. |
1381 /// |
1381 /// |
1382 /// \return The processed arc. |
1382 /// \return The processed arc. |
1383 /// |
1383 /// |
1384 /// \pre The stack must not be empty! |
1384 /// \pre The stack must not be empty! |
1385 Arc processNextArc() { |
1385 Arc processNextArc() { |
1386 Arc e = _stack[_stack_head]; |
1386 Arc e = _stack[_stack_head]; |
1387 Node m = _digraph->target(e); |
1387 Node m = _digraph->target(e); |
1388 if(!(*_reached)[m]) { |
1388 if(!(*_reached)[m]) { |
1389 _visitor->discover(e); |
1389 _visitor->discover(e); |
1390 _visitor->reach(m); |
1390 _visitor->reach(m); |
1391 _reached->set(m, true); |
1391 _reached->set(m, true); |
1392 _digraph->firstOut(_stack[++_stack_head], m); |
1392 _digraph->firstOut(_stack[++_stack_head], m); |
1393 } else { |
1393 } else { |
1394 _visitor->examine(e); |
1394 _visitor->examine(e); |
1395 m = _digraph->source(e); |
1395 m = _digraph->source(e); |
1396 _digraph->nextOut(_stack[_stack_head]); |
1396 _digraph->nextOut(_stack[_stack_head]); |
1397 } |
1397 } |
1398 while (_stack_head>=0 && _stack[_stack_head] == INVALID) { |
1398 while (_stack_head>=0 && _stack[_stack_head] == INVALID) { |
1399 _visitor->leave(m); |
1399 _visitor->leave(m); |
1400 --_stack_head; |
1400 --_stack_head; |
1401 if (_stack_head >= 0) { |
1401 if (_stack_head >= 0) { |
1402 _visitor->backtrack(_stack[_stack_head]); |
1402 _visitor->backtrack(_stack[_stack_head]); |
1403 m = _digraph->source(_stack[_stack_head]); |
1403 m = _digraph->source(_stack[_stack_head]); |
1404 _digraph->nextOut(_stack[_stack_head]); |
1404 _digraph->nextOut(_stack[_stack_head]); |
1405 } else { |
1405 } else { |
1406 _visitor->stop(m); |
1406 _visitor->stop(m); |
1407 } |
1407 } |
1408 } |
1408 } |
1409 return e; |
1409 return e; |
1410 } |
1410 } |
1411 |
1411 |
1412 /// \brief Next arc to be processed. |
1412 /// \brief Next arc to be processed. |
1413 /// |
1413 /// |
1414 /// Next arc to be processed. |
1414 /// Next arc to be processed. |
1415 /// |
1415 /// |
1416 /// \return The next arc to be processed or INVALID if the stack is |
1416 /// \return The next arc to be processed or INVALID if the stack is |
1417 /// empty. |
1417 /// empty. |
1418 Arc nextArc() { |
1418 Arc nextArc() { |
1419 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; |
1419 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; |
1420 } |
1420 } |
1421 |
1421 |
1422 /// \brief Returns \c false if there are nodes |
1422 /// \brief Returns \c false if there are nodes |
1423 /// to be processed in the queue |
1423 /// to be processed in the queue |
1428 |
1428 |
1429 /// \brief Returns the number of the nodes to be processed. |
1429 /// \brief Returns the number of the nodes to be processed. |
1430 /// |
1430 /// |
1431 /// Returns the number of the nodes to be processed in the queue. |
1431 /// Returns the number of the nodes to be processed in the queue. |
1432 int queueSize() { return _stack_head + 1; } |
1432 int queueSize() { return _stack_head + 1; } |
1433 |
1433 |
1434 /// \brief Executes the algorithm. |
1434 /// \brief Executes the algorithm. |
1435 /// |
1435 /// |
1436 /// Executes the algorithm. |
1436 /// Executes the algorithm. |
1437 /// |
1437 /// |
1438 /// \pre init() must be called and at least one node should be added |
1438 /// \pre init() must be called and at least one node should be added |
1439 /// with addSource() before using this function. |
1439 /// with addSource() before using this function. |
1440 void start() { |
1440 void start() { |
1441 while ( !emptyQueue() ) processNextArc(); |
1441 while ( !emptyQueue() ) processNextArc(); |
1442 } |
1442 } |
1443 |
1443 |
1444 /// \brief Executes the algorithm until \c dest is reached. |
1444 /// \brief Executes the algorithm until \c dest is reached. |
1445 /// |
1445 /// |
1446 /// Executes the algorithm until \c dest is reached. |
1446 /// Executes the algorithm until \c dest is reached. |
1447 /// |
1447 /// |
1448 /// \pre init() must be called and at least one node should be added |
1448 /// \pre init() must be called and at least one node should be added |
1449 /// with addSource() before using this function. |
1449 /// with addSource() before using this function. |
1450 void start(Node dest) { |
1450 void start(Node dest) { |
1451 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) |
1451 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) |
1452 processNextArc(); |
1452 processNextArc(); |
1453 } |
1453 } |
1454 |
1454 |
1455 /// \brief Executes the algorithm until a condition is met. |
1455 /// \brief Executes the algorithm until a condition is met. |
1456 /// |
1456 /// |
1457 /// Executes the algorithm until a condition is met. |
1457 /// Executes the algorithm until a condition is met. |
1458 /// |
1458 /// |
1459 /// \pre init() must be called and at least one node should be added |
1459 /// \pre init() must be called and at least one node should be added |