|
alpar@100
|
1 |
/* -*- C++ -*-
|
|
alpar@100
|
2 |
*
|
|
alpar@100
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
|
alpar@100
|
4 |
*
|
|
alpar@100
|
5 |
* Copyright (C) 2003-2008
|
|
alpar@100
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
|
alpar@100
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
|
alpar@100
|
8 |
*
|
|
alpar@100
|
9 |
* Permission to use, modify and distribute this software is granted
|
|
alpar@100
|
10 |
* provided that this copyright notice appears in all copies. For
|
|
alpar@100
|
11 |
* precise terms see the accompanying LICENSE file.
|
|
alpar@100
|
12 |
*
|
|
alpar@100
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
|
alpar@100
|
14 |
* express or implied, and with no claim as to its suitability for any
|
|
alpar@100
|
15 |
* purpose.
|
|
alpar@100
|
16 |
*
|
|
alpar@100
|
17 |
*/
|
|
alpar@100
|
18 |
|
|
alpar@100
|
19 |
#ifndef LEMON_DIJKSTRA_H
|
|
alpar@100
|
20 |
#define LEMON_DIJKSTRA_H
|
|
alpar@100
|
21 |
|
|
alpar@100
|
22 |
///\ingroup shortest_path
|
|
alpar@100
|
23 |
///\file
|
|
alpar@100
|
24 |
///\brief Dijkstra algorithm.
|
|
alpar@100
|
25 |
|
|
alpar@184
|
26 |
#include <limits>
|
|
kpeter@169
|
27 |
#include <lemon/list_graph.h>
|
|
alpar@100
|
28 |
#include <lemon/bin_heap.h>
|
|
alpar@100
|
29 |
#include <lemon/bits/path_dump.h>
|
|
alpar@100
|
30 |
#include <lemon/bits/invalid.h>
|
|
alpar@100
|
31 |
#include <lemon/error.h>
|
|
alpar@100
|
32 |
#include <lemon/maps.h>
|
|
alpar@100
|
33 |
|
|
alpar@100
|
34 |
namespace lemon {
|
|
alpar@100
|
35 |
|
|
alpar@100
|
36 |
/// \brief Default OperationTraits for the Dijkstra algorithm class.
|
|
alpar@100
|
37 |
///
|
|
alpar@100
|
38 |
/// It defines all computational operations and constants which are
|
|
alpar@100
|
39 |
/// used in the Dijkstra algorithm.
|
|
alpar@100
|
40 |
template <typename Value>
|
|
alpar@100
|
41 |
struct DijkstraDefaultOperationTraits {
|
|
alpar@100
|
42 |
/// \brief Gives back the zero value of the type.
|
|
alpar@100
|
43 |
static Value zero() {
|
|
alpar@100
|
44 |
return static_cast<Value>(0);
|
|
alpar@100
|
45 |
}
|
|
alpar@100
|
46 |
/// \brief Gives back the sum of the given two elements.
|
|
alpar@100
|
47 |
static Value plus(const Value& left, const Value& right) {
|
|
alpar@100
|
48 |
return left + right;
|
|
alpar@100
|
49 |
}
|
|
alpar@100
|
50 |
/// \brief Gives back true only if the first value less than the second.
|
|
alpar@100
|
51 |
static bool less(const Value& left, const Value& right) {
|
|
alpar@100
|
52 |
return left < right;
|
|
alpar@100
|
53 |
}
|
|
alpar@100
|
54 |
};
|
|
alpar@100
|
55 |
|
|
alpar@100
|
56 |
/// \brief Widest path OperationTraits for the Dijkstra algorithm class.
|
|
alpar@100
|
57 |
///
|
|
alpar@100
|
58 |
/// It defines all computational operations and constants which are
|
|
alpar@100
|
59 |
/// used in the Dijkstra algorithm for widest path computation.
|
|
alpar@100
|
60 |
template <typename Value>
|
|
alpar@100
|
61 |
struct DijkstraWidestPathOperationTraits {
|
|
alpar@100
|
62 |
/// \brief Gives back the maximum value of the type.
|
|
alpar@100
|
63 |
static Value zero() {
|
|
alpar@100
|
64 |
return std::numeric_limits<Value>::max();
|
|
alpar@100
|
65 |
}
|
|
alpar@100
|
66 |
/// \brief Gives back the minimum of the given two elements.
|
|
alpar@100
|
67 |
static Value plus(const Value& left, const Value& right) {
|
|
alpar@100
|
68 |
return std::min(left, right);
|
|
alpar@100
|
69 |
}
|
|
alpar@100
|
70 |
/// \brief Gives back true only if the first value less than the second.
|
|
alpar@100
|
71 |
static bool less(const Value& left, const Value& right) {
|
|
alpar@100
|
72 |
return left < right;
|
|
alpar@100
|
73 |
}
|
|
alpar@100
|
74 |
};
|
|
alpar@100
|
75 |
|
|
alpar@100
|
76 |
///Default traits class of Dijkstra class.
|
|
alpar@100
|
77 |
|
|
alpar@100
|
78 |
///Default traits class of Dijkstra class.
|
|
kpeter@157
|
79 |
///\tparam GR Digraph type.
|
|
kpeter@157
|
80 |
///\tparam LM Type of length map.
|
|
alpar@100
|
81 |
template<class GR, class LM>
|
|
alpar@100
|
82 |
struct DijkstraDefaultTraits
|
|
alpar@100
|
83 |
{
|
|
alpar@100
|
84 |
///The digraph type the algorithm runs on.
|
|
alpar@100
|
85 |
typedef GR Digraph;
|
|
alpar@100
|
86 |
///The type of the map that stores the arc lengths.
|
|
alpar@100
|
87 |
|
|
alpar@100
|
88 |
///The type of the map that stores the arc lengths.
|
|
alpar@100
|
89 |
///It must meet the \ref concepts::ReadMap "ReadMap" concept.
|
|
alpar@100
|
90 |
typedef LM LengthMap;
|
|
alpar@100
|
91 |
//The type of the length of the arcs.
|
|
alpar@100
|
92 |
typedef typename LM::Value Value;
|
|
alpar@100
|
93 |
/// Operation traits for Dijkstra algorithm.
|
|
alpar@100
|
94 |
|
|
alpar@100
|
95 |
/// It defines the used operation by the algorithm.
|
|
alpar@100
|
96 |
/// \see DijkstraDefaultOperationTraits
|
|
alpar@100
|
97 |
typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
|
|
alpar@100
|
98 |
/// The cross reference type used by heap.
|
|
alpar@100
|
99 |
|
|
alpar@100
|
100 |
|
|
alpar@100
|
101 |
/// The cross reference type used by heap.
|
|
alpar@100
|
102 |
/// Usually it is \c Digraph::NodeMap<int>.
|
|
alpar@100
|
103 |
typedef typename Digraph::template NodeMap<int> HeapCrossRef;
|
|
alpar@100
|
104 |
///Instantiates a HeapCrossRef.
|
|
alpar@100
|
105 |
|
|
alpar@100
|
106 |
///This function instantiates a \c HeapCrossRef.
|
|
alpar@100
|
107 |
/// \param G is the digraph, to which we would like to define the
|
|
alpar@100
|
108 |
/// HeapCrossRef.
|
|
alpar@100
|
109 |
static HeapCrossRef *createHeapCrossRef(const GR &G)
|
|
alpar@100
|
110 |
{
|
|
alpar@100
|
111 |
return new HeapCrossRef(G);
|
|
alpar@100
|
112 |
}
|
|
alpar@100
|
113 |
|
|
alpar@100
|
114 |
///The heap type used by Dijkstra algorithm.
|
|
alpar@100
|
115 |
|
|
alpar@100
|
116 |
///The heap type used by Dijkstra algorithm.
|
|
alpar@100
|
117 |
///
|
|
alpar@100
|
118 |
///\sa BinHeap
|
|
alpar@100
|
119 |
///\sa Dijkstra
|
|
alpar@100
|
120 |
typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
|
|
alpar@100
|
121 |
|
|
alpar@100
|
122 |
static Heap *createHeap(HeapCrossRef& R)
|
|
alpar@100
|
123 |
{
|
|
alpar@100
|
124 |
return new Heap(R);
|
|
alpar@100
|
125 |
}
|
|
alpar@100
|
126 |
|
|
alpar@100
|
127 |
///\brief The type of the map that stores the last
|
|
alpar@100
|
128 |
///arcs of the shortest paths.
|
|
alpar@100
|
129 |
///
|
|
alpar@100
|
130 |
///The type of the map that stores the last
|
|
alpar@100
|
131 |
///arcs of the shortest paths.
|
|
alpar@100
|
132 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
|
|
alpar@100
|
133 |
///
|
|
alpar@100
|
134 |
typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
|
|
alpar@100
|
135 |
///Instantiates a PredMap.
|
|
alpar@100
|
136 |
|
|
alpar@100
|
137 |
///This function instantiates a \c PredMap.
|
|
alpar@100
|
138 |
///\param G is the digraph, to which we would like to define the PredMap.
|
|
alpar@100
|
139 |
///\todo The digraph alone may be insufficient for the initialization
|
|
alpar@100
|
140 |
static PredMap *createPredMap(const GR &G)
|
|
alpar@100
|
141 |
{
|
|
alpar@100
|
142 |
return new PredMap(G);
|
|
alpar@100
|
143 |
}
|
|
alpar@100
|
144 |
|
|
alpar@100
|
145 |
///The type of the map that stores whether a nodes is processed.
|
|
alpar@100
|
146 |
|
|
alpar@100
|
147 |
///The type of the map that stores whether a nodes is processed.
|
|
alpar@100
|
148 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
|
|
alpar@100
|
149 |
///By default it is a NullMap.
|
|
alpar@100
|
150 |
///\todo If it is set to a real map,
|
|
alpar@100
|
151 |
///Dijkstra::processed() should read this.
|
|
alpar@100
|
152 |
///\todo named parameter to set this type, function to read and write.
|
|
alpar@100
|
153 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
|
|
alpar@100
|
154 |
///Instantiates a ProcessedMap.
|
|
alpar@100
|
155 |
|
|
alpar@100
|
156 |
///This function instantiates a \c ProcessedMap.
|
|
alpar@100
|
157 |
///\param g is the digraph, to which
|
|
alpar@100
|
158 |
///we would like to define the \c ProcessedMap
|
|
alpar@100
|
159 |
#ifdef DOXYGEN
|
|
alpar@100
|
160 |
static ProcessedMap *createProcessedMap(const GR &g)
|
|
alpar@100
|
161 |
#else
|
|
alpar@100
|
162 |
static ProcessedMap *createProcessedMap(const GR &)
|
|
alpar@100
|
163 |
#endif
|
|
alpar@100
|
164 |
{
|
|
alpar@100
|
165 |
return new ProcessedMap();
|
|
alpar@100
|
166 |
}
|
|
alpar@100
|
167 |
///The type of the map that stores the dists of the nodes.
|
|
alpar@100
|
168 |
|
|
alpar@100
|
169 |
///The type of the map that stores the dists of the nodes.
|
|
alpar@100
|
170 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
|
|
alpar@100
|
171 |
///
|
|
alpar@100
|
172 |
typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
|
|
alpar@100
|
173 |
///Instantiates a DistMap.
|
|
alpar@100
|
174 |
|
|
alpar@100
|
175 |
///This function instantiates a \ref DistMap.
|
|
alpar@100
|
176 |
///\param G is the digraph, to which we would like to define the \ref DistMap
|
|
alpar@100
|
177 |
static DistMap *createDistMap(const GR &G)
|
|
alpar@100
|
178 |
{
|
|
alpar@100
|
179 |
return new DistMap(G);
|
|
alpar@100
|
180 |
}
|
|
alpar@100
|
181 |
};
|
|
alpar@100
|
182 |
|
|
alpar@100
|
183 |
///%Dijkstra algorithm class.
|
|
alpar@100
|
184 |
|
|
alpar@100
|
185 |
/// \ingroup shortest_path
|
|
alpar@100
|
186 |
///This class provides an efficient implementation of %Dijkstra algorithm.
|
|
alpar@100
|
187 |
///The arc lengths are passed to the algorithm using a
|
|
alpar@100
|
188 |
///\ref concepts::ReadMap "ReadMap",
|
|
alpar@100
|
189 |
///so it is easy to change it to any kind of length.
|
|
alpar@100
|
190 |
///
|
|
alpar@100
|
191 |
///The type of the length is determined by the
|
|
alpar@100
|
192 |
///\ref concepts::ReadMap::Value "Value" of the length map.
|
|
alpar@100
|
193 |
///
|
|
alpar@100
|
194 |
///It is also possible to change the underlying priority heap.
|
|
alpar@100
|
195 |
///
|
|
kpeter@157
|
196 |
///\tparam GR The digraph type the algorithm runs on. The default value
|
|
alpar@100
|
197 |
///is \ref ListDigraph. The value of GR is not used directly by
|
|
alpar@100
|
198 |
///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
|
|
kpeter@157
|
199 |
///\tparam LM This read-only ArcMap determines the lengths of the
|
|
alpar@100
|
200 |
///arcs. It is read once for each arc, so the map may involve in
|
|
alpar@100
|
201 |
///relatively time consuming process to compute the arc length if
|
|
alpar@100
|
202 |
///it is necessary. The default map type is \ref
|
|
alpar@100
|
203 |
///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value
|
|
alpar@100
|
204 |
///of LM is not used directly by Dijkstra, it is only passed to \ref
|
|
kpeter@157
|
205 |
///DijkstraDefaultTraits.
|
|
kpeter@157
|
206 |
///\tparam TR Traits class to set
|
|
alpar@100
|
207 |
///various data types used by the algorithm. The default traits
|
|
alpar@100
|
208 |
///class is \ref DijkstraDefaultTraits
|
|
alpar@100
|
209 |
///"DijkstraDefaultTraits<GR,LM>". See \ref
|
|
alpar@100
|
210 |
///DijkstraDefaultTraits for the documentation of a Dijkstra traits
|
|
alpar@100
|
211 |
///class.
|
|
alpar@100
|
212 |
|
|
alpar@100
|
213 |
#ifdef DOXYGEN
|
|
alpar@100
|
214 |
template <typename GR, typename LM, typename TR>
|
|
alpar@100
|
215 |
#else
|
|
alpar@100
|
216 |
template <typename GR=ListDigraph,
|
|
alpar@100
|
217 |
typename LM=typename GR::template ArcMap<int>,
|
|
alpar@100
|
218 |
typename TR=DijkstraDefaultTraits<GR,LM> >
|
|
alpar@100
|
219 |
#endif
|
|
alpar@100
|
220 |
class Dijkstra {
|
|
alpar@100
|
221 |
public:
|
|
alpar@100
|
222 |
/**
|
|
alpar@100
|
223 |
* \brief \ref Exception for uninitialized parameters.
|
|
alpar@100
|
224 |
*
|
|
alpar@100
|
225 |
* This error represents problems in the initialization
|
|
alpar@100
|
226 |
* of the parameters of the algorithms.
|
|
alpar@100
|
227 |
*/
|
|
alpar@100
|
228 |
class UninitializedParameter : public lemon::UninitializedParameter {
|
|
alpar@100
|
229 |
public:
|
|
alpar@100
|
230 |
virtual const char* what() const throw() {
|
|
alpar@100
|
231 |
return "lemon::Dijkstra::UninitializedParameter";
|
|
alpar@100
|
232 |
}
|
|
alpar@100
|
233 |
};
|
|
alpar@100
|
234 |
|
|
alpar@100
|
235 |
typedef TR Traits;
|
|
alpar@100
|
236 |
///The type of the underlying digraph.
|
|
alpar@100
|
237 |
typedef typename TR::Digraph Digraph;
|
|
alpar@100
|
238 |
///\e
|
|
alpar@100
|
239 |
typedef typename Digraph::Node Node;
|
|
alpar@100
|
240 |
///\e
|
|
alpar@100
|
241 |
typedef typename Digraph::NodeIt NodeIt;
|
|
alpar@100
|
242 |
///\e
|
|
alpar@100
|
243 |
typedef typename Digraph::Arc Arc;
|
|
alpar@100
|
244 |
///\e
|
|
alpar@100
|
245 |
typedef typename Digraph::OutArcIt OutArcIt;
|
|
alpar@100
|
246 |
|
|
alpar@100
|
247 |
///The type of the length of the arcs.
|
|
alpar@100
|
248 |
typedef typename TR::LengthMap::Value Value;
|
|
alpar@100
|
249 |
///The type of the map that stores the arc lengths.
|
|
alpar@100
|
250 |
typedef typename TR::LengthMap LengthMap;
|
|
alpar@100
|
251 |
///\brief The type of the map that stores the last
|
|
alpar@100
|
252 |
///arcs of the shortest paths.
|
|
alpar@100
|
253 |
typedef typename TR::PredMap PredMap;
|
|
alpar@100
|
254 |
///The type of the map indicating if a node is processed.
|
|
alpar@100
|
255 |
typedef typename TR::ProcessedMap ProcessedMap;
|
|
alpar@100
|
256 |
///The type of the map that stores the dists of the nodes.
|
|
alpar@100
|
257 |
typedef typename TR::DistMap DistMap;
|
|
alpar@100
|
258 |
///The cross reference type used for the current heap.
|
|
alpar@100
|
259 |
typedef typename TR::HeapCrossRef HeapCrossRef;
|
|
alpar@100
|
260 |
///The heap type used by the dijkstra algorithm.
|
|
alpar@100
|
261 |
typedef typename TR::Heap Heap;
|
|
alpar@100
|
262 |
///The operation traits.
|
|
alpar@100
|
263 |
typedef typename TR::OperationTraits OperationTraits;
|
|
alpar@100
|
264 |
private:
|
|
alpar@100
|
265 |
/// Pointer to the underlying digraph.
|
|
alpar@100
|
266 |
const Digraph *G;
|
|
alpar@100
|
267 |
/// Pointer to the length map
|
|
alpar@100
|
268 |
const LengthMap *length;
|
|
alpar@100
|
269 |
///Pointer to the map of predecessors arcs.
|
|
alpar@100
|
270 |
PredMap *_pred;
|
|
alpar@100
|
271 |
///Indicates if \ref _pred is locally allocated (\c true) or not.
|
|
alpar@100
|
272 |
bool local_pred;
|
|
alpar@100
|
273 |
///Pointer to the map of distances.
|
|
alpar@100
|
274 |
DistMap *_dist;
|
|
alpar@100
|
275 |
///Indicates if \ref _dist is locally allocated (\c true) or not.
|
|
alpar@100
|
276 |
bool local_dist;
|
|
alpar@100
|
277 |
///Pointer to the map of processed status of the nodes.
|
|
alpar@100
|
278 |
ProcessedMap *_processed;
|
|
alpar@100
|
279 |
///Indicates if \ref _processed is locally allocated (\c true) or not.
|
|
alpar@100
|
280 |
bool local_processed;
|
|
alpar@100
|
281 |
///Pointer to the heap cross references.
|
|
alpar@100
|
282 |
HeapCrossRef *_heap_cross_ref;
|
|
alpar@100
|
283 |
///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
|
|
alpar@100
|
284 |
bool local_heap_cross_ref;
|
|
alpar@100
|
285 |
///Pointer to the heap.
|
|
alpar@100
|
286 |
Heap *_heap;
|
|
alpar@100
|
287 |
///Indicates if \ref _heap is locally allocated (\c true) or not.
|
|
alpar@100
|
288 |
bool local_heap;
|
|
alpar@100
|
289 |
|
|
alpar@100
|
290 |
///Creates the maps if necessary.
|
|
alpar@100
|
291 |
|
|
alpar@100
|
292 |
///\todo Better memory allocation (instead of new).
|
|
alpar@100
|
293 |
void create_maps()
|
|
alpar@100
|
294 |
{
|
|
alpar@100
|
295 |
if(!_pred) {
|
|
alpar@100
|
296 |
local_pred = true;
|
|
alpar@100
|
297 |
_pred = Traits::createPredMap(*G);
|
|
alpar@100
|
298 |
}
|
|
alpar@100
|
299 |
if(!_dist) {
|
|
alpar@100
|
300 |
local_dist = true;
|
|
alpar@100
|
301 |
_dist = Traits::createDistMap(*G);
|
|
alpar@100
|
302 |
}
|
|
alpar@100
|
303 |
if(!_processed) {
|
|
alpar@100
|
304 |
local_processed = true;
|
|
alpar@100
|
305 |
_processed = Traits::createProcessedMap(*G);
|
|
alpar@100
|
306 |
}
|
|
alpar@100
|
307 |
if (!_heap_cross_ref) {
|
|
alpar@100
|
308 |
local_heap_cross_ref = true;
|
|
alpar@100
|
309 |
_heap_cross_ref = Traits::createHeapCrossRef(*G);
|
|
alpar@100
|
310 |
}
|
|
alpar@100
|
311 |
if (!_heap) {
|
|
alpar@100
|
312 |
local_heap = true;
|
|
alpar@100
|
313 |
_heap = Traits::createHeap(*_heap_cross_ref);
|
|
alpar@100
|
314 |
}
|
|
alpar@100
|
315 |
}
|
|
alpar@100
|
316 |
|
|
alpar@100
|
317 |
public :
|
|
alpar@100
|
318 |
|
|
alpar@100
|
319 |
typedef Dijkstra Create;
|
|
alpar@100
|
320 |
|
|
alpar@100
|
321 |
///\name Named template parameters
|
|
alpar@100
|
322 |
|
|
alpar@100
|
323 |
///@{
|
|
alpar@100
|
324 |
|
|
alpar@100
|
325 |
template <class T>
|
|
alpar@100
|
326 |
struct DefPredMapTraits : public Traits {
|
|
alpar@100
|
327 |
typedef T PredMap;
|
|
alpar@100
|
328 |
static PredMap *createPredMap(const Digraph &)
|
|
alpar@100
|
329 |
{
|
|
alpar@100
|
330 |
throw UninitializedParameter();
|
|
alpar@100
|
331 |
}
|
|
alpar@100
|
332 |
};
|
|
alpar@100
|
333 |
///\ref named-templ-param "Named parameter" for setting PredMap type
|
|
alpar@100
|
334 |
|
|
alpar@100
|
335 |
///\ref named-templ-param "Named parameter" for setting PredMap type
|
|
alpar@100
|
336 |
///
|
|
alpar@100
|
337 |
template <class T>
|
|
alpar@100
|
338 |
struct DefPredMap
|
|
alpar@100
|
339 |
: public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
|
|
alpar@100
|
340 |
typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create;
|
|
alpar@100
|
341 |
};
|
|
alpar@100
|
342 |
|
|
alpar@100
|
343 |
template <class T>
|
|
alpar@100
|
344 |
struct DefDistMapTraits : public Traits {
|
|
alpar@100
|
345 |
typedef T DistMap;
|
|
alpar@100
|
346 |
static DistMap *createDistMap(const Digraph &)
|
|
alpar@100
|
347 |
{
|
|
alpar@100
|
348 |
throw UninitializedParameter();
|
|
alpar@100
|
349 |
}
|
|
alpar@100
|
350 |
};
|
|
alpar@100
|
351 |
///\ref named-templ-param "Named parameter" for setting DistMap type
|
|
alpar@100
|
352 |
|
|
alpar@100
|
353 |
///\ref named-templ-param "Named parameter" for setting DistMap type
|
|
alpar@100
|
354 |
///
|
|
alpar@100
|
355 |
template <class T>
|
|
alpar@100
|
356 |
struct DefDistMap
|
|
alpar@100
|
357 |
: public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
|
|
alpar@100
|
358 |
typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
|
|
alpar@100
|
359 |
};
|
|
alpar@100
|
360 |
|
|
alpar@100
|
361 |
template <class T>
|
|
alpar@100
|
362 |
struct DefProcessedMapTraits : public Traits {
|
|
alpar@100
|
363 |
typedef T ProcessedMap;
|
|
alpar@100
|
364 |
static ProcessedMap *createProcessedMap(const Digraph &G)
|
|
alpar@100
|
365 |
{
|
|
alpar@100
|
366 |
throw UninitializedParameter();
|
|
alpar@100
|
367 |
}
|
|
alpar@100
|
368 |
};
|
|
alpar@100
|
369 |
///\ref named-templ-param "Named parameter" for setting ProcessedMap type
|
|
alpar@100
|
370 |
|
|
alpar@100
|
371 |
///\ref named-templ-param "Named parameter" for setting ProcessedMap type
|
|
alpar@100
|
372 |
///
|
|
alpar@100
|
373 |
template <class T>
|
|
alpar@100
|
374 |
struct DefProcessedMap
|
|
alpar@100
|
375 |
: public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
|
|
alpar@100
|
376 |
typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create;
|
|
alpar@100
|
377 |
};
|
|
alpar@100
|
378 |
|
|
alpar@100
|
379 |
struct DefDigraphProcessedMapTraits : public Traits {
|
|
alpar@100
|
380 |
typedef typename Digraph::template NodeMap<bool> ProcessedMap;
|
|
alpar@100
|
381 |
static ProcessedMap *createProcessedMap(const Digraph &G)
|
|
alpar@100
|
382 |
{
|
|
alpar@100
|
383 |
return new ProcessedMap(G);
|
|
alpar@100
|
384 |
}
|
|
alpar@100
|
385 |
};
|
|
alpar@100
|
386 |
///\brief \ref named-templ-param "Named parameter"
|
|
alpar@100
|
387 |
///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
|
|
alpar@100
|
388 |
///
|
|
alpar@100
|
389 |
///\ref named-templ-param "Named parameter"
|
|
alpar@100
|
390 |
///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
|
|
alpar@100
|
391 |
///If you don't set it explicitely, it will be automatically allocated.
|
|
alpar@100
|
392 |
template <class T>
|
|
alpar@100
|
393 |
struct DefProcessedMapToBeDefaultMap
|
|
alpar@100
|
394 |
: public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
|
|
alpar@100
|
395 |
typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
|
|
alpar@100
|
396 |
};
|
|
alpar@100
|
397 |
|
|
alpar@100
|
398 |
template <class H, class CR>
|
|
alpar@100
|
399 |
struct DefHeapTraits : public Traits {
|
|
alpar@100
|
400 |
typedef CR HeapCrossRef;
|
|
alpar@100
|
401 |
typedef H Heap;
|
|
alpar@100
|
402 |
static HeapCrossRef *createHeapCrossRef(const Digraph &) {
|
|
alpar@100
|
403 |
throw UninitializedParameter();
|
|
alpar@100
|
404 |
}
|
|
alpar@100
|
405 |
static Heap *createHeap(HeapCrossRef &)
|
|
alpar@100
|
406 |
{
|
|
alpar@100
|
407 |
throw UninitializedParameter();
|
|
alpar@100
|
408 |
}
|
|
alpar@100
|
409 |
};
|
|
alpar@100
|
410 |
///\brief \ref named-templ-param "Named parameter" for setting
|
|
alpar@100
|
411 |
///heap and cross reference type
|
|
alpar@100
|
412 |
///
|
|
alpar@100
|
413 |
///\ref named-templ-param "Named parameter" for setting heap and cross
|
|
alpar@100
|
414 |
///reference type
|
|
alpar@100
|
415 |
///
|
|
alpar@100
|
416 |
template <class H, class CR = typename Digraph::template NodeMap<int> >
|
|
alpar@100
|
417 |
struct DefHeap
|
|
alpar@100
|
418 |
: public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
|
|
alpar@100
|
419 |
typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create;
|
|
alpar@100
|
420 |
};
|
|
alpar@100
|
421 |
|
|
alpar@100
|
422 |
template <class H, class CR>
|
|
alpar@100
|
423 |
struct DefStandardHeapTraits : public Traits {
|
|
alpar@100
|
424 |
typedef CR HeapCrossRef;
|
|
alpar@100
|
425 |
typedef H Heap;
|
|
alpar@100
|
426 |
static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
|
|
alpar@100
|
427 |
return new HeapCrossRef(G);
|
|
alpar@100
|
428 |
}
|
|
alpar@100
|
429 |
static Heap *createHeap(HeapCrossRef &R)
|
|
alpar@100
|
430 |
{
|
|
alpar@100
|
431 |
return new Heap(R);
|
|
alpar@100
|
432 |
}
|
|
alpar@100
|
433 |
};
|
|
alpar@100
|
434 |
///\brief \ref named-templ-param "Named parameter" for setting
|
|
alpar@100
|
435 |
///heap and cross reference type with automatic allocation
|
|
alpar@100
|
436 |
///
|
|
alpar@100
|
437 |
///\ref named-templ-param "Named parameter" for setting heap and cross
|
|
alpar@100
|
438 |
///reference type. It can allocate the heap and the cross reference
|
|
alpar@100
|
439 |
///object if the cross reference's constructor waits for the digraph as
|
|
alpar@100
|
440 |
///parameter and the heap's constructor waits for the cross reference.
|
|
alpar@100
|
441 |
template <class H, class CR = typename Digraph::template NodeMap<int> >
|
|
alpar@100
|
442 |
struct DefStandardHeap
|
|
alpar@100
|
443 |
: public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {
|
|
alpar@100
|
444 |
typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >
|
|
alpar@100
|
445 |
Create;
|
|
alpar@100
|
446 |
};
|
|
alpar@100
|
447 |
|
|
alpar@100
|
448 |
template <class T>
|
|
alpar@100
|
449 |
struct DefOperationTraitsTraits : public Traits {
|
|
alpar@100
|
450 |
typedef T OperationTraits;
|
|
alpar@100
|
451 |
};
|
|
alpar@100
|
452 |
|
|
alpar@100
|
453 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
|
alpar@100
|
454 |
/// OperationTraits type
|
|
alpar@100
|
455 |
///
|
|
alpar@100
|
456 |
/// \ref named-templ-param "Named parameter" for setting OperationTraits
|
|
alpar@100
|
457 |
/// type
|
|
alpar@100
|
458 |
template <class T>
|
|
alpar@100
|
459 |
struct DefOperationTraits
|
|
alpar@100
|
460 |
: public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
|
|
alpar@100
|
461 |
typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> >
|
|
alpar@100
|
462 |
Create;
|
|
alpar@100
|
463 |
};
|
|
alpar@100
|
464 |
|
|
alpar@100
|
465 |
///@}
|
|
alpar@100
|
466 |
|
|
alpar@100
|
467 |
|
|
alpar@100
|
468 |
protected:
|
|
alpar@100
|
469 |
|
|
alpar@100
|
470 |
Dijkstra() {}
|
|
alpar@100
|
471 |
|
|
alpar@100
|
472 |
public:
|
|
alpar@100
|
473 |
|
|
alpar@100
|
474 |
///Constructor.
|
|
alpar@100
|
475 |
|
|
alpar@100
|
476 |
///\param _G the digraph the algorithm will run on.
|
|
alpar@100
|
477 |
///\param _length the length map used by the algorithm.
|
|
alpar@100
|
478 |
Dijkstra(const Digraph& _G, const LengthMap& _length) :
|
|
alpar@100
|
479 |
G(&_G), length(&_length),
|
|
alpar@100
|
480 |
_pred(NULL), local_pred(false),
|
|
alpar@100
|
481 |
_dist(NULL), local_dist(false),
|
|
alpar@100
|
482 |
_processed(NULL), local_processed(false),
|
|
alpar@100
|
483 |
_heap_cross_ref(NULL), local_heap_cross_ref(false),
|
|
alpar@100
|
484 |
_heap(NULL), local_heap(false)
|
|
alpar@100
|
485 |
{ }
|
|
alpar@100
|
486 |
|
|
alpar@100
|
487 |
///Destructor.
|
|
alpar@100
|
488 |
~Dijkstra()
|
|
alpar@100
|
489 |
{
|
|
alpar@100
|
490 |
if(local_pred) delete _pred;
|
|
alpar@100
|
491 |
if(local_dist) delete _dist;
|
|
alpar@100
|
492 |
if(local_processed) delete _processed;
|
|
alpar@100
|
493 |
if(local_heap_cross_ref) delete _heap_cross_ref;
|
|
alpar@100
|
494 |
if(local_heap) delete _heap;
|
|
alpar@100
|
495 |
}
|
|
alpar@100
|
496 |
|
|
alpar@100
|
497 |
///Sets the length map.
|
|
alpar@100
|
498 |
|
|
alpar@100
|
499 |
///Sets the length map.
|
|
alpar@100
|
500 |
///\return <tt> (*this) </tt>
|
|
alpar@100
|
501 |
Dijkstra &lengthMap(const LengthMap &m)
|
|
alpar@100
|
502 |
{
|
|
alpar@100
|
503 |
length = &m;
|
|
alpar@100
|
504 |
return *this;
|
|
alpar@100
|
505 |
}
|
|
alpar@100
|
506 |
|
|
alpar@100
|
507 |
///Sets the map storing the predecessor arcs.
|
|
alpar@100
|
508 |
|
|
alpar@100
|
509 |
///Sets the map storing the predecessor arcs.
|
|
alpar@100
|
510 |
///If you don't use this function before calling \ref run(),
|
|
alpar@100
|
511 |
///it will allocate one. The destuctor deallocates this
|
|
alpar@100
|
512 |
///automatically allocated map, of course.
|
|
alpar@100
|
513 |
///\return <tt> (*this) </tt>
|
|
alpar@100
|
514 |
Dijkstra &predMap(PredMap &m)
|
|
alpar@100
|
515 |
{
|
|
alpar@100
|
516 |
if(local_pred) {
|
|
alpar@100
|
517 |
delete _pred;
|
|
alpar@100
|
518 |
local_pred=false;
|
|
alpar@100
|
519 |
}
|
|
alpar@100
|
520 |
_pred = &m;
|
|
alpar@100
|
521 |
return *this;
|
|
alpar@100
|
522 |
}
|
|
alpar@100
|
523 |
|
|
alpar@100
|
524 |
///Sets the map storing the distances calculated by the algorithm.
|
|
alpar@100
|
525 |
|
|
alpar@100
|
526 |
///Sets the map storing the distances calculated by the algorithm.
|
|
alpar@100
|
527 |
///If you don't use this function before calling \ref run(),
|
|
alpar@100
|
528 |
///it will allocate one. The destuctor deallocates this
|
|
alpar@100
|
529 |
///automatically allocated map, of course.
|
|
alpar@100
|
530 |
///\return <tt> (*this) </tt>
|
|
alpar@100
|
531 |
Dijkstra &distMap(DistMap &m)
|
|
alpar@100
|
532 |
{
|
|
alpar@100
|
533 |
if(local_dist) {
|
|
alpar@100
|
534 |
delete _dist;
|
|
alpar@100
|
535 |
local_dist=false;
|
|
alpar@100
|
536 |
}
|
|
alpar@100
|
537 |
_dist = &m;
|
|
alpar@100
|
538 |
return *this;
|
|
alpar@100
|
539 |
}
|
|
alpar@100
|
540 |
|
|
alpar@100
|
541 |
///Sets the heap and the cross reference used by algorithm.
|
|
alpar@100
|
542 |
|
|
alpar@100
|
543 |
///Sets the heap and the cross reference used by algorithm.
|
|
alpar@100
|
544 |
///If you don't use this function before calling \ref run(),
|
|
alpar@100
|
545 |
///it will allocate one. The destuctor deallocates this
|
|
alpar@100
|
546 |
///automatically allocated heap and cross reference, of course.
|
|
alpar@100
|
547 |
///\return <tt> (*this) </tt>
|
|
alpar@100
|
548 |
Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
|
|
alpar@100
|
549 |
{
|
|
alpar@100
|
550 |
if(local_heap_cross_ref) {
|
|
alpar@100
|
551 |
delete _heap_cross_ref;
|
|
alpar@100
|
552 |
local_heap_cross_ref=false;
|
|
alpar@100
|
553 |
}
|
|
alpar@100
|
554 |
_heap_cross_ref = &cr;
|
|
alpar@100
|
555 |
if(local_heap) {
|
|
alpar@100
|
556 |
delete _heap;
|
|
alpar@100
|
557 |
local_heap=false;
|
|
alpar@100
|
558 |
}
|
|
alpar@100
|
559 |
_heap = &hp;
|
|
alpar@100
|
560 |
return *this;
|
|
alpar@100
|
561 |
}
|
|
alpar@100
|
562 |
|
|
alpar@100
|
563 |
private:
|
|
alpar@100
|
564 |
void finalizeNodeData(Node v,Value dst)
|
|
alpar@100
|
565 |
{
|
|
alpar@100
|
566 |
_processed->set(v,true);
|
|
alpar@100
|
567 |
_dist->set(v, dst);
|
|
alpar@100
|
568 |
}
|
|
alpar@100
|
569 |
|
|
alpar@100
|
570 |
public:
|
|
alpar@100
|
571 |
|
|
alpar@100
|
572 |
typedef PredMapPath<Digraph, PredMap> Path;
|
|
alpar@100
|
573 |
|
|
alpar@100
|
574 |
///\name Execution control
|
|
alpar@100
|
575 |
///The simplest way to execute the algorithm is to use
|
|
alpar@100
|
576 |
///one of the member functions called \c run(...).
|
|
alpar@100
|
577 |
///\n
|
|
alpar@100
|
578 |
///If you need more control on the execution,
|
|
alpar@100
|
579 |
///first you must call \ref init(), then you can add several source nodes
|
|
alpar@100
|
580 |
///with \ref addSource().
|
|
alpar@100
|
581 |
///Finally \ref start() will perform the actual path
|
|
alpar@100
|
582 |
///computation.
|
|
alpar@100
|
583 |
|
|
alpar@100
|
584 |
///@{
|
|
alpar@100
|
585 |
|
|
alpar@100
|
586 |
///Initializes the internal data structures.
|
|
alpar@100
|
587 |
|
|
alpar@100
|
588 |
///Initializes the internal data structures.
|
|
alpar@100
|
589 |
///
|
|
alpar@100
|
590 |
void init()
|
|
alpar@100
|
591 |
{
|
|
alpar@100
|
592 |
create_maps();
|
|
alpar@100
|
593 |
_heap->clear();
|
|
alpar@100
|
594 |
for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
|
|
alpar@100
|
595 |
_pred->set(u,INVALID);
|
|
alpar@100
|
596 |
_processed->set(u,false);
|
|
alpar@100
|
597 |
_heap_cross_ref->set(u,Heap::PRE_HEAP);
|
|
alpar@100
|
598 |
}
|
|
alpar@100
|
599 |
}
|
|
alpar@100
|
600 |
|
|
alpar@100
|
601 |
///Adds a new source node.
|
|
alpar@100
|
602 |
|
|
alpar@100
|
603 |
///Adds a new source node to the priority heap.
|
|
alpar@100
|
604 |
///
|
|
alpar@100
|
605 |
///The optional second parameter is the initial distance of the node.
|
|
alpar@100
|
606 |
///
|
|
alpar@100
|
607 |
///It checks if the node has already been added to the heap and
|
|
alpar@100
|
608 |
///it is pushed to the heap only if either it was not in the heap
|
|
alpar@100
|
609 |
///or the shortest path found till then is shorter than \c dst.
|
|
alpar@100
|
610 |
void addSource(Node s,Value dst=OperationTraits::zero())
|
|
alpar@100
|
611 |
{
|
|
alpar@100
|
612 |
if(_heap->state(s) != Heap::IN_HEAP) {
|
|
alpar@100
|
613 |
_heap->push(s,dst);
|
|
alpar@100
|
614 |
} else if(OperationTraits::less((*_heap)[s], dst)) {
|
|
alpar@100
|
615 |
_heap->set(s,dst);
|
|
alpar@100
|
616 |
_pred->set(s,INVALID);
|
|
alpar@100
|
617 |
}
|
|
alpar@100
|
618 |
}
|
|
alpar@100
|
619 |
|
|
alpar@100
|
620 |
///Processes the next node in the priority heap
|
|
alpar@100
|
621 |
|
|
alpar@100
|
622 |
///Processes the next node in the priority heap.
|
|
alpar@100
|
623 |
///
|
|
alpar@100
|
624 |
///\return The processed node.
|
|
alpar@100
|
625 |
///
|
|
alpar@100
|
626 |
///\warning The priority heap must not be empty!
|
|
alpar@100
|
627 |
Node processNextNode()
|
|
alpar@100
|
628 |
{
|
|
alpar@100
|
629 |
Node v=_heap->top();
|
|
alpar@100
|
630 |
Value oldvalue=_heap->prio();
|
|
alpar@100
|
631 |
_heap->pop();
|
|
alpar@100
|
632 |
finalizeNodeData(v,oldvalue);
|
|
alpar@100
|
633 |
|
|
alpar@100
|
634 |
for(OutArcIt e(*G,v); e!=INVALID; ++e) {
|
|
alpar@100
|
635 |
Node w=G->target(e);
|
|
alpar@100
|
636 |
switch(_heap->state(w)) {
|
|
alpar@100
|
637 |
case Heap::PRE_HEAP:
|
|
alpar@100
|
638 |
_heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
|
|
alpar@100
|
639 |
_pred->set(w,e);
|
|
alpar@100
|
640 |
break;
|
|
alpar@100
|
641 |
case Heap::IN_HEAP:
|
|
alpar@100
|
642 |
{
|
|
alpar@100
|
643 |
Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
|
|
alpar@100
|
644 |
if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
|
|
alpar@100
|
645 |
_heap->decrease(w, newvalue);
|
|
alpar@100
|
646 |
_pred->set(w,e);
|
|
alpar@100
|
647 |
}
|
|
alpar@100
|
648 |
}
|
|
alpar@100
|
649 |
break;
|
|
alpar@100
|
650 |
case Heap::POST_HEAP:
|
|
alpar@100
|
651 |
break;
|
|
alpar@100
|
652 |
}
|
|
alpar@100
|
653 |
}
|
|
alpar@100
|
654 |
return v;
|
|
alpar@100
|
655 |
}
|
|
alpar@100
|
656 |
|
|
alpar@100
|
657 |
///Next node to be processed.
|
|
alpar@100
|
658 |
|
|
alpar@100
|
659 |
///Next node to be processed.
|
|
alpar@100
|
660 |
///
|
|
alpar@100
|
661 |
///\return The next node to be processed or INVALID if the priority heap
|
|
alpar@100
|
662 |
/// is empty.
|
|
alpar@100
|
663 |
Node nextNode()
|
|
alpar@100
|
664 |
{
|
|
alpar@100
|
665 |
return !_heap->empty()?_heap->top():INVALID;
|
|
alpar@100
|
666 |
}
|
|
alpar@100
|
667 |
|
|
alpar@100
|
668 |
///\brief Returns \c false if there are nodes
|
|
alpar@100
|
669 |
///to be processed in the priority heap
|
|
alpar@100
|
670 |
///
|
|
alpar@100
|
671 |
///Returns \c false if there are nodes
|
|
alpar@100
|
672 |
///to be processed in the priority heap
|
|
alpar@100
|
673 |
bool emptyQueue() { return _heap->empty(); }
|
|
alpar@100
|
674 |
///Returns the number of the nodes to be processed in the priority heap
|
|
alpar@100
|
675 |
|
|
alpar@100
|
676 |
///Returns the number of the nodes to be processed in the priority heap
|
|
alpar@100
|
677 |
///
|
|
alpar@100
|
678 |
int queueSize() { return _heap->size(); }
|
|
alpar@100
|
679 |
|
|
alpar@100
|
680 |
///Executes the algorithm.
|
|
alpar@100
|
681 |
|
|
alpar@100
|
682 |
///Executes the algorithm.
|
|
alpar@100
|
683 |
///
|
|
alpar@100
|
684 |
///\pre init() must be called and at least one node should be added
|
|
alpar@100
|
685 |
///with addSource() before using this function.
|
|
alpar@100
|
686 |
///
|
|
alpar@100
|
687 |
///This method runs the %Dijkstra algorithm from the root node(s)
|
|
alpar@100
|
688 |
///in order to
|
|
alpar@100
|
689 |
///compute the
|
|
alpar@100
|
690 |
///shortest path to each node. The algorithm computes
|
|
alpar@100
|
691 |
///- The shortest path tree.
|
|
alpar@100
|
692 |
///- The distance of each node from the root(s).
|
|
alpar@100
|
693 |
///
|
|
alpar@100
|
694 |
void start()
|
|
alpar@100
|
695 |
{
|
|
alpar@100
|
696 |
while ( !_heap->empty() ) processNextNode();
|
|
alpar@100
|
697 |
}
|
|
alpar@100
|
698 |
|
|
alpar@100
|
699 |
///Executes the algorithm until \c dest is reached.
|
|
alpar@100
|
700 |
|
|
alpar@100
|
701 |
///Executes the algorithm until \c dest is reached.
|
|
alpar@100
|
702 |
///
|
|
alpar@100
|
703 |
///\pre init() must be called and at least one node should be added
|
|
alpar@100
|
704 |
///with addSource() before using this function.
|
|
alpar@100
|
705 |
///
|
|
alpar@100
|
706 |
///This method runs the %Dijkstra algorithm from the root node(s)
|
|
alpar@100
|
707 |
///in order to
|
|
alpar@100
|
708 |
///compute the
|
|
alpar@100
|
709 |
///shortest path to \c dest. The algorithm computes
|
|
alpar@100
|
710 |
///- The shortest path to \c dest.
|
|
alpar@100
|
711 |
///- The distance of \c dest from the root(s).
|
|
alpar@100
|
712 |
///
|
|
alpar@100
|
713 |
void start(Node dest)
|
|
alpar@100
|
714 |
{
|
|
alpar@100
|
715 |
while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
|
|
alpar@100
|
716 |
if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
|
|
alpar@100
|
717 |
}
|
|
alpar@100
|
718 |
|
|
alpar@100
|
719 |
///Executes the algorithm until a condition is met.
|
|
alpar@100
|
720 |
|
|
alpar@100
|
721 |
///Executes the algorithm until a condition is met.
|
|
alpar@100
|
722 |
///
|
|
alpar@100
|
723 |
///\pre init() must be called and at least one node should be added
|
|
alpar@100
|
724 |
///with addSource() before using this function.
|
|
alpar@100
|
725 |
///
|
|
alpar@100
|
726 |
///\param nm must be a bool (or convertible) node map. The algorithm
|
|
alpar@100
|
727 |
///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
|
|
alpar@100
|
728 |
///
|
|
alpar@100
|
729 |
///\return The reached node \c v with <tt>nm[v]</tt> true or
|
|
alpar@100
|
730 |
///\c INVALID if no such node was found.
|
|
alpar@100
|
731 |
template<class NodeBoolMap>
|
|
alpar@100
|
732 |
Node start(const NodeBoolMap &nm)
|
|
alpar@100
|
733 |
{
|
|
alpar@100
|
734 |
while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
|
|
alpar@100
|
735 |
if ( _heap->empty() ) return INVALID;
|
|
alpar@100
|
736 |
finalizeNodeData(_heap->top(),_heap->prio());
|
|
alpar@100
|
737 |
return _heap->top();
|
|
alpar@100
|
738 |
}
|
|
alpar@100
|
739 |
|
|
alpar@100
|
740 |
///Runs %Dijkstra algorithm from node \c s.
|
|
alpar@100
|
741 |
|
|
alpar@100
|
742 |
///This method runs the %Dijkstra algorithm from a root node \c s
|
|
alpar@100
|
743 |
///in order to
|
|
alpar@100
|
744 |
///compute the
|
|
alpar@100
|
745 |
///shortest path to each node. The algorithm computes
|
|
alpar@100
|
746 |
///- The shortest path tree.
|
|
alpar@100
|
747 |
///- The distance of each node from the root.
|
|
alpar@100
|
748 |
///
|
|
alpar@100
|
749 |
///\note d.run(s) is just a shortcut of the following code.
|
|
alpar@100
|
750 |
///\code
|
|
alpar@100
|
751 |
/// d.init();
|
|
alpar@100
|
752 |
/// d.addSource(s);
|
|
alpar@100
|
753 |
/// d.start();
|
|
alpar@100
|
754 |
///\endcode
|
|
alpar@100
|
755 |
void run(Node s) {
|
|
alpar@100
|
756 |
init();
|
|
alpar@100
|
757 |
addSource(s);
|
|
alpar@100
|
758 |
start();
|
|
alpar@100
|
759 |
}
|
|
alpar@100
|
760 |
|
|
alpar@100
|
761 |
///Finds the shortest path between \c s and \c t.
|
|
alpar@100
|
762 |
|
|
alpar@100
|
763 |
///Finds the shortest path between \c s and \c t.
|
|
alpar@100
|
764 |
///
|
|
alpar@100
|
765 |
///\return The length of the shortest s---t path if there exists one,
|
|
alpar@100
|
766 |
///0 otherwise.
|
|
alpar@100
|
767 |
///\note Apart from the return value, d.run(s) is
|
|
alpar@100
|
768 |
///just a shortcut of the following code.
|
|
alpar@100
|
769 |
///\code
|
|
alpar@100
|
770 |
/// d.init();
|
|
alpar@100
|
771 |
/// d.addSource(s);
|
|
alpar@100
|
772 |
/// d.start(t);
|
|
alpar@100
|
773 |
///\endcode
|
|
alpar@100
|
774 |
Value run(Node s,Node t) {
|
|
alpar@100
|
775 |
init();
|
|
alpar@100
|
776 |
addSource(s);
|
|
alpar@100
|
777 |
start(t);
|
|
alpar@100
|
778 |
return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
|
|
alpar@100
|
779 |
}
|
|
alpar@100
|
780 |
|
|
alpar@100
|
781 |
///@}
|
|
alpar@100
|
782 |
|
|
alpar@100
|
783 |
///\name Query Functions
|
|
alpar@100
|
784 |
///The result of the %Dijkstra algorithm can be obtained using these
|
|
alpar@100
|
785 |
///functions.\n
|
|
alpar@100
|
786 |
///Before the use of these functions,
|
|
alpar@100
|
787 |
///either run() or start() must be called.
|
|
alpar@100
|
788 |
|
|
alpar@100
|
789 |
///@{
|
|
alpar@100
|
790 |
|
|
alpar@100
|
791 |
///Gives back the shortest path.
|
|
alpar@100
|
792 |
|
|
alpar@100
|
793 |
///Gives back the shortest path.
|
|
alpar@100
|
794 |
///\pre The \c t should be reachable from the source.
|
|
alpar@100
|
795 |
Path path(Node t)
|
|
alpar@100
|
796 |
{
|
|
alpar@100
|
797 |
return Path(*G, *_pred, t);
|
|
alpar@100
|
798 |
}
|
|
alpar@100
|
799 |
|
|
alpar@100
|
800 |
///The distance of a node from the root.
|
|
alpar@100
|
801 |
|
|
alpar@100
|
802 |
///Returns the distance of a node from the root.
|
|
alpar@100
|
803 |
///\pre \ref run() must be called before using this function.
|
|
alpar@100
|
804 |
///\warning If node \c v in unreachable from the root the return value
|
|
alpar@100
|
805 |
///of this funcion is undefined.
|
|
alpar@100
|
806 |
Value dist(Node v) const { return (*_dist)[v]; }
|
|
alpar@100
|
807 |
|
|
alpar@100
|
808 |
///The current distance of a node from the root.
|
|
alpar@100
|
809 |
|
|
alpar@100
|
810 |
///Returns the current distance of a node from the root.
|
|
alpar@100
|
811 |
///It may be decreased in the following processes.
|
|
alpar@100
|
812 |
///\pre \c node should be reached but not processed
|
|
alpar@100
|
813 |
Value currentDist(Node v) const { return (*_heap)[v]; }
|
|
alpar@100
|
814 |
|
|
alpar@100
|
815 |
///Returns the 'previous arc' of the shortest path tree.
|
|
alpar@100
|
816 |
|
|
alpar@100
|
817 |
///For a node \c v it returns the 'previous arc' of the shortest path tree,
|
|
alpar@100
|
818 |
///i.e. it returns the last arc of a shortest path from the root to \c
|
|
alpar@100
|
819 |
///v. It is \ref INVALID
|
|
alpar@100
|
820 |
///if \c v is unreachable from the root or if \c v=s. The
|
|
alpar@100
|
821 |
///shortest path tree used here is equal to the shortest path tree used in
|
|
alpar@100
|
822 |
///\ref predNode(). \pre \ref run() must be called before using
|
|
alpar@100
|
823 |
///this function.
|
|
alpar@100
|
824 |
Arc predArc(Node v) const { return (*_pred)[v]; }
|
|
alpar@100
|
825 |
|
|
alpar@100
|
826 |
///Returns the 'previous node' of the shortest path tree.
|
|
alpar@100
|
827 |
|
|
alpar@100
|
828 |
///For a node \c v it returns the 'previous node' of the shortest path tree,
|
|
alpar@100
|
829 |
///i.e. it returns the last but one node from a shortest path from the
|
|
alpar@100
|
830 |
///root to \c /v. It is INVALID if \c v is unreachable from the root or if
|
|
alpar@100
|
831 |
///\c v=s. The shortest path tree used here is equal to the shortest path
|
|
alpar@100
|
832 |
///tree used in \ref predArc(). \pre \ref run() must be called before
|
|
alpar@100
|
833 |
///using this function.
|
|
alpar@100
|
834 |
Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
|
|
alpar@100
|
835 |
G->source((*_pred)[v]); }
|
|
alpar@100
|
836 |
|
|
alpar@100
|
837 |
///Returns a reference to the NodeMap of distances.
|
|
alpar@100
|
838 |
|
|
alpar@100
|
839 |
///Returns a reference to the NodeMap of distances. \pre \ref run() must
|
|
alpar@100
|
840 |
///be called before using this function.
|
|
alpar@100
|
841 |
const DistMap &distMap() const { return *_dist;}
|
|
alpar@100
|
842 |
|
|
alpar@100
|
843 |
///Returns a reference to the shortest path tree map.
|
|
alpar@100
|
844 |
|
|
alpar@100
|
845 |
///Returns a reference to the NodeMap of the arcs of the
|
|
alpar@100
|
846 |
///shortest path tree.
|
|
alpar@100
|
847 |
///\pre \ref run() must be called before using this function.
|
|
alpar@100
|
848 |
const PredMap &predMap() const { return *_pred;}
|
|
alpar@100
|
849 |
|
|
alpar@100
|
850 |
///Checks if a node is reachable from the root.
|
|
alpar@100
|
851 |
|
|
alpar@100
|
852 |
///Returns \c true if \c v is reachable from the root.
|
|
alpar@100
|
853 |
///\warning The source nodes are inditated as unreached.
|
|
alpar@100
|
854 |
///\pre \ref run() must be called before using this function.
|
|
alpar@100
|
855 |
///
|
|
alpar@100
|
856 |
bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
|
|
alpar@100
|
857 |
|
|
alpar@100
|
858 |
///Checks if a node is processed.
|
|
alpar@100
|
859 |
|
|
alpar@100
|
860 |
///Returns \c true if \c v is processed, i.e. the shortest
|
|
alpar@100
|
861 |
///path to \c v has already found.
|
|
alpar@100
|
862 |
///\pre \ref run() must be called before using this function.
|
|
alpar@100
|
863 |
///
|
|
alpar@100
|
864 |
bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
|
|
alpar@100
|
865 |
|
|
alpar@100
|
866 |
///@}
|
|
alpar@100
|
867 |
};
|
|
alpar@100
|
868 |
|
|
alpar@100
|
869 |
|
|
alpar@100
|
870 |
|
|
alpar@100
|
871 |
|
|
alpar@100
|
872 |
|
|
alpar@100
|
873 |
///Default traits class of Dijkstra function.
|
|
alpar@100
|
874 |
|
|
alpar@100
|
875 |
///Default traits class of Dijkstra function.
|
|
kpeter@157
|
876 |
///\tparam GR Digraph type.
|
|
kpeter@157
|
877 |
///\tparam LM Type of length map.
|
|
alpar@100
|
878 |
template<class GR, class LM>
|
|
alpar@100
|
879 |
struct DijkstraWizardDefaultTraits
|
|
alpar@100
|
880 |
{
|
|
alpar@100
|
881 |
///The digraph type the algorithm runs on.
|
|
alpar@100
|
882 |
typedef GR Digraph;
|
|
alpar@100
|
883 |
///The type of the map that stores the arc lengths.
|
|
alpar@100
|
884 |
|
|
alpar@100
|
885 |
///The type of the map that stores the arc lengths.
|
|
alpar@100
|
886 |
///It must meet the \ref concepts::ReadMap "ReadMap" concept.
|
|
alpar@100
|
887 |
typedef LM LengthMap;
|
|
alpar@100
|
888 |
//The type of the length of the arcs.
|
|
alpar@100
|
889 |
typedef typename LM::Value Value;
|
|
alpar@100
|
890 |
/// Operation traits for Dijkstra algorithm.
|
|
alpar@100
|
891 |
|
|
alpar@100
|
892 |
/// It defines the used operation by the algorithm.
|
|
alpar@100
|
893 |
/// \see DijkstraDefaultOperationTraits
|
|
alpar@100
|
894 |
typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
|
|
alpar@100
|
895 |
///The heap type used by Dijkstra algorithm.
|
|
alpar@100
|
896 |
|
|
alpar@100
|
897 |
/// The cross reference type used by heap.
|
|
alpar@100
|
898 |
|
|
alpar@100
|
899 |
/// The cross reference type used by heap.
|
|
alpar@100
|
900 |
/// Usually it is \c Digraph::NodeMap<int>.
|
|
alpar@100
|
901 |
typedef typename Digraph::template NodeMap<int> HeapCrossRef;
|
|
alpar@100
|
902 |
///Instantiates a HeapCrossRef.
|
|
alpar@100
|
903 |
|
|
alpar@100
|
904 |
///This function instantiates a \ref HeapCrossRef.
|
|
alpar@100
|
905 |
/// \param G is the digraph, to which we would like to define the
|
|
alpar@100
|
906 |
/// HeapCrossRef.
|
|
alpar@100
|
907 |
/// \todo The digraph alone may be insufficient for the initialization
|
|
alpar@100
|
908 |
static HeapCrossRef *createHeapCrossRef(const GR &G)
|
|
alpar@100
|
909 |
{
|
|
alpar@100
|
910 |
return new HeapCrossRef(G);
|
|
alpar@100
|
911 |
}
|
|
alpar@100
|
912 |
|
|
alpar@100
|
913 |
///The heap type used by Dijkstra algorithm.
|
|
alpar@100
|
914 |
|
|
alpar@100
|
915 |
///The heap type used by Dijkstra algorithm.
|
|
alpar@100
|
916 |
///
|
|
alpar@100
|
917 |
///\sa BinHeap
|
|
alpar@100
|
918 |
///\sa Dijkstra
|
|
alpar@100
|
919 |
typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
|
|
alpar@100
|
920 |
std::less<Value> > Heap;
|
|
alpar@100
|
921 |
|
|
alpar@100
|
922 |
static Heap *createHeap(HeapCrossRef& R)
|
|
alpar@100
|
923 |
{
|
|
alpar@100
|
924 |
return new Heap(R);
|
|
alpar@100
|
925 |
}
|
|
alpar@100
|
926 |
|
|
alpar@100
|
927 |
///\brief The type of the map that stores the last
|
|
alpar@100
|
928 |
///arcs of the shortest paths.
|
|
alpar@100
|
929 |
///
|
|
alpar@100
|
930 |
///The type of the map that stores the last
|
|
alpar@100
|
931 |
///arcs of the shortest paths.
|
|
alpar@100
|
932 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
|
|
alpar@100
|
933 |
///
|
|
alpar@100
|
934 |
typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
|
|
alpar@100
|
935 |
///Instantiates a PredMap.
|
|
alpar@100
|
936 |
|
|
alpar@100
|
937 |
///This function instantiates a \ref PredMap.
|
|
alpar@100
|
938 |
///\param g is the digraph, to which we would like to define the PredMap.
|
|
alpar@100
|
939 |
///\todo The digraph alone may be insufficient for the initialization
|
|
alpar@100
|
940 |
#ifdef DOXYGEN
|
|
alpar@100
|
941 |
static PredMap *createPredMap(const GR &g)
|
|
alpar@100
|
942 |
#else
|
|
alpar@100
|
943 |
static PredMap *createPredMap(const GR &)
|
|
alpar@100
|
944 |
#endif
|
|
alpar@100
|
945 |
{
|
|
alpar@100
|
946 |
return new PredMap();
|
|
alpar@100
|
947 |
}
|
|
alpar@100
|
948 |
///The type of the map that stores whether a nodes is processed.
|
|
alpar@100
|
949 |
|
|
alpar@100
|
950 |
///The type of the map that stores whether a nodes is processed.
|
|
alpar@100
|
951 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
|
|
alpar@100
|
952 |
///By default it is a NullMap.
|
|
alpar@100
|
953 |
///\todo If it is set to a real map,
|
|
alpar@100
|
954 |
///Dijkstra::processed() should read this.
|
|
alpar@100
|
955 |
///\todo named parameter to set this type, function to read and write.
|
|
alpar@100
|
956 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
|
|
alpar@100
|
957 |
///Instantiates a ProcessedMap.
|
|
alpar@100
|
958 |
|
|
alpar@100
|
959 |
///This function instantiates a \ref ProcessedMap.
|
|
alpar@100
|
960 |
///\param g is the digraph, to which
|
|
alpar@100
|
961 |
///we would like to define the \ref ProcessedMap
|
|
alpar@100
|
962 |
#ifdef DOXYGEN
|
|
alpar@100
|
963 |
static ProcessedMap *createProcessedMap(const GR &g)
|
|
alpar@100
|
964 |
#else
|
|
alpar@100
|
965 |
static ProcessedMap *createProcessedMap(const GR &)
|
|
alpar@100
|
966 |
#endif
|
|
alpar@100
|
967 |
{
|
|
alpar@100
|
968 |
return new ProcessedMap();
|
|
alpar@100
|
969 |
}
|
|
alpar@100
|
970 |
///The type of the map that stores the dists of the nodes.
|
|
alpar@100
|
971 |
|
|
alpar@100
|
972 |
///The type of the map that stores the dists of the nodes.
|
|
alpar@100
|
973 |
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
|
|
alpar@100
|
974 |
///
|
|
alpar@100
|
975 |
typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
|
|
alpar@100
|
976 |
///Instantiates a DistMap.
|
|
alpar@100
|
977 |
|
|
alpar@100
|
978 |
///This function instantiates a \ref DistMap.
|
|
alpar@100
|
979 |
///\param g is the digraph, to which we would like to define the \ref DistMap
|
|
alpar@100
|
980 |
#ifdef DOXYGEN
|
|
alpar@100
|
981 |
static DistMap *createDistMap(const GR &g)
|
|
alpar@100
|
982 |
#else
|
|
alpar@100
|
983 |
static DistMap *createDistMap(const GR &)
|
|
alpar@100
|
984 |
#endif
|
|
alpar@100
|
985 |
{
|
|
alpar@100
|
986 |
return new DistMap();
|
|
alpar@100
|
987 |
}
|
|
alpar@100
|
988 |
};
|
|
alpar@100
|
989 |
|
|
alpar@100
|
990 |
/// Default traits used by \ref DijkstraWizard
|
|
alpar@100
|
991 |
|
|
alpar@100
|
992 |
/// To make it easier to use Dijkstra algorithm
|
|
alpar@100
|
993 |
///we have created a wizard class.
|
|
alpar@100
|
994 |
/// This \ref DijkstraWizard class needs default traits,
|
|
alpar@100
|
995 |
///as well as the \ref Dijkstra class.
|
|
alpar@100
|
996 |
/// The \ref DijkstraWizardBase is a class to be the default traits of the
|
|
alpar@100
|
997 |
/// \ref DijkstraWizard class.
|
|
alpar@100
|
998 |
/// \todo More named parameters are required...
|
|
alpar@100
|
999 |
template<class GR,class LM>
|
|
alpar@100
|
1000 |
class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
|
|
alpar@100
|
1001 |
{
|
|
alpar@100
|
1002 |
|
|
alpar@100
|
1003 |
typedef DijkstraWizardDefaultTraits<GR,LM> Base;
|
|
alpar@100
|
1004 |
protected:
|
|
alpar@100
|
1005 |
/// Type of the nodes in the digraph.
|
|
alpar@100
|
1006 |
typedef typename Base::Digraph::Node Node;
|
|
alpar@100
|
1007 |
|
|
alpar@100
|
1008 |
/// Pointer to the underlying digraph.
|
|
alpar@100
|
1009 |
void *_g;
|
|
alpar@100
|
1010 |
/// Pointer to the length map
|
|
alpar@100
|
1011 |
void *_length;
|
|
alpar@100
|
1012 |
///Pointer to the map of predecessors arcs.
|
|
alpar@100
|
1013 |
void *_pred;
|
|
alpar@100
|
1014 |
///Pointer to the map of distances.
|
|
alpar@100
|
1015 |
void *_dist;
|
|
alpar@100
|
1016 |
///Pointer to the source node.
|
|
alpar@100
|
1017 |
Node _source;
|
|
alpar@100
|
1018 |
|
|
alpar@100
|
1019 |
public:
|
|
alpar@100
|
1020 |
/// Constructor.
|
|
alpar@100
|
1021 |
|
|
alpar@100
|
1022 |
/// This constructor does not require parameters, therefore it initiates
|
|
alpar@100
|
1023 |
/// all of the attributes to default values (0, INVALID).
|
|
alpar@100
|
1024 |
DijkstraWizardBase() : _g(0), _length(0), _pred(0),
|
|
alpar@100
|
1025 |
_dist(0), _source(INVALID) {}
|
|
alpar@100
|
1026 |
|
|
alpar@100
|
1027 |
/// Constructor.
|
|
alpar@100
|
1028 |
|
|
alpar@100
|
1029 |
/// This constructor requires some parameters,
|
|
alpar@100
|
1030 |
/// listed in the parameters list.
|
|
alpar@100
|
1031 |
/// Others are initiated to 0.
|
|
alpar@100
|
1032 |
/// \param g is the initial value of \ref _g
|
|
alpar@100
|
1033 |
/// \param l is the initial value of \ref _length
|
|
alpar@100
|
1034 |
/// \param s is the initial value of \ref _source
|
|
alpar@100
|
1035 |
DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
|
|
alpar@100
|
1036 |
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
|
|
alpar@100
|
1037 |
_length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
|
|
alpar@100
|
1038 |
_pred(0), _dist(0), _source(s) {}
|
|
alpar@100
|
1039 |
|
|
alpar@100
|
1040 |
};
|
|
alpar@100
|
1041 |
|
|
alpar@100
|
1042 |
/// A class to make the usage of Dijkstra algorithm easier
|
|
alpar@100
|
1043 |
|
|
alpar@100
|
1044 |
/// This class is created to make it easier to use Dijkstra algorithm.
|
|
alpar@100
|
1045 |
/// It uses the functions and features of the plain \ref Dijkstra,
|
|
alpar@100
|
1046 |
/// but it is much simpler to use it.
|
|
alpar@100
|
1047 |
///
|
|
alpar@100
|
1048 |
/// Simplicity means that the way to change the types defined
|
|
alpar@100
|
1049 |
/// in the traits class is based on functions that returns the new class
|
|
alpar@100
|
1050 |
/// and not on templatable built-in classes.
|
|
alpar@100
|
1051 |
/// When using the plain \ref Dijkstra
|
|
alpar@100
|
1052 |
/// the new class with the modified type comes from
|
|
alpar@100
|
1053 |
/// the original class by using the ::
|
|
alpar@100
|
1054 |
/// operator. In the case of \ref DijkstraWizard only
|
|
alpar@100
|
1055 |
/// a function have to be called and it will
|
|
alpar@100
|
1056 |
/// return the needed class.
|
|
alpar@100
|
1057 |
///
|
|
alpar@100
|
1058 |
/// It does not have own \ref run method. When its \ref run method is called
|
|
alpar@100
|
1059 |
/// it initiates a plain \ref Dijkstra class, and calls the \ref
|
|
alpar@100
|
1060 |
/// Dijkstra::run method of it.
|
|
alpar@100
|
1061 |
template<class TR>
|
|
alpar@100
|
1062 |
class DijkstraWizard : public TR
|
|
alpar@100
|
1063 |
{
|
|
alpar@100
|
1064 |
typedef TR Base;
|
|
alpar@100
|
1065 |
|
|
alpar@100
|
1066 |
///The type of the underlying digraph.
|
|
alpar@100
|
1067 |
typedef typename TR::Digraph Digraph;
|
|
alpar@100
|
1068 |
//\e
|
|
alpar@100
|
1069 |
typedef typename Digraph::Node Node;
|
|
alpar@100
|
1070 |
//\e
|
|
alpar@100
|
1071 |
typedef typename Digraph::NodeIt NodeIt;
|
|
alpar@100
|
1072 |
//\e
|
|
alpar@100
|
1073 |
typedef typename Digraph::Arc Arc;
|
|
alpar@100
|
1074 |
//\e
|
|
alpar@100
|
1075 |
typedef typename Digraph::OutArcIt OutArcIt;
|
|
alpar@100
|
1076 |
|
|
alpar@100
|
1077 |
///The type of the map that stores the arc lengths.
|
|
alpar@100
|
1078 |
typedef typename TR::LengthMap LengthMap;
|
|
alpar@100
|
1079 |
///The type of the length of the arcs.
|
|
alpar@100
|
1080 |
typedef typename LengthMap::Value Value;
|
|
alpar@100
|
1081 |
///\brief The type of the map that stores the last
|
|
alpar@100
|
1082 |
///arcs of the shortest paths.
|
|
alpar@100
|
1083 |
typedef typename TR::PredMap PredMap;
|
|
alpar@100
|
1084 |
///The type of the map that stores the dists of the nodes.
|
|
alpar@100
|
1085 |
typedef typename TR::DistMap DistMap;
|
|
alpar@100
|
1086 |
///The heap type used by the dijkstra algorithm.
|
|
alpar@100
|
1087 |
typedef typename TR::Heap Heap;
|
|
alpar@100
|
1088 |
public:
|
|
alpar@100
|
1089 |
/// Constructor.
|
|
alpar@100
|
1090 |
DijkstraWizard() : TR() {}
|
|
alpar@100
|
1091 |
|
|
alpar@100
|
1092 |
/// Constructor that requires parameters.
|
|
alpar@100
|
1093 |
|
|
alpar@100
|
1094 |
/// Constructor that requires parameters.
|
|
alpar@100
|
1095 |
/// These parameters will be the default values for the traits class.
|
|
alpar@100
|
1096 |
DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
|
|
alpar@100
|
1097 |
TR(g,l,s) {}
|
|
alpar@100
|
1098 |
|
|
alpar@100
|
1099 |
///Copy constructor
|
|
alpar@100
|
1100 |
DijkstraWizard(const TR &b) : TR(b) {}
|
|
alpar@100
|
1101 |
|
|
alpar@100
|
1102 |
~DijkstraWizard() {}
|
|
alpar@100
|
1103 |
|
|
alpar@100
|
1104 |
///Runs Dijkstra algorithm from a given node.
|
|
alpar@100
|
1105 |
|
|
alpar@100
|
1106 |
///Runs Dijkstra algorithm from a given node.
|
|
alpar@100
|
1107 |
///The node can be given by the \ref source function.
|
|
alpar@100
|
1108 |
void run()
|
|
alpar@100
|
1109 |
{
|
|
alpar@100
|
1110 |
if(Base::_source==INVALID) throw UninitializedParameter();
|
|
alpar@100
|
1111 |
Dijkstra<Digraph,LengthMap,TR>
|
|
alpar@100
|
1112 |
dij(*reinterpret_cast<const Digraph*>(Base::_g),
|
|
alpar@100
|
1113 |
*reinterpret_cast<const LengthMap*>(Base::_length));
|
|
alpar@100
|
1114 |
if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
|
|
alpar@100
|
1115 |
if(Base::_dist) dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
|
|
alpar@100
|
1116 |
dij.run(Base::_source);
|
|
alpar@100
|
1117 |
}
|
|
alpar@100
|
1118 |
|
|
alpar@100
|
1119 |
///Runs Dijkstra algorithm from the given node.
|
|
alpar@100
|
1120 |
|
|
alpar@100
|
1121 |
///Runs Dijkstra algorithm from the given node.
|
|
alpar@100
|
1122 |
///\param s is the given source.
|
|
alpar@100
|
1123 |
void run(Node s)
|
|
alpar@100
|
1124 |
{
|
|
alpar@100
|
1125 |
Base::_source=s;
|
|
alpar@100
|
1126 |
run();
|
|
alpar@100
|
1127 |
}
|
|
alpar@100
|
1128 |
|
|
alpar@100
|
1129 |
template<class T>
|
|
alpar@100
|
1130 |
struct DefPredMapBase : public Base {
|
|
alpar@100
|
1131 |
typedef T PredMap;
|
|
alpar@100
|
1132 |
static PredMap *createPredMap(const Digraph &) { return 0; };
|
|
alpar@100
|
1133 |
DefPredMapBase(const TR &b) : TR(b) {}
|
|
alpar@100
|
1134 |
};
|
|
alpar@100
|
1135 |
|
|
alpar@100
|
1136 |
///\brief \ref named-templ-param "Named parameter"
|
|
alpar@100
|
1137 |
///function for setting PredMap type
|
|
alpar@100
|
1138 |
///
|
|
alpar@100
|
1139 |
/// \ref named-templ-param "Named parameter"
|
|
alpar@100
|
1140 |
///function for setting PredMap type
|
|
alpar@100
|
1141 |
///
|
|
alpar@100
|
1142 |
template<class T>
|
|
alpar@100
|
1143 |
DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
|
|
alpar@100
|
1144 |
{
|
|
alpar@100
|
1145 |
Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
|
|
alpar@100
|
1146 |
return DijkstraWizard<DefPredMapBase<T> >(*this);
|
|
alpar@100
|
1147 |
}
|
|
alpar@100
|
1148 |
|
|
alpar@100
|
1149 |
template<class T>
|
|
alpar@100
|
1150 |
struct DefDistMapBase : public Base {
|
|
alpar@100
|
1151 |
typedef T DistMap;
|
|
alpar@100
|
1152 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
|
alpar@100
|
1153 |
DefDistMapBase(const TR &b) : TR(b) {}
|
|
alpar@100
|
1154 |
};
|
|
alpar@100
|
1155 |
|
|
alpar@100
|
1156 |
///\brief \ref named-templ-param "Named parameter"
|
|
alpar@100
|
1157 |
///function for setting DistMap type
|
|
alpar@100
|
1158 |
///
|
|
alpar@100
|
1159 |
/// \ref named-templ-param "Named parameter"
|
|
alpar@100
|
1160 |
///function for setting DistMap type
|
|
alpar@100
|
1161 |
///
|
|
alpar@100
|
1162 |
template<class T>
|
|
alpar@100
|
1163 |
DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
|
|
alpar@100
|
1164 |
{
|
|
alpar@100
|
1165 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
|
|
alpar@100
|
1166 |
return DijkstraWizard<DefDistMapBase<T> >(*this);
|
|
alpar@100
|
1167 |
}
|
|
alpar@100
|
1168 |
|
|
alpar@100
|
1169 |
/// Sets the source node, from which the Dijkstra algorithm runs.
|
|
alpar@100
|
1170 |
|
|
alpar@100
|
1171 |
/// Sets the source node, from which the Dijkstra algorithm runs.
|
|
alpar@100
|
1172 |
/// \param s is the source node.
|
|
alpar@100
|
1173 |
DijkstraWizard<TR> &source(Node s)
|
|
alpar@100
|
1174 |
{
|
|
alpar@100
|
1175 |
Base::_source=s;
|
|
alpar@100
|
1176 |
return *this;
|
|
alpar@100
|
1177 |
}
|
|
alpar@100
|
1178 |
|
|
alpar@100
|
1179 |
};
|
|
alpar@100
|
1180 |
|
|
alpar@100
|
1181 |
///Function type interface for Dijkstra algorithm.
|
|
alpar@100
|
1182 |
|
|
alpar@100
|
1183 |
/// \ingroup shortest_path
|
|
alpar@100
|
1184 |
///Function type interface for Dijkstra algorithm.
|
|
alpar@100
|
1185 |
///
|
|
alpar@100
|
1186 |
///This function also has several
|
|
alpar@100
|
1187 |
///\ref named-templ-func-param "named parameters",
|
|
alpar@100
|
1188 |
///they are declared as the members of class \ref DijkstraWizard.
|
|
alpar@100
|
1189 |
///The following
|
|
alpar@100
|
1190 |
///example shows how to use these parameters.
|
|
alpar@100
|
1191 |
///\code
|
|
alpar@100
|
1192 |
/// dijkstra(g,length,source).predMap(preds).run();
|
|
alpar@100
|
1193 |
///\endcode
|
|
alpar@100
|
1194 |
///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
|
|
alpar@100
|
1195 |
///to the end of the parameter list.
|
|
alpar@100
|
1196 |
///\sa DijkstraWizard
|
|
alpar@100
|
1197 |
///\sa Dijkstra
|
|
alpar@100
|
1198 |
template<class GR, class LM>
|
|
alpar@100
|
1199 |
DijkstraWizard<DijkstraWizardBase<GR,LM> >
|
|
alpar@100
|
1200 |
dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
|
|
alpar@100
|
1201 |
{
|
|
alpar@100
|
1202 |
return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
|
|
alpar@100
|
1203 |
}
|
|
alpar@100
|
1204 |
|
|
alpar@100
|
1205 |
} //END OF NAMESPACE LEMON
|
|
alpar@100
|
1206 |
|
|
alpar@100
|
1207 |
#endif
|