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