14 namespace hugo { |
14 namespace hugo { |
15 |
15 |
16 /// \addtogroup flowalgs |
16 /// \addtogroup flowalgs |
17 /// @{ |
17 /// @{ |
18 |
18 |
19 ///%Bfs algorithm class. |
19 ///%BFS algorithm class. |
20 |
20 |
21 ///This class provides an efficient implementation of %Bfs algorithm. |
21 ///This class provides an efficient implementation of %BFS algorithm. |
22 ///The edge lengths are passed to the algorithm using a |
22 ///\param GR The graph type the algorithm runs on. |
23 ///\ref ReadMapSkeleton "readable map", |
23 ///This class does the same as Dijkstra does with constant 1 edge length, |
24 ///so it is easy to change it to any kind of length. |
24 ///but it is faster. |
25 /// |
25 /// |
26 ///The type of the length is determined by the \c ValueType of the length map. |
26 ///\author Alpar Juttner |
27 /// |
|
28 ///It is also possible to change the underlying priority heap. |
|
29 /// |
|
30 ///\param GR The graph type the algorithm runs on. |
|
31 ///\param LM This read-only |
|
32 ///EdgeMap |
|
33 ///determines the |
|
34 ///lengths of the edges. It is read once for each edge, so the map |
|
35 ///may involve in relatively time consuming process to compute the edge |
|
36 ///length if it is necessary. The default map type is |
|
37 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" |
|
38 ///\param Heap The heap type used by the %Bfs |
|
39 ///algorithm. The default |
|
40 ///is using \ref BinHeap "binary heap". |
|
41 /// |
|
42 ///\author Jacint Szabo and Alpar Juttner |
|
43 ///\todo We need a typedef-names should be standardized. (-: |
|
44 ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap |
|
45 ///should not be fixed. (Problematic to solve). |
|
46 |
27 |
47 #ifdef DOXYGEN |
28 #ifdef DOXYGEN |
48 template <typename GR> |
29 template <typename GR> |
49 #else |
30 #else |
50 template <typename GR> |
31 template <typename GR> |
112 distance(NULL), local_distance(false) |
86 distance(NULL), local_distance(false) |
113 { } |
87 { } |
114 |
88 |
115 ~Bfs() |
89 ~Bfs() |
116 { |
90 { |
117 // if(local_length) delete length; |
|
118 if(local_predecessor) delete predecessor; |
91 if(local_predecessor) delete predecessor; |
119 if(local_pred_node) delete pred_node; |
92 if(local_pred_node) delete pred_node; |
120 if(local_distance) delete distance; |
93 if(local_distance) delete distance; |
121 } |
94 } |
122 |
95 |
123 ///Sets the graph the algorithm will run on. |
96 ///Sets the graph the algorithm will run on. |
124 |
97 |
125 ///Sets the graph the algorithm will run on. |
98 ///Sets the graph the algorithm will run on. |
126 ///\return <tt> (*this) </tt> |
99 ///\return <tt> (*this) </tt> |
|
100 ///\bug What about maps? |
|
101 ///\todo It may be unnecessary |
127 Bfs &setGraph(const Graph &_G) |
102 Bfs &setGraph(const Graph &_G) |
128 { |
103 { |
129 G = &_G; |
104 G = &_G; |
130 return *this; |
105 return *this; |
131 } |
106 } |
132 ///Sets the length map. |
|
133 |
|
134 ///Sets the map storing the predecessor edges. |
107 ///Sets the map storing the predecessor edges. |
135 |
108 |
136 ///Sets the map storing the predecessor edges. |
109 ///Sets the map storing the predecessor edges. |
137 ///If you don't use this function before calling \ref run(), |
110 ///If you don't use this function before calling \ref run(), |
138 ///it will allocate one. The destuctor deallocates this |
111 ///it will allocate one. The destuctor deallocates this |
230 ///\pre \ref run() must be called before using this function. |
203 ///\pre \ref run() must be called before using this function. |
231 ///\warning If node \c v in unreachable from the root the return value |
204 ///\warning If node \c v in unreachable from the root the return value |
232 ///of this funcion is undefined. |
205 ///of this funcion is undefined. |
233 int dist(Node v) const { return (*distance)[v]; } |
206 int dist(Node v) const { return (*distance)[v]; } |
234 |
207 |
235 ///Returns the 'previous edge' of the shortest path tree. |
208 ///Returns the 'previous edge' of the %BFS path tree. |
236 |
209 |
237 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
210 ///For a node \c v it returns the 'previous edge' of the %BFS tree, |
238 ///i.e. it returns the last edge from a shortest path from the root to \c |
211 ///i.e. it returns the last edge of a shortest path from the root to \c |
239 ///v. It is \ref INVALID |
212 ///v. It is \ref INVALID |
240 ///if \c v is unreachable from the root or if \c v=s. The |
213 ///if \c v is unreachable from the root or if \c v=s. The |
241 ///shortest path tree used here is equal to the shortest path tree used in |
214 ///%BFS tree used here is equal to the %BFS tree used in |
242 ///\ref predNode(Node v). \pre \ref run() must be called before using |
215 ///\ref predNode(Node v). \pre \ref run() must be called before using |
243 ///this function. |
216 ///this function. |
244 Edge pred(Node v) const { return (*predecessor)[v]; } |
217 Edge pred(Node v) const { return (*predecessor)[v]; } |
245 |
218 |
246 ///Returns the 'previous node' of the shortest path tree. |
219 ///Returns the 'previous node' of the %BFS tree. |
247 |
220 |
248 ///For a node \c v it returns the 'previous node' of the shortest path tree, |
221 ///For a node \c v it returns the 'previous node' on the %BFS tree, |
249 ///i.e. it returns the last but one node from a shortest path from the |
222 ///i.e. it returns the last but one node from a shortest path from the |
250 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
223 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
251 ///\c v=s. The shortest path tree used here is equal to the shortest path |
224 ///\c v=s. The shortest path tree used here is equal to the %BFS |
252 ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
225 ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
253 ///using this function. |
226 ///using this function. |
254 Node predNode(Node v) const { return (*pred_node)[v]; } |
227 Node predNode(Node v) const { return (*pred_node)[v]; } |
255 |
228 |
256 ///Returns a reference to the NodeMap of distances. |
229 ///Returns a reference to the NodeMap of distances. |
257 |
230 |
258 ///Returns a reference to the NodeMap of distances. \pre \ref run() must |
231 ///Returns a reference to the NodeMap of distances. \pre \ref run() must |
259 ///be called before using this function. |
232 ///be called before using this function. |
260 const DistMap &distMap() const { return *distance;} |
233 const DistMap &distMap() const { return *distance;} |
261 |
234 |
262 ///Returns a reference to the shortest path tree map. |
235 ///Returns a reference to the %BFS tree map. |
263 |
236 |
264 ///Returns a reference to the NodeMap of the edges of the |
237 ///Returns a reference to the NodeMap of the edges of the |
265 ///shortest path tree. |
238 ///%BFS tree. |
266 ///\pre \ref run() must be called before using this function. |
239 ///\pre \ref run() must be called before using this function. |
267 const PredMap &predMap() const { return *predecessor;} |
240 const PredMap &predMap() const { return *predecessor;} |
268 |
241 |
269 ///Returns a reference to the map of nodes of shortest paths. |
242 ///Returns a reference to the map of last but one nodes of shortest paths. |
270 |
243 |
271 ///Returns a reference to the NodeMap of the last but one nodes of the |
244 ///Returns a reference to the NodeMap of the last but one nodes on the |
272 ///shortest path tree. |
245 ///%BFS tree. |
273 ///\pre \ref run() must be called before using this function. |
246 ///\pre \ref run() must be called before using this function. |
274 const PredNodeMap &predNodeMap() const { return *pred_node;} |
247 const PredNodeMap &predNodeMap() const { return *pred_node;} |
275 |
248 |
276 ///Checks if a node is reachable from the root. |
249 ///Checks if a node is reachable from the root. |
277 |
250 |