91 typedef _Graph Graph; |
91 typedef _Graph Graph; |
92 |
92 |
93 /// \brief The type of the map that stores the edge lengths. |
93 /// \brief The type of the map that stores the edge lengths. |
94 /// |
94 /// |
95 /// The type of the map that stores the edge lengths. |
95 /// The type of the map that stores the edge lengths. |
96 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
96 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
97 typedef _LengthMap LengthMap; |
97 typedef _LengthMap LengthMap; |
98 |
98 |
99 // The type of the length of the edges. |
99 // The type of the length of the edges. |
100 typedef typename _LengthMap::Value Value; |
100 typedef typename _LengthMap::Value Value; |
101 |
101 |
109 /// \brief The type of the map that stores the last edges of the |
109 /// \brief The type of the map that stores the last edges of the |
110 /// shortest paths. |
110 /// shortest paths. |
111 /// |
111 /// |
112 /// The type of the map that stores the last |
112 /// The type of the map that stores the last |
113 /// edges of the shortest paths. |
113 /// edges of the shortest paths. |
114 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
114 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
115 /// |
115 /// |
116 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
116 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
117 |
117 |
118 /// \brief Instantiates a PredMap. |
118 /// \brief Instantiates a PredMap. |
119 /// |
119 /// |
126 } |
126 } |
127 |
127 |
128 /// \brief The type of the map that stores the dists of the nodes. |
128 /// \brief The type of the map that stores the dists of the nodes. |
129 /// |
129 /// |
130 /// The type of the map that stores the dists of the nodes. |
130 /// The type of the map that stores the dists of the nodes. |
131 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
131 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
132 /// |
132 /// |
133 typedef typename Graph::template NodeMap<typename _LengthMap::Value> |
133 typedef typename Graph::template NodeMap<typename _LengthMap::Value> |
134 DistMap; |
134 DistMap; |
135 |
135 |
136 /// \brief Instantiates a DistMap. |
136 /// \brief Instantiates a DistMap. |
203 typedef _Graph Graph; |
203 typedef _Graph Graph; |
204 |
204 |
205 /// \brief The type of the map that stores the edge lengths. |
205 /// \brief The type of the map that stores the edge lengths. |
206 /// |
206 /// |
207 /// The type of the map that stores the edge lengths. |
207 /// The type of the map that stores the edge lengths. |
208 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
208 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
209 typedef _LengthMap LengthMap; |
209 typedef _LengthMap LengthMap; |
210 |
210 |
211 // The type of the length of the edges. |
211 // The type of the length of the edges. |
212 typedef typename _LengthMap::Value Value; |
212 typedef typename _LengthMap::Value Value; |
213 |
213 |
221 /// \brief The type of the map that stores the last edges of the |
221 /// \brief The type of the map that stores the last edges of the |
222 /// longest paths. |
222 /// longest paths. |
223 /// |
223 /// |
224 /// The type of the map that stores the last |
224 /// The type of the map that stores the last |
225 /// edges of the longest paths. |
225 /// edges of the longest paths. |
226 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
226 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
227 /// |
227 /// |
228 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
228 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
229 |
229 |
230 /// \brief Instantiates a PredMap. |
230 /// \brief Instantiates a PredMap. |
231 /// |
231 /// |
238 } |
238 } |
239 |
239 |
240 /// \brief The type of the map that stores the dists of the nodes. |
240 /// \brief The type of the map that stores the dists of the nodes. |
241 /// |
241 /// |
242 /// The type of the map that stores the dists of the nodes. |
242 /// The type of the map that stores the dists of the nodes. |
243 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
243 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
244 /// |
244 /// |
245 typedef typename Graph::template NodeMap<typename _LengthMap::Value> |
245 typedef typename Graph::template NodeMap<typename _LengthMap::Value> |
246 DistMap; |
246 DistMap; |
247 |
247 |
248 /// \brief Instantiates a DistMap. |
248 /// \brief Instantiates a DistMap. |
260 /// \brief %DagShortestPath algorithm class. |
260 /// \brief %DagShortestPath algorithm class. |
261 /// |
261 /// |
262 /// \ingroup flowalgs |
262 /// \ingroup flowalgs |
263 /// This class provides an efficient implementation of a Dag sortest path |
263 /// This class provides an efficient implementation of a Dag sortest path |
264 /// searching algorithm. The edge lengths are passed to the algorithm |
264 /// searching algorithm. The edge lengths are passed to the algorithm |
265 /// using a \ref concept::ReadMap "ReadMap", so it is easy to change it |
265 /// using a \ref concepts::ReadMap "ReadMap", so it is easy to change it |
266 /// to any kind of length. |
266 /// to any kind of length. |
267 /// |
267 /// |
268 /// The complexity of the algorithm is O(n + e). |
268 /// The complexity of the algorithm is O(n + e). |
269 /// |
269 /// |
270 /// The type of the length is determined by the |
270 /// The type of the length is determined by the |
271 /// \ref concept::ReadMap::Value "Value" of the length map. |
271 /// \ref concepts::ReadMap::Value "Value" of the length map. |
272 /// |
272 /// |
273 /// \param _Graph The graph type the algorithm runs on. The default value |
273 /// \param _Graph The graph type the algorithm runs on. The default value |
274 /// is \ref ListGraph. The value of _Graph is not used directly by |
274 /// is \ref ListGraph. The value of _Graph is not used directly by |
275 /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. |
275 /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. |
276 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
276 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
277 /// edges. The default map type is \ref concept::Graph::EdgeMap |
277 /// edges. The default map type is \ref concepts::Graph::EdgeMap |
278 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly |
278 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly |
279 /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. |
279 /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. |
280 /// \param _Traits Traits class to set various data types used by the |
280 /// \param _Traits Traits class to set various data types used by the |
281 /// algorithm. The default traits class is \ref DagShortestPathDefaultTraits |
281 /// algorithm. The default traits class is \ref DagShortestPathDefaultTraits |
282 /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>". See \ref |
282 /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>". See \ref |
809 typedef _Graph Graph; |
809 typedef _Graph Graph; |
810 |
810 |
811 /// \brief The type of the map that stores the edge lengths. |
811 /// \brief The type of the map that stores the edge lengths. |
812 /// |
812 /// |
813 /// The type of the map that stores the edge lengths. |
813 /// The type of the map that stores the edge lengths. |
814 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
814 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
815 typedef _LengthMap LengthMap; |
815 typedef _LengthMap LengthMap; |
816 |
816 |
817 /// \brief The value type of the length map. |
817 /// \brief The value type of the length map. |
818 typedef typename _LengthMap::Value Value; |
818 typedef typename _LengthMap::Value Value; |
819 |
819 |
827 /// \brief The type of the map that stores the last |
827 /// \brief The type of the map that stores the last |
828 /// edges of the shortest paths. |
828 /// edges of the shortest paths. |
829 /// |
829 /// |
830 /// The type of the map that stores the last |
830 /// The type of the map that stores the last |
831 /// edges of the shortest paths. |
831 /// edges of the shortest paths. |
832 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
832 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
833 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap; |
833 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap; |
834 |
834 |
835 /// \brief Instantiates a PredMap. |
835 /// \brief Instantiates a PredMap. |
836 /// |
836 /// |
837 /// This function instantiates a \ref PredMap. |
837 /// This function instantiates a \ref PredMap. |
839 return new PredMap(); |
839 return new PredMap(); |
840 } |
840 } |
841 /// \brief The type of the map that stores the dists of the nodes. |
841 /// \brief The type of the map that stores the dists of the nodes. |
842 /// |
842 /// |
843 /// The type of the map that stores the dists of the nodes. |
843 /// The type of the map that stores the dists of the nodes. |
844 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
844 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
845 typedef NullMap<typename Graph::Node, Value> DistMap; |
845 typedef NullMap<typename Graph::Node, Value> DistMap; |
846 /// \brief Instantiates a DistMap. |
846 /// \brief Instantiates a DistMap. |
847 /// |
847 /// |
848 /// This function instantiates a \ref DistMap. |
848 /// This function instantiates a \ref DistMap. |
849 static DistMap *createDistMap(const _Graph &) { |
849 static DistMap *createDistMap(const _Graph &) { |