24 */ |
25 */ |
25 |
26 |
26 #ifndef HUGO_DIJKSTRA_H |
27 #ifndef HUGO_DIJKSTRA_H |
27 #define HUGO_DIJKSTRA_H |
28 #define HUGO_DIJKSTRA_H |
28 |
29 |
|
30 ///\file |
|
31 ///\brief Dijkstra algorithm. |
|
32 |
29 #include <fib_heap.h> |
33 #include <fib_heap.h> |
|
34 #include <bin_heap.h> |
30 #include <invalid.h> |
35 #include <invalid.h> |
31 |
36 |
32 namespace hugo { |
37 namespace hugo { |
33 |
38 |
34 template <typename Graph, typename T, |
39 //Alpar: Changed the order of the parameters |
35 typename Heap=FibHeap<typename Graph::Node, T, |
40 |
36 typename Graph::NodeMap<int> >, |
41 ///%Dijkstra algorithm class. |
37 typename LengthMap=typename Graph::EdgeMap<T> > |
42 |
|
43 ///This class provides an efficient implementation of %Dijkstra algorithm. |
|
44 ///The edge lengths are passed to the algorithm using a |
|
45 ///\ref ReadMapSkeleton "readable map", |
|
46 ///so it is easy to change it to any kind of length. |
|
47 /// |
|
48 ///The type of the length is determined by the \c ValueType of the length map. |
|
49 /// |
|
50 ///It is also possible to change the underlying priority heap. |
|
51 /// |
|
52 ///\param Graph The graph type the algorithm runs on. |
|
53 ///\param LengthMap This read-only |
|
54 ///EdgeMap |
|
55 ///determines the |
|
56 ///lengths of the edges. It is read once for each edge, so the map |
|
57 ///may involve in relatively time consuming process to compute the edge |
|
58 ///length if it is necessary. The default map type is |
|
59 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" |
|
60 ///\param Heap The heap type used by the %Dijkstra |
|
61 ///algorithm. The default |
|
62 ///is using \ref BinHeap "binary heap". |
|
63 |
|
64 #ifdef DOXYGEN |
|
65 template <typename Graph, |
|
66 typename LengthMap, |
|
67 typename Heap> |
|
68 #else |
|
69 template <typename Graph, |
|
70 typename LengthMap=typename Graph::EdgeMap<int>, |
|
71 template <class,class,class> class Heap = BinHeap > |
|
72 #endif |
38 class Dijkstra{ |
73 class Dijkstra{ |
|
74 public: |
39 typedef typename Graph::Node Node; |
75 typedef typename Graph::Node Node; |
40 typedef typename Graph::NodeIt NodeIt; |
76 typedef typename Graph::NodeIt NodeIt; |
41 typedef typename Graph::Edge Edge; |
77 typedef typename Graph::Edge Edge; |
42 typedef typename Graph::OutEdgeIt OutEdgeIt; |
78 typedef typename Graph::OutEdgeIt OutEdgeIt; |
43 |
79 |
|
80 typedef typename LengthMap::ValueType ValueType; |
|
81 typedef typename Graph::NodeMap<Edge> PredMap; |
|
82 typedef typename Graph::NodeMap<Node> PredNodeMap; |
|
83 typedef typename Graph::NodeMap<ValueType> DistMap; |
|
84 |
|
85 private: |
44 const Graph& G; |
86 const Graph& G; |
45 const LengthMap& length; |
87 const LengthMap& length; |
46 typename Graph::NodeMap<Edge> predecessor; |
88 PredMap predecessor; |
47 typename Graph::NodeMap<T> distance; |
89 PredNodeMap pred_node; |
48 //FIXME: |
90 DistMap distance; |
49 typename Graph::NodeMap<bool> reach; |
|
50 //typename Graph::NodeMap<int> reach; |
|
51 |
91 |
52 public : |
92 public : |
53 |
93 |
54 /* |
94 Dijkstra(Graph& _G, LengthMap& _length) : |
55 The distance of the nodes is 0. |
95 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
56 */ |
96 |
57 Dijkstra(Graph& _G, LengthMap& _length) : G(_G), |
97 void run(Node s); |
58 length(_length), predecessor(_G), distance(_G), reach(_G) { } |
98 |
59 |
99 ///The distance of a node from the source. |
60 |
100 |
61 void run(Node s) { |
101 ///Returns the distance of a node from the source. |
62 |
102 ///\pre \ref run() must be called before using this function. |
63 NodeIt u; |
103 ///\warning If node \c v in unreachable from the source the return value |
64 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
104 ///of this funcion is undefined. |
65 predecessor.set(u,INVALID); |
105 ValueType dist(Node v) const { return distance[v]; } |
66 distance.set(u,0); |
106 ///Returns the edges of the shortest path tree. |
67 reach.set(u,false); |
107 |
68 } |
108 ///For a node \c v it returns the last edge of the shortest path |
69 |
109 ///from the source to \c v or INVALID if \c v is unreachable |
70 //FIXME: |
110 ///from the source. |
71 typename Graph::NodeMap<bool> scanned(G,false); |
111 ///\pre \ref run() must be called before using this function. |
72 //typename Graph::NodeMap<int> scanned(G,false); |
112 Edge pred(Node v) const { return predecessor[v]; } |
73 typename Graph::NodeMap<int> heap_map(G,-1); |
113 ///Returns the nodes of the shortest paths. |
74 |
114 |
75 Heap heap(heap_map); |
115 ///For a node \c v it returns the last but one node of the shortest path |
76 |
116 ///from the source to \c v or INVALID if \c v is unreachable |
77 heap.push(s,0); |
117 ///from the source. |
78 reach.set(s, true); |
118 ///\pre \ref run() must be called before using this function. |
79 |
119 Node predNode(Node v) const { return pred_node[v]; } |
|
120 |
|
121 ///Returns a reference to the NodeMap of distances. |
|
122 |
|
123 ///\pre \ref run() must be called before using this function. |
|
124 /// |
|
125 const DistMap &distMap() const { return distance;} |
|
126 ///Returns a reference to the shortest path tree map. |
|
127 |
|
128 ///Returns a reference to the NodeMap of the edges of the |
|
129 ///shortest path tree. |
|
130 ///\pre \ref run() must be called before using this function. |
|
131 const PredMap &predMap() const { return predecessor;} |
|
132 ///Returns a reference to the map of nodes of shortest paths. |
|
133 |
|
134 ///Returns a reference to the NodeMap of the last but one nodes of the |
|
135 ///shortest paths. |
|
136 ///\pre \ref run() must be called before using this function. |
|
137 const PredNodeMap &predNodeMap() const { return pred_node;} |
|
138 |
|
139 ///Checks if a node is reachable from the source. |
|
140 |
|
141 ///Returns \c true if \c v is reachable from the source. |
|
142 ///\warning the source node is reported to be unreached! |
|
143 ///\todo Is this what we want? |
|
144 ///\pre \ref run() must be called before using this function. |
|
145 /// |
|
146 bool reached(Node v) { return G.valid(predecessor[v]); } |
|
147 |
|
148 }; |
|
149 |
|
150 |
|
151 // ********************************************************************** |
|
152 // IMPLEMENTATIONS |
|
153 // ********************************************************************** |
|
154 |
|
155 ///Runs %Dijkstra algorithm from node the source. |
|
156 |
|
157 ///This method runs the %Dijkstra algorithm from a source node \c s |
|
158 ///in order to |
|
159 ///compute the |
|
160 ///shortest path to each node. The algorithm computes |
|
161 ///- The shortest path tree. |
|
162 ///- The distance of each node from the source. |
|
163 template <typename Graph, typename LengthMap, |
|
164 template<class,class,class> class Heap > |
|
165 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
|
166 |
|
167 NodeIt u; |
|
168 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
|
169 predecessor.set(u,INVALID); |
|
170 pred_node.set(u,INVALID); |
|
171 // If a node is unreacheable, then why should be the dist=0? |
|
172 // distance.set(u,0); |
|
173 // reach.set(u,false); |
|
174 } |
|
175 |
|
176 typename Graph::NodeMap<int> heap_map(G,-1); |
|
177 |
|
178 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); |
|
179 |
|
180 heap.push(s,0); |
|
181 |
80 while ( !heap.empty() ) { |
182 while ( !heap.empty() ) { |
81 |
183 |
82 Node v=heap.top(); |
184 Node v=heap.top(); |
83 T oldvalue=heap.get(v); |
185 ValueType oldvalue=heap[v]; |
84 heap.pop(); |
186 heap.pop(); |
85 distance.set(v, oldvalue); |
187 distance.set(v, oldvalue); |
86 scanned.set(v,true); |
188 |
87 |
189 { //FIXME this bracket is for e to be local |
88 OutEdgeIt e; |
190 OutEdgeIt e; |
89 for( G.first(e,v); G.valid(e); G.next(e)) { |
191 for(G.first(e, v); |
|
192 G.valid(e); G.next(e)) { |
90 Node w=G.head(e); |
193 Node w=G.head(e); |
91 |
194 |
92 if ( !scanned[w] ) { |
195 switch(heap.state(w)) { |
93 if ( !reach[w] ) { |
196 case heap.PRE_HEAP: |
94 reach.set(w,true); |
197 heap.push(w,oldvalue+length[e]); |
95 heap.push(w,oldvalue+length[e]); |
198 predecessor.set(w,e); |
|
199 pred_node.set(w,v); |
|
200 break; |
|
201 case heap.IN_HEAP: |
|
202 if ( oldvalue+length[e] < heap[w] ) { |
|
203 heap.decrease(w, oldvalue+length[e]); |
96 predecessor.set(w,e); |
204 predecessor.set(w,e); |
97 } else if ( oldvalue+length[e] < heap.get(w) ) { |
205 pred_node.set(w,v); |
98 predecessor.set(w,e); |
|
99 heap.decrease(w, oldvalue+length[e]); |
|
100 } |
206 } |
|
207 break; |
|
208 case heap.POST_HEAP: |
|
209 break; |
101 } |
210 } |
102 } |
211 } |
|
212 } //FIXME tis bracket |
103 } |
213 } |
104 } |
214 } |
105 |
215 |
106 T dist(Node v) { |
216 } //END OF NAMESPACE HUGO |
107 return distance[v]; |
|
108 } |
|
109 |
|
110 Edge pred(Node v) { |
|
111 return predecessor[v]; |
|
112 } |
|
113 |
|
114 bool reached(Node v) { |
|
115 return reach[v]; |
|
116 } |
|
117 |
|
118 }; |
|
119 |
|
120 } |
|
121 |
217 |
122 #endif |
218 #endif |
123 |
219 |
124 |
220 |