equal
deleted
inserted
replaced
149 }; |
149 }; |
150 |
150 |
151 typedef TR Traits; |
151 typedef TR Traits; |
152 ///The type of the underlying graph. |
152 ///The type of the underlying graph. |
153 typedef typename TR::Graph Graph; |
153 typedef typename TR::Graph Graph; |
154 ///\e |
|
155 typedef typename Graph::Node Node; |
|
156 ///\e |
|
157 typedef typename Graph::NodeIt NodeIt; |
|
158 ///\e |
|
159 typedef typename Graph::Edge Edge; |
|
160 ///\e |
|
161 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
162 |
154 |
163 ///\brief The type of the map that stores the last |
155 ///\brief The type of the map that stores the last |
164 ///edges of the shortest paths. |
156 ///edges of the shortest paths. |
165 typedef typename TR::PredMap PredMap; |
157 typedef typename TR::PredMap PredMap; |
166 ///The type of the map indicating which nodes are reached. |
158 ///The type of the map indicating which nodes are reached. |
168 ///The type of the map indicating which nodes are processed. |
160 ///The type of the map indicating which nodes are processed. |
169 typedef typename TR::ProcessedMap ProcessedMap; |
161 typedef typename TR::ProcessedMap ProcessedMap; |
170 ///The type of the map that stores the dists of the nodes. |
162 ///The type of the map that stores the dists of the nodes. |
171 typedef typename TR::DistMap DistMap; |
163 typedef typename TR::DistMap DistMap; |
172 private: |
164 private: |
|
165 |
|
166 typedef typename Graph::Node Node; |
|
167 typedef typename Graph::NodeIt NodeIt; |
|
168 typedef typename Graph::Edge Edge; |
|
169 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
170 |
173 /// Pointer to the underlying graph. |
171 /// Pointer to the underlying graph. |
174 const Graph *G; |
172 const Graph *G; |
175 ///Pointer to the map of predecessors edges. |
173 ///Pointer to the map of predecessors edges. |
176 PredMap *_pred; |
174 PredMap *_pred; |
177 ///Indicates if \ref _pred is locally allocated (\c true) or not. |
175 ///Indicates if \ref _pred is locally allocated (\c true) or not. |
234 static PredMap *createPredMap(const Graph &) |
232 static PredMap *createPredMap(const Graph &) |
235 { |
233 { |
236 throw UninitializedParameter(); |
234 throw UninitializedParameter(); |
237 } |
235 } |
238 }; |
236 }; |
239 ///\ref named-templ-param "Named parameter" for setting PredMap type |
237 ///\brief \ref named-templ-param "Named parameter" for setting |
240 |
238 ///PredMap type |
|
239 /// |
241 ///\ref named-templ-param "Named parameter" for setting PredMap type |
240 ///\ref named-templ-param "Named parameter" for setting PredMap type |
242 /// |
241 /// |
243 template <class T> |
242 template <class T> |
244 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { |
243 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { |
245 typedef Bfs< Graph, DefPredMapTraits<T> > Create; |
244 typedef Bfs< Graph, DefPredMapTraits<T> > Create; |
251 static DistMap *createDistMap(const Graph &) |
250 static DistMap *createDistMap(const Graph &) |
252 { |
251 { |
253 throw UninitializedParameter(); |
252 throw UninitializedParameter(); |
254 } |
253 } |
255 }; |
254 }; |
256 ///\ref named-templ-param "Named parameter" for setting DistMap type |
255 ///\brief \ref named-templ-param "Named parameter" for setting |
257 |
256 ///DistMap type |
|
257 /// |
258 ///\ref named-templ-param "Named parameter" for setting DistMap type |
258 ///\ref named-templ-param "Named parameter" for setting DistMap type |
259 /// |
259 /// |
260 template <class T> |
260 template <class T> |
261 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > { |
261 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > { |
262 typedef Bfs< Graph, DefDistMapTraits<T> > Create; |
262 typedef Bfs< Graph, DefDistMapTraits<T> > Create; |
268 static ReachedMap *createReachedMap(const Graph &) |
268 static ReachedMap *createReachedMap(const Graph &) |
269 { |
269 { |
270 throw UninitializedParameter(); |
270 throw UninitializedParameter(); |
271 } |
271 } |
272 }; |
272 }; |
273 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
273 ///\brief \ref named-templ-param "Named parameter" for setting |
274 |
274 ///ReachedMap type |
|
275 /// |
275 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
276 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
276 /// |
277 /// |
277 template <class T> |
278 template <class T> |
278 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > { |
279 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > { |
279 typedef Bfs< Graph, DefReachedMapTraits<T> > Create; |
280 typedef Bfs< Graph, DefReachedMapTraits<T> > Create; |
285 static ProcessedMap *createProcessedMap(const Graph &) |
286 static ProcessedMap *createProcessedMap(const Graph &) |
286 { |
287 { |
287 throw UninitializedParameter(); |
288 throw UninitializedParameter(); |
288 } |
289 } |
289 }; |
290 }; |
290 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
291 ///\brief \ref named-templ-param "Named parameter" for setting |
291 |
292 ///ProcessedMap type |
|
293 /// |
292 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
294 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
293 /// |
295 /// |
294 template <class T> |
296 template <class T> |
295 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > { |
297 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > { |
296 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create; |
298 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create; |
419 ///Finally \ref start() will perform the actual path |
421 ///Finally \ref start() will perform the actual path |
420 ///computation. |
422 ///computation. |
421 |
423 |
422 ///@{ |
424 ///@{ |
423 |
425 |
424 ///Initializes the internal data structures. |
426 ///\brief Initializes the internal data structures. |
425 |
427 /// |
426 ///Initializes the internal data structures. |
428 ///Initializes the internal data structures. |
427 /// |
429 /// |
428 void init() |
430 void init() |
429 { |
431 { |
430 create_maps(); |
432 create_maps(); |
1099 } |
1101 } |
1100 |
1102 |
1101 #ifdef DOXYGEN |
1103 #ifdef DOXYGEN |
1102 /// \brief Visitor class for bfs. |
1104 /// \brief Visitor class for bfs. |
1103 /// |
1105 /// |
1104 /// It gives a simple interface for a functional interface for bfs |
1106 /// This class defines the interface of the BfsVisit events, and |
1105 /// traversal. The traversal on a linear data structure. |
1107 /// it could be the base of a real Visitor class. |
1106 template <typename _Graph> |
1108 template <typename _Graph> |
1107 struct BfsVisitor { |
1109 struct BfsVisitor { |
1108 typedef _Graph Graph; |
1110 typedef _Graph Graph; |
1109 typedef typename Graph::Edge Edge; |
1111 typedef typename Graph::Edge Edge; |
1110 typedef typename Graph::Node Node; |
1112 typedef typename Graph::Node Node; |
1185 static ReachedMap *createReachedMap(const Graph &graph) { |
1187 static ReachedMap *createReachedMap(const Graph &graph) { |
1186 return new ReachedMap(graph); |
1188 return new ReachedMap(graph); |
1187 } |
1189 } |
1188 |
1190 |
1189 }; |
1191 }; |
1190 |
1192 |
1191 /// %BFS Visit algorithm class. |
|
1192 |
|
1193 /// \ingroup search |
1193 /// \ingroup search |
|
1194 /// |
|
1195 /// \brief %BFS Visit algorithm class. |
|
1196 /// |
1194 /// This class provides an efficient implementation of the %BFS algorithm |
1197 /// This class provides an efficient implementation of the %BFS algorithm |
1195 /// with visitor interface. |
1198 /// with visitor interface. |
1196 /// |
1199 /// |
1197 /// The %BfsVisit class provides an alternative interface to the Bfs |
1200 /// The %BfsVisit class provides an alternative interface to the Bfs |
1198 /// class. It works with callback mechanism, the BfsVisit object calls |
1201 /// class. It works with callback mechanism, the BfsVisit object calls |