[255] | 1 | // -*- C++ -*- |
---|
| 2 | #ifndef HUGO_DIJKSTRA_H |
---|
| 3 | #define HUGO_DIJKSTRA_H |
---|
| 4 | |
---|
[758] | 5 | ///\ingroup flowalgs |
---|
[255] | 6 | ///\file |
---|
| 7 | ///\brief Dijkstra algorithm. |
---|
| 8 | |
---|
[542] | 9 | #include <hugo/bin_heap.h> |
---|
| 10 | #include <hugo/invalid.h> |
---|
[255] | 11 | |
---|
| 12 | namespace hugo { |
---|
[385] | 13 | |
---|
[758] | 14 | /// \addtogroup flowalgs |
---|
[430] | 15 | /// @{ |
---|
| 16 | |
---|
[255] | 17 | ///%Dijkstra algorithm class. |
---|
| 18 | |
---|
| 19 | ///This class provides an efficient implementation of %Dijkstra algorithm. |
---|
| 20 | ///The edge lengths are passed to the algorithm using a |
---|
[880] | 21 | ///\ref skeleton::ReadMap "ReadMap", |
---|
[255] | 22 | ///so it is easy to change it to any kind of length. |
---|
| 23 | /// |
---|
[880] | 24 | ///The type of the length is determined by the |
---|
| 25 | ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. |
---|
[255] | 26 | /// |
---|
| 27 | ///It is also possible to change the underlying priority heap. |
---|
| 28 | /// |
---|
[584] | 29 | ///\param GR The graph type the algorithm runs on. |
---|
| 30 | ///\param LM This read-only |
---|
[385] | 31 | ///EdgeMap |
---|
| 32 | ///determines the |
---|
| 33 | ///lengths of the edges. It is read once for each edge, so the map |
---|
| 34 | ///may involve in relatively time consuming process to compute the edge |
---|
| 35 | ///length if it is necessary. The default map type is |
---|
[880] | 36 | ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>" |
---|
[385] | 37 | ///\param Heap The heap type used by the %Dijkstra |
---|
| 38 | ///algorithm. The default |
---|
| 39 | ///is using \ref BinHeap "binary heap". |
---|
[456] | 40 | /// |
---|
[689] | 41 | ///\author Jacint Szabo and Alpar Juttner |
---|
[693] | 42 | ///\todo We need a typedef-names should be standardized. (-: |
---|
[734] | 43 | ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap |
---|
| 44 | ///should not be fixed. (Problematic to solve). |
---|
[584] | 45 | |
---|
[255] | 46 | #ifdef DOXYGEN |
---|
[584] | 47 | template <typename GR, |
---|
| 48 | typename LM, |
---|
[255] | 49 | typename Heap> |
---|
| 50 | #else |
---|
[584] | 51 | template <typename GR, |
---|
| 52 | typename LM=typename GR::template EdgeMap<int>, |
---|
[532] | 53 | template <class,class,class,class> class Heap = BinHeap > |
---|
[255] | 54 | #endif |
---|
| 55 | class Dijkstra{ |
---|
| 56 | public: |
---|
[584] | 57 | ///The type of the underlying graph. |
---|
| 58 | typedef GR Graph; |
---|
[802] | 59 | ///. |
---|
[255] | 60 | typedef typename Graph::Node Node; |
---|
[802] | 61 | ///. |
---|
[255] | 62 | typedef typename Graph::NodeIt NodeIt; |
---|
[802] | 63 | ///. |
---|
[255] | 64 | typedef typename Graph::Edge Edge; |
---|
[802] | 65 | ///. |
---|
[255] | 66 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 67 | |
---|
[584] | 68 | ///The type of the length of the edges. |
---|
| 69 | typedef typename LM::ValueType ValueType; |
---|
[693] | 70 | ///The type of the map that stores the edge lengths. |
---|
[584] | 71 | typedef LM LengthMap; |
---|
[693] | 72 | ///\brief The type of the map that stores the last |
---|
[584] | 73 | ///edges of the shortest paths. |
---|
[433] | 74 | typedef typename Graph::template NodeMap<Edge> PredMap; |
---|
[693] | 75 | ///\brief The type of the map that stores the last but one |
---|
[584] | 76 | ///nodes of the shortest paths. |
---|
[433] | 77 | typedef typename Graph::template NodeMap<Node> PredNodeMap; |
---|
[693] | 78 | ///The type of the map that stores the dists of the nodes. |
---|
[433] | 79 | typedef typename Graph::template NodeMap<ValueType> DistMap; |
---|
[255] | 80 | |
---|
| 81 | private: |
---|
[802] | 82 | /// Pointer to the underlying graph. |
---|
[688] | 83 | const Graph *G; |
---|
[802] | 84 | /// Pointer to the length map |
---|
[688] | 85 | const LM *length; |
---|
[802] | 86 | ///Pointer to the map of predecessors edges. |
---|
[688] | 87 | PredMap *predecessor; |
---|
[802] | 88 | ///Indicates if \ref predecessor is locally allocated (\c true) or not. |
---|
[688] | 89 | bool local_predecessor; |
---|
[802] | 90 | ///Pointer to the map of predecessors nodes. |
---|
[688] | 91 | PredNodeMap *pred_node; |
---|
[802] | 92 | ///Indicates if \ref pred_node is locally allocated (\c true) or not. |
---|
[688] | 93 | bool local_pred_node; |
---|
[802] | 94 | ///Pointer to the map of distances. |
---|
[688] | 95 | DistMap *distance; |
---|
[802] | 96 | ///Indicates if \ref distance is locally allocated (\c true) or not. |
---|
[688] | 97 | bool local_distance; |
---|
| 98 | |
---|
[802] | 99 | ///The source node of the last execution. |
---|
[774] | 100 | Node source; |
---|
| 101 | |
---|
[785] | 102 | ///Initializes the maps. |
---|
[688] | 103 | |
---|
[694] | 104 | ///\todo Error if \c G or are \c NULL. What about \c length? |
---|
[688] | 105 | ///\todo Better memory allocation (instead of new). |
---|
| 106 | void init_maps() |
---|
| 107 | { |
---|
| 108 | if(!predecessor) { |
---|
| 109 | local_predecessor = true; |
---|
| 110 | predecessor = new PredMap(*G); |
---|
| 111 | } |
---|
| 112 | if(!pred_node) { |
---|
| 113 | local_pred_node = true; |
---|
| 114 | pred_node = new PredNodeMap(*G); |
---|
| 115 | } |
---|
| 116 | if(!distance) { |
---|
| 117 | local_distance = true; |
---|
| 118 | distance = new DistMap(*G); |
---|
| 119 | } |
---|
| 120 | } |
---|
[255] | 121 | |
---|
| 122 | public : |
---|
[802] | 123 | ///Constructor. |
---|
[255] | 124 | |
---|
[802] | 125 | ///\param _G the graph the algorithm will run on. |
---|
| 126 | ///\param _length the length map used by the algorithm. |
---|
[584] | 127 | Dijkstra(const Graph& _G, const LM& _length) : |
---|
[688] | 128 | G(&_G), length(&_length), |
---|
[707] | 129 | predecessor(NULL), local_predecessor(false), |
---|
| 130 | pred_node(NULL), local_pred_node(false), |
---|
| 131 | distance(NULL), local_distance(false) |
---|
[688] | 132 | { } |
---|
| 133 | |
---|
[802] | 134 | ///Destructor. |
---|
[688] | 135 | ~Dijkstra() |
---|
| 136 | { |
---|
| 137 | if(local_predecessor) delete predecessor; |
---|
| 138 | if(local_pred_node) delete pred_node; |
---|
| 139 | if(local_distance) delete distance; |
---|
| 140 | } |
---|
| 141 | |
---|
| 142 | ///Sets the length map. |
---|
| 143 | |
---|
| 144 | ///Sets the length map. |
---|
| 145 | ///\return <tt> (*this) </tt> |
---|
| 146 | Dijkstra &setLengthMap(const LM &m) |
---|
| 147 | { |
---|
| 148 | length = &m; |
---|
| 149 | return *this; |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | ///Sets the map storing the predecessor edges. |
---|
| 153 | |
---|
| 154 | ///Sets the map storing the predecessor edges. |
---|
| 155 | ///If you don't use this function before calling \ref run(), |
---|
| 156 | ///it will allocate one. The destuctor deallocates this |
---|
| 157 | ///automatically allocated map, of course. |
---|
| 158 | ///\return <tt> (*this) </tt> |
---|
| 159 | Dijkstra &setPredMap(PredMap &m) |
---|
| 160 | { |
---|
| 161 | if(local_predecessor) { |
---|
| 162 | delete predecessor; |
---|
| 163 | local_predecessor=false; |
---|
| 164 | } |
---|
| 165 | predecessor = &m; |
---|
| 166 | return *this; |
---|
| 167 | } |
---|
| 168 | |
---|
| 169 | ///Sets the map storing the predecessor nodes. |
---|
| 170 | |
---|
| 171 | ///Sets the map storing the predecessor nodes. |
---|
| 172 | ///If you don't use this function before calling \ref run(), |
---|
| 173 | ///it will allocate one. The destuctor deallocates this |
---|
| 174 | ///automatically allocated map, of course. |
---|
| 175 | ///\return <tt> (*this) </tt> |
---|
| 176 | Dijkstra &setPredNodeMap(PredNodeMap &m) |
---|
| 177 | { |
---|
| 178 | if(local_pred_node) { |
---|
| 179 | delete pred_node; |
---|
| 180 | local_pred_node=false; |
---|
| 181 | } |
---|
| 182 | pred_node = &m; |
---|
| 183 | return *this; |
---|
| 184 | } |
---|
| 185 | |
---|
| 186 | ///Sets the map storing the distances calculated by the algorithm. |
---|
| 187 | |
---|
| 188 | ///Sets the map storing the distances calculated by the algorithm. |
---|
| 189 | ///If you don't use this function before calling \ref run(), |
---|
| 190 | ///it will allocate one. The destuctor deallocates this |
---|
| 191 | ///automatically allocated map, of course. |
---|
| 192 | ///\return <tt> (*this) </tt> |
---|
| 193 | Dijkstra &setDistMap(DistMap &m) |
---|
| 194 | { |
---|
| 195 | if(local_distance) { |
---|
| 196 | delete distance; |
---|
| 197 | local_distance=false; |
---|
| 198 | } |
---|
| 199 | distance = &m; |
---|
| 200 | return *this; |
---|
| 201 | } |
---|
[255] | 202 | |
---|
[694] | 203 | ///Runs %Dijkstra algorithm from node \c s. |
---|
| 204 | |
---|
| 205 | ///This method runs the %Dijkstra algorithm from a root node \c s |
---|
| 206 | ///in order to |
---|
| 207 | ///compute the |
---|
| 208 | ///shortest path to each node. The algorithm computes |
---|
| 209 | ///- The shortest path tree. |
---|
| 210 | ///- The distance of each node from the root. |
---|
| 211 | |
---|
| 212 | void run(Node s) { |
---|
| 213 | |
---|
| 214 | init_maps(); |
---|
| 215 | |
---|
[774] | 216 | source = s; |
---|
| 217 | |
---|
| 218 | for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
---|
[694] | 219 | predecessor->set(u,INVALID); |
---|
| 220 | pred_node->set(u,INVALID); |
---|
| 221 | } |
---|
| 222 | |
---|
| 223 | typename GR::template NodeMap<int> heap_map(*G,-1); |
---|
| 224 | |
---|
| 225 | typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, |
---|
| 226 | std::less<ValueType> > |
---|
| 227 | HeapType; |
---|
| 228 | |
---|
| 229 | HeapType heap(heap_map); |
---|
| 230 | |
---|
| 231 | heap.push(s,0); |
---|
| 232 | |
---|
| 233 | while ( !heap.empty() ) { |
---|
| 234 | |
---|
| 235 | Node v=heap.top(); |
---|
| 236 | ValueType oldvalue=heap[v]; |
---|
| 237 | heap.pop(); |
---|
| 238 | distance->set(v, oldvalue); |
---|
| 239 | |
---|
| 240 | |
---|
[774] | 241 | for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
---|
| 242 | Node w=G->head(e); |
---|
[694] | 243 | switch(heap.state(w)) { |
---|
| 244 | case HeapType::PRE_HEAP: |
---|
| 245 | heap.push(w,oldvalue+(*length)[e]); |
---|
| 246 | predecessor->set(w,e); |
---|
| 247 | pred_node->set(w,v); |
---|
| 248 | break; |
---|
| 249 | case HeapType::IN_HEAP: |
---|
| 250 | if ( oldvalue+(*length)[e] < heap[w] ) { |
---|
| 251 | heap.decrease(w, oldvalue+(*length)[e]); |
---|
| 252 | predecessor->set(w,e); |
---|
| 253 | pred_node->set(w,v); |
---|
| 254 | } |
---|
| 255 | break; |
---|
| 256 | case HeapType::POST_HEAP: |
---|
| 257 | break; |
---|
| 258 | } |
---|
| 259 | } |
---|
| 260 | } |
---|
| 261 | } |
---|
[255] | 262 | |
---|
[385] | 263 | ///The distance of a node from the root. |
---|
[255] | 264 | |
---|
[385] | 265 | ///Returns the distance of a node from the root. |
---|
[255] | 266 | ///\pre \ref run() must be called before using this function. |
---|
[385] | 267 | ///\warning If node \c v in unreachable from the root the return value |
---|
[255] | 268 | ///of this funcion is undefined. |
---|
[688] | 269 | ValueType dist(Node v) const { return (*distance)[v]; } |
---|
[373] | 270 | |
---|
[584] | 271 | ///Returns the 'previous edge' of the shortest path tree. |
---|
[255] | 272 | |
---|
[584] | 273 | ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
---|
[785] | 274 | ///i.e. it returns the last edge of a shortest path from the root to \c |
---|
[688] | 275 | ///v. It is \ref INVALID |
---|
| 276 | ///if \c v is unreachable from the root or if \c v=s. The |
---|
[385] | 277 | ///shortest path tree used here is equal to the shortest path tree used in |
---|
| 278 | ///\ref predNode(Node v). \pre \ref run() must be called before using |
---|
| 279 | ///this function. |
---|
[780] | 280 | ///\todo predEdge could be a better name. |
---|
[688] | 281 | Edge pred(Node v) const { return (*predecessor)[v]; } |
---|
[373] | 282 | |
---|
[584] | 283 | ///Returns the 'previous node' of the shortest path tree. |
---|
[255] | 284 | |
---|
[584] | 285 | ///For a node \c v it returns the 'previous node' of the shortest path tree, |
---|
[385] | 286 | ///i.e. it returns the last but one node from a shortest path from the |
---|
| 287 | ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
---|
| 288 | ///\c v=s. The shortest path tree used here is equal to the shortest path |
---|
| 289 | ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
---|
| 290 | ///using this function. |
---|
[688] | 291 | Node predNode(Node v) const { return (*pred_node)[v]; } |
---|
[255] | 292 | |
---|
| 293 | ///Returns a reference to the NodeMap of distances. |
---|
| 294 | |
---|
[385] | 295 | ///Returns a reference to the NodeMap of distances. \pre \ref run() must |
---|
| 296 | ///be called before using this function. |
---|
[688] | 297 | const DistMap &distMap() const { return *distance;} |
---|
[385] | 298 | |
---|
[255] | 299 | ///Returns a reference to the shortest path tree map. |
---|
| 300 | |
---|
| 301 | ///Returns a reference to the NodeMap of the edges of the |
---|
| 302 | ///shortest path tree. |
---|
| 303 | ///\pre \ref run() must be called before using this function. |
---|
[688] | 304 | const PredMap &predMap() const { return *predecessor;} |
---|
[385] | 305 | |
---|
| 306 | ///Returns a reference to the map of nodes of shortest paths. |
---|
[255] | 307 | |
---|
| 308 | ///Returns a reference to the NodeMap of the last but one nodes of the |
---|
[385] | 309 | ///shortest path tree. |
---|
[255] | 310 | ///\pre \ref run() must be called before using this function. |
---|
[688] | 311 | const PredNodeMap &predNodeMap() const { return *pred_node;} |
---|
[255] | 312 | |
---|
[385] | 313 | ///Checks if a node is reachable from the root. |
---|
[255] | 314 | |
---|
[385] | 315 | ///Returns \c true if \c v is reachable from the root. |
---|
[802] | 316 | ///\note The root node is reported to be reached! |
---|
[255] | 317 | ///\pre \ref run() must be called before using this function. |
---|
[385] | 318 | /// |
---|
[780] | 319 | bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
---|
[255] | 320 | |
---|
| 321 | }; |
---|
| 322 | |
---|
[430] | 323 | /// @} |
---|
[255] | 324 | |
---|
| 325 | } //END OF NAMESPACE HUGO |
---|
| 326 | |
---|
| 327 | #endif |
---|
| 328 | |
---|
| 329 | |
---|