40 { |
40 { |
41 ///The graph type the algorithm runs on. |
41 ///The graph type the algorithm runs on. |
42 typedef GR Graph; |
42 typedef GR Graph; |
43 ///The type of the map that stores the edge lengths. |
43 ///The type of the map that stores the edge lengths. |
44 |
44 |
45 ///It must meet the \ref ReadMap concept. |
45 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
46 /// |
46 /// |
47 typedef LM LengthMap; |
47 typedef LM LengthMap; |
48 //The type of the length of the edges. |
48 //The type of the length of the edges. |
49 typedef typename LM::ValueType ValueType; |
49 typedef typename LM::ValueType ValueType; |
50 ///The heap type used by Dijkstra algorithm. |
50 ///The heap type used by Dijkstra algorithm. |
|
51 |
|
52 ///The heap type used by Dijkstra algorithm. |
|
53 /// |
|
54 ///\sa BinHeap |
|
55 ///\sa Dijkstra |
51 typedef BinHeap<typename Graph::Node, |
56 typedef BinHeap<typename Graph::Node, |
52 typename LM::ValueType, |
57 typename LM::ValueType, |
53 typename GR::template NodeMap<int>, |
58 typename GR::template NodeMap<int>, |
54 std::less<ValueType> > Heap; |
59 std::less<ValueType> > Heap; |
55 |
60 |
56 ///\brief The type of the map that stores the last |
61 ///\brief The type of the map that stores the last |
57 ///edges of the shortest paths. |
62 ///edges of the shortest paths. |
58 /// |
63 /// |
59 ///It must meet the \ref WriteMap concept. |
64 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
60 /// |
65 /// |
61 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
66 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
62 ///Instantiates a PredMap. |
67 ///Instantiates a PredMap. |
63 |
68 |
64 ///\todo Please document... |
69 ///\todo Please document... |
68 return new PredMap(G); |
73 return new PredMap(G); |
69 } |
74 } |
70 ///\brief The type of the map that stores the last but one |
75 ///\brief The type of the map that stores the last but one |
71 ///nodes of the shortest paths. |
76 ///nodes of the shortest paths. |
72 /// |
77 /// |
73 ///It must meet the \ref WriteMap concept. |
78 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
74 /// |
79 /// |
75 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap; |
80 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap; |
76 ///Instantiates a PredNodeMap. |
81 ///Instantiates a PredNodeMap. |
77 |
82 |
78 ///\todo Please document... |
83 ///\todo Please document... |
79 /// |
84 /// |
80 static PredNodeMap *createPredNodeMap(const GR &G) |
85 static PredNodeMap *createPredNodeMap(const GR &G) |
81 { |
86 { |
82 return new PredNodeMap(G); |
87 return new PredNodeMap(G); |
83 } |
88 } |
84 ///The type of the map that stores the dists of the nodes. |
89 ///The type of the map that stores the dists of the nodes. |
85 |
90 |
86 ///It must meet the \ref WriteMap concept. |
91 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
87 /// |
92 /// |
88 typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap; |
93 typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap; |
89 ///Instantiates a DistMap. |
94 ///Instantiates a DistMap. |
90 |
95 |
91 ///\todo Please document... |
96 ///\todo Please document... |
164 typedef typename TR::PredNodeMap PredNodeMap; |
169 typedef typename TR::PredNodeMap PredNodeMap; |
165 ///The type of the map that stores the dists of the nodes. |
170 ///The type of the map that stores the dists of the nodes. |
166 typedef typename TR::DistMap DistMap; |
171 typedef typename TR::DistMap DistMap; |
167 ///The heap type used by the dijkstra algorithm. |
172 ///The heap type used by the dijkstra algorithm. |
168 typedef typename TR::Heap Heap; |
173 typedef typename TR::Heap Heap; |
169 |
|
170 private: |
174 private: |
171 /// Pointer to the underlying graph. |
175 /// Pointer to the underlying graph. |
172 const Graph *G; |
176 const Graph *G; |
173 /// Pointer to the length map |
177 /// Pointer to the length map |
174 const LengthMap *length; |
178 const LengthMap *length; |