32 |
32 |
33 namespace hugo { |
33 namespace hugo { |
34 |
34 |
35 //Alpar: Changed the order of the parameters |
35 //Alpar: Changed the order of the parameters |
36 |
36 |
37 ///Dijkstra algorithm class. |
37 ///%Dijkstra algorithm class. |
38 |
38 |
39 ///This class provides an efficient implementation of Dijkstra algorithm. |
39 ///This class provides an efficient implementation of %Dijkstra algorithm. |
40 ///The edge lengths are passed to the algorithm using a |
40 ///The edge lengths are passed to the algorithm using a |
41 ///\ref ReadMapSkeleton "readable map", |
41 ///\ref ReadMapSkeleton "readable map", |
42 ///so it is easy to change it to any kind of length. |
42 ///so it is easy to change it to any kind of length. |
43 /// |
43 /// |
44 ///The type of the length is determined by the \c ValueType of the length map. |
44 ///The type of the length is determined by the \c ValueType of the length map. |
48 ///\param Graph The graph type the algorithm runs on. |
48 ///\param Graph The graph type the algorithm runs on. |
49 ///\param LengthMap This read-only EdgeMap determines the |
49 ///\param LengthMap This read-only EdgeMap determines the |
50 ///lengths of the edges. It is read once for each edge, so the map |
50 ///lengths of the edges. It is read once for each edge, so the map |
51 ///may involve in relatively time consuming process to compute the edge |
51 ///may involve in relatively time consuming process to compute the edge |
52 ///length if it is necessary. |
52 ///length if it is necessary. |
53 ///\param Heap The heap type used by the Dijkstra |
53 ///\param Heap The heap type used by the %Dijkstra |
54 ///algorithm. The default |
54 ///algorithm. The default |
55 ///is using \ref BinHeap "binary heap". |
55 ///is using \ref BinHeap "binary heap". |
56 template <typename Graph, |
56 template <typename Graph, |
57 typename LengthMap=typename Graph::EdgeMap<int>, |
57 typename LengthMap=typename Graph::EdgeMap<int>, |
58 typename Heap=BinHeap <typename Graph::Node, |
58 typename Heap=BinHeap <typename Graph::Node, |
95 |
95 |
96 ///The distance of a node from the source. |
96 ///The distance of a node from the source. |
97 |
97 |
98 ///Returns the distance of a node from the source. |
98 ///Returns the distance of a node from the source. |
99 ///\pre \ref run() must be called before using this function. |
99 ///\pre \ref run() must be called before using this function. |
100 ///\warning If node \c v in unreachable from \c s the return value |
100 ///\warning If node \c v in unreachable from the source the return value |
101 ///of this funcion is undefined. |
101 ///of this funcion is undefined. |
102 ValueType dist(Node v) const { return distance[v]; } |
102 ValueType dist(Node v) const { return distance[v]; } |
103 ///Returns the edges of the shortest path tree. |
103 ///Returns the edges of the shortest path tree. |
104 |
104 |
105 ///For a node \c v it returns the last edge of the shortest path |
105 ///For a node \c v it returns the last edge of the shortest path |
106 ///from \c s to \c v or INVALID if \c v is unreachable from \c s. |
106 ///from the source to \c v or INVALID if \c v is unreachable |
|
107 ///from the source. |
107 ///\pre \ref run() must be called before using this function. |
108 ///\pre \ref run() must be called before using this function. |
108 Edge pred(Node v) const { return predecessor[v]; } |
109 Edge pred(Node v) const { return predecessor[v]; } |
109 ///Returns the nodes of the shortest paths. |
110 ///Returns the nodes of the shortest paths. |
110 |
111 |
111 ///For a node \c v it returns the last but one node of the shortest path |
112 ///For a node \c v it returns the last but one node of the shortest path |
112 ///from \c s to \c v or INVALID if \c v is unreachable from \c s. |
113 ///from the source to \c v or INVALID if \c v is unreachable |
|
114 ///from the source. |
113 ///\pre \ref run() must be called before using this function. |
115 ///\pre \ref run() must be called before using this function. |
114 Node predNode(Node v) const { return pred_node[v]; } |
116 Node predNode(Node v) const { return pred_node[v]; } |
115 |
117 |
116 ///Returns a reference to the NodeMap of distances. |
118 ///Returns a reference to the NodeMap of distances. |
117 |
119 |
131 ///\pre \ref run() must be called before using this function. |
133 ///\pre \ref run() must be called before using this function. |
132 const PredNodeMap &predNodeMap() const { return pred_node;} |
134 const PredNodeMap &predNodeMap() const { return pred_node;} |
133 |
135 |
134 // bool reached(Node v) { return reach[v]; } |
136 // bool reached(Node v) { return reach[v]; } |
135 |
137 |
136 ///Chech if a node is reachable from \c s. |
138 ///Chechs if a node is reachable from the source. |
137 |
139 |
138 ///Returns \c true if \c v is reachable from \c s. |
140 ///Returns \c true if \c v is reachable from the source. |
139 ///\warning \c s is reported to be unreached! |
141 ///\warning the source node is reported to be unreached! |
140 ///\todo Is this what we want? |
142 ///\todo Is this what we want? |
141 ///\pre \ref run() must be called before using this function. |
143 ///\pre \ref run() must be called before using this function. |
142 /// |
144 /// |
143 bool reached(Node v) { return G.valid(predecessor[v]); } |
145 bool reached(Node v) { return G.valid(predecessor[v]); } |
144 |
146 |
147 |
149 |
148 // ********************************************************************** |
150 // ********************************************************************** |
149 // IMPLEMENTATIONS |
151 // IMPLEMENTATIONS |
150 // ********************************************************************** |
152 // ********************************************************************** |
151 |
153 |
152 ///Runs Dijkstra algorithm from node \c s. |
154 ///Runs %Dijkstra algorithm from node the source. |
153 |
155 |
154 ///This method runs the Dijkstra algorithm from node \c s in order to |
156 ///This method runs the %Dijkstra algorithm from a source node \c s |
|
157 ///in order to |
155 ///compute the |
158 ///compute the |
156 ///shortest path to each node. The algorithm computes |
159 ///shortest path to each node. The algorithm computes |
157 ///- The shortest path tree. |
160 ///- The shortest path tree. |
158 ///- The distance of each node. |
161 ///- The distance of each node from the source. |
159 template <typename Graph, typename LengthMap, typename Heap > |
162 template <typename Graph, typename LengthMap, typename Heap > |
160 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
163 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
161 |
164 |
162 NodeIt u; |
165 NodeIt u; |
163 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
166 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |