kpeter@743
|
1 |
/* -*- C++ -*-
|
kpeter@743
|
2 |
*
|
kpeter@743
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
kpeter@743
|
4 |
*
|
kpeter@743
|
5 |
* Copyright (C) 2003-2008
|
kpeter@743
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@743
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@743
|
8 |
*
|
kpeter@743
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@743
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@743
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@743
|
12 |
*
|
kpeter@743
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@743
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@743
|
15 |
* purpose.
|
kpeter@743
|
16 |
*
|
kpeter@743
|
17 |
*/
|
kpeter@743
|
18 |
|
kpeter@744
|
19 |
#ifndef LEMON_BELLMAN_FORD_H
|
kpeter@744
|
20 |
#define LEMON_BELLMAN_FORD_H
|
kpeter@743
|
21 |
|
kpeter@743
|
22 |
/// \ingroup shortest_path
|
kpeter@743
|
23 |
/// \file
|
kpeter@743
|
24 |
/// \brief Bellman-Ford algorithm.
|
kpeter@743
|
25 |
|
kpeter@828
|
26 |
#include <lemon/list_graph.h>
|
kpeter@743
|
27 |
#include <lemon/bits/path_dump.h>
|
kpeter@743
|
28 |
#include <lemon/core.h>
|
kpeter@743
|
29 |
#include <lemon/error.h>
|
kpeter@743
|
30 |
#include <lemon/maps.h>
|
kpeter@744
|
31 |
#include <lemon/path.h>
|
kpeter@743
|
32 |
|
kpeter@743
|
33 |
#include <limits>
|
kpeter@743
|
34 |
|
kpeter@743
|
35 |
namespace lemon {
|
kpeter@743
|
36 |
|
kpeter@743
|
37 |
/// \brief Default OperationTraits for the BellmanFord algorithm class.
|
kpeter@743
|
38 |
///
|
kpeter@744
|
39 |
/// This operation traits class defines all computational operations
|
kpeter@744
|
40 |
/// and constants that are used in the Bellman-Ford algorithm.
|
kpeter@744
|
41 |
/// The default implementation is based on the \c numeric_limits class.
|
kpeter@744
|
42 |
/// If the numeric type does not have infinity value, then the maximum
|
kpeter@744
|
43 |
/// value is used as extremal infinity value.
|
kpeter@743
|
44 |
template <
|
kpeter@744
|
45 |
typename V,
|
kpeter@744
|
46 |
bool has_inf = std::numeric_limits<V>::has_infinity>
|
kpeter@743
|
47 |
struct BellmanFordDefaultOperationTraits {
|
kpeter@744
|
48 |
/// \e
|
kpeter@744
|
49 |
typedef V Value;
|
kpeter@743
|
50 |
/// \brief Gives back the zero value of the type.
|
kpeter@743
|
51 |
static Value zero() {
|
kpeter@743
|
52 |
return static_cast<Value>(0);
|
kpeter@743
|
53 |
}
|
kpeter@743
|
54 |
/// \brief Gives back the positive infinity value of the type.
|
kpeter@743
|
55 |
static Value infinity() {
|
kpeter@743
|
56 |
return std::numeric_limits<Value>::infinity();
|
kpeter@743
|
57 |
}
|
kpeter@743
|
58 |
/// \brief Gives back the sum of the given two elements.
|
kpeter@743
|
59 |
static Value plus(const Value& left, const Value& right) {
|
kpeter@743
|
60 |
return left + right;
|
kpeter@743
|
61 |
}
|
kpeter@744
|
62 |
/// \brief Gives back \c true only if the first value is less than
|
kpeter@744
|
63 |
/// the second.
|
kpeter@743
|
64 |
static bool less(const Value& left, const Value& right) {
|
kpeter@743
|
65 |
return left < right;
|
kpeter@743
|
66 |
}
|
kpeter@743
|
67 |
};
|
kpeter@743
|
68 |
|
kpeter@744
|
69 |
template <typename V>
|
kpeter@744
|
70 |
struct BellmanFordDefaultOperationTraits<V, false> {
|
kpeter@744
|
71 |
typedef V Value;
|
kpeter@743
|
72 |
static Value zero() {
|
kpeter@743
|
73 |
return static_cast<Value>(0);
|
kpeter@743
|
74 |
}
|
kpeter@743
|
75 |
static Value infinity() {
|
kpeter@743
|
76 |
return std::numeric_limits<Value>::max();
|
kpeter@743
|
77 |
}
|
kpeter@743
|
78 |
static Value plus(const Value& left, const Value& right) {
|
kpeter@743
|
79 |
if (left == infinity() || right == infinity()) return infinity();
|
kpeter@743
|
80 |
return left + right;
|
kpeter@743
|
81 |
}
|
kpeter@743
|
82 |
static bool less(const Value& left, const Value& right) {
|
kpeter@743
|
83 |
return left < right;
|
kpeter@743
|
84 |
}
|
kpeter@743
|
85 |
};
|
kpeter@743
|
86 |
|
kpeter@743
|
87 |
/// \brief Default traits class of BellmanFord class.
|
kpeter@743
|
88 |
///
|
kpeter@743
|
89 |
/// Default traits class of BellmanFord class.
|
kpeter@744
|
90 |
/// \param GR The type of the digraph.
|
kpeter@744
|
91 |
/// \param LEN The type of the length map.
|
kpeter@744
|
92 |
template<typename GR, typename LEN>
|
kpeter@743
|
93 |
struct BellmanFordDefaultTraits {
|
kpeter@744
|
94 |
/// The type of the digraph the algorithm runs on.
|
kpeter@744
|
95 |
typedef GR Digraph;
|
kpeter@743
|
96 |
|
kpeter@743
|
97 |
/// \brief The type of the map that stores the arc lengths.
|
kpeter@743
|
98 |
///
|
kpeter@743
|
99 |
/// The type of the map that stores the arc lengths.
|
kpeter@744
|
100 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@744
|
101 |
typedef LEN LengthMap;
|
kpeter@743
|
102 |
|
kpeter@744
|
103 |
/// The type of the arc lengths.
|
kpeter@744
|
104 |
typedef typename LEN::Value Value;
|
kpeter@743
|
105 |
|
kpeter@743
|
106 |
/// \brief Operation traits for Bellman-Ford algorithm.
|
kpeter@743
|
107 |
///
|
kpeter@744
|
108 |
/// It defines the used operations and the infinity value for the
|
kpeter@744
|
109 |
/// given \c Value type.
|
kpeter@743
|
110 |
/// \see BellmanFordDefaultOperationTraits
|
kpeter@743
|
111 |
typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
|
kpeter@743
|
112 |
|
kpeter@743
|
113 |
/// \brief The type of the map that stores the last arcs of the
|
kpeter@743
|
114 |
/// shortest paths.
|
kpeter@743
|
115 |
///
|
kpeter@743
|
116 |
/// The type of the map that stores the last
|
kpeter@743
|
117 |
/// arcs of the shortest paths.
|
kpeter@744
|
118 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@744
|
119 |
typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
|
kpeter@743
|
120 |
|
kpeter@744
|
121 |
/// \brief Instantiates a \c PredMap.
|
kpeter@743
|
122 |
///
|
kpeter@743
|
123 |
/// This function instantiates a \ref PredMap.
|
kpeter@744
|
124 |
/// \param g is the digraph to which we would like to define the
|
kpeter@744
|
125 |
/// \ref PredMap.
|
kpeter@744
|
126 |
static PredMap *createPredMap(const GR& g) {
|
kpeter@744
|
127 |
return new PredMap(g);
|
kpeter@743
|
128 |
}
|
kpeter@743
|
129 |
|
kpeter@744
|
130 |
/// \brief The type of the map that stores the distances of the nodes.
|
kpeter@743
|
131 |
///
|
kpeter@744
|
132 |
/// The type of the map that stores the distances of the nodes.
|
kpeter@744
|
133 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@744
|
134 |
typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
|
kpeter@743
|
135 |
|
kpeter@744
|
136 |
/// \brief Instantiates a \c DistMap.
|
kpeter@743
|
137 |
///
|
kpeter@743
|
138 |
/// This function instantiates a \ref DistMap.
|
kpeter@744
|
139 |
/// \param g is the digraph to which we would like to define the
|
kpeter@744
|
140 |
/// \ref DistMap.
|
kpeter@744
|
141 |
static DistMap *createDistMap(const GR& g) {
|
kpeter@744
|
142 |
return new DistMap(g);
|
kpeter@743
|
143 |
}
|
kpeter@743
|
144 |
|
kpeter@743
|
145 |
};
|
kpeter@743
|
146 |
|
kpeter@743
|
147 |
/// \brief %BellmanFord algorithm class.
|
kpeter@743
|
148 |
///
|
kpeter@743
|
149 |
/// \ingroup shortest_path
|
kpeter@744
|
150 |
/// This class provides an efficient implementation of the Bellman-Ford
|
kpeter@744
|
151 |
/// algorithm. The maximum time complexity of the algorithm is
|
kpeter@744
|
152 |
/// <tt>O(ne)</tt>.
|
kpeter@744
|
153 |
///
|
kpeter@744
|
154 |
/// The Bellman-Ford algorithm solves the single-source shortest path
|
kpeter@744
|
155 |
/// problem when the arcs can have negative lengths, but the digraph
|
kpeter@744
|
156 |
/// should not contain directed cycles with negative total length.
|
kpeter@744
|
157 |
/// If all arc costs are non-negative, consider to use the Dijkstra
|
kpeter@744
|
158 |
/// algorithm instead, since it is more efficient.
|
kpeter@744
|
159 |
///
|
kpeter@744
|
160 |
/// The arc lengths are passed to the algorithm using a
|
kpeter@743
|
161 |
/// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
|
kpeter@744
|
162 |
/// kind of length. The type of the length values is determined by the
|
kpeter@744
|
163 |
/// \ref concepts::ReadMap::Value "Value" type of the length map.
|
kpeter@743
|
164 |
///
|
kpeter@744
|
165 |
/// There is also a \ref bellmanFord() "function-type interface" for the
|
kpeter@744
|
166 |
/// Bellman-Ford algorithm, which is convenient in the simplier cases and
|
kpeter@744
|
167 |
/// it can be used easier.
|
kpeter@743
|
168 |
///
|
kpeter@744
|
169 |
/// \tparam GR The type of the digraph the algorithm runs on.
|
kpeter@744
|
170 |
/// The default type is \ref ListDigraph.
|
kpeter@744
|
171 |
/// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
|
kpeter@744
|
172 |
/// the lengths of the arcs. The default map type is
|
kpeter@744
|
173 |
/// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
|
kpeter@743
|
174 |
#ifdef DOXYGEN
|
kpeter@744
|
175 |
template <typename GR, typename LEN, typename TR>
|
kpeter@743
|
176 |
#else
|
kpeter@744
|
177 |
template <typename GR=ListDigraph,
|
kpeter@744
|
178 |
typename LEN=typename GR::template ArcMap<int>,
|
kpeter@744
|
179 |
typename TR=BellmanFordDefaultTraits<GR,LEN> >
|
kpeter@743
|
180 |
#endif
|
kpeter@743
|
181 |
class BellmanFord {
|
kpeter@743
|
182 |
public:
|
kpeter@743
|
183 |
|
kpeter@743
|
184 |
///The type of the underlying digraph.
|
kpeter@744
|
185 |
typedef typename TR::Digraph Digraph;
|
kpeter@744
|
186 |
|
kpeter@744
|
187 |
/// \brief The type of the arc lengths.
|
kpeter@744
|
188 |
typedef typename TR::LengthMap::Value Value;
|
kpeter@744
|
189 |
/// \brief The type of the map that stores the arc lengths.
|
kpeter@744
|
190 |
typedef typename TR::LengthMap LengthMap;
|
kpeter@744
|
191 |
/// \brief The type of the map that stores the last
|
kpeter@744
|
192 |
/// arcs of the shortest paths.
|
kpeter@744
|
193 |
typedef typename TR::PredMap PredMap;
|
kpeter@744
|
194 |
/// \brief The type of the map that stores the distances of the nodes.
|
kpeter@744
|
195 |
typedef typename TR::DistMap DistMap;
|
kpeter@744
|
196 |
/// The type of the paths.
|
kpeter@744
|
197 |
typedef PredMapPath<Digraph, PredMap> Path;
|
kpeter@744
|
198 |
///\brief The \ref BellmanFordDefaultOperationTraits
|
kpeter@744
|
199 |
/// "operation traits class" of the algorithm.
|
kpeter@744
|
200 |
typedef typename TR::OperationTraits OperationTraits;
|
kpeter@744
|
201 |
|
kpeter@744
|
202 |
///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
|
kpeter@744
|
203 |
typedef TR Traits;
|
kpeter@744
|
204 |
|
kpeter@744
|
205 |
private:
|
kpeter@743
|
206 |
|
kpeter@743
|
207 |
typedef typename Digraph::Node Node;
|
kpeter@743
|
208 |
typedef typename Digraph::NodeIt NodeIt;
|
kpeter@743
|
209 |
typedef typename Digraph::Arc Arc;
|
kpeter@743
|
210 |
typedef typename Digraph::OutArcIt OutArcIt;
|
kpeter@744
|
211 |
|
kpeter@744
|
212 |
// Pointer to the underlying digraph.
|
kpeter@744
|
213 |
const Digraph *_gr;
|
kpeter@744
|
214 |
// Pointer to the length map
|
kpeter@744
|
215 |
const LengthMap *_length;
|
kpeter@744
|
216 |
// Pointer to the map of predecessors arcs.
|
kpeter@743
|
217 |
PredMap *_pred;
|
kpeter@744
|
218 |
// Indicates if _pred is locally allocated (true) or not.
|
kpeter@744
|
219 |
bool _local_pred;
|
kpeter@744
|
220 |
// Pointer to the map of distances.
|
kpeter@743
|
221 |
DistMap *_dist;
|
kpeter@744
|
222 |
// Indicates if _dist is locally allocated (true) or not.
|
kpeter@744
|
223 |
bool _local_dist;
|
kpeter@743
|
224 |
|
kpeter@743
|
225 |
typedef typename Digraph::template NodeMap<bool> MaskMap;
|
kpeter@743
|
226 |
MaskMap *_mask;
|
kpeter@743
|
227 |
|
kpeter@743
|
228 |
std::vector<Node> _process;
|
kpeter@743
|
229 |
|
kpeter@744
|
230 |
// Creates the maps if necessary.
|
kpeter@743
|
231 |
void create_maps() {
|
kpeter@743
|
232 |
if(!_pred) {
|
kpeter@744
|
233 |
_local_pred = true;
|
kpeter@744
|
234 |
_pred = Traits::createPredMap(*_gr);
|
kpeter@743
|
235 |
}
|
kpeter@743
|
236 |
if(!_dist) {
|
kpeter@744
|
237 |
_local_dist = true;
|
kpeter@744
|
238 |
_dist = Traits::createDistMap(*_gr);
|
kpeter@743
|
239 |
}
|
kpeter@744
|
240 |
_mask = new MaskMap(*_gr, false);
|
kpeter@743
|
241 |
}
|
kpeter@743
|
242 |
|
kpeter@743
|
243 |
public :
|
kpeter@743
|
244 |
|
kpeter@743
|
245 |
typedef BellmanFord Create;
|
kpeter@743
|
246 |
|
kpeter@744
|
247 |
/// \name Named Template Parameters
|
kpeter@743
|
248 |
|
kpeter@743
|
249 |
///@{
|
kpeter@743
|
250 |
|
kpeter@743
|
251 |
template <class T>
|
kpeter@744
|
252 |
struct SetPredMapTraits : public Traits {
|
kpeter@743
|
253 |
typedef T PredMap;
|
kpeter@743
|
254 |
static PredMap *createPredMap(const Digraph&) {
|
kpeter@743
|
255 |
LEMON_ASSERT(false, "PredMap is not initialized");
|
kpeter@743
|
256 |
return 0; // ignore warnings
|
kpeter@743
|
257 |
}
|
kpeter@743
|
258 |
};
|
kpeter@743
|
259 |
|
kpeter@744
|
260 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
261 |
/// \c PredMap type.
|
kpeter@743
|
262 |
///
|
kpeter@744
|
263 |
/// \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
264 |
/// \c PredMap type.
|
kpeter@744
|
265 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@743
|
266 |
template <class T>
|
kpeter@743
|
267 |
struct SetPredMap
|
kpeter@744
|
268 |
: public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
|
kpeter@744
|
269 |
typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
|
kpeter@743
|
270 |
};
|
kpeter@743
|
271 |
|
kpeter@743
|
272 |
template <class T>
|
kpeter@744
|
273 |
struct SetDistMapTraits : public Traits {
|
kpeter@743
|
274 |
typedef T DistMap;
|
kpeter@743
|
275 |
static DistMap *createDistMap(const Digraph&) {
|
kpeter@743
|
276 |
LEMON_ASSERT(false, "DistMap is not initialized");
|
kpeter@743
|
277 |
return 0; // ignore warnings
|
kpeter@743
|
278 |
}
|
kpeter@743
|
279 |
};
|
kpeter@743
|
280 |
|
kpeter@744
|
281 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
282 |
/// \c DistMap type.
|
kpeter@743
|
283 |
///
|
kpeter@744
|
284 |
/// \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
285 |
/// \c DistMap type.
|
kpeter@744
|
286 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@743
|
287 |
template <class T>
|
kpeter@743
|
288 |
struct SetDistMap
|
kpeter@744
|
289 |
: public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
|
kpeter@744
|
290 |
typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
|
kpeter@743
|
291 |
};
|
kpeter@744
|
292 |
|
kpeter@743
|
293 |
template <class T>
|
kpeter@744
|
294 |
struct SetOperationTraitsTraits : public Traits {
|
kpeter@743
|
295 |
typedef T OperationTraits;
|
kpeter@743
|
296 |
};
|
kpeter@743
|
297 |
|
kpeter@743
|
298 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
299 |
/// \c OperationTraits type.
|
kpeter@743
|
300 |
///
|
kpeter@744
|
301 |
/// \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
302 |
/// \c OperationTraits type.
|
kpeter@744
|
303 |
/// For more information see \ref BellmanFordDefaultOperationTraits.
|
kpeter@743
|
304 |
template <class T>
|
kpeter@743
|
305 |
struct SetOperationTraits
|
kpeter@744
|
306 |
: public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
|
kpeter@744
|
307 |
typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
|
kpeter@743
|
308 |
Create;
|
kpeter@743
|
309 |
};
|
kpeter@743
|
310 |
|
kpeter@743
|
311 |
///@}
|
kpeter@743
|
312 |
|
kpeter@743
|
313 |
protected:
|
kpeter@743
|
314 |
|
kpeter@743
|
315 |
BellmanFord() {}
|
kpeter@743
|
316 |
|
kpeter@743
|
317 |
public:
|
kpeter@743
|
318 |
|
kpeter@743
|
319 |
/// \brief Constructor.
|
kpeter@743
|
320 |
///
|
kpeter@744
|
321 |
/// Constructor.
|
kpeter@744
|
322 |
/// \param g The digraph the algorithm runs on.
|
kpeter@744
|
323 |
/// \param length The length map used by the algorithm.
|
kpeter@744
|
324 |
BellmanFord(const Digraph& g, const LengthMap& length) :
|
kpeter@744
|
325 |
_gr(&g), _length(&length),
|
kpeter@744
|
326 |
_pred(0), _local_pred(false),
|
kpeter@744
|
327 |
_dist(0), _local_dist(false), _mask(0) {}
|
kpeter@743
|
328 |
|
kpeter@743
|
329 |
///Destructor.
|
kpeter@743
|
330 |
~BellmanFord() {
|
kpeter@744
|
331 |
if(_local_pred) delete _pred;
|
kpeter@744
|
332 |
if(_local_dist) delete _dist;
|
kpeter@743
|
333 |
if(_mask) delete _mask;
|
kpeter@743
|
334 |
}
|
kpeter@743
|
335 |
|
kpeter@743
|
336 |
/// \brief Sets the length map.
|
kpeter@743
|
337 |
///
|
kpeter@743
|
338 |
/// Sets the length map.
|
kpeter@744
|
339 |
/// \return <tt>(*this)</tt>
|
kpeter@744
|
340 |
BellmanFord &lengthMap(const LengthMap &map) {
|
kpeter@744
|
341 |
_length = ↦
|
kpeter@743
|
342 |
return *this;
|
kpeter@743
|
343 |
}
|
kpeter@743
|
344 |
|
kpeter@744
|
345 |
/// \brief Sets the map that stores the predecessor arcs.
|
kpeter@743
|
346 |
///
|
kpeter@744
|
347 |
/// Sets the map that stores the predecessor arcs.
|
kpeter@744
|
348 |
/// If you don't use this function before calling \ref run()
|
kpeter@744
|
349 |
/// or \ref init(), an instance will be allocated automatically.
|
kpeter@744
|
350 |
/// The destructor deallocates this automatically allocated map,
|
kpeter@744
|
351 |
/// of course.
|
kpeter@744
|
352 |
/// \return <tt>(*this)</tt>
|
kpeter@744
|
353 |
BellmanFord &predMap(PredMap &map) {
|
kpeter@744
|
354 |
if(_local_pred) {
|
kpeter@743
|
355 |
delete _pred;
|
kpeter@744
|
356 |
_local_pred=false;
|
kpeter@743
|
357 |
}
|
kpeter@744
|
358 |
_pred = ↦
|
kpeter@743
|
359 |
return *this;
|
kpeter@743
|
360 |
}
|
kpeter@743
|
361 |
|
kpeter@744
|
362 |
/// \brief Sets the map that stores the distances of the nodes.
|
kpeter@743
|
363 |
///
|
kpeter@744
|
364 |
/// Sets the map that stores the distances of the nodes calculated
|
kpeter@744
|
365 |
/// by the algorithm.
|
kpeter@744
|
366 |
/// If you don't use this function before calling \ref run()
|
kpeter@744
|
367 |
/// or \ref init(), an instance will be allocated automatically.
|
kpeter@744
|
368 |
/// The destructor deallocates this automatically allocated map,
|
kpeter@744
|
369 |
/// of course.
|
kpeter@744
|
370 |
/// \return <tt>(*this)</tt>
|
kpeter@744
|
371 |
BellmanFord &distMap(DistMap &map) {
|
kpeter@744
|
372 |
if(_local_dist) {
|
kpeter@743
|
373 |
delete _dist;
|
kpeter@744
|
374 |
_local_dist=false;
|
kpeter@743
|
375 |
}
|
kpeter@744
|
376 |
_dist = ↦
|
kpeter@743
|
377 |
return *this;
|
kpeter@743
|
378 |
}
|
kpeter@743
|
379 |
|
kpeter@744
|
380 |
/// \name Execution Control
|
kpeter@744
|
381 |
/// The simplest way to execute the Bellman-Ford algorithm is to use
|
kpeter@744
|
382 |
/// one of the member functions called \ref run().\n
|
kpeter@744
|
383 |
/// If you need better control on the execution, you have to call
|
kpeter@744
|
384 |
/// \ref init() first, then you can add several source nodes
|
kpeter@744
|
385 |
/// with \ref addSource(). Finally the actual path computation can be
|
kpeter@744
|
386 |
/// performed with \ref start(), \ref checkedStart() or
|
kpeter@744
|
387 |
/// \ref limitedStart().
|
kpeter@743
|
388 |
|
kpeter@743
|
389 |
///@{
|
kpeter@743
|
390 |
|
kpeter@743
|
391 |
/// \brief Initializes the internal data structures.
|
kpeter@743
|
392 |
///
|
kpeter@744
|
393 |
/// Initializes the internal data structures. The optional parameter
|
kpeter@744
|
394 |
/// is the initial distance of each node.
|
kpeter@743
|
395 |
void init(const Value value = OperationTraits::infinity()) {
|
kpeter@743
|
396 |
create_maps();
|
kpeter@744
|
397 |
for (NodeIt it(*_gr); it != INVALID; ++it) {
|
kpeter@743
|
398 |
_pred->set(it, INVALID);
|
kpeter@743
|
399 |
_dist->set(it, value);
|
kpeter@743
|
400 |
}
|
kpeter@743
|
401 |
_process.clear();
|
kpeter@743
|
402 |
if (OperationTraits::less(value, OperationTraits::infinity())) {
|
kpeter@744
|
403 |
for (NodeIt it(*_gr); it != INVALID; ++it) {
|
kpeter@743
|
404 |
_process.push_back(it);
|
kpeter@743
|
405 |
_mask->set(it, true);
|
kpeter@743
|
406 |
}
|
kpeter@743
|
407 |
}
|
kpeter@743
|
408 |
}
|
kpeter@743
|
409 |
|
kpeter@743
|
410 |
/// \brief Adds a new source node.
|
kpeter@743
|
411 |
///
|
kpeter@744
|
412 |
/// This function adds a new source node. The optional second parameter
|
kpeter@744
|
413 |
/// is the initial distance of the node.
|
kpeter@743
|
414 |
void addSource(Node source, Value dst = OperationTraits::zero()) {
|
kpeter@743
|
415 |
_dist->set(source, dst);
|
kpeter@743
|
416 |
if (!(*_mask)[source]) {
|
kpeter@743
|
417 |
_process.push_back(source);
|
kpeter@743
|
418 |
_mask->set(source, true);
|
kpeter@743
|
419 |
}
|
kpeter@743
|
420 |
}
|
kpeter@743
|
421 |
|
kpeter@743
|
422 |
/// \brief Executes one round from the Bellman-Ford algorithm.
|
kpeter@743
|
423 |
///
|
kpeter@743
|
424 |
/// If the algoritm calculated the distances in the previous round
|
kpeter@744
|
425 |
/// exactly for the paths of at most \c k arcs, then this function
|
kpeter@744
|
426 |
/// will calculate the distances exactly for the paths of at most
|
kpeter@744
|
427 |
/// <tt>k+1</tt> arcs. Performing \c k iterations using this function
|
kpeter@744
|
428 |
/// calculates the shortest path distances exactly for the paths
|
kpeter@744
|
429 |
/// consisting of at most \c k arcs.
|
kpeter@743
|
430 |
///
|
kpeter@743
|
431 |
/// \warning The paths with limited arc number cannot be retrieved
|
kpeter@744
|
432 |
/// easily with \ref path() or \ref predArc() functions. If you also
|
kpeter@744
|
433 |
/// need the shortest paths and not only the distances, you should
|
kpeter@744
|
434 |
/// store the \ref predMap() "predecessor map" after each iteration
|
kpeter@744
|
435 |
/// and build the path manually.
|
kpeter@743
|
436 |
///
|
kpeter@743
|
437 |
/// \return \c true when the algorithm have not found more shorter
|
kpeter@743
|
438 |
/// paths.
|
kpeter@744
|
439 |
///
|
kpeter@744
|
440 |
/// \see ActiveIt
|
kpeter@743
|
441 |
bool processNextRound() {
|
kpeter@743
|
442 |
for (int i = 0; i < int(_process.size()); ++i) {
|
kpeter@743
|
443 |
_mask->set(_process[i], false);
|
kpeter@743
|
444 |
}
|
kpeter@743
|
445 |
std::vector<Node> nextProcess;
|
kpeter@743
|
446 |
std::vector<Value> values(_process.size());
|
kpeter@743
|
447 |
for (int i = 0; i < int(_process.size()); ++i) {
|
kpeter@743
|
448 |
values[i] = (*_dist)[_process[i]];
|
kpeter@743
|
449 |
}
|
kpeter@743
|
450 |
for (int i = 0; i < int(_process.size()); ++i) {
|
kpeter@744
|
451 |
for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
|
kpeter@744
|
452 |
Node target = _gr->target(it);
|
kpeter@744
|
453 |
Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
|
kpeter@743
|
454 |
if (OperationTraits::less(relaxed, (*_dist)[target])) {
|
kpeter@743
|
455 |
_pred->set(target, it);
|
kpeter@743
|
456 |
_dist->set(target, relaxed);
|
kpeter@743
|
457 |
if (!(*_mask)[target]) {
|
kpeter@743
|
458 |
_mask->set(target, true);
|
kpeter@743
|
459 |
nextProcess.push_back(target);
|
kpeter@743
|
460 |
}
|
kpeter@743
|
461 |
}
|
kpeter@743
|
462 |
}
|
kpeter@743
|
463 |
}
|
kpeter@743
|
464 |
_process.swap(nextProcess);
|
kpeter@743
|
465 |
return _process.empty();
|
kpeter@743
|
466 |
}
|
kpeter@743
|
467 |
|
kpeter@743
|
468 |
/// \brief Executes one weak round from the Bellman-Ford algorithm.
|
kpeter@743
|
469 |
///
|
kpeter@744
|
470 |
/// If the algorithm calculated the distances in the previous round
|
kpeter@744
|
471 |
/// at least for the paths of at most \c k arcs, then this function
|
kpeter@744
|
472 |
/// will calculate the distances at least for the paths of at most
|
kpeter@744
|
473 |
/// <tt>k+1</tt> arcs.
|
kpeter@744
|
474 |
/// This function does not make it possible to calculate the shortest
|
kpeter@744
|
475 |
/// path distances exactly for paths consisting of at most \c k arcs,
|
kpeter@744
|
476 |
/// this is why it is called weak round.
|
kpeter@744
|
477 |
///
|
kpeter@744
|
478 |
/// \return \c true when the algorithm have not found more shorter
|
kpeter@744
|
479 |
/// paths.
|
kpeter@744
|
480 |
///
|
kpeter@744
|
481 |
/// \see ActiveIt
|
kpeter@743
|
482 |
bool processNextWeakRound() {
|
kpeter@743
|
483 |
for (int i = 0; i < int(_process.size()); ++i) {
|
kpeter@743
|
484 |
_mask->set(_process[i], false);
|
kpeter@743
|
485 |
}
|
kpeter@743
|
486 |
std::vector<Node> nextProcess;
|
kpeter@743
|
487 |
for (int i = 0; i < int(_process.size()); ++i) {
|
kpeter@744
|
488 |
for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
|
kpeter@744
|
489 |
Node target = _gr->target(it);
|
kpeter@743
|
490 |
Value relaxed =
|
kpeter@744
|
491 |
OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
|
kpeter@743
|
492 |
if (OperationTraits::less(relaxed, (*_dist)[target])) {
|
kpeter@743
|
493 |
_pred->set(target, it);
|
kpeter@743
|
494 |
_dist->set(target, relaxed);
|
kpeter@743
|
495 |
if (!(*_mask)[target]) {
|
kpeter@743
|
496 |
_mask->set(target, true);
|
kpeter@743
|
497 |
nextProcess.push_back(target);
|
kpeter@743
|
498 |
}
|
kpeter@743
|
499 |
}
|
kpeter@743
|
500 |
}
|
kpeter@743
|
501 |
}
|
kpeter@743
|
502 |
_process.swap(nextProcess);
|
kpeter@743
|
503 |
return _process.empty();
|
kpeter@743
|
504 |
}
|
kpeter@743
|
505 |
|
kpeter@743
|
506 |
/// \brief Executes the algorithm.
|
kpeter@743
|
507 |
///
|
kpeter@744
|
508 |
/// Executes the algorithm.
|
kpeter@743
|
509 |
///
|
kpeter@744
|
510 |
/// This method runs the Bellman-Ford algorithm from the root node(s)
|
kpeter@744
|
511 |
/// in order to compute the shortest path to each node.
|
kpeter@744
|
512 |
///
|
kpeter@744
|
513 |
/// The algorithm computes
|
kpeter@744
|
514 |
/// - the shortest path tree (forest),
|
kpeter@744
|
515 |
/// - the distance of each node from the root(s).
|
kpeter@744
|
516 |
///
|
kpeter@744
|
517 |
/// \pre init() must be called and at least one root node should be
|
kpeter@744
|
518 |
/// added with addSource() before using this function.
|
kpeter@743
|
519 |
void start() {
|
kpeter@744
|
520 |
int num = countNodes(*_gr) - 1;
|
kpeter@743
|
521 |
for (int i = 0; i < num; ++i) {
|
kpeter@743
|
522 |
if (processNextWeakRound()) break;
|
kpeter@743
|
523 |
}
|
kpeter@743
|
524 |
}
|
kpeter@743
|
525 |
|
kpeter@743
|
526 |
/// \brief Executes the algorithm and checks the negative cycles.
|
kpeter@743
|
527 |
///
|
kpeter@744
|
528 |
/// Executes the algorithm and checks the negative cycles.
|
kpeter@743
|
529 |
///
|
kpeter@744
|
530 |
/// This method runs the Bellman-Ford algorithm from the root node(s)
|
kpeter@744
|
531 |
/// in order to compute the shortest path to each node and also checks
|
kpeter@744
|
532 |
/// if the digraph contains cycles with negative total length.
|
kpeter@744
|
533 |
///
|
kpeter@744
|
534 |
/// The algorithm computes
|
kpeter@744
|
535 |
/// - the shortest path tree (forest),
|
kpeter@744
|
536 |
/// - the distance of each node from the root(s).
|
kpeter@743
|
537 |
///
|
kpeter@743
|
538 |
/// \return \c false if there is a negative cycle in the digraph.
|
kpeter@744
|
539 |
///
|
kpeter@744
|
540 |
/// \pre init() must be called and at least one root node should be
|
kpeter@744
|
541 |
/// added with addSource() before using this function.
|
kpeter@743
|
542 |
bool checkedStart() {
|
kpeter@744
|
543 |
int num = countNodes(*_gr);
|
kpeter@743
|
544 |
for (int i = 0; i < num; ++i) {
|
kpeter@743
|
545 |
if (processNextWeakRound()) return true;
|
kpeter@743
|
546 |
}
|
kpeter@743
|
547 |
return _process.empty();
|
kpeter@743
|
548 |
}
|
kpeter@743
|
549 |
|
kpeter@744
|
550 |
/// \brief Executes the algorithm with arc number limit.
|
kpeter@743
|
551 |
///
|
kpeter@744
|
552 |
/// Executes the algorithm with arc number limit.
|
kpeter@743
|
553 |
///
|
kpeter@744
|
554 |
/// This method runs the Bellman-Ford algorithm from the root node(s)
|
kpeter@744
|
555 |
/// in order to compute the shortest path distance for each node
|
kpeter@744
|
556 |
/// using only the paths consisting of at most \c num arcs.
|
kpeter@744
|
557 |
///
|
kpeter@744
|
558 |
/// The algorithm computes
|
kpeter@744
|
559 |
/// - the limited distance of each node from the root(s),
|
kpeter@744
|
560 |
/// - the predecessor arc for each node.
|
kpeter@743
|
561 |
///
|
kpeter@743
|
562 |
/// \warning The paths with limited arc number cannot be retrieved
|
kpeter@744
|
563 |
/// easily with \ref path() or \ref predArc() functions. If you also
|
kpeter@744
|
564 |
/// need the shortest paths and not only the distances, you should
|
kpeter@744
|
565 |
/// store the \ref predMap() "predecessor map" after each iteration
|
kpeter@744
|
566 |
/// and build the path manually.
|
kpeter@743
|
567 |
///
|
kpeter@744
|
568 |
/// \pre init() must be called and at least one root node should be
|
kpeter@744
|
569 |
/// added with addSource() before using this function.
|
kpeter@743
|
570 |
void limitedStart(int num) {
|
kpeter@743
|
571 |
for (int i = 0; i < num; ++i) {
|
kpeter@743
|
572 |
if (processNextRound()) break;
|
kpeter@743
|
573 |
}
|
kpeter@743
|
574 |
}
|
kpeter@743
|
575 |
|
kpeter@744
|
576 |
/// \brief Runs the algorithm from the given root node.
|
kpeter@743
|
577 |
///
|
kpeter@744
|
578 |
/// This method runs the Bellman-Ford algorithm from the given root
|
kpeter@744
|
579 |
/// node \c s in order to compute the shortest path to each node.
|
kpeter@743
|
580 |
///
|
kpeter@744
|
581 |
/// The algorithm computes
|
kpeter@744
|
582 |
/// - the shortest path tree (forest),
|
kpeter@744
|
583 |
/// - the distance of each node from the root(s).
|
kpeter@744
|
584 |
///
|
kpeter@744
|
585 |
/// \note bf.run(s) is just a shortcut of the following code.
|
kpeter@744
|
586 |
/// \code
|
kpeter@744
|
587 |
/// bf.init();
|
kpeter@744
|
588 |
/// bf.addSource(s);
|
kpeter@744
|
589 |
/// bf.start();
|
kpeter@744
|
590 |
/// \endcode
|
kpeter@743
|
591 |
void run(Node s) {
|
kpeter@743
|
592 |
init();
|
kpeter@743
|
593 |
addSource(s);
|
kpeter@743
|
594 |
start();
|
kpeter@743
|
595 |
}
|
kpeter@743
|
596 |
|
kpeter@744
|
597 |
/// \brief Runs the algorithm from the given root node with arc
|
kpeter@744
|
598 |
/// number limit.
|
kpeter@743
|
599 |
///
|
kpeter@744
|
600 |
/// This method runs the Bellman-Ford algorithm from the given root
|
kpeter@744
|
601 |
/// node \c s in order to compute the shortest path distance for each
|
kpeter@744
|
602 |
/// node using only the paths consisting of at most \c num arcs.
|
kpeter@743
|
603 |
///
|
kpeter@744
|
604 |
/// The algorithm computes
|
kpeter@744
|
605 |
/// - the limited distance of each node from the root(s),
|
kpeter@744
|
606 |
/// - the predecessor arc for each node.
|
kpeter@744
|
607 |
///
|
kpeter@744
|
608 |
/// \warning The paths with limited arc number cannot be retrieved
|
kpeter@744
|
609 |
/// easily with \ref path() or \ref predArc() functions. If you also
|
kpeter@744
|
610 |
/// need the shortest paths and not only the distances, you should
|
kpeter@744
|
611 |
/// store the \ref predMap() "predecessor map" after each iteration
|
kpeter@744
|
612 |
/// and build the path manually.
|
kpeter@744
|
613 |
///
|
kpeter@744
|
614 |
/// \note bf.run(s, num) is just a shortcut of the following code.
|
kpeter@744
|
615 |
/// \code
|
kpeter@744
|
616 |
/// bf.init();
|
kpeter@744
|
617 |
/// bf.addSource(s);
|
kpeter@744
|
618 |
/// bf.limitedStart(num);
|
kpeter@744
|
619 |
/// \endcode
|
kpeter@743
|
620 |
void run(Node s, int num) {
|
kpeter@743
|
621 |
init();
|
kpeter@743
|
622 |
addSource(s);
|
kpeter@743
|
623 |
limitedStart(num);
|
kpeter@743
|
624 |
}
|
kpeter@743
|
625 |
|
kpeter@743
|
626 |
///@}
|
kpeter@743
|
627 |
|
kpeter@744
|
628 |
/// \brief LEMON iterator for getting the active nodes.
|
kpeter@743
|
629 |
///
|
kpeter@744
|
630 |
/// This class provides a common style LEMON iterator that traverses
|
kpeter@744
|
631 |
/// the active nodes of the Bellman-Ford algorithm after the last
|
kpeter@744
|
632 |
/// phase. These nodes should be checked in the next phase to
|
kpeter@744
|
633 |
/// find augmenting arcs outgoing from them.
|
kpeter@743
|
634 |
class ActiveIt {
|
kpeter@743
|
635 |
public:
|
kpeter@743
|
636 |
|
kpeter@743
|
637 |
/// \brief Constructor.
|
kpeter@743
|
638 |
///
|
kpeter@744
|
639 |
/// Constructor for getting the active nodes of the given BellmanFord
|
kpeter@744
|
640 |
/// instance.
|
kpeter@743
|
641 |
ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
|
kpeter@743
|
642 |
{
|
kpeter@743
|
643 |
_index = _algorithm->_process.size() - 1;
|
kpeter@743
|
644 |
}
|
kpeter@743
|
645 |
|
kpeter@743
|
646 |
/// \brief Invalid constructor.
|
kpeter@743
|
647 |
///
|
kpeter@743
|
648 |
/// Invalid constructor.
|
kpeter@743
|
649 |
ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
|
kpeter@743
|
650 |
|
kpeter@744
|
651 |
/// \brief Conversion to \c Node.
|
kpeter@743
|
652 |
///
|
kpeter@744
|
653 |
/// Conversion to \c Node.
|
kpeter@743
|
654 |
operator Node() const {
|
kpeter@743
|
655 |
return _index >= 0 ? _algorithm->_process[_index] : INVALID;
|
kpeter@743
|
656 |
}
|
kpeter@743
|
657 |
|
kpeter@743
|
658 |
/// \brief Increment operator.
|
kpeter@743
|
659 |
///
|
kpeter@743
|
660 |
/// Increment operator.
|
kpeter@743
|
661 |
ActiveIt& operator++() {
|
kpeter@743
|
662 |
--_index;
|
kpeter@743
|
663 |
return *this;
|
kpeter@743
|
664 |
}
|
kpeter@743
|
665 |
|
kpeter@743
|
666 |
bool operator==(const ActiveIt& it) const {
|
kpeter@743
|
667 |
return static_cast<Node>(*this) == static_cast<Node>(it);
|
kpeter@743
|
668 |
}
|
kpeter@743
|
669 |
bool operator!=(const ActiveIt& it) const {
|
kpeter@743
|
670 |
return static_cast<Node>(*this) != static_cast<Node>(it);
|
kpeter@743
|
671 |
}
|
kpeter@743
|
672 |
bool operator<(const ActiveIt& it) const {
|
kpeter@743
|
673 |
return static_cast<Node>(*this) < static_cast<Node>(it);
|
kpeter@743
|
674 |
}
|
kpeter@743
|
675 |
|
kpeter@743
|
676 |
private:
|
kpeter@743
|
677 |
const BellmanFord* _algorithm;
|
kpeter@743
|
678 |
int _index;
|
kpeter@743
|
679 |
};
|
kpeter@744
|
680 |
|
kpeter@744
|
681 |
/// \name Query Functions
|
kpeter@744
|
682 |
/// The result of the Bellman-Ford algorithm can be obtained using these
|
kpeter@744
|
683 |
/// functions.\n
|
kpeter@744
|
684 |
/// Either \ref run() or \ref init() should be called before using them.
|
kpeter@744
|
685 |
|
kpeter@744
|
686 |
///@{
|
kpeter@743
|
687 |
|
kpeter@744
|
688 |
/// \brief The shortest path to the given node.
|
kpeter@744
|
689 |
///
|
kpeter@744
|
690 |
/// Gives back the shortest path to the given node from the root(s).
|
kpeter@744
|
691 |
///
|
kpeter@744
|
692 |
/// \warning \c t should be reached from the root(s).
|
kpeter@744
|
693 |
///
|
kpeter@744
|
694 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
695 |
/// using this function.
|
kpeter@744
|
696 |
Path path(Node t) const
|
kpeter@744
|
697 |
{
|
kpeter@744
|
698 |
return Path(*_gr, *_pred, t);
|
kpeter@744
|
699 |
}
|
kpeter@744
|
700 |
|
kpeter@744
|
701 |
/// \brief The distance of the given node from the root(s).
|
kpeter@744
|
702 |
///
|
kpeter@744
|
703 |
/// Returns the distance of the given node from the root(s).
|
kpeter@744
|
704 |
///
|
kpeter@744
|
705 |
/// \warning If node \c v is not reached from the root(s), then
|
kpeter@744
|
706 |
/// the return value of this function is undefined.
|
kpeter@744
|
707 |
///
|
kpeter@744
|
708 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
709 |
/// using this function.
|
kpeter@744
|
710 |
Value dist(Node v) const { return (*_dist)[v]; }
|
kpeter@743
|
711 |
|
kpeter@744
|
712 |
/// \brief Returns the 'previous arc' of the shortest path tree for
|
kpeter@744
|
713 |
/// the given node.
|
kpeter@744
|
714 |
///
|
kpeter@744
|
715 |
/// This function returns the 'previous arc' of the shortest path
|
kpeter@744
|
716 |
/// tree for node \c v, i.e. it returns the last arc of a
|
kpeter@744
|
717 |
/// shortest path from a root to \c v. It is \c INVALID if \c v
|
kpeter@744
|
718 |
/// is not reached from the root(s) or if \c v is a root.
|
kpeter@744
|
719 |
///
|
kpeter@744
|
720 |
/// The shortest path tree used here is equal to the shortest path
|
kpeter@744
|
721 |
/// tree used in \ref predNode() and \predMap().
|
kpeter@744
|
722 |
///
|
kpeter@744
|
723 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
724 |
/// using this function.
|
kpeter@744
|
725 |
Arc predArc(Node v) const { return (*_pred)[v]; }
|
kpeter@744
|
726 |
|
kpeter@744
|
727 |
/// \brief Returns the 'previous node' of the shortest path tree for
|
kpeter@744
|
728 |
/// the given node.
|
kpeter@744
|
729 |
///
|
kpeter@744
|
730 |
/// This function returns the 'previous node' of the shortest path
|
kpeter@744
|
731 |
/// tree for node \c v, i.e. it returns the last but one node of
|
kpeter@744
|
732 |
/// a shortest path from a root to \c v. It is \c INVALID if \c v
|
kpeter@744
|
733 |
/// is not reached from the root(s) or if \c v is a root.
|
kpeter@744
|
734 |
///
|
kpeter@744
|
735 |
/// The shortest path tree used here is equal to the shortest path
|
kpeter@744
|
736 |
/// tree used in \ref predArc() and \predMap().
|
kpeter@744
|
737 |
///
|
kpeter@744
|
738 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
739 |
/// using this function.
|
kpeter@744
|
740 |
Node predNode(Node v) const {
|
kpeter@744
|
741 |
return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
|
kpeter@744
|
742 |
}
|
kpeter@744
|
743 |
|
kpeter@744
|
744 |
/// \brief Returns a const reference to the node map that stores the
|
kpeter@744
|
745 |
/// distances of the nodes.
|
kpeter@744
|
746 |
///
|
kpeter@744
|
747 |
/// Returns a const reference to the node map that stores the distances
|
kpeter@744
|
748 |
/// of the nodes calculated by the algorithm.
|
kpeter@744
|
749 |
///
|
kpeter@744
|
750 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
751 |
/// using this function.
|
kpeter@744
|
752 |
const DistMap &distMap() const { return *_dist;}
|
kpeter@744
|
753 |
|
kpeter@744
|
754 |
/// \brief Returns a const reference to the node map that stores the
|
kpeter@744
|
755 |
/// predecessor arcs.
|
kpeter@744
|
756 |
///
|
kpeter@744
|
757 |
/// Returns a const reference to the node map that stores the predecessor
|
kpeter@744
|
758 |
/// arcs, which form the shortest path tree (forest).
|
kpeter@744
|
759 |
///
|
kpeter@744
|
760 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
761 |
/// using this function.
|
kpeter@744
|
762 |
const PredMap &predMap() const { return *_pred; }
|
kpeter@744
|
763 |
|
kpeter@744
|
764 |
/// \brief Checks if a node is reached from the root(s).
|
kpeter@744
|
765 |
///
|
kpeter@744
|
766 |
/// Returns \c true if \c v is reached from the root(s).
|
kpeter@744
|
767 |
///
|
kpeter@744
|
768 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@744
|
769 |
/// using this function.
|
kpeter@744
|
770 |
bool reached(Node v) const {
|
kpeter@744
|
771 |
return (*_dist)[v] != OperationTraits::infinity();
|
kpeter@743
|
772 |
}
|
kpeter@743
|
773 |
|
kpeter@746
|
774 |
/// \brief Gives back a negative cycle.
|
kpeter@746
|
775 |
///
|
kpeter@746
|
776 |
/// This function gives back a directed cycle with negative total
|
kpeter@746
|
777 |
/// length if the algorithm has already found one.
|
kpeter@746
|
778 |
/// Otherwise it gives back an empty path.
|
kpeter@828
|
779 |
lemon::Path<Digraph> negativeCycle() const {
|
kpeter@746
|
780 |
typename Digraph::template NodeMap<int> state(*_gr, -1);
|
kpeter@746
|
781 |
lemon::Path<Digraph> cycle;
|
kpeter@746
|
782 |
for (int i = 0; i < int(_process.size()); ++i) {
|
kpeter@746
|
783 |
if (state[_process[i]] != -1) continue;
|
kpeter@746
|
784 |
for (Node v = _process[i]; (*_pred)[v] != INVALID;
|
kpeter@746
|
785 |
v = _gr->source((*_pred)[v])) {
|
kpeter@746
|
786 |
if (state[v] == i) {
|
kpeter@746
|
787 |
cycle.addFront((*_pred)[v]);
|
kpeter@746
|
788 |
for (Node u = _gr->source((*_pred)[v]); u != v;
|
kpeter@746
|
789 |
u = _gr->source((*_pred)[u])) {
|
kpeter@746
|
790 |
cycle.addFront((*_pred)[u]);
|
kpeter@746
|
791 |
}
|
kpeter@746
|
792 |
return cycle;
|
kpeter@746
|
793 |
}
|
kpeter@746
|
794 |
else if (state[v] >= 0) {
|
kpeter@746
|
795 |
break;
|
kpeter@746
|
796 |
}
|
kpeter@746
|
797 |
state[v] = i;
|
kpeter@746
|
798 |
}
|
kpeter@746
|
799 |
}
|
kpeter@746
|
800 |
return cycle;
|
kpeter@746
|
801 |
}
|
kpeter@743
|
802 |
|
kpeter@743
|
803 |
///@}
|
kpeter@743
|
804 |
};
|
kpeter@743
|
805 |
|
kpeter@744
|
806 |
/// \brief Default traits class of bellmanFord() function.
|
kpeter@743
|
807 |
///
|
kpeter@744
|
808 |
/// Default traits class of bellmanFord() function.
|
kpeter@744
|
809 |
/// \tparam GR The type of the digraph.
|
kpeter@744
|
810 |
/// \tparam LEN The type of the length map.
|
kpeter@744
|
811 |
template <typename GR, typename LEN>
|
kpeter@743
|
812 |
struct BellmanFordWizardDefaultTraits {
|
kpeter@744
|
813 |
/// The type of the digraph the algorithm runs on.
|
kpeter@744
|
814 |
typedef GR Digraph;
|
kpeter@743
|
815 |
|
kpeter@743
|
816 |
/// \brief The type of the map that stores the arc lengths.
|
kpeter@743
|
817 |
///
|
kpeter@743
|
818 |
/// The type of the map that stores the arc lengths.
|
kpeter@743
|
819 |
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@744
|
820 |
typedef LEN LengthMap;
|
kpeter@743
|
821 |
|
kpeter@744
|
822 |
/// The type of the arc lengths.
|
kpeter@744
|
823 |
typedef typename LEN::Value Value;
|
kpeter@743
|
824 |
|
kpeter@743
|
825 |
/// \brief Operation traits for Bellman-Ford algorithm.
|
kpeter@743
|
826 |
///
|
kpeter@744
|
827 |
/// It defines the used operations and the infinity value for the
|
kpeter@744
|
828 |
/// given \c Value type.
|
kpeter@743
|
829 |
/// \see BellmanFordDefaultOperationTraits
|
kpeter@743
|
830 |
typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
|
kpeter@743
|
831 |
|
kpeter@743
|
832 |
/// \brief The type of the map that stores the last
|
kpeter@743
|
833 |
/// arcs of the shortest paths.
|
kpeter@743
|
834 |
///
|
kpeter@744
|
835 |
/// The type of the map that stores the last arcs of the shortest paths.
|
kpeter@744
|
836 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@744
|
837 |
typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
|
kpeter@743
|
838 |
|
kpeter@744
|
839 |
/// \brief Instantiates a \c PredMap.
|
kpeter@743
|
840 |
///
|
kpeter@744
|
841 |
/// This function instantiates a \ref PredMap.
|
kpeter@744
|
842 |
/// \param g is the digraph to which we would like to define the
|
kpeter@744
|
843 |
/// \ref PredMap.
|
kpeter@744
|
844 |
static PredMap *createPredMap(const GR &g) {
|
kpeter@744
|
845 |
return new PredMap(g);
|
kpeter@743
|
846 |
}
|
kpeter@744
|
847 |
|
kpeter@744
|
848 |
/// \brief The type of the map that stores the distances of the nodes.
|
kpeter@743
|
849 |
///
|
kpeter@744
|
850 |
/// The type of the map that stores the distances of the nodes.
|
kpeter@744
|
851 |
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@744
|
852 |
typedef typename GR::template NodeMap<Value> DistMap;
|
kpeter@744
|
853 |
|
kpeter@744
|
854 |
/// \brief Instantiates a \c DistMap.
|
kpeter@743
|
855 |
///
|
kpeter@743
|
856 |
/// This function instantiates a \ref DistMap.
|
kpeter@744
|
857 |
/// \param g is the digraph to which we would like to define the
|
kpeter@744
|
858 |
/// \ref DistMap.
|
kpeter@744
|
859 |
static DistMap *createDistMap(const GR &g) {
|
kpeter@744
|
860 |
return new DistMap(g);
|
kpeter@743
|
861 |
}
|
kpeter@744
|
862 |
|
kpeter@744
|
863 |
///The type of the shortest paths.
|
kpeter@744
|
864 |
|
kpeter@744
|
865 |
///The type of the shortest paths.
|
kpeter@744
|
866 |
///It must meet the \ref concepts::Path "Path" concept.
|
kpeter@744
|
867 |
typedef lemon::Path<Digraph> Path;
|
kpeter@743
|
868 |
};
|
kpeter@743
|
869 |
|
kpeter@744
|
870 |
/// \brief Default traits class used by BellmanFordWizard.
|
kpeter@743
|
871 |
///
|
kpeter@744
|
872 |
/// Default traits class used by BellmanFordWizard.
|
kpeter@744
|
873 |
/// \tparam GR The type of the digraph.
|
kpeter@744
|
874 |
/// \tparam LEN The type of the length map.
|
kpeter@744
|
875 |
template <typename GR, typename LEN>
|
kpeter@743
|
876 |
class BellmanFordWizardBase
|
kpeter@744
|
877 |
: public BellmanFordWizardDefaultTraits<GR, LEN> {
|
kpeter@743
|
878 |
|
kpeter@744
|
879 |
typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
|
kpeter@743
|
880 |
protected:
|
kpeter@744
|
881 |
// Type of the nodes in the digraph.
|
kpeter@743
|
882 |
typedef typename Base::Digraph::Node Node;
|
kpeter@743
|
883 |
|
kpeter@744
|
884 |
// Pointer to the underlying digraph.
|
kpeter@743
|
885 |
void *_graph;
|
kpeter@744
|
886 |
// Pointer to the length map
|
kpeter@743
|
887 |
void *_length;
|
kpeter@744
|
888 |
// Pointer to the map of predecessors arcs.
|
kpeter@743
|
889 |
void *_pred;
|
kpeter@744
|
890 |
// Pointer to the map of distances.
|
kpeter@743
|
891 |
void *_dist;
|
kpeter@744
|
892 |
//Pointer to the shortest path to the target node.
|
kpeter@744
|
893 |
void *_path;
|
kpeter@744
|
894 |
//Pointer to the distance of the target node.
|
kpeter@744
|
895 |
void *_di;
|
kpeter@743
|
896 |
|
kpeter@743
|
897 |
public:
|
kpeter@743
|
898 |
/// Constructor.
|
kpeter@743
|
899 |
|
kpeter@744
|
900 |
/// This constructor does not require parameters, it initiates
|
kpeter@744
|
901 |
/// all of the attributes to default values \c 0.
|
kpeter@744
|
902 |
BellmanFordWizardBase() :
|
kpeter@744
|
903 |
_graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
|
kpeter@743
|
904 |
|
kpeter@743
|
905 |
/// Constructor.
|
kpeter@743
|
906 |
|
kpeter@744
|
907 |
/// This constructor requires two parameters,
|
kpeter@744
|
908 |
/// others are initiated to \c 0.
|
kpeter@744
|
909 |
/// \param gr The digraph the algorithm runs on.
|
kpeter@744
|
910 |
/// \param len The length map.
|
kpeter@744
|
911 |
BellmanFordWizardBase(const GR& gr,
|
kpeter@744
|
912 |
const LEN& len) :
|
kpeter@744
|
913 |
_graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
|
kpeter@744
|
914 |
_length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
|
kpeter@744
|
915 |
_pred(0), _dist(0), _path(0), _di(0) {}
|
kpeter@743
|
916 |
|
kpeter@743
|
917 |
};
|
kpeter@743
|
918 |
|
kpeter@744
|
919 |
/// \brief Auxiliary class for the function-type interface of the
|
kpeter@744
|
920 |
/// \ref BellmanFord "Bellman-Ford" algorithm.
|
kpeter@744
|
921 |
///
|
kpeter@744
|
922 |
/// This auxiliary class is created to implement the
|
kpeter@744
|
923 |
/// \ref bellmanFord() "function-type interface" of the
|
kpeter@744
|
924 |
/// \ref BellmanFord "Bellman-Ford" algorithm.
|
kpeter@744
|
925 |
/// It does not have own \ref run() method, it uses the
|
kpeter@744
|
926 |
/// functions and features of the plain \ref BellmanFord.
|
kpeter@744
|
927 |
///
|
kpeter@744
|
928 |
/// This class should only be used through the \ref bellmanFord()
|
kpeter@744
|
929 |
/// function, which makes it easier to use the algorithm.
|
kpeter@744
|
930 |
template<class TR>
|
kpeter@744
|
931 |
class BellmanFordWizard : public TR {
|
kpeter@744
|
932 |
typedef TR Base;
|
kpeter@743
|
933 |
|
kpeter@744
|
934 |
typedef typename TR::Digraph Digraph;
|
kpeter@743
|
935 |
|
kpeter@743
|
936 |
typedef typename Digraph::Node Node;
|
kpeter@743
|
937 |
typedef typename Digraph::NodeIt NodeIt;
|
kpeter@743
|
938 |
typedef typename Digraph::Arc Arc;
|
kpeter@743
|
939 |
typedef typename Digraph::OutArcIt ArcIt;
|
kpeter@743
|
940 |
|
kpeter@744
|
941 |
typedef typename TR::LengthMap LengthMap;
|
kpeter@743
|
942 |
typedef typename LengthMap::Value Value;
|
kpeter@744
|
943 |
typedef typename TR::PredMap PredMap;
|
kpeter@744
|
944 |
typedef typename TR::DistMap DistMap;
|
kpeter@744
|
945 |
typedef typename TR::Path Path;
|
kpeter@743
|
946 |
|
kpeter@743
|
947 |
public:
|
kpeter@743
|
948 |
/// Constructor.
|
kpeter@744
|
949 |
BellmanFordWizard() : TR() {}
|
kpeter@743
|
950 |
|
kpeter@743
|
951 |
/// \brief Constructor that requires parameters.
|
kpeter@743
|
952 |
///
|
kpeter@743
|
953 |
/// Constructor that requires parameters.
|
kpeter@743
|
954 |
/// These parameters will be the default values for the traits class.
|
kpeter@744
|
955 |
/// \param gr The digraph the algorithm runs on.
|
kpeter@744
|
956 |
/// \param len The length map.
|
kpeter@744
|
957 |
BellmanFordWizard(const Digraph& gr, const LengthMap& len)
|
kpeter@744
|
958 |
: TR(gr, len) {}
|
kpeter@743
|
959 |
|
kpeter@743
|
960 |
/// \brief Copy constructor
|
kpeter@744
|
961 |
BellmanFordWizard(const TR &b) : TR(b) {}
|
kpeter@743
|
962 |
|
kpeter@743
|
963 |
~BellmanFordWizard() {}
|
kpeter@743
|
964 |
|
kpeter@744
|
965 |
/// \brief Runs the Bellman-Ford algorithm from the given source node.
|
kpeter@743
|
966 |
///
|
kpeter@744
|
967 |
/// This method runs the Bellman-Ford algorithm from the given source
|
kpeter@744
|
968 |
/// node in order to compute the shortest path to each node.
|
kpeter@744
|
969 |
void run(Node s) {
|
kpeter@744
|
970 |
BellmanFord<Digraph,LengthMap,TR>
|
kpeter@743
|
971 |
bf(*reinterpret_cast<const Digraph*>(Base::_graph),
|
kpeter@743
|
972 |
*reinterpret_cast<const LengthMap*>(Base::_length));
|
kpeter@743
|
973 |
if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
|
kpeter@743
|
974 |
if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
|
kpeter@744
|
975 |
bf.run(s);
|
kpeter@743
|
976 |
}
|
kpeter@743
|
977 |
|
kpeter@744
|
978 |
/// \brief Runs the Bellman-Ford algorithm to find the shortest path
|
kpeter@744
|
979 |
/// between \c s and \c t.
|
kpeter@743
|
980 |
///
|
kpeter@744
|
981 |
/// This method runs the Bellman-Ford algorithm from node \c s
|
kpeter@744
|
982 |
/// in order to compute the shortest path to node \c t.
|
kpeter@744
|
983 |
/// Actually, it computes the shortest path to each node, but using
|
kpeter@744
|
984 |
/// this function you can retrieve the distance and the shortest path
|
kpeter@744
|
985 |
/// for a single target node easier.
|
kpeter@744
|
986 |
///
|
kpeter@744
|
987 |
/// \return \c true if \c t is reachable form \c s.
|
kpeter@744
|
988 |
bool run(Node s, Node t) {
|
kpeter@744
|
989 |
BellmanFord<Digraph,LengthMap,TR>
|
kpeter@744
|
990 |
bf(*reinterpret_cast<const Digraph*>(Base::_graph),
|
kpeter@744
|
991 |
*reinterpret_cast<const LengthMap*>(Base::_length));
|
kpeter@744
|
992 |
if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
|
kpeter@744
|
993 |
if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
|
kpeter@744
|
994 |
bf.run(s);
|
kpeter@744
|
995 |
if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
|
kpeter@744
|
996 |
if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
|
kpeter@744
|
997 |
return bf.reached(t);
|
kpeter@743
|
998 |
}
|
kpeter@743
|
999 |
|
kpeter@743
|
1000 |
template<class T>
|
kpeter@744
|
1001 |
struct SetPredMapBase : public Base {
|
kpeter@743
|
1002 |
typedef T PredMap;
|
kpeter@743
|
1003 |
static PredMap *createPredMap(const Digraph &) { return 0; };
|
kpeter@744
|
1004 |
SetPredMapBase(const TR &b) : TR(b) {}
|
kpeter@743
|
1005 |
};
|
kpeter@743
|
1006 |
|
kpeter@744
|
1007 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
1008 |
/// the predecessor map.
|
kpeter@743
|
1009 |
///
|
kpeter@744
|
1010 |
/// \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
1011 |
/// the map that stores the predecessor arcs of the nodes.
|
kpeter@743
|
1012 |
template<class T>
|
kpeter@744
|
1013 |
BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
|
kpeter@743
|
1014 |
Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@744
|
1015 |
return BellmanFordWizard<SetPredMapBase<T> >(*this);
|
kpeter@743
|
1016 |
}
|
kpeter@743
|
1017 |
|
kpeter@743
|
1018 |
template<class T>
|
kpeter@744
|
1019 |
struct SetDistMapBase : public Base {
|
kpeter@743
|
1020 |
typedef T DistMap;
|
kpeter@743
|
1021 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
kpeter@744
|
1022 |
SetDistMapBase(const TR &b) : TR(b) {}
|
kpeter@743
|
1023 |
};
|
kpeter@743
|
1024 |
|
kpeter@744
|
1025 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
1026 |
/// the distance map.
|
kpeter@743
|
1027 |
///
|
kpeter@744
|
1028 |
/// \ref named-templ-param "Named parameter" for setting
|
kpeter@744
|
1029 |
/// the map that stores the distances of the nodes calculated
|
kpeter@744
|
1030 |
/// by the algorithm.
|
kpeter@743
|
1031 |
template<class T>
|
kpeter@744
|
1032 |
BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
|
kpeter@743
|
1033 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@744
|
1034 |
return BellmanFordWizard<SetDistMapBase<T> >(*this);
|
kpeter@743
|
1035 |
}
|
kpeter@743
|
1036 |
|
kpeter@743
|
1037 |
template<class T>
|
kpeter@744
|
1038 |
struct SetPathBase : public Base {
|
kpeter@744
|
1039 |
typedef T Path;
|
kpeter@744
|
1040 |
SetPathBase(const TR &b) : TR(b) {}
|
kpeter@743
|
1041 |
};
|
kpeter@744
|
1042 |
|
kpeter@744
|
1043 |
/// \brief \ref named-func-param "Named parameter" for getting
|
kpeter@744
|
1044 |
/// the shortest path to the target node.
|
kpeter@743
|
1045 |
///
|
kpeter@744
|
1046 |
/// \ref named-func-param "Named parameter" for getting
|
kpeter@744
|
1047 |
/// the shortest path to the target node.
|
kpeter@744
|
1048 |
template<class T>
|
kpeter@744
|
1049 |
BellmanFordWizard<SetPathBase<T> > path(const T &t)
|
kpeter@744
|
1050 |
{
|
kpeter@744
|
1051 |
Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@744
|
1052 |
return BellmanFordWizard<SetPathBase<T> >(*this);
|
kpeter@744
|
1053 |
}
|
kpeter@744
|
1054 |
|
kpeter@744
|
1055 |
/// \brief \ref named-func-param "Named parameter" for getting
|
kpeter@744
|
1056 |
/// the distance of the target node.
|
kpeter@743
|
1057 |
///
|
kpeter@744
|
1058 |
/// \ref named-func-param "Named parameter" for getting
|
kpeter@744
|
1059 |
/// the distance of the target node.
|
kpeter@744
|
1060 |
BellmanFordWizard dist(const Value &d)
|
kpeter@744
|
1061 |
{
|
kpeter@744
|
1062 |
Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
|
kpeter@743
|
1063 |
return *this;
|
kpeter@743
|
1064 |
}
|
kpeter@743
|
1065 |
|
kpeter@743
|
1066 |
};
|
kpeter@743
|
1067 |
|
kpeter@744
|
1068 |
/// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
|
kpeter@744
|
1069 |
/// algorithm.
|
kpeter@743
|
1070 |
///
|
kpeter@743
|
1071 |
/// \ingroup shortest_path
|
kpeter@744
|
1072 |
/// Function type interface for the \ref BellmanFord "Bellman-Ford"
|
kpeter@744
|
1073 |
/// algorithm.
|
kpeter@743
|
1074 |
///
|
kpeter@743
|
1075 |
/// This function also has several \ref named-templ-func-param
|
kpeter@743
|
1076 |
/// "named parameters", they are declared as the members of class
|
kpeter@743
|
1077 |
/// \ref BellmanFordWizard.
|
kpeter@744
|
1078 |
/// The following examples show how to use these parameters.
|
kpeter@744
|
1079 |
/// \code
|
kpeter@744
|
1080 |
/// // Compute shortest path from node s to each node
|
kpeter@744
|
1081 |
/// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
|
kpeter@744
|
1082 |
///
|
kpeter@744
|
1083 |
/// // Compute shortest path from s to t
|
kpeter@744
|
1084 |
/// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
|
kpeter@744
|
1085 |
/// \endcode
|
kpeter@743
|
1086 |
/// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
|
kpeter@743
|
1087 |
/// to the end of the parameter list.
|
kpeter@743
|
1088 |
/// \sa BellmanFordWizard
|
kpeter@743
|
1089 |
/// \sa BellmanFord
|
kpeter@744
|
1090 |
template<typename GR, typename LEN>
|
kpeter@744
|
1091 |
BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
|
kpeter@744
|
1092 |
bellmanFord(const GR& digraph,
|
kpeter@744
|
1093 |
const LEN& length)
|
kpeter@744
|
1094 |
{
|
kpeter@744
|
1095 |
return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
|
kpeter@743
|
1096 |
}
|
kpeter@743
|
1097 |
|
kpeter@743
|
1098 |
} //END OF NAMESPACE LEMON
|
kpeter@743
|
1099 |
|
kpeter@743
|
1100 |
#endif
|
kpeter@743
|
1101 |
|