31 #endif |
31 #endif |
32 class Dfs{ |
32 class Dfs{ |
33 public: |
33 public: |
34 ///The type of the underlying graph. |
34 ///The type of the underlying graph. |
35 typedef GR Graph; |
35 typedef GR Graph; |
|
36 /// . |
36 typedef typename Graph::Node Node; |
37 typedef typename Graph::Node Node; |
|
38 /// . |
37 typedef typename Graph::NodeIt NodeIt; |
39 typedef typename Graph::NodeIt NodeIt; |
|
40 /// . |
38 typedef typename Graph::Edge Edge; |
41 typedef typename Graph::Edge Edge; |
|
42 /// . |
39 typedef typename Graph::OutEdgeIt OutEdgeIt; |
43 typedef typename Graph::OutEdgeIt OutEdgeIt; |
40 |
44 |
41 ///\brief The type of the map that stores the last |
45 ///\brief The type of the map that stores the last |
42 ///edges of the paths on the %DFS tree. |
46 ///edges of the paths on the %DFS tree. |
43 typedef typename Graph::template NodeMap<Edge> PredMap; |
47 typedef typename Graph::template NodeMap<Edge> PredMap; |
46 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
50 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
47 ///The type of the map that stores the dists of the nodes on the %DFS tree. |
51 ///The type of the map that stores the dists of the nodes on the %DFS tree. |
48 typedef typename Graph::template NodeMap<int> DistMap; |
52 typedef typename Graph::template NodeMap<int> DistMap; |
49 |
53 |
50 private: |
54 private: |
|
55 /// Pointer to the underlying graph. |
51 const Graph *G; |
56 const Graph *G; |
|
57 ///Pointer to the map of predecessors edges. |
52 PredMap *predecessor; |
58 PredMap *predecessor; |
|
59 ///Indicates if \ref predecessor is locally allocated (\c true) or not. |
53 bool local_predecessor; |
60 bool local_predecessor; |
|
61 ///Pointer to the map of predecessors nodes. |
54 PredNodeMap *pred_node; |
62 PredNodeMap *pred_node; |
|
63 ///Indicates if \ref pred_node is locally allocated (\c true) or not. |
55 bool local_pred_node; |
64 bool local_pred_node; |
|
65 ///Pointer to the map of distances. |
56 DistMap *distance; |
66 DistMap *distance; |
|
67 ///Indicates if \ref distance is locally allocated (\c true) or not. |
57 bool local_distance; |
68 bool local_distance; |
58 |
69 |
59 //The source node of the last execution. |
70 ///The source node of the last execution. |
60 Node source; |
71 Node source; |
61 |
72 |
62 |
73 |
63 ///Initializes the maps. |
74 ///Initializes the maps. |
64 void init_maps() |
75 void init_maps() |
76 distance = new DistMap(*G); |
87 distance = new DistMap(*G); |
77 } |
88 } |
78 } |
89 } |
79 |
90 |
80 public : |
91 public : |
|
92 ///Constructor. |
|
93 |
|
94 ///\param _G the graph the algorithm will run on. |
81 Dfs(const Graph& _G) : |
95 Dfs(const Graph& _G) : |
82 G(&_G), |
96 G(&_G), |
83 predecessor(NULL), local_predecessor(false), |
97 predecessor(NULL), local_predecessor(false), |
84 pred_node(NULL), local_pred_node(false), |
98 pred_node(NULL), local_pred_node(false), |
85 distance(NULL), local_distance(false) |
99 distance(NULL), local_distance(false) |
86 { } |
100 { } |
87 |
101 |
|
102 ///Destructor. |
88 ~Dfs() |
103 ~Dfs() |
89 { |
104 { |
90 if(local_predecessor) delete predecessor; |
105 if(local_predecessor) delete predecessor; |
91 if(local_pred_node) delete pred_node; |
106 if(local_pred_node) delete pred_node; |
92 if(local_distance) delete distance; |
107 if(local_distance) delete distance; |
93 } |
108 } |
94 |
109 |
95 ///Sets the graph the algorithm will run on. |
|
96 |
|
97 ///Sets the graph the algorithm will run on. |
|
98 ///\return <tt> (*this) </tt> |
|
99 ///\bug What about maps? |
|
100 ///\todo It may be unnecessary |
|
101 Dfs &setGraph(const Graph &_G) |
|
102 { |
|
103 G = &_G; |
|
104 return *this; |
|
105 } |
|
106 ///Sets the map storing the predecessor edges. |
110 ///Sets the map storing the predecessor edges. |
107 |
111 |
108 ///Sets the map storing the predecessor edges. |
112 ///Sets the map storing the predecessor edges. |
109 ///If you don't use this function before calling \ref run(), |
113 ///If you don't use this function before calling \ref run(), |
110 ///it will allocate one. The destuctor deallocates this |
114 ///it will allocate one. The destuctor deallocates this |
251 const PredNodeMap &predNodeMap() const { return *pred_node;} |
255 const PredNodeMap &predNodeMap() const { return *pred_node;} |
252 |
256 |
253 ///Checks if a node is reachable from the root. |
257 ///Checks if a node is reachable from the root. |
254 |
258 |
255 ///Returns \c true if \c v is reachable from the root. |
259 ///Returns \c true if \c v is reachable from the root. |
256 ///\warning The root node is reported to be reached! |
260 ///\note The root node is reported to be reached! |
257 /// |
261 /// |
258 ///\pre \ref run() must be called before using this function. |
262 ///\pre \ref run() must be called before using this function. |
259 /// |
263 /// |
260 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
264 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
261 |
265 |