changeset 1751 | a2a454f1232d |
parent 1710 | f531c16dd923 |
child 1761 | 896464fe9fbb |
14:68a55869c13c | 15:9acaaad3a762 |
---|---|
25 #include <lemon/graph_utils.h> |
25 #include <lemon/graph_utils.h> |
26 #include <lemon/invalid.h> |
26 #include <lemon/invalid.h> |
27 #include <lemon/error.h> |
27 #include <lemon/error.h> |
28 #include <lemon/maps.h> |
28 #include <lemon/maps.h> |
29 |
29 |
30 #include <lemon/concept_check.h> |
|
31 |
|
30 namespace lemon { |
32 namespace lemon { |
31 |
|
32 |
33 |
33 |
34 |
34 ///Default traits class of Dfs class. |
35 ///Default traits class of Dfs class. |
35 |
36 |
36 ///Default traits class of Dfs class. |
37 ///Default traits class of Dfs class. |
121 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". |
122 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". |
122 ///See \ref DfsDefaultTraits for the documentation of |
123 ///See \ref DfsDefaultTraits for the documentation of |
123 ///a Dfs traits class. |
124 ///a Dfs traits class. |
124 /// |
125 /// |
125 ///\author Jacint Szabo and Alpar Juttner |
126 ///\author Jacint Szabo and Alpar Juttner |
126 ///\todo A compare object would be nice. |
|
127 |
|
128 #ifdef DOXYGEN |
127 #ifdef DOXYGEN |
129 template <typename GR, |
128 template <typename GR, |
130 typename TR> |
129 typename TR> |
131 #else |
130 #else |
132 template <typename GR=ListGraph, |
131 template <typename GR=ListGraph, |
273 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
272 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
274 |
273 |
275 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
274 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
276 /// |
275 /// |
277 template <class T> |
276 template <class T> |
278 struct DefReachedMap { |
277 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > { |
279 typedef Dfs< Graph, DefReachedMapTraits<T> > Create; |
278 typedef Dfs< Graph, DefReachedMapTraits<T> > Create; |
280 }; |
279 }; |
281 |
280 |
282 template <class T> |
281 template <class T> |
283 struct DefProcessedMapTraits : public Traits { |
282 struct DefProcessedMapTraits : public Traits { |
324 ///\param _G the graph the algorithm will run on. |
323 ///\param _G the graph the algorithm will run on. |
325 /// |
324 /// |
326 Dfs(const Graph& _G) : |
325 Dfs(const Graph& _G) : |
327 G(&_G), |
326 G(&_G), |
328 _pred(NULL), local_pred(false), |
327 _pred(NULL), local_pred(false), |
329 // _predNode(NULL), local_predNode(false), |
|
330 _dist(NULL), local_dist(false), |
328 _dist(NULL), local_dist(false), |
331 _reached(NULL), local_reached(false), |
329 _reached(NULL), local_reached(false), |
332 _processed(NULL), local_processed(false) |
330 _processed(NULL), local_processed(false) |
333 { } |
331 { } |
334 |
332 |
335 ///Destructor. |
333 ///Destructor. |
336 ~Dfs() |
334 ~Dfs() |
337 { |
335 { |
338 if(local_pred) delete _pred; |
336 if(local_pred) delete _pred; |
339 // if(local_predNode) delete _predNode; |
|
340 if(local_dist) delete _dist; |
337 if(local_dist) delete _dist; |
341 if(local_reached) delete _reached; |
338 if(local_reached) delete _reached; |
342 if(local_processed) delete _processed; |
339 if(local_processed) delete _processed; |
343 } |
340 } |
344 |
341 |
356 local_pred=false; |
353 local_pred=false; |
357 } |
354 } |
358 _pred = &m; |
355 _pred = &m; |
359 return *this; |
356 return *this; |
360 } |
357 } |
361 |
|
362 // ///Sets the map storing the predecessor nodes. |
|
363 |
|
364 // ///Sets the map storing the predecessor nodes. |
|
365 // ///If you don't use this function before calling \ref run(), |
|
366 // ///it will allocate one. The destuctor deallocates this |
|
367 // ///automatically allocated map, of course. |
|
368 // ///\return <tt> (*this) </tt> |
|
369 // Dfs &predNodeMap(PredNodeMap &m) |
|
370 // { |
|
371 // if(local_predNode) { |
|
372 // delete _predNode; |
|
373 // local_predNode=false; |
|
374 // } |
|
375 // _predNode = &m; |
|
376 // return *this; |
|
377 // } |
|
378 |
358 |
379 ///Sets the map storing the distances calculated by the algorithm. |
359 ///Sets the map storing the distances calculated by the algorithm. |
380 |
360 |
381 ///Sets the map storing the distances calculated by the algorithm. |
361 ///Sets the map storing the distances calculated by the algorithm. |
382 ///If you don't use this function before calling \ref run(), |
362 ///If you don't use this function before calling \ref run(), |
466 { |
446 { |
467 if(!(*_reached)[s]) |
447 if(!(*_reached)[s]) |
468 { |
448 { |
469 _reached->set(s,true); |
449 _reached->set(s,true); |
470 _pred->set(s,INVALID); |
450 _pred->set(s,INVALID); |
471 // _predNode->set(u,INVALID); |
|
472 OutEdgeIt e(*G,s); |
451 OutEdgeIt e(*G,s); |
473 if(e!=INVALID) { |
452 if(e!=INVALID) { |
474 _stack[++_stack_head]=e; |
453 _stack[++_stack_head]=e; |
475 _dist->set(s,_stack_head); |
454 _dist->set(s,_stack_head); |
476 } |
455 } |
493 Node m; |
472 Node m; |
494 Edge e=_stack[_stack_head]; |
473 Edge e=_stack[_stack_head]; |
495 if(!(*_reached)[m=G->target(e)]) { |
474 if(!(*_reached)[m=G->target(e)]) { |
496 _pred->set(m,e); |
475 _pred->set(m,e); |
497 _reached->set(m,true); |
476 _reached->set(m,true); |
498 // _pred_node->set(m,G->source(e)); |
|
499 ++_stack_head; |
477 ++_stack_head; |
500 _stack[_stack_head] = OutEdgeIt(*G, m); |
478 _stack[_stack_head] = OutEdgeIt(*G, m); |
501 _dist->set(m,_stack_head); |
479 _dist->set(m,_stack_head); |
502 } |
480 } |
503 else { |
481 else { |
504 m=G->source(e); |
482 m=G->source(e); |
505 ++_stack[_stack_head]; |
483 ++_stack[_stack_head]; |
506 } |
484 } |
507 //'m' is now the (original) source of the _stack[_stack_head] |
|
508 while(_stack_head>=0 && _stack[_stack_head]==INVALID) { |
485 while(_stack_head>=0 && _stack[_stack_head]==INVALID) { |
509 _processed->set(m,true); |
486 _processed->set(m,true); |
510 --_stack_head; |
487 --_stack_head; |
511 if(_stack_head>=0) { |
488 if(_stack_head>=0) { |
512 m=G->source(_stack[_stack_head]); |
489 m=G->source(_stack[_stack_head]); |
588 ///with addSource() before using this function. |
565 ///with addSource() before using this function. |
589 /// |
566 /// |
590 ///\param nm must be a bool (or convertible) edge map. The algorithm |
567 ///\param nm must be a bool (or convertible) edge map. The algorithm |
591 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>. |
568 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>. |
592 /// |
569 /// |
593 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map, |
570 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map, |
594 ///not a node map. |
571 ///not a node map. |
595 template<class NM> |
572 template<class EM> |
596 void start(const NM &nm) |
573 void start(const EM &em) |
597 { |
574 { |
598 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge(); |
575 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge(); |
599 } |
576 } |
600 |
577 |
601 ///Runs %DFS algorithm from node \c s. |
578 ///Runs %DFS algorithm from node \c s. |
602 |
579 |
603 ///This method runs the %DFS algorithm from a root node \c s |
580 ///This method runs the %DFS algorithm from a root node \c s |
604 ///in order to |
581 ///in order to |
605 ///compute the |
582 ///compute the |
723 ///%DFS tree. |
700 ///%DFS tree. |
724 ///\pre Either \ref run() or \ref init() |
701 ///\pre Either \ref run() or \ref init() |
725 ///must be called before using this function. |
702 ///must be called before using this function. |
726 const PredMap &predMap() const { return *_pred;} |
703 const PredMap &predMap() const { return *_pred;} |
727 |
704 |
728 // ///Returns a reference to the map of nodes of %DFS paths. |
|
729 |
|
730 // ///Returns a reference to the NodeMap of the last but one nodes of the |
|
731 // ///%DFS tree. |
|
732 // ///\pre \ref run() must be called before using this function. |
|
733 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
|
734 |
|
735 ///Checks if a node is reachable from the root. |
705 ///Checks if a node is reachable from the root. |
736 |
706 |
737 ///Returns \c true if \c v is reachable from the root(s). |
707 ///Returns \c true if \c v is reachable from the root(s). |
738 ///\warning The source nodes are inditated as unreachable. |
708 ///\warning The source nodes are inditated as unreachable. |
739 ///\pre Either \ref run() or \ref start() |
709 ///\pre Either \ref run() or \ref start() |
772 static PredMap *createPredMap(const GR &) |
742 static PredMap *createPredMap(const GR &) |
773 #endif |
743 #endif |
774 { |
744 { |
775 return new PredMap(); |
745 return new PredMap(); |
776 } |
746 } |
777 // ///\brief The type of the map that stores the last but one |
|
778 // ///nodes of the %DFS paths. |
|
779 // /// |
|
780 // ///The type of the map that stores the last but one |
|
781 // ///nodes of the %DFS paths. |
|
782 // ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
783 // /// |
|
784 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap; |
|
785 // ///Instantiates a PredNodeMap. |
|
786 |
|
787 // ///This function instantiates a \ref PredNodeMap. |
|
788 // ///\param G is the graph, to which |
|
789 // ///we would like to define the \ref PredNodeMap |
|
790 // static PredNodeMap *createPredNodeMap(const GR &G) |
|
791 // { |
|
792 // return new PredNodeMap(); |
|
793 // } |
|
794 |
747 |
795 ///The type of the map that indicates which nodes are processed. |
748 ///The type of the map that indicates which nodes are processed. |
796 |
749 |
797 ///The type of the map that indicates which nodes are processed. |
750 ///The type of the map that indicates which nodes are processed. |
798 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
751 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
869 void *_reached; |
822 void *_reached; |
870 ///Pointer to the map of processed nodes. |
823 ///Pointer to the map of processed nodes. |
871 void *_processed; |
824 void *_processed; |
872 ///Pointer to the map of predecessors edges. |
825 ///Pointer to the map of predecessors edges. |
873 void *_pred; |
826 void *_pred; |
874 // ///Pointer to the map of predecessors nodes. |
|
875 // void *_predNode; |
|
876 ///Pointer to the map of distances. |
827 ///Pointer to the map of distances. |
877 void *_dist; |
828 void *_dist; |
878 ///Pointer to the source node. |
829 ///Pointer to the source node. |
879 Node _source; |
830 Node _source; |
880 |
831 |
882 /// Constructor. |
833 /// Constructor. |
883 |
834 |
884 /// This constructor does not require parameters, therefore it initiates |
835 /// This constructor does not require parameters, therefore it initiates |
885 /// all of the attributes to default values (0, INVALID). |
836 /// all of the attributes to default values (0, INVALID). |
886 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
837 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
887 // _predNode(0), |
|
888 _dist(0), _source(INVALID) {} |
838 _dist(0), _source(INVALID) {} |
889 |
839 |
890 /// Constructor. |
840 /// Constructor. |
891 |
841 |
892 /// This constructor requires some parameters, |
842 /// This constructor requires some parameters, |
894 /// Others are initiated to 0. |
844 /// Others are initiated to 0. |
895 /// \param g is the initial value of \ref _g |
845 /// \param g is the initial value of \ref _g |
896 /// \param s is the initial value of \ref _source |
846 /// \param s is the initial value of \ref _source |
897 DfsWizardBase(const GR &g, Node s=INVALID) : |
847 DfsWizardBase(const GR &g, Node s=INVALID) : |
898 _g((void *)&g), _reached(0), _processed(0), _pred(0), |
848 _g((void *)&g), _reached(0), _processed(0), _pred(0), |
899 // _predNode(0), |
|
900 _dist(0), _source(s) {} |
849 _dist(0), _source(s) {} |
901 |
850 |
902 }; |
851 }; |
903 |
852 |
904 /// A class to make the usage of the Dfs algorithm easier |
853 /// A class to make the usage of the Dfs algorithm easier |
943 ///the processed nodes |
892 ///the processed nodes |
944 typedef typename TR::ProcessedMap ProcessedMap; |
893 typedef typename TR::ProcessedMap ProcessedMap; |
945 ///\brief The type of the map that stores the last |
894 ///\brief The type of the map that stores the last |
946 ///edges of the %DFS paths. |
895 ///edges of the %DFS paths. |
947 typedef typename TR::PredMap PredMap; |
896 typedef typename TR::PredMap PredMap; |
948 // ///\brief The type of the map that stores the last but one |
|
949 // ///nodes of the %DFS paths. |
|
950 // typedef typename TR::PredNodeMap PredNodeMap; |
|
951 ///The type of the map that stores the distances of the nodes. |
897 ///The type of the map that stores the distances of the nodes. |
952 typedef typename TR::DistMap DistMap; |
898 typedef typename TR::DistMap DistMap; |
953 |
899 |
954 public: |
900 public: |
955 /// Constructor. |
901 /// Constructor. |
976 if(Base::_source==INVALID) throw UninitializedParameter(); |
922 if(Base::_source==INVALID) throw UninitializedParameter(); |
977 Dfs<Graph,TR> alg(*(Graph*)Base::_g); |
923 Dfs<Graph,TR> alg(*(Graph*)Base::_g); |
978 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached); |
924 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached); |
979 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); |
925 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); |
980 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); |
926 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); |
981 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode); |
|
982 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); |
927 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); |
983 alg.run(Base::_source); |
928 alg.run(Base::_source); |
984 } |
929 } |
985 |
930 |
986 ///Runs Dfs algorithm from the given node. |
931 ///Runs Dfs algorithm from the given node. |
1053 { |
998 { |
1054 Base::_pred=(void *)&t; |
999 Base::_pred=(void *)&t; |
1055 return DfsWizard<DefProcessedMapBase<T> >(*this); |
1000 return DfsWizard<DefProcessedMapBase<T> >(*this); |
1056 } |
1001 } |
1057 |
1002 |
1058 |
|
1059 // template<class T> |
|
1060 // struct DefPredNodeMapBase : public Base { |
|
1061 // typedef T PredNodeMap; |
|
1062 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; |
|
1063 // DefPredNodeMapBase(const TR &b) : TR(b) {} |
|
1064 // }; |
|
1065 |
|
1066 // ///\brief \ref named-templ-param "Named parameter" |
|
1067 // ///function for setting PredNodeMap type |
|
1068 // /// |
|
1069 // /// \ref named-templ-param "Named parameter" |
|
1070 // ///function for setting PredNodeMap type |
|
1071 // /// |
|
1072 // template<class T> |
|
1073 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
|
1074 // { |
|
1075 // Base::_predNode=(void *)&t; |
|
1076 // return DfsWizard<DefPredNodeMapBase<T> >(*this); |
|
1077 // } |
|
1078 |
|
1079 template<class T> |
1003 template<class T> |
1080 struct DefDistMapBase : public Base { |
1004 struct DefDistMapBase : public Base { |
1081 typedef T DistMap; |
1005 typedef T DistMap; |
1082 static DistMap *createDistMap(const Graph &) { return 0; }; |
1006 static DistMap *createDistMap(const Graph &) { return 0; }; |
1083 DefDistMapBase(const TR &b) : TR(b) {} |
1007 DefDistMapBase(const TR &b) : TR(b) {} |
1130 dfs(const GR &g,typename GR::Node s=INVALID) |
1054 dfs(const GR &g,typename GR::Node s=INVALID) |
1131 { |
1055 { |
1132 return DfsWizard<DfsWizardBase<GR> >(g,s); |
1056 return DfsWizard<DfsWizardBase<GR> >(g,s); |
1133 } |
1057 } |
1134 |
1058 |
1059 /// \brief Visitor class for dfs. |
|
1060 /// |
|
1061 /// It gives a simple interface for a functional interface for dfs |
|
1062 /// traversal. The traversal on a linear data structure. |
|
1063 template <typename _Graph> |
|
1064 struct DfsVisitor { |
|
1065 typedef _Graph Graph; |
|
1066 typedef typename Graph::Edge Edge; |
|
1067 typedef typename Graph::Node Node; |
|
1068 /// \brief Called when the edge reach a node. |
|
1069 /// |
|
1070 /// It is called when the dfs find an edge which target is not |
|
1071 /// reached yet. |
|
1072 void discover(const Edge& edge) {} |
|
1073 /// \brief Called when the node reached first time. |
|
1074 /// |
|
1075 /// It is Called when the node reached first time. |
|
1076 void reach(const Node& node) {} |
|
1077 /// \brief Called when we step back on an edge. |
|
1078 /// |
|
1079 /// It is called when the dfs should step back on the edge. |
|
1080 void backtrack(const Edge& edge) {} |
|
1081 /// \brief Called when we step back from the node. |
|
1082 /// |
|
1083 /// It is called when we step back from the node. |
|
1084 void leave(const Node& node) {} |
|
1085 /// \brief Called when the edge examined but target of the edge |
|
1086 /// already discovered. |
|
1087 /// |
|
1088 /// It called when the edge examined but the target of the edge |
|
1089 /// already discovered. |
|
1090 void examine(const Edge& edge) {} |
|
1091 /// \brief Called for the source node of the dfs. |
|
1092 /// |
|
1093 /// It is called for the source node of the dfs. |
|
1094 void start(const Node&) {} |
|
1095 /// \brief Called when we leave the source node of the dfs. |
|
1096 /// |
|
1097 /// It is called when we leave the source node of the dfs. |
|
1098 void stop(const Node&) {} |
|
1099 |
|
1100 template <typename _Visitor> |
|
1101 struct Constraints { |
|
1102 void constraints() { |
|
1103 Edge edge; |
|
1104 Node node; |
|
1105 visitor.discover(edge); |
|
1106 visitor.reach(node); |
|
1107 visitor.backtrack(edge); |
|
1108 visitor.leave(node); |
|
1109 visitor.examine(edge); |
|
1110 visitor.start(node); |
|
1111 visitor.stop(edge); |
|
1112 } |
|
1113 _Visitor& visitor; |
|
1114 }; |
|
1115 }; |
|
1116 |
|
1117 /// \brief Default traits class of DfsVisit class. |
|
1118 /// |
|
1119 /// Default traits class of DfsVisit class. |
|
1120 /// \param _Graph Graph type. |
|
1121 template<class _Graph> |
|
1122 struct DfsVisitDefaultTraits { |
|
1123 |
|
1124 /// \brief The graph type the algorithm runs on. |
|
1125 typedef _Graph Graph; |
|
1126 |
|
1127 /// \brief The type of the map that indicates which nodes are reached. |
|
1128 /// |
|
1129 /// The type of the map that indicates which nodes are reached. |
|
1130 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
1131 /// \todo named parameter to set this type, function to read and write. |
|
1132 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
1133 |
|
1134 /// \brief Instantiates a ReachedMap. |
|
1135 /// |
|
1136 /// This function instantiates a \ref ReachedMap. |
|
1137 /// \param G is the graph, to which |
|
1138 /// we would like to define the \ref ReachedMap. |
|
1139 static ReachedMap *createReachedMap(const Graph &graph) { |
|
1140 return new ReachedMap(graph); |
|
1141 } |
|
1142 |
|
1143 }; |
|
1144 |
|
1145 /// %DFS Visit algorithm class. |
|
1146 |
|
1147 /// \ingroup flowalgs |
|
1148 /// This class provides an efficient implementation of the %DFS algorithm |
|
1149 /// with visitor interface. |
|
1150 /// |
|
1151 /// The %DfsVisit class provides an alternative interface to the Dfs |
|
1152 /// class. It works with callback mechanism, the DfsVisit object calls |
|
1153 /// on every dfs event the \c Visitor class member functions. |
|
1154 /// |
|
1155 /// \param _Graph The graph type the algorithm runs on. The default value is |
|
1156 /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it |
|
1157 /// is only passed to \ref DfsDefaultTraits. |
|
1158 /// \param _Visitor The Visitor object for the algorithm. The |
|
1159 /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which |
|
1160 /// does not observe the Dfs events. If you want to observe the dfs |
|
1161 /// events you should implement your own Visitor class. |
|
1162 /// \param _Traits Traits class to set various data types used by the |
|
1163 /// algorithm. The default traits class is |
|
1164 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>". |
|
1165 /// See \ref DfsVisitDefaultTraits for the documentation of |
|
1166 /// a Dfs visit traits class. |
|
1167 /// |
|
1168 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso |
|
1169 #ifdef DOXYGEN |
|
1170 template <typename _Graph, typename _Visitor, typename _Traits> |
|
1171 #else |
|
1172 template <typename _Graph = ListGraph, |
|
1173 typename _Visitor = DfsVisitor<_Graph>, |
|
1174 typename _Traits = DfsDefaultTraits<_Graph> > |
|
1175 #endif |
|
1176 class DfsVisit { |
|
1177 public: |
|
1178 |
|
1179 /// \brief \ref Exception for uninitialized parameters. |
|
1180 /// |
|
1181 /// This error represents problems in the initialization |
|
1182 /// of the parameters of the algorithms. |
|
1183 class UninitializedParameter : public lemon::UninitializedParameter { |
|
1184 public: |
|
1185 virtual const char* exceptionName() const { |
|
1186 return "lemon::DfsVisit::UninitializedParameter"; |
|
1187 } |
|
1188 }; |
|
1189 |
|
1190 typedef _Traits Traits; |
|
1191 |
|
1192 typedef typename Traits::Graph Graph; |
|
1193 |
|
1194 typedef _Visitor Visitor; |
|
1195 |
|
1196 ///The type of the map indicating which nodes are reached. |
|
1197 typedef typename Traits::ReachedMap ReachedMap; |
|
1198 |
|
1199 private: |
|
1200 |
|
1201 typedef typename Graph::Node Node; |
|
1202 typedef typename Graph::NodeIt NodeIt; |
|
1203 typedef typename Graph::Edge Edge; |
|
1204 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
1205 |
|
1206 /// Pointer to the underlying graph. |
|
1207 const Graph *_graph; |
|
1208 /// Pointer to the visitor object. |
|
1209 Visitor *_visitor; |
|
1210 ///Pointer to the map of reached status of the nodes. |
|
1211 ReachedMap *_reached; |
|
1212 ///Indicates if \ref _reached is locally allocated (\c true) or not. |
|
1213 bool local_reached; |
|
1214 |
|
1215 std::vector<typename Graph::Edge> _stack; |
|
1216 int _stack_head; |
|
1217 |
|
1218 /// \brief Creates the maps if necessary. |
|
1219 /// |
|
1220 /// Creates the maps if necessary. |
|
1221 void create_maps() { |
|
1222 if(!_reached) { |
|
1223 local_reached = true; |
|
1224 _reached = Traits::createReachedMap(*_graph); |
|
1225 } |
|
1226 } |
|
1227 |
|
1228 protected: |
|
1229 |
|
1230 DfsVisit() {} |
|
1231 |
|
1232 public: |
|
1233 |
|
1234 typedef DfsVisit Create; |
|
1235 |
|
1236 /// \name Named template parameters |
|
1237 |
|
1238 ///@{ |
|
1239 template <class T> |
|
1240 struct DefReachedMapTraits : public Traits { |
|
1241 typedef T ReachedMap; |
|
1242 static ReachedMap *createReachedMap(const Graph &graph) { |
|
1243 throw UninitializedParameter(); |
|
1244 } |
|
1245 }; |
|
1246 /// \brief \ref named-templ-param "Named parameter" for setting |
|
1247 /// ReachedMap type |
|
1248 /// |
|
1249 /// \ref named-templ-param "Named parameter" for setting ReachedMap type |
|
1250 template <class T> |
|
1251 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > { |
|
1252 typedef Dfs< Graph, DefReachedMapTraits<T> > Create; |
|
1253 }; |
|
1254 ///@} |
|
1255 |
|
1256 public: |
|
1257 |
|
1258 /// \brief Constructor. |
|
1259 /// |
|
1260 /// Constructor. |
|
1261 /// |
|
1262 /// \param graph the graph the algorithm will run on. |
|
1263 /// \param visitor The visitor of the algorithm. |
|
1264 /// |
|
1265 DfsVisit(const Graph& graph, Visitor& visitor) |
|
1266 : _graph(&graph), _visitor(&visitor), |
|
1267 _reached(0), local_reached(false) {} |
|
1268 |
|
1269 /// \brief Destructor. |
|
1270 /// |
|
1271 /// Destructor. |
|
1272 ~DfsVisit() { |
|
1273 if(local_reached) delete _reached; |
|
1274 } |
|
1275 |
|
1276 /// \brief Sets the map indicating if a node is reached. |
|
1277 /// |
|
1278 /// Sets the map indicating if a node is reached. |
|
1279 /// If you don't use this function before calling \ref run(), |
|
1280 /// it will allocate one. The destuctor deallocates this |
|
1281 /// automatically allocated map, of course. |
|
1282 /// \return <tt> (*this) </tt> |
|
1283 DfsVisit &reachedMap(ReachedMap &m) { |
|
1284 if(local_reached) { |
|
1285 delete _reached; |
|
1286 local_reached=false; |
|
1287 } |
|
1288 _reached = &m; |
|
1289 return *this; |
|
1290 } |
|
1291 |
|
1292 public: |
|
1293 /// \name Execution control |
|
1294 /// The simplest way to execute the algorithm is to use |
|
1295 /// one of the member functions called \c run(...). |
|
1296 /// \n |
|
1297 /// If you need more control on the execution, |
|
1298 /// first you must call \ref init(), then you can add several source nodes |
|
1299 /// with \ref addSource(). |
|
1300 /// Finally \ref start() will perform the actual path |
|
1301 /// computation. |
|
1302 |
|
1303 /// @{ |
|
1304 /// \brief Initializes the internal data structures. |
|
1305 /// |
|
1306 /// Initializes the internal data structures. |
|
1307 /// |
|
1308 void init() { |
|
1309 create_maps(); |
|
1310 _stack.resize(countNodes(*_graph)); |
|
1311 _stack_head = -1; |
|
1312 for (NodeIt u(*_graph) ; u != INVALID ; ++u) { |
|
1313 _reached->set(u, false); |
|
1314 } |
|
1315 } |
|
1316 |
|
1317 /// \brief Adds a new source node. |
|
1318 /// |
|
1319 /// Adds a new source node to the set of nodes to be processed. |
|
1320 void addSource(Node s) { |
|
1321 if(!(*_reached)[s]) { |
|
1322 _reached->set(s,true); |
|
1323 _visitor->start(s); |
|
1324 _visitor->reach(s); |
|
1325 Edge e; |
|
1326 _graph->firstOut(e, s); |
|
1327 if (e != INVALID) { |
|
1328 _stack[++_stack_head] = e; |
|
1329 } else { |
|
1330 _visitor->leave(s); |
|
1331 } |
|
1332 } |
|
1333 } |
|
1334 |
|
1335 /// \brief Processes the next edge. |
|
1336 /// |
|
1337 /// Processes the next edge. |
|
1338 /// |
|
1339 /// \return The processed edge. |
|
1340 /// |
|
1341 /// \pre The stack must not be empty! |
|
1342 Edge processNextEdge() { |
|
1343 Edge e = _stack[_stack_head]; |
|
1344 Node m = _graph->target(e); |
|
1345 if(!(*_reached)[m]) { |
|
1346 _visitor->discover(e); |
|
1347 _visitor->reach(m); |
|
1348 _reached->set(m, true); |
|
1349 _graph->firstOut(_stack[++_stack_head], m); |
|
1350 } else { |
|
1351 _visitor->examine(e); |
|
1352 m = _graph->source(e); |
|
1353 _graph->nextOut(_stack[_stack_head]); |
|
1354 } |
|
1355 while (_stack_head>=0 && _stack[_stack_head] == INVALID) { |
|
1356 _visitor->leave(m); |
|
1357 --_stack_head; |
|
1358 if (_stack_head >= 0) { |
|
1359 _visitor->backtrack(_stack[_stack_head]); |
|
1360 m = _graph->source(_stack[_stack_head]); |
|
1361 _graph->nextOut(_stack[_stack_head]); |
|
1362 } else { |
|
1363 _visitor->stop(m); |
|
1364 } |
|
1365 } |
|
1366 return e; |
|
1367 } |
|
1368 |
|
1369 /// \brief Next edge to be processed. |
|
1370 /// |
|
1371 /// Next edge to be processed. |
|
1372 /// |
|
1373 /// \return The next edge to be processed or INVALID if the stack is |
|
1374 /// empty. |
|
1375 Edge nextEdge() { |
|
1376 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; |
|
1377 } |
|
1378 |
|
1379 /// \brief Returns \c false if there are nodes |
|
1380 /// to be processed in the queue |
|
1381 /// |
|
1382 /// Returns \c false if there are nodes |
|
1383 /// to be processed in the queue |
|
1384 /// |
|
1385 /// \todo This should be called emptyStack() or some "neutral" name. |
|
1386 bool emptyQueue() { return _stack_head < 0; } |
|
1387 |
|
1388 /// \brief Returns the number of the nodes to be processed. |
|
1389 /// |
|
1390 /// Returns the number of the nodes to be processed in the queue. |
|
1391 /// |
|
1392 ///\todo This should be called stackSize() or some "neutral" name. |
|
1393 int queueSize() { return _stack_head + 1; } |
|
1394 |
|
1395 /// \brief Executes the algorithm. |
|
1396 /// |
|
1397 /// Executes the algorithm. |
|
1398 /// |
|
1399 /// \pre init() must be called and at least one node should be added |
|
1400 /// with addSource() before using this function. |
|
1401 void start() { |
|
1402 while ( !emptyQueue() ) processNextEdge(); |
|
1403 } |
|
1404 |
|
1405 /// \brief Executes the algorithm until \c dest is reached. |
|
1406 /// |
|
1407 /// Executes the algorithm until \c dest is reached. |
|
1408 /// |
|
1409 /// \pre init() must be called and at least one node should be added |
|
1410 /// with addSource() before using this function. |
|
1411 void start(Node dest) { |
|
1412 while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest) |
|
1413 processNextEdge(); |
|
1414 } |
|
1415 |
|
1416 /// \brief Executes the algorithm until a condition is met. |
|
1417 /// |
|
1418 /// Executes the algorithm until a condition is met. |
|
1419 /// |
|
1420 /// \pre init() must be called and at least one node should be added |
|
1421 /// with addSource() before using this function. |
|
1422 /// |
|
1423 /// \param nm must be a bool (or convertible) edge map. The algorithm |
|
1424 /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>. |
|
1425 /// |
|
1426 /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map, |
|
1427 /// not a node map. |
|
1428 template <typename EM> |
|
1429 void start(const EM &em) { |
|
1430 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge(); |
|
1431 } |
|
1432 |
|
1433 /// \brief Runs %DFS algorithm from node \c s. |
|
1434 /// |
|
1435 /// This method runs the %DFS algorithm from a root node \c s. |
|
1436 /// \note d.run(s) is just a shortcut of the following code. |
|
1437 /// \code |
|
1438 /// d.init(); |
|
1439 /// d.addSource(s); |
|
1440 /// d.start(); |
|
1441 /// \endcode |
|
1442 void run(Node s) { |
|
1443 init(); |
|
1444 addSource(s); |
|
1445 start(); |
|
1446 } |
|
1447 ///@} |
|
1448 |
|
1449 /// \name Query Functions |
|
1450 /// The result of the %DFS algorithm can be obtained using these |
|
1451 /// functions.\n |
|
1452 /// Before the use of these functions, |
|
1453 /// either run() or start() must be called. |
|
1454 ///@{ |
|
1455 /// \brief Checks if a node is reachable from the root. |
|
1456 /// |
|
1457 /// Returns \c true if \c v is reachable from the root(s). |
|
1458 /// \warning The source nodes are inditated as unreachable. |
|
1459 /// \pre Either \ref run() or \ref start() |
|
1460 /// must be called before using this function. |
|
1461 /// |
|
1462 bool reached(Node v) { return (*_reached)[v]; } |
|
1463 ///@} |
|
1464 }; |
|
1465 |
|
1466 |
|
1135 } //END OF NAMESPACE LEMON |
1467 } //END OF NAMESPACE LEMON |
1136 |
1468 |
1137 #endif |
1469 #endif |
1138 |
1470 |