19 #ifndef LEMON_DFS_H |
19 #ifndef LEMON_DFS_H |
20 #define LEMON_DFS_H |
20 #define LEMON_DFS_H |
21 |
21 |
22 ///\ingroup search |
22 ///\ingroup search |
23 ///\file |
23 ///\file |
24 ///\brief Dfs algorithm. |
24 ///\brief DFS algorithm. |
25 |
25 |
26 #include <lemon/list_graph.h> |
26 #include <lemon/list_graph.h> |
27 #include <lemon/graph_utils.h> |
27 #include <lemon/graph_utils.h> |
28 #include <lemon/bits/path_dump.h> |
28 #include <lemon/bits/path_dump.h> |
29 #include <lemon/bits/invalid.h> |
29 #include <lemon/bits/invalid.h> |
30 #include <lemon/error.h> |
30 #include <lemon/error.h> |
|
31 #include <lemon/assert.h> |
31 #include <lemon/maps.h> |
32 #include <lemon/maps.h> |
32 |
33 |
33 #include <lemon/concept_check.h> |
|
34 |
|
35 namespace lemon { |
34 namespace lemon { |
36 |
|
37 |
35 |
38 ///Default traits class of Dfs class. |
36 ///Default traits class of Dfs class. |
39 |
37 |
40 ///Default traits class of Dfs class. |
38 ///Default traits class of Dfs class. |
41 ///\tparam GR Digraph type. |
39 ///\tparam GR Digraph type. |
42 template<class GR> |
40 template<class GR> |
43 struct DfsDefaultTraits |
41 struct DfsDefaultTraits |
44 { |
42 { |
45 ///The digraph type the algorithm runs on. |
43 ///The type of the digraph the algorithm runs on. |
46 typedef GR Digraph; |
44 typedef GR Digraph; |
47 ///\brief The type of the map that stores the last |
45 |
|
46 ///\brief The type of the map that stores the predecessor |
48 ///arcs of the %DFS paths. |
47 ///arcs of the %DFS paths. |
49 /// |
48 /// |
50 ///The type of the map that stores the last |
49 ///The type of the map that stores the predecessor |
51 ///arcs of the %DFS paths. |
50 ///arcs of the %DFS paths. |
52 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
53 /// |
52 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
54 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
53 ///Instantiates a \ref PredMap. |
55 ///Instantiates a PredMap. |
|
56 |
54 |
57 ///This function instantiates a \ref PredMap. |
55 ///This function instantiates a \ref PredMap. |
58 ///\param G is the digraph, to which we would like to define the PredMap. |
56 ///\param g is the digraph, to which we would like to define the |
|
57 ///\ref PredMap. |
59 ///\todo The digraph alone may be insufficient to initialize |
58 ///\todo The digraph alone may be insufficient to initialize |
60 static PredMap *createPredMap(const GR &G) |
59 static PredMap *createPredMap(const Digraph &g) |
61 { |
60 { |
62 return new PredMap(G); |
61 return new PredMap(g); |
63 } |
62 } |
64 |
63 |
65 ///The type of the map that indicates which nodes are processed. |
64 ///The type of the map that indicates which nodes are processed. |
66 |
65 |
67 ///The type of the map that indicates which nodes are processed. |
66 ///The type of the map that indicates which nodes are processed. |
68 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
67 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
69 ///\todo named parameter to set this type, function to read and write. |
68 ///By default it is a NullMap. |
70 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
69 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
71 ///Instantiates a ProcessedMap. |
70 ///Instantiates a \ref ProcessedMap. |
72 |
71 |
73 ///This function instantiates a \ref ProcessedMap. |
72 ///This function instantiates a \ref ProcessedMap. |
74 ///\param g is the digraph, to which |
73 ///\param g is the digraph, to which |
75 ///we would like to define the \ref ProcessedMap |
74 ///we would like to define the \ref ProcessedMap |
76 #ifdef DOXYGEN |
75 #ifdef DOXYGEN |
77 static ProcessedMap *createProcessedMap(const GR &g) |
76 static ProcessedMap *createProcessedMap(const Digraph &g) |
78 #else |
77 #else |
79 static ProcessedMap *createProcessedMap(const GR &) |
78 static ProcessedMap *createProcessedMap(const Digraph &) |
80 #endif |
79 #endif |
81 { |
80 { |
82 return new ProcessedMap(); |
81 return new ProcessedMap(); |
83 } |
82 } |
|
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::ReadWriteMap "ReadWriteMap" concept. |
|
88 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
89 ///Instantiates a \ref ReachedMap. |
|
90 |
|
91 ///This function instantiates a \ref ReachedMap. |
|
92 ///\param g is the digraph, to which |
|
93 ///we would like to define the \ref ReachedMap. |
|
94 static ReachedMap *createReachedMap(const Digraph &g) |
|
95 { |
|
96 return new ReachedMap(g); |
|
97 } |
|
98 |
|
99 ///The type of the map that stores the distances of the nodes. |
|
100 |
|
101 ///The type of the map that stores the distances of the nodes. |
87 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
88 ///\todo named parameter to set this type, function to read and write. |
|
89 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
90 ///Instantiates a ReachedMap. |
|
91 |
|
92 ///This function instantiates a \ref ReachedMap. |
|
93 ///\param G is the digraph, to which |
|
94 ///we would like to define the \ref ReachedMap. |
|
95 static ReachedMap *createReachedMap(const GR &G) |
|
96 { |
|
97 return new ReachedMap(G); |
|
98 } |
|
99 ///The type of the map that stores the dists of the nodes. |
|
100 |
|
101 ///The type of the map that stores the dists of the nodes. |
|
102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
103 /// |
|
104 typedef typename Digraph::template NodeMap<int> DistMap; |
103 typedef typename Digraph::template NodeMap<int> DistMap; |
105 ///Instantiates a DistMap. |
104 ///Instantiates a \ref DistMap. |
106 |
105 |
107 ///This function instantiates a \ref DistMap. |
106 ///This function instantiates a \ref DistMap. |
108 ///\param G is the digraph, to which we would like to define |
107 ///\param g is the digraph, to which we would like to define the |
109 ///the \ref DistMap |
108 ///\ref DistMap. |
110 static DistMap *createDistMap(const GR &G) |
109 static DistMap *createDistMap(const Digraph &g) |
111 { |
110 { |
112 return new DistMap(G); |
111 return new DistMap(g); |
113 } |
112 } |
114 }; |
113 }; |
115 |
114 |
116 ///%DFS algorithm class. |
115 ///%DFS algorithm class. |
117 |
116 |
118 ///\ingroup search |
117 ///\ingroup search |
119 ///This class provides an efficient implementation of the %DFS algorithm. |
118 ///This class provides an efficient implementation of the %DFS algorithm. |
120 /// |
119 /// |
121 ///\tparam GR The digraph type the algorithm runs on. The default value is |
120 ///There is also a \ref dfs() "function type interface" for the DFS |
122 ///\ref ListDigraph. The value of GR is not used directly by Dfs, it |
121 ///algorithm, which is convenient in the simplier cases and it can be |
123 ///is only passed to \ref DfsDefaultTraits. |
122 ///used easier. |
|
123 /// |
|
124 ///\tparam GR The type of the digraph the algorithm runs on. |
|
125 ///The default value is \ref ListDigraph. The value of GR is not used |
|
126 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. |
124 ///\tparam TR Traits class to set various data types used by the algorithm. |
127 ///\tparam TR Traits class to set various data types used by the algorithm. |
125 ///The default traits class is |
128 ///The default traits class is |
126 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". |
129 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". |
127 ///See \ref DfsDefaultTraits for the documentation of |
130 ///See \ref DfsDefaultTraits for the documentation of |
128 ///a Dfs traits class. |
131 ///a Dfs traits class. |
133 template <typename GR=ListDigraph, |
136 template <typename GR=ListDigraph, |
134 typename TR=DfsDefaultTraits<GR> > |
137 typename TR=DfsDefaultTraits<GR> > |
135 #endif |
138 #endif |
136 class Dfs { |
139 class Dfs { |
137 public: |
140 public: |
138 /** |
141 ///\ref Exception for uninitialized parameters. |
139 * \brief \ref Exception for uninitialized parameters. |
142 |
140 * |
143 ///This error represents problems in the initialization of the |
141 * This error represents problems in the initialization |
144 ///parameters of the algorithm. |
142 * of the parameters of the algorithms. |
|
143 */ |
|
144 class UninitializedParameter : public lemon::UninitializedParameter { |
145 class UninitializedParameter : public lemon::UninitializedParameter { |
145 public: |
146 public: |
146 virtual const char* what() const throw() { |
147 virtual const char* what() const throw() { |
147 return "lemon::Dfs::UninitializedParameter"; |
148 return "lemon::Dfs::UninitializedParameter"; |
148 } |
149 } |
149 }; |
150 }; |
150 |
151 |
|
152 ///The type of the digraph the algorithm runs on. |
|
153 typedef typename TR::Digraph Digraph; |
|
154 |
|
155 ///\brief The type of the map that stores the predecessor arcs of the |
|
156 ///DFS paths. |
|
157 typedef typename TR::PredMap PredMap; |
|
158 ///The type of the map that stores the distances of the nodes. |
|
159 typedef typename TR::DistMap DistMap; |
|
160 ///The type of the map that indicates which nodes are reached. |
|
161 typedef typename TR::ReachedMap ReachedMap; |
|
162 ///The type of the map that indicates which nodes are processed. |
|
163 typedef typename TR::ProcessedMap ProcessedMap; |
|
164 ///The type of the paths. |
|
165 typedef PredMapPath<Digraph, PredMap> Path; |
|
166 |
|
167 ///The traits class. |
151 typedef TR Traits; |
168 typedef TR Traits; |
152 ///The type of the underlying digraph. |
169 |
153 typedef typename TR::Digraph Digraph; |
170 private: |
154 ///\e |
171 |
155 typedef typename Digraph::Node Node; |
172 typedef typename Digraph::Node Node; |
156 ///\e |
|
157 typedef typename Digraph::NodeIt NodeIt; |
173 typedef typename Digraph::NodeIt NodeIt; |
158 ///\e |
|
159 typedef typename Digraph::Arc Arc; |
174 typedef typename Digraph::Arc Arc; |
160 ///\e |
|
161 typedef typename Digraph::OutArcIt OutArcIt; |
175 typedef typename Digraph::OutArcIt OutArcIt; |
162 |
176 |
163 ///\brief The type of the map that stores the last |
177 //Pointer to the underlying digraph. |
164 ///arcs of the %DFS paths. |
|
165 typedef typename TR::PredMap PredMap; |
|
166 ///The type of the map indicating which nodes are reached. |
|
167 typedef typename TR::ReachedMap ReachedMap; |
|
168 ///The type of the map indicating which nodes are processed. |
|
169 typedef typename TR::ProcessedMap ProcessedMap; |
|
170 ///The type of the map that stores the dists of the nodes. |
|
171 typedef typename TR::DistMap DistMap; |
|
172 private: |
|
173 /// Pointer to the underlying digraph. |
|
174 const Digraph *G; |
178 const Digraph *G; |
175 ///Pointer to the map of predecessors arcs. |
179 //Pointer to the map of predecessor arcs. |
176 PredMap *_pred; |
180 PredMap *_pred; |
177 ///Indicates if \ref _pred is locally allocated (\c true) or not. |
181 //Indicates if _pred is locally allocated (true) or not. |
178 bool local_pred; |
182 bool local_pred; |
179 ///Pointer to the map of distances. |
183 //Pointer to the map of distances. |
180 DistMap *_dist; |
184 DistMap *_dist; |
181 ///Indicates if \ref _dist is locally allocated (\c true) or not. |
185 //Indicates if _dist is locally allocated (true) or not. |
182 bool local_dist; |
186 bool local_dist; |
183 ///Pointer to the map of reached status of the nodes. |
187 //Pointer to the map of reached status of the nodes. |
184 ReachedMap *_reached; |
188 ReachedMap *_reached; |
185 ///Indicates if \ref _reached is locally allocated (\c true) or not. |
189 //Indicates if _reached is locally allocated (true) or not. |
186 bool local_reached; |
190 bool local_reached; |
187 ///Pointer to the map of processed status of the nodes. |
191 //Pointer to the map of processed status of the nodes. |
188 ProcessedMap *_processed; |
192 ProcessedMap *_processed; |
189 ///Indicates if \ref _processed is locally allocated (\c true) or not. |
193 //Indicates if _processed is locally allocated (true) or not. |
190 bool local_processed; |
194 bool local_processed; |
191 |
195 |
192 std::vector<typename Digraph::OutArcIt> _stack; |
196 std::vector<typename Digraph::OutArcIt> _stack; |
193 int _stack_head; |
197 int _stack_head; |
194 |
198 |
195 ///Creates the maps if necessary. |
199 ///Creates the maps if necessary. |
196 |
|
197 ///\todo Better memory allocation (instead of new). |
200 ///\todo Better memory allocation (instead of new). |
198 void create_maps() |
201 void create_maps() |
199 { |
202 { |
200 if(!_pred) { |
203 if(!_pred) { |
201 local_pred = true; |
204 local_pred = true; |
496 ++_stack[_stack_head]; |
503 ++_stack[_stack_head]; |
497 } |
504 } |
498 } |
505 } |
499 return e; |
506 return e; |
500 } |
507 } |
|
508 |
501 ///Next arc to be processed. |
509 ///Next arc to be processed. |
502 |
510 |
503 ///Next arc to be processed. |
511 ///Next arc to be processed. |
504 /// |
512 /// |
505 ///\return The next arc to be processed or INVALID if the stack is |
513 ///\return The next arc to be processed or \c INVALID if the stack |
506 /// empty. |
514 ///is empty. |
507 OutArcIt nextArc() |
515 OutArcIt nextArc() const |
508 { |
516 { |
509 return _stack_head>=0?_stack[_stack_head]:INVALID; |
517 return _stack_head>=0?_stack[_stack_head]:INVALID; |
510 } |
518 } |
511 |
519 |
512 ///\brief Returns \c false if there are nodes |
520 ///\brief Returns \c false if there are nodes |
513 ///to be processed in the queue |
521 ///to be processed. |
514 /// |
522 /// |
515 ///Returns \c false if there are nodes |
523 ///Returns \c false if there are nodes |
516 ///to be processed in the queue |
524 ///to be processed in the queue (stack). |
517 bool emptyQueue() { return _stack_head<0; } |
525 bool emptyQueue() const { return _stack_head<0; } |
|
526 |
518 ///Returns the number of the nodes to be processed. |
527 ///Returns the number of the nodes to be processed. |
519 |
528 |
520 ///Returns the number of the nodes to be processed in the queue. |
529 ///Returns the number of the nodes to be processed in the queue (stack). |
521 int queueSize() { return _stack_head+1; } |
530 int queueSize() const { return _stack_head+1; } |
522 |
531 |
523 ///Executes the algorithm. |
532 ///Executes the algorithm. |
524 |
533 |
525 ///Executes the algorithm. |
534 ///Executes the algorithm. |
526 /// |
535 /// |
527 ///\pre init() must be called and at least one node should be added |
536 ///This method runs the %DFS algorithm from the root node |
528 ///with addSource() before using this function. |
537 ///in order to compute the DFS path to each node. |
529 /// |
538 /// |
530 ///This method runs the %DFS algorithm from the root node(s) |
539 /// The algorithm computes |
531 ///in order to |
540 ///- the %DFS tree, |
532 ///compute the |
541 ///- the distance of each node from the root in the %DFS tree. |
533 ///%DFS path to each node. The algorithm computes |
542 /// |
534 ///- The %DFS tree. |
543 ///\pre init() must be called and a root node should be |
535 ///- The distance of each node from the root(s) in the %DFS tree. |
544 ///added with addSource() before using this function. |
536 /// |
545 /// |
|
546 ///\note <tt>d.start()</tt> is just a shortcut of the following code. |
|
547 ///\code |
|
548 /// while ( !d.emptyQueue() ) { |
|
549 /// d.processNextArc(); |
|
550 /// } |
|
551 ///\endcode |
537 void start() |
552 void start() |
538 { |
553 { |
539 while ( !emptyQueue() ) processNextArc(); |
554 while ( !emptyQueue() ) processNextArc(); |
540 } |
555 } |
541 |
556 |
542 ///Executes the algorithm until \c dest is reached. |
557 ///Executes the algorithm until the given target node is reached. |
543 |
558 |
544 ///Executes the algorithm until \c dest is reached. |
559 ///Executes the algorithm until the given target node is reached. |
545 /// |
560 /// |
546 ///\pre init() must be called and at least one node should be added |
561 ///This method runs the %DFS algorithm from the root node |
547 ///with addSource() before using this function. |
562 ///in order to compute the DFS path to \c dest. |
548 /// |
563 /// |
549 ///This method runs the %DFS algorithm from the root node(s) |
564 ///The algorithm computes |
550 ///in order to |
565 ///- the %DFS path to \c dest, |
551 ///compute the |
566 ///- the distance of \c dest from the root in the %DFS tree. |
552 ///%DFS path to \c dest. The algorithm computes |
567 /// |
553 ///- The %DFS path to \c dest. |
568 ///\pre init() must be called and a root node should be |
554 ///- The distance of \c dest from the root(s) in the %DFS tree. |
569 ///added with addSource() before using this function. |
555 /// |
|
556 void start(Node dest) |
570 void start(Node dest) |
557 { |
571 { |
558 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) |
572 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) |
559 processNextArc(); |
573 processNextArc(); |
560 } |
574 } |
561 |
575 |
562 ///Executes the algorithm until a condition is met. |
576 ///Executes the algorithm until a condition is met. |
563 |
577 |
564 ///Executes the algorithm until a condition is met. |
578 ///Executes the algorithm until a condition is met. |
565 /// |
579 /// |
566 ///\pre init() must be called and at least one node should be added |
580 ///This method runs the %DFS algorithm from the root node |
567 ///with addSource() before using this function. |
581 ///until an arc \c a with <tt>am[a]</tt> true is found. |
568 /// |
582 /// |
569 ///\param em must be a bool (or convertible) arc map. The algorithm |
583 ///\param am A \c bool (or convertible) arc map. The algorithm |
570 ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true. |
584 ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true. |
571 /// |
585 /// |
572 ///\return The reached arc \c e with <tt>em[e]</tt> true or |
586 ///\return The reached arc \c a with <tt>am[a]</tt> true or |
573 ///\c INVALID if no such arc was found. |
587 ///\c INVALID if no such arc was found. |
574 /// |
588 /// |
575 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, |
589 ///\pre init() must be called and a root node should be |
|
590 ///added with addSource() before using this function. |
|
591 /// |
|
592 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, |
576 ///not a node map. |
593 ///not a node map. |
577 template<class EM> |
594 template<class ArcBoolMap> |
578 Arc start(const EM &em) |
595 Arc start(const ArcBoolMap &am) |
579 { |
596 { |
580 while ( !emptyQueue() && !em[_stack[_stack_head]] ) |
597 while ( !emptyQueue() && !am[_stack[_stack_head]] ) |
581 processNextArc(); |
598 processNextArc(); |
582 return emptyQueue() ? INVALID : _stack[_stack_head]; |
599 return emptyQueue() ? INVALID : _stack[_stack_head]; |
583 } |
600 } |
584 |
601 |
585 ///Runs %DFS algorithm to visit all nodes in the digraph. |
602 ///Runs the algorithm from the given node. |
586 |
603 |
587 ///This method runs the %DFS algorithm in order to |
604 ///This method runs the %DFS algorithm from node \c s |
588 ///compute the |
605 ///in order to compute the DFS path to each node. |
589 ///%DFS path to each node. The algorithm computes |
606 /// |
590 ///- The %DFS tree. |
607 ///The algorithm computes |
591 ///- The distance of each node from the root in the %DFS tree. |
608 ///- the %DFS tree, |
592 /// |
609 ///- the distance of each node from the root in the %DFS tree. |
593 ///\note d.run() is just a shortcut of the following code. |
610 /// |
|
611 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code. |
594 ///\code |
612 ///\code |
595 /// d.init(); |
613 /// d.init(); |
596 /// for (NodeIt it(digraph); it != INVALID; ++it) { |
614 /// d.addSource(s); |
597 /// if (!d.reached(it)) { |
615 /// d.start(); |
598 /// d.addSource(it); |
616 ///\endcode |
|
617 void run(Node s) { |
|
618 init(); |
|
619 addSource(s); |
|
620 start(); |
|
621 } |
|
622 |
|
623 ///Finds the %DFS path between \c s and \c t. |
|
624 |
|
625 ///This method runs the %DFS algorithm from node \c s |
|
626 ///in order to compute the DFS path to \c t. |
|
627 /// |
|
628 ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path, |
|
629 ///if \c t is reachable form \c s, \c 0 otherwise. |
|
630 /// |
|
631 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is |
|
632 ///just a shortcut of the following code. |
|
633 ///\code |
|
634 /// d.init(); |
|
635 /// d.addSource(s); |
|
636 /// d.start(t); |
|
637 ///\endcode |
|
638 int run(Node s,Node t) { |
|
639 init(); |
|
640 addSource(s); |
|
641 start(t); |
|
642 return reached(t)?_stack_head+1:0; |
|
643 } |
|
644 |
|
645 ///Runs the algorithm to visit all nodes in the digraph. |
|
646 |
|
647 ///This method runs the %DFS algorithm in order to compute the |
|
648 ///%DFS path to each node. |
|
649 /// |
|
650 ///The algorithm computes |
|
651 ///- the %DFS tree, |
|
652 ///- the distance of each node from the root in the %DFS tree. |
|
653 /// |
|
654 ///\note <tt>d.run()</tt> is just a shortcut of the following code. |
|
655 ///\code |
|
656 /// d.init(); |
|
657 /// for (NodeIt n(digraph); n != INVALID; ++n) { |
|
658 /// if (!d.reached(n)) { |
|
659 /// d.addSource(n); |
599 /// d.start(); |
660 /// d.start(); |
600 /// } |
661 /// } |
601 /// } |
662 /// } |
602 ///\endcode |
663 ///\endcode |
603 void run() { |
664 void run() { |
608 start(); |
669 start(); |
609 } |
670 } |
610 } |
671 } |
611 } |
672 } |
612 |
673 |
613 ///Runs %DFS algorithm from node \c s. |
|
614 |
|
615 ///This method runs the %DFS algorithm from a root node \c s |
|
616 ///in order to |
|
617 ///compute the |
|
618 ///%DFS path to each node. The algorithm computes |
|
619 ///- The %DFS tree. |
|
620 ///- The distance of each node from the root in the %DFS tree. |
|
621 /// |
|
622 ///\note d.run(s) is just a shortcut of the following code. |
|
623 ///\code |
|
624 /// d.init(); |
|
625 /// d.addSource(s); |
|
626 /// d.start(); |
|
627 ///\endcode |
|
628 void run(Node s) { |
|
629 init(); |
|
630 addSource(s); |
|
631 start(); |
|
632 } |
|
633 |
|
634 ///Finds the %DFS path between \c s and \c t. |
|
635 |
|
636 ///Finds the %DFS path between \c s and \c t. |
|
637 /// |
|
638 ///\return The length of the %DFS s---t path if there exists one, |
|
639 ///0 otherwise. |
|
640 ///\note Apart from the return value, d.run(s,t) is |
|
641 ///just a shortcut of the following code. |
|
642 ///\code |
|
643 /// d.init(); |
|
644 /// d.addSource(s); |
|
645 /// d.start(t); |
|
646 ///\endcode |
|
647 int run(Node s,Node t) { |
|
648 init(); |
|
649 addSource(s); |
|
650 start(t); |
|
651 return reached(t)?_stack_head+1:0; |
|
652 } |
|
653 |
|
654 ///@} |
674 ///@} |
655 |
675 |
656 ///\name Query Functions |
676 ///\name Query Functions |
657 ///The result of the %DFS algorithm can be obtained using these |
677 ///The result of the %DFS algorithm can be obtained using these |
658 ///functions.\n |
678 ///functions.\n |
659 ///Before the use of these functions, |
679 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start() |
660 ///either run() or start() must be called. |
680 ///"start()" must be called before using them. |
661 |
681 |
662 ///@{ |
682 ///@{ |
663 |
683 |
664 typedef PredMapPath<Digraph, PredMap> Path; |
684 ///The DFS path to a node. |
665 |
685 |
666 ///Gives back the shortest path. |
686 ///Returns the DFS path to a node. |
667 |
687 /// |
668 ///Gives back the shortest path. |
688 ///\warning \c t should be reachable from the root. |
669 ///\pre The \c t should be reachable from the source. |
689 /// |
670 Path path(Node t) |
690 ///\pre Either \ref run() or \ref start() must be called before |
671 { |
691 ///using this function. |
672 return Path(*G, *_pred, t); |
692 Path path(Node t) const { return Path(*G, *_pred, t); } |
673 } |
693 |
674 |
694 ///The distance of a node from the root. |
675 ///The distance of a node from the root(s). |
695 |
676 |
696 ///Returns the distance of a node from the root. |
677 ///Returns the distance of a node from the root(s). |
697 /// |
678 ///\pre \ref run() must be called before using this function. |
698 ///\warning If node \c v is not reachable from the root, then |
679 ///\warning If node \c v is unreachable from the root(s) then the return |
699 ///the return value of this function is undefined. |
680 ///value of this funcion is undefined. |
700 /// |
|
701 ///\pre Either \ref run() or \ref start() must be called before |
|
702 ///using this function. |
681 int dist(Node v) const { return (*_dist)[v]; } |
703 int dist(Node v) const { return (*_dist)[v]; } |
682 |
704 |
683 ///Returns the 'previous arc' of the %DFS tree. |
705 ///Returns the 'previous arc' of the %DFS tree for a node. |
684 |
706 |
685 ///For a node \c v it returns the 'previous arc' |
707 ///This function returns the 'previous arc' of the %DFS tree for the |
686 ///of the %DFS path, |
708 ///node \c v, i.e. it returns the last arc of a %DFS path from the |
687 ///i.e. it returns the last arc of a %DFS path from the root(s) to \c |
709 ///root to \c v. It is \c INVALID |
688 ///v. It is \ref INVALID |
710 ///if \c v is not reachable from the root(s) or if \c v is a root. |
689 ///if \c v is unreachable from the root(s) or \c v is a root. The |
711 /// |
690 ///%DFS tree used here is equal to the %DFS tree used in |
712 ///The %DFS tree used here is equal to the %DFS tree used in |
691 ///\ref predNode(). |
713 ///\ref predNode(). |
|
714 /// |
692 ///\pre Either \ref run() or \ref start() must be called before using |
715 ///\pre Either \ref run() or \ref start() must be called before using |
693 ///this function. |
716 ///this function. |
694 Arc predArc(Node v) const { return (*_pred)[v];} |
717 Arc predArc(Node v) const { return (*_pred)[v];} |
695 |
718 |
696 ///Returns the 'previous node' of the %DFS tree. |
719 ///Returns the 'previous node' of the %DFS tree. |
697 |
720 |
698 ///For a node \c v it returns the 'previous node' |
721 ///This function returns the 'previous node' of the %DFS |
699 ///of the %DFS tree, |
722 ///tree for the node \c v, i.e. it returns the last but one node |
700 ///i.e. it returns the last but one node from a %DFS path from the |
723 ///from a %DFS path from the root to \c v. It is \c INVALID |
701 ///root(s) to \c v. |
724 ///if \c v is not reachable from the root(s) or if \c v is a root. |
702 ///It is INVALID if \c v is unreachable from the root(s) or |
725 /// |
703 ///if \c v itself a root. |
726 ///The %DFS tree used here is equal to the %DFS tree used in |
704 ///The %DFS tree used here is equal to the %DFS |
727 ///\ref predArc(). |
705 ///tree used in \ref predArc(). |
728 /// |
706 ///\pre Either \ref run() or \ref start() must be called before |
729 ///\pre Either \ref run() or \ref start() must be called before |
707 ///using this function. |
730 ///using this function. |
708 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
731 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
709 G->source((*_pred)[v]); } |
732 G->source((*_pred)[v]); } |
710 |
733 |
711 ///Returns a reference to the NodeMap of distances. |
734 ///\brief Returns a const reference to the node map that stores the |
712 |
735 ///distances of the nodes. |
713 ///Returns a reference to the NodeMap of distances. |
736 /// |
714 ///\pre Either \ref run() or \ref init() must |
737 ///Returns a const reference to the node map that stores the |
715 ///be called before using this function. |
738 ///distances of the nodes calculated by the algorithm. |
|
739 /// |
|
740 ///\pre Either \ref run() or \ref init() |
|
741 ///must be called before using this function. |
716 const DistMap &distMap() const { return *_dist;} |
742 const DistMap &distMap() const { return *_dist;} |
717 |
743 |
718 ///Returns a reference to the %DFS arc-tree map. |
744 ///\brief Returns a const reference to the node map that stores the |
719 |
745 ///predecessor arcs. |
720 ///Returns a reference to the NodeMap of the arcs of the |
746 /// |
721 ///%DFS tree. |
747 ///Returns a const reference to the node map that stores the predecessor |
|
748 ///arcs, which form the DFS tree. |
|
749 /// |
722 ///\pre Either \ref run() or \ref init() |
750 ///\pre Either \ref run() or \ref init() |
723 ///must be called before using this function. |
751 ///must be called before using this function. |
724 const PredMap &predMap() const { return *_pred;} |
752 const PredMap &predMap() const { return *_pred;} |
725 |
753 |
726 ///Checks if a node is reachable from the root. |
754 ///Checks if a node is reachable from the root(s). |
727 |
755 |
728 ///Returns \c true if \c v is reachable from the root(s). |
756 ///Returns \c true if \c v is reachable from the root(s). |
729 ///\warning The source nodes are inditated as unreachable. |
|
730 ///\pre Either \ref run() or \ref start() |
757 ///\pre Either \ref run() or \ref start() |
731 ///must be called before using this function. |
758 ///must be called before using this function. |
732 /// |
759 bool reached(Node v) const { return (*_reached)[v]; } |
733 bool reached(Node v) { return (*_reached)[v]; } |
|
734 |
760 |
735 ///@} |
761 ///@} |
736 }; |
762 }; |
737 |
763 |
738 ///Default traits class of Dfs function. |
764 ///Default traits class of dfs() function. |
739 |
765 |
740 ///Default traits class of Dfs function. |
766 ///Default traits class of dfs() function. |
741 ///\tparam GR Digraph type. |
767 ///\tparam GR Digraph type. |
742 template<class GR> |
768 template<class GR> |
743 struct DfsWizardDefaultTraits |
769 struct DfsWizardDefaultTraits |
744 { |
770 { |
745 ///The digraph type the algorithm runs on. |
771 ///The type of the digraph the algorithm runs on. |
746 typedef GR Digraph; |
772 typedef GR Digraph; |
747 ///\brief The type of the map that stores the last |
773 |
|
774 ///\brief The type of the map that stores the predecessor |
748 ///arcs of the %DFS paths. |
775 ///arcs of the %DFS paths. |
749 /// |
776 /// |
750 ///The type of the map that stores the last |
777 ///The type of the map that stores the predecessor |
751 ///arcs of the %DFS paths. |
778 ///arcs of the %DFS paths. |
752 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
779 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
753 /// |
780 /// |
754 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; |
781 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; |
755 ///Instantiates a PredMap. |
782 ///Instantiates a \ref PredMap. |
756 |
783 |
757 ///This function instantiates a \ref PredMap. |
784 ///This function instantiates a \ref PredMap. |
758 ///\param g is the digraph, to which we would like to define the PredMap. |
785 ///\param g is the digraph, to which we would like to define the |
|
786 ///\ref PredMap. |
759 ///\todo The digraph alone may be insufficient to initialize |
787 ///\todo The digraph alone may be insufficient to initialize |
760 #ifdef DOXYGEN |
788 #ifdef DOXYGEN |
761 static PredMap *createPredMap(const GR &g) |
789 static PredMap *createPredMap(const Digraph &g) |
762 #else |
790 #else |
763 static PredMap *createPredMap(const GR &) |
791 static PredMap *createPredMap(const Digraph &) |
764 #endif |
792 #endif |
765 { |
793 { |
766 return new PredMap(); |
794 return new PredMap(); |
767 } |
795 } |
768 |
796 |
769 ///The type of the map that indicates which nodes are processed. |
797 ///The type of the map that indicates which nodes are processed. |
770 |
798 |
771 ///The type of the map that indicates which nodes are processed. |
799 ///The type of the map that indicates which nodes are processed. |
772 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
800 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
773 ///\todo named parameter to set this type, function to read and write. |
|
774 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
801 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
775 ///Instantiates a ProcessedMap. |
802 ///Instantiates a \ref ProcessedMap. |
776 |
803 |
777 ///This function instantiates a \ref ProcessedMap. |
804 ///This function instantiates a \ref ProcessedMap. |
778 ///\param g is the digraph, to which |
805 ///\param g is the digraph, to which |
779 ///we would like to define the \ref ProcessedMap |
806 ///we would like to define the \ref ProcessedMap. |
780 #ifdef DOXYGEN |
807 #ifdef DOXYGEN |
781 static ProcessedMap *createProcessedMap(const GR &g) |
808 static ProcessedMap *createProcessedMap(const Digraph &g) |
782 #else |
809 #else |
783 static ProcessedMap *createProcessedMap(const GR &) |
810 static ProcessedMap *createProcessedMap(const Digraph &) |
784 #endif |
811 #endif |
785 { |
812 { |
786 return new ProcessedMap(); |
813 return new ProcessedMap(); |
787 } |
814 } |
|
815 |
788 ///The type of the map that indicates which nodes are reached. |
816 ///The type of the map that indicates which nodes are reached. |
789 |
817 |
790 ///The type of the map that indicates which nodes are reached. |
818 ///The type of the map that indicates which nodes are reached. |
|
819 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
820 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
821 ///Instantiates a \ref ReachedMap. |
|
822 |
|
823 ///This function instantiates a \ref ReachedMap. |
|
824 ///\param g is the digraph, to which |
|
825 ///we would like to define the \ref ReachedMap. |
|
826 static ReachedMap *createReachedMap(const Digraph &g) |
|
827 { |
|
828 return new ReachedMap(g); |
|
829 } |
|
830 |
|
831 ///The type of the map that stores the distances of the nodes. |
|
832 |
|
833 ///The type of the map that stores the distances of the nodes. |
791 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
834 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
792 ///\todo named parameter to set this type, function to read and write. |
|
793 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
794 ///Instantiates a ReachedMap. |
|
795 |
|
796 ///This function instantiates a \ref ReachedMap. |
|
797 ///\param G is the digraph, to which |
|
798 ///we would like to define the \ref ReachedMap. |
|
799 static ReachedMap *createReachedMap(const GR &G) |
|
800 { |
|
801 return new ReachedMap(G); |
|
802 } |
|
803 ///The type of the map that stores the dists of the nodes. |
|
804 |
|
805 ///The type of the map that stores the dists of the nodes. |
|
806 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
807 /// |
835 /// |
808 typedef NullMap<typename Digraph::Node,int> DistMap; |
836 typedef NullMap<typename Digraph::Node,int> DistMap; |
809 ///Instantiates a DistMap. |
837 ///Instantiates a \ref DistMap. |
810 |
838 |
811 ///This function instantiates a \ref DistMap. |
839 ///This function instantiates a \ref DistMap. |
812 ///\param g is the digraph, to which we would like to define |
840 ///\param g is the digraph, to which we would like to define |
813 ///the \ref DistMap |
841 ///the \ref DistMap |
814 #ifdef DOXYGEN |
842 #ifdef DOXYGEN |
815 static DistMap *createDistMap(const GR &g) |
843 static DistMap *createDistMap(const Digraph &g) |
816 #else |
844 #else |
817 static DistMap *createDistMap(const GR &) |
845 static DistMap *createDistMap(const Digraph &) |
818 #endif |
846 #endif |
819 { |
847 { |
820 return new DistMap(); |
848 return new DistMap(); |
821 } |
849 } |
822 }; |
850 }; |
823 |
851 |
824 /// Default traits used by \ref DfsWizard |
852 /// Default traits class used by \ref DfsWizard |
825 |
853 |
826 /// To make it easier to use Dfs algorithm |
854 /// To make it easier to use Dfs algorithm |
827 ///we have created a wizard class. |
855 /// we have created a wizard class. |
828 /// This \ref DfsWizard class needs default traits, |
856 /// This \ref DfsWizard class needs default traits, |
829 ///as well as the \ref Dfs class. |
857 /// as well as the \ref Dfs class. |
830 /// The \ref DfsWizardBase is a class to be the default traits of the |
858 /// The \ref DfsWizardBase is a class to be the default traits of the |
831 /// \ref DfsWizard class. |
859 /// \ref DfsWizard class. |
832 template<class GR> |
860 template<class GR> |
833 class DfsWizardBase : public DfsWizardDefaultTraits<GR> |
861 class DfsWizardBase : public DfsWizardDefaultTraits<GR> |
834 { |
862 { |
835 |
863 |
836 typedef DfsWizardDefaultTraits<GR> Base; |
864 typedef DfsWizardDefaultTraits<GR> Base; |
837 protected: |
865 protected: |
838 /// Type of the nodes in the digraph. |
866 //The type of the nodes in the digraph. |
839 typedef typename Base::Digraph::Node Node; |
867 typedef typename Base::Digraph::Node Node; |
840 |
868 |
841 /// Pointer to the underlying digraph. |
869 //Pointer to the digraph the algorithm runs on. |
842 void *_g; |
870 void *_g; |
843 ///Pointer to the map of reached nodes. |
871 //Pointer to the map of reached nodes. |
844 void *_reached; |
872 void *_reached; |
845 ///Pointer to the map of processed nodes. |
873 //Pointer to the map of processed nodes. |
846 void *_processed; |
874 void *_processed; |
847 ///Pointer to the map of predecessors arcs. |
875 //Pointer to the map of predecessors arcs. |
848 void *_pred; |
876 void *_pred; |
849 ///Pointer to the map of distances. |
877 //Pointer to the map of distances. |
850 void *_dist; |
878 void *_dist; |
851 ///Pointer to the source node. |
879 //Pointer to the source node. |
852 Node _source; |
880 Node _source; |
853 |
881 |
854 public: |
882 public: |
855 /// Constructor. |
883 /// Constructor. |
856 |
884 |
857 /// This constructor does not require parameters, therefore it initiates |
885 /// This constructor does not require parameters, therefore it initiates |
858 /// all of the attributes to default values (0, INVALID). |
886 /// all of the attributes to default values (0, INVALID). |
859 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
887 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
860 _dist(0), _source(INVALID) {} |
888 _dist(0), _source(INVALID) {} |
861 |
889 |
862 /// Constructor. |
890 /// Constructor. |
863 |
891 |
864 /// This constructor requires some parameters, |
892 /// This constructor requires some parameters, |
865 /// listed in the parameters list. |
893 /// listed in the parameters list. |
866 /// Others are initiated to 0. |
894 /// Others are initiated to 0. |
867 /// \param g is the initial value of \ref _g |
895 /// \param g The digraph the algorithm runs on. |
868 /// \param s is the initial value of \ref _source |
896 /// \param s The source node. |
869 DfsWizardBase(const GR &g, Node s=INVALID) : |
897 DfsWizardBase(const GR &g, Node s=INVALID) : |
870 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
898 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
871 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
899 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
872 |
900 |
873 }; |
901 }; |
874 |
902 |
875 /// A class to make the usage of the Dfs algorithm easier |
903 /// Auxiliary class for the function type interface of DFS algorithm. |
876 |
904 |
877 /// This class is created to make it easier to use the Dfs algorithm. |
905 /// This auxiliary class is created to implement the function type |
878 /// It uses the functions and features of the plain \ref Dfs, |
906 /// interface of \ref Dfs algorithm. It uses the functions and features |
879 /// but it is much simpler to use it. |
907 /// of the plain \ref Dfs, but it is much simpler to use it. |
|
908 /// It should only be used through the \ref dfs() function, which makes |
|
909 /// it easier to use the algorithm. |
880 /// |
910 /// |
881 /// Simplicity means that the way to change the types defined |
911 /// Simplicity means that the way to change the types defined |
882 /// in the traits class is based on functions that returns the new class |
912 /// in the traits class is based on functions that returns the new class |
883 /// and not on templatable built-in classes. |
913 /// and not on templatable built-in classes. |
884 /// When using the plain \ref Dfs |
914 /// When using the plain \ref Dfs |
885 /// the new class with the modified type comes from |
915 /// the new class with the modified type comes from |
886 /// the original class by using the :: |
916 /// the original class by using the :: |
887 /// operator. In the case of \ref DfsWizard only |
917 /// operator. In the case of \ref DfsWizard only |
888 /// a function have to be called and it will |
918 /// a function have to be called, and it will |
889 /// return the needed class. |
919 /// return the needed class. |
890 /// |
920 /// |
891 /// It does not have own \ref run method. When its \ref run method is called |
921 /// It does not have own \ref run() method. When its \ref run() method |
892 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run |
922 /// is called, it initiates a plain \ref Dfs object, and calls the |
893 /// method of it. |
923 /// \ref Dfs::run() method of it. |
894 template<class TR> |
924 template<class TR> |
895 class DfsWizard : public TR |
925 class DfsWizard : public TR |
896 { |
926 { |
897 typedef TR Base; |
927 typedef TR Base; |
898 |
928 |
899 ///The type of the underlying digraph. |
929 ///The type of the digraph the algorithm runs on. |
900 typedef typename TR::Digraph Digraph; |
930 typedef typename TR::Digraph Digraph; |
901 //\e |
931 |
902 typedef typename Digraph::Node Node; |
932 typedef typename Digraph::Node Node; |
903 //\e |
|
904 typedef typename Digraph::NodeIt NodeIt; |
933 typedef typename Digraph::NodeIt NodeIt; |
905 //\e |
|
906 typedef typename Digraph::Arc Arc; |
934 typedef typename Digraph::Arc Arc; |
907 //\e |
|
908 typedef typename Digraph::OutArcIt OutArcIt; |
935 typedef typename Digraph::OutArcIt OutArcIt; |
909 |
936 |
910 ///\brief The type of the map that stores |
937 ///\brief The type of the map that stores the predecessor |
911 ///the reached nodes |
938 ///arcs of the shortest paths. |
|
939 typedef typename TR::PredMap PredMap; |
|
940 ///\brief The type of the map that stores the distances of the nodes. |
|
941 typedef typename TR::DistMap DistMap; |
|
942 ///\brief The type of the map that indicates which nodes are reached. |
912 typedef typename TR::ReachedMap ReachedMap; |
943 typedef typename TR::ReachedMap ReachedMap; |
913 ///\brief The type of the map that stores |
944 ///\brief The type of the map that indicates which nodes are processed. |
914 ///the processed nodes |
|
915 typedef typename TR::ProcessedMap ProcessedMap; |
945 typedef typename TR::ProcessedMap ProcessedMap; |
916 ///\brief The type of the map that stores the last |
|
917 ///arcs of the %DFS paths. |
|
918 typedef typename TR::PredMap PredMap; |
|
919 ///The type of the map that stores the distances of the nodes. |
|
920 typedef typename TR::DistMap DistMap; |
|
921 |
946 |
922 public: |
947 public: |
|
948 |
923 /// Constructor. |
949 /// Constructor. |
924 DfsWizard() : TR() {} |
950 DfsWizard() : TR() {} |
925 |
951 |
926 /// Constructor that requires parameters. |
952 /// Constructor that requires parameters. |
927 |
953 |
952 if(Base::_dist) |
978 if(Base::_dist) |
953 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
979 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
954 alg.run(Base::_source); |
980 alg.run(Base::_source); |
955 } |
981 } |
956 |
982 |
957 ///Runs Dfs algorithm from the given node. |
983 ///Runs DFS algorithm from the given node. |
958 |
984 |
959 ///Runs Dfs algorithm from the given node. |
985 ///Runs DFS algorithm from the given node. |
960 ///\param s is the given source. |
986 ///\param s is the given source. |
961 void run(Node s) |
987 void run(Node s) |
962 { |
988 { |
963 Base::_source=s; |
989 Base::_source=s; |
964 run(); |
990 run(); |
|
991 } |
|
992 |
|
993 /// Sets the source node, from which the Dfs algorithm runs. |
|
994 |
|
995 /// Sets the source node, from which the Dfs algorithm runs. |
|
996 /// \param s is the source node. |
|
997 DfsWizard<TR> &source(Node s) |
|
998 { |
|
999 Base::_source=s; |
|
1000 return *this; |
965 } |
1001 } |
966 |
1002 |
967 template<class T> |
1003 template<class T> |
968 struct DefPredMapBase : public Base { |
1004 struct DefPredMapBase : public Base { |
969 typedef T PredMap; |
1005 typedef T PredMap; |
970 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1006 static PredMap *createPredMap(const Digraph &) { return 0; }; |
971 DefPredMapBase(const TR &b) : TR(b) {} |
1007 DefPredMapBase(const TR &b) : TR(b) {} |
972 }; |
1008 }; |
973 |
|
974 ///\brief \ref named-templ-param "Named parameter" |
1009 ///\brief \ref named-templ-param "Named parameter" |
975 ///function for setting PredMap type |
1010 ///for setting \ref PredMap object. |
976 /// |
1011 /// |
977 /// \ref named-templ-param "Named parameter" |
1012 ///\ref named-templ-param "Named parameter" |
978 ///function for setting PredMap type |
1013 ///for setting \ref PredMap object. |
979 /// |
|
980 template<class T> |
1014 template<class T> |
981 DfsWizard<DefPredMapBase<T> > predMap(const T &t) |
1015 DfsWizard<DefPredMapBase<T> > predMap(const T &t) |
982 { |
1016 { |
983 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1017 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
984 return DfsWizard<DefPredMapBase<T> >(*this); |
1018 return DfsWizard<DefPredMapBase<T> >(*this); |
985 } |
1019 } |
986 |
|
987 |
1020 |
988 template<class T> |
1021 template<class T> |
989 struct DefReachedMapBase : public Base { |
1022 struct DefReachedMapBase : public Base { |
990 typedef T ReachedMap; |
1023 typedef T ReachedMap; |
991 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1024 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
992 DefReachedMapBase(const TR &b) : TR(b) {} |
1025 DefReachedMapBase(const TR &b) : TR(b) {} |
993 }; |
1026 }; |
994 |
|
995 ///\brief \ref named-templ-param "Named parameter" |
1027 ///\brief \ref named-templ-param "Named parameter" |
996 ///function for setting ReachedMap |
1028 ///for setting \ref ReachedMap object. |
997 /// |
1029 /// |
998 /// \ref named-templ-param "Named parameter" |
1030 /// \ref named-templ-param "Named parameter" |
999 ///function for setting ReachedMap |
1031 ///for setting \ref ReachedMap object. |
1000 /// |
|
1001 template<class T> |
1032 template<class T> |
1002 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1033 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1003 { |
1034 { |
1004 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1035 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1005 return DfsWizard<DefReachedMapBase<T> >(*this); |
1036 return DfsWizard<DefReachedMapBase<T> >(*this); |
1006 } |
1037 } |
1007 |
|
1008 |
1038 |
1009 template<class T> |
1039 template<class T> |
1010 struct DefProcessedMapBase : public Base { |
1040 struct DefProcessedMapBase : public Base { |
1011 typedef T ProcessedMap; |
1041 typedef T ProcessedMap; |
1012 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1042 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1013 DefProcessedMapBase(const TR &b) : TR(b) {} |
1043 DefProcessedMapBase(const TR &b) : TR(b) {} |
1014 }; |
1044 }; |
1015 |
|
1016 ///\brief \ref named-templ-param "Named parameter" |
1045 ///\brief \ref named-templ-param "Named parameter" |
1017 ///function for setting ProcessedMap |
1046 ///for setting \ref ProcessedMap object. |
1018 /// |
1047 /// |
1019 /// \ref named-templ-param "Named parameter" |
1048 /// \ref named-templ-param "Named parameter" |
1020 ///function for setting ProcessedMap |
1049 ///for setting \ref ProcessedMap object. |
1021 /// |
|
1022 template<class T> |
1050 template<class T> |
1023 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1051 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1024 { |
1052 { |
1025 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1053 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1026 return DfsWizard<DefProcessedMapBase<T> >(*this); |
1054 return DfsWizard<DefProcessedMapBase<T> >(*this); |
1081 { |
1097 { |
1082 return DfsWizard<DfsWizardBase<GR> >(g,s); |
1098 return DfsWizard<DfsWizardBase<GR> >(g,s); |
1083 } |
1099 } |
1084 |
1100 |
1085 #ifdef DOXYGEN |
1101 #ifdef DOXYGEN |
1086 /// \brief Visitor class for dfs. |
1102 /// \brief Visitor class for DFS. |
1087 /// |
1103 /// |
1088 /// It gives a simple interface for a functional interface for dfs |
1104 /// This class defines the interface of the DfsVisit events, and |
1089 /// traversal. The traversal on a linear data structure. |
1105 /// it could be the base of a real visitor class. |
1090 template <typename _Digraph> |
1106 template <typename _Digraph> |
1091 struct DfsVisitor { |
1107 struct DfsVisitor { |
1092 typedef _Digraph Digraph; |
1108 typedef _Digraph Digraph; |
1093 typedef typename Digraph::Arc Arc; |
1109 typedef typename Digraph::Arc Arc; |
1094 typedef typename Digraph::Node Node; |
1110 typedef typename Digraph::Node Node; |
1095 /// \brief Called when the arc reach a node. |
1111 /// \brief Called for the source node of the DFS. |
1096 /// |
1112 /// |
1097 /// It is called when the dfs find an arc which target is not |
1113 /// This function is called for the source node of the DFS. |
1098 /// reached yet. |
1114 void start(const Node& node) {} |
|
1115 /// \brief Called when the source node is leaved. |
|
1116 /// |
|
1117 /// This function is called when the source node is leaved. |
|
1118 void stop(const Node& node) {} |
|
1119 /// \brief Called when a node is reached first time. |
|
1120 /// |
|
1121 /// This function is called when a node is reached first time. |
|
1122 void reach(const Node& node) {} |
|
1123 /// \brief Called when an arc reaches a new node. |
|
1124 /// |
|
1125 /// This function is called when the DFS finds an arc whose target node |
|
1126 /// is not reached yet. |
1099 void discover(const Arc& arc) {} |
1127 void discover(const Arc& arc) {} |
1100 /// \brief Called when the node reached first time. |
1128 /// \brief Called when an arc is examined but its target node is |
1101 /// |
|
1102 /// It is Called when the node reached first time. |
|
1103 void reach(const Node& node) {} |
|
1104 /// \brief Called when we step back on an arc. |
|
1105 /// |
|
1106 /// It is called when the dfs should step back on the arc. |
|
1107 void backtrack(const Arc& arc) {} |
|
1108 /// \brief Called when we step back from the node. |
|
1109 /// |
|
1110 /// It is called when we step back from the node. |
|
1111 void leave(const Node& node) {} |
|
1112 /// \brief Called when the arc examined but target of the arc |
|
1113 /// already discovered. |
1129 /// already discovered. |
1114 /// |
1130 /// |
1115 /// It called when the arc examined but the target of the arc |
1131 /// This function is called when an arc is examined but its target node is |
1116 /// already discovered. |
1132 /// already discovered. |
1117 void examine(const Arc& arc) {} |
1133 void examine(const Arc& arc) {} |
1118 /// \brief Called for the source node of the dfs. |
1134 /// \brief Called when the DFS steps back from a node. |
1119 /// |
1135 /// |
1120 /// It is called for the source node of the dfs. |
1136 /// This function is called when the DFS steps back from a node. |
1121 void start(const Node& node) {} |
1137 void leave(const Node& node) {} |
1122 /// \brief Called when we leave the source node of the dfs. |
1138 /// \brief Called when the DFS steps back on an arc. |
1123 /// |
1139 /// |
1124 /// It is called when we leave the source node of the dfs. |
1140 /// This function is called when the DFS steps back on an arc. |
1125 void stop(const Node& node) {} |
1141 void backtrack(const Arc& arc) {} |
1126 |
|
1127 }; |
1142 }; |
1128 #else |
1143 #else |
1129 template <typename _Digraph> |
1144 template <typename _Digraph> |
1130 struct DfsVisitor { |
1145 struct DfsVisitor { |
1131 typedef _Digraph Digraph; |
1146 typedef _Digraph Digraph; |
1132 typedef typename Digraph::Arc Arc; |
1147 typedef typename Digraph::Arc Arc; |
1133 typedef typename Digraph::Node Node; |
1148 typedef typename Digraph::Node Node; |
1134 void discover(const Arc&) {} |
|
1135 void reach(const Node&) {} |
|
1136 void backtrack(const Arc&) {} |
|
1137 void leave(const Node&) {} |
|
1138 void examine(const Arc&) {} |
|
1139 void start(const Node&) {} |
1149 void start(const Node&) {} |
1140 void stop(const Node&) {} |
1150 void stop(const Node&) {} |
|
1151 void reach(const Node&) {} |
|
1152 void discover(const Arc&) {} |
|
1153 void examine(const Arc&) {} |
|
1154 void leave(const Node&) {} |
|
1155 void backtrack(const Arc&) {} |
1141 |
1156 |
1142 template <typename _Visitor> |
1157 template <typename _Visitor> |
1143 struct Constraints { |
1158 struct Constraints { |
1144 void constraints() { |
1159 void constraints() { |
1145 Arc arc; |
1160 Arc arc; |
1146 Node node; |
1161 Node node; |
1147 visitor.discover(arc); |
|
1148 visitor.reach(node); |
|
1149 visitor.backtrack(arc); |
|
1150 visitor.leave(node); |
|
1151 visitor.examine(arc); |
|
1152 visitor.start(node); |
1162 visitor.start(node); |
1153 visitor.stop(arc); |
1163 visitor.stop(arc); |
|
1164 visitor.reach(node); |
|
1165 visitor.discover(arc); |
|
1166 visitor.examine(arc); |
|
1167 visitor.leave(node); |
|
1168 visitor.backtrack(arc); |
1154 } |
1169 } |
1155 _Visitor& visitor; |
1170 _Visitor& visitor; |
1156 }; |
1171 }; |
1157 }; |
1172 }; |
1158 #endif |
1173 #endif |
1159 |
1174 |
1160 /// \brief Default traits class of DfsVisit class. |
1175 /// \brief Default traits class of DfsVisit class. |
1161 /// |
1176 /// |
1162 /// Default traits class of DfsVisit class. |
1177 /// Default traits class of DfsVisit class. |
1163 /// \tparam _Digraph Digraph type. |
1178 /// \tparam _Digraph The type of the digraph the algorithm runs on. |
1164 template<class _Digraph> |
1179 template<class _Digraph> |
1165 struct DfsVisitDefaultTraits { |
1180 struct DfsVisitDefaultTraits { |
1166 |
1181 |
1167 /// \brief The digraph type the algorithm runs on. |
1182 /// \brief The type of the digraph the algorithm runs on. |
1168 typedef _Digraph Digraph; |
1183 typedef _Digraph Digraph; |
1169 |
1184 |
1170 /// \brief The type of the map that indicates which nodes are reached. |
1185 /// \brief The type of the map that indicates which nodes are reached. |
1171 /// |
1186 /// |
1172 /// The type of the map that indicates which nodes are reached. |
1187 /// The type of the map that indicates which nodes are reached. |
1173 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1188 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
1174 /// \todo named parameter to set this type, function to read and write. |
|
1175 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1189 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1176 |
1190 |
1177 /// \brief Instantiates a ReachedMap. |
1191 /// \brief Instantiates a \ref ReachedMap. |
1178 /// |
1192 /// |
1179 /// This function instantiates a \ref ReachedMap. |
1193 /// This function instantiates a \ref ReachedMap. |
1180 /// \param digraph is the digraph, to which |
1194 /// \param digraph is the digraph, to which |
1181 /// we would like to define the \ref ReachedMap. |
1195 /// we would like to define the \ref ReachedMap. |
1182 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1196 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1183 return new ReachedMap(digraph); |
1197 return new ReachedMap(digraph); |
1184 } |
1198 } |
1185 |
1199 |
1186 }; |
1200 }; |
1187 |
1201 |
1188 /// %DFS Visit algorithm class. |
|
1189 |
|
1190 /// \ingroup search |
1202 /// \ingroup search |
|
1203 /// |
|
1204 /// \brief %DFS algorithm class with visitor interface. |
|
1205 /// |
1191 /// This class provides an efficient implementation of the %DFS algorithm |
1206 /// This class provides an efficient implementation of the %DFS algorithm |
1192 /// with visitor interface. |
1207 /// with visitor interface. |
1193 /// |
1208 /// |
1194 /// The %DfsVisit class provides an alternative interface to the Dfs |
1209 /// The %DfsVisit class provides an alternative interface to the Dfs |
1195 /// class. It works with callback mechanism, the DfsVisit object calls |
1210 /// class. It works with callback mechanism, the DfsVisit object calls |
1196 /// on every dfs event the \c Visitor class member functions. |
1211 /// the member functions of the \c Visitor class on every DFS event. |
1197 /// |
1212 /// |
1198 /// \tparam _Digraph The digraph type the algorithm runs on. |
1213 /// \tparam _Digraph The type of the digraph the algorithm runs on. |
1199 /// The default value is |
1214 /// The default value is |
1200 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it |
1215 /// \ref ListDigraph. The value of _Digraph is not used directly by |
1201 /// is only passed to \ref DfsDefaultTraits. |
1216 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits. |
1202 /// \tparam _Visitor The Visitor object for the algorithm. The |
1217 /// \tparam _Visitor The Visitor type that is used by the algorithm. |
1203 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which |
1218 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which |
1204 /// does not observe the Dfs events. If you want to observe the dfs |
1219 /// does not observe the DFS events. If you want to observe the DFS |
1205 /// events you should implement your own Visitor class. |
1220 /// events, you should implement your own visitor class. |
1206 /// \tparam _Traits Traits class to set various data types used by the |
1221 /// \tparam _Traits Traits class to set various data types used by the |
1207 /// algorithm. The default traits class is |
1222 /// algorithm. The default traits class is |
1208 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". |
1223 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". |
1209 /// See \ref DfsVisitDefaultTraits for the documentation of |
1224 /// See \ref DfsVisitDefaultTraits for the documentation of |
1210 /// a Dfs visit traits class. |
1225 /// a DFS visit traits class. |
1211 /// |
|
1212 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso |
|
1213 #ifdef DOXYGEN |
1226 #ifdef DOXYGEN |
1214 template <typename _Digraph, typename _Visitor, typename _Traits> |
1227 template <typename _Digraph, typename _Visitor, typename _Traits> |
1215 #else |
1228 #else |
1216 template <typename _Digraph = ListDigraph, |
1229 template <typename _Digraph = ListDigraph, |
1217 typename _Visitor = DfsVisitor<_Digraph>, |
1230 typename _Visitor = DfsVisitor<_Digraph>, |
1416 /// |
1438 /// |
1417 /// Next arc to be processed. |
1439 /// Next arc to be processed. |
1418 /// |
1440 /// |
1419 /// \return The next arc to be processed or INVALID if the stack is |
1441 /// \return The next arc to be processed or INVALID if the stack is |
1420 /// empty. |
1442 /// empty. |
1421 Arc nextArc() { |
1443 Arc nextArc() const { |
1422 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; |
1444 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; |
1423 } |
1445 } |
1424 |
1446 |
1425 /// \brief Returns \c false if there are nodes |
1447 /// \brief Returns \c false if there are nodes |
1426 /// to be processed in the queue |
1448 /// to be processed. |
1427 /// |
1449 /// |
1428 /// Returns \c false if there are nodes |
1450 /// Returns \c false if there are nodes |
1429 /// to be processed in the queue |
1451 /// to be processed in the queue (stack). |
1430 bool emptyQueue() { return _stack_head < 0; } |
1452 bool emptyQueue() const { return _stack_head < 0; } |
1431 |
1453 |
1432 /// \brief Returns the number of the nodes to be processed. |
1454 /// \brief Returns the number of the nodes to be processed. |
1433 /// |
1455 /// |
1434 /// Returns the number of the nodes to be processed in the queue. |
1456 /// Returns the number of the nodes to be processed in the queue (stack). |
1435 int queueSize() { return _stack_head + 1; } |
1457 int queueSize() const { return _stack_head + 1; } |
1436 |
1458 |
1437 /// \brief Executes the algorithm. |
1459 /// \brief Executes the algorithm. |
1438 /// |
1460 /// |
1439 /// Executes the algorithm. |
1461 /// Executes the algorithm. |
1440 /// |
1462 /// |
1441 /// \pre init() must be called and at least one node should be added |
1463 /// This method runs the %DFS algorithm from the root node |
1442 /// with addSource() before using this function. |
1464 /// in order to compute the %DFS path to each node. |
|
1465 /// |
|
1466 /// The algorithm computes |
|
1467 /// - the %DFS tree, |
|
1468 /// - the distance of each node from the root in the %DFS tree. |
|
1469 /// |
|
1470 /// \pre init() must be called and a root node should be |
|
1471 /// added with addSource() before using this function. |
|
1472 /// |
|
1473 /// \note <tt>d.start()</tt> is just a shortcut of the following code. |
|
1474 /// \code |
|
1475 /// while ( !d.emptyQueue() ) { |
|
1476 /// d.processNextArc(); |
|
1477 /// } |
|
1478 /// \endcode |
1443 void start() { |
1479 void start() { |
1444 while ( !emptyQueue() ) processNextArc(); |
1480 while ( !emptyQueue() ) processNextArc(); |
1445 } |
1481 } |
1446 |
1482 |
1447 /// \brief Executes the algorithm until \c dest is reached. |
1483 /// \brief Executes the algorithm until the given target node is reached. |
1448 /// |
1484 /// |
1449 /// Executes the algorithm until \c dest is reached. |
1485 /// Executes the algorithm until the given target node is reached. |
1450 /// |
1486 /// |
1451 /// \pre init() must be called and at least one node should be added |
1487 /// This method runs the %DFS algorithm from the root node |
|
1488 /// in order to compute the DFS path to \c dest. |
|
1489 /// |
|
1490 /// The algorithm computes |
|
1491 /// - the %DFS path to \c dest, |
|
1492 /// - the distance of \c dest from the root in the %DFS tree. |
|
1493 /// |
|
1494 /// \pre init() must be called and a root node should be added |
1452 /// with addSource() before using this function. |
1495 /// with addSource() before using this function. |
1453 void start(Node dest) { |
1496 void start(Node dest) { |
1454 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) |
1497 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) |
1455 processNextArc(); |
1498 processNextArc(); |
1456 } |
1499 } |
1457 |
1500 |
1458 /// \brief Executes the algorithm until a condition is met. |
1501 /// \brief Executes the algorithm until a condition is met. |
1459 /// |
1502 /// |
1460 /// Executes the algorithm until a condition is met. |
1503 /// Executes the algorithm until a condition is met. |
1461 /// |
1504 /// |
1462 /// \pre init() must be called and at least one node should be added |
1505 /// This method runs the %DFS algorithm from the root node |
|
1506 /// until an arc \c a with <tt>am[a]</tt> true is found. |
|
1507 /// |
|
1508 /// \param am A \c bool (or convertible) arc map. The algorithm |
|
1509 /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true. |
|
1510 /// |
|
1511 /// \return The reached arc \c a with <tt>am[a]</tt> true or |
|
1512 /// \c INVALID if no such arc was found. |
|
1513 /// |
|
1514 /// \pre init() must be called and a root node should be added |
1463 /// with addSource() before using this function. |
1515 /// with addSource() before using this function. |
1464 /// |
1516 /// |
1465 /// \param em must be a bool (or convertible) arc map. The algorithm |
1517 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, |
1466 /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true. |
|
1467 /// |
|
1468 ///\return The reached arc \c e with <tt>em[e]</tt> true or |
|
1469 ///\c INVALID if no such arc was found. |
|
1470 /// |
|
1471 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, |
|
1472 /// not a node map. |
1518 /// not a node map. |
1473 template <typename EM> |
1519 template <typename AM> |
1474 Arc start(const EM &em) { |
1520 Arc start(const AM &am) { |
1475 while ( !emptyQueue() && !em[_stack[_stack_head]] ) |
1521 while ( !emptyQueue() && !am[_stack[_stack_head]] ) |
1476 processNextArc(); |
1522 processNextArc(); |
1477 return emptyQueue() ? INVALID : _stack[_stack_head]; |
1523 return emptyQueue() ? INVALID : _stack[_stack_head]; |
1478 } |
1524 } |
1479 |
1525 |
1480 /// \brief Runs %DFSVisit algorithm from node \c s. |
1526 /// \brief Runs the algorithm from the given node. |
1481 /// |
1527 /// |
1482 /// This method runs the %DFS algorithm from a root node \c s. |
1528 /// This method runs the %DFS algorithm from node \c s. |
1483 /// \note d.run(s) is just a shortcut of the following code. |
1529 /// in order to compute the DFS path to each node. |
|
1530 /// |
|
1531 /// The algorithm computes |
|
1532 /// - the %DFS tree, |
|
1533 /// - the distance of each node from the root in the %DFS tree. |
|
1534 /// |
|
1535 /// \note <tt>d.run(s)</tt> is just a shortcut of the following code. |
1484 ///\code |
1536 ///\code |
1485 /// d.init(); |
1537 /// d.init(); |
1486 /// d.addSource(s); |
1538 /// d.addSource(s); |
1487 /// d.start(); |
1539 /// d.start(); |
1488 ///\endcode |
1540 ///\endcode |