deba@1699
|
1 |
/* -*- C++ -*-
|
deba@1699
|
2 |
* lemon/floyd_warshall.h - Part of LEMON, a generic C++ optimization library
|
deba@1699
|
3 |
*
|
deba@1699
|
4 |
* Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@1699
|
5 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@1699
|
6 |
*
|
deba@1699
|
7 |
* Permission to use, modify and distribute this software is granted
|
deba@1699
|
8 |
* provided that this copyright notice appears in all copies. For
|
deba@1699
|
9 |
* precise terms see the accompanying LICENSE file.
|
deba@1699
|
10 |
*
|
deba@1699
|
11 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@1699
|
12 |
* express or implied, and with no claim as to its suitability for any
|
deba@1699
|
13 |
* purpose.
|
deba@1699
|
14 |
*
|
deba@1699
|
15 |
*/
|
deba@1699
|
16 |
|
deba@1699
|
17 |
#ifndef LEMON_FLOYD_WARSHALL_H
|
deba@1699
|
18 |
#define LEMON_FLOYD_WARSHALL_H
|
deba@1699
|
19 |
|
deba@1699
|
20 |
///\ingroup flowalgs
|
deba@1699
|
21 |
/// \file
|
deba@1699
|
22 |
/// \brief FloydWarshall algorithm.
|
deba@1699
|
23 |
///
|
deba@1699
|
24 |
|
deba@1699
|
25 |
#include <lemon/list_graph.h>
|
deba@1699
|
26 |
#include <lemon/graph_utils.h>
|
deba@1699
|
27 |
#include <lemon/invalid.h>
|
deba@1699
|
28 |
#include <lemon/error.h>
|
deba@1723
|
29 |
#include <lemon/matrix_maps.h>
|
deba@1699
|
30 |
#include <lemon/maps.h>
|
deba@1699
|
31 |
|
deba@1699
|
32 |
#include <limits>
|
deba@1699
|
33 |
|
deba@1699
|
34 |
namespace lemon {
|
deba@1699
|
35 |
|
deba@1699
|
36 |
/// \brief Default OperationTraits for the FloydWarshall algorithm class.
|
deba@1699
|
37 |
///
|
deba@1699
|
38 |
/// It defines all computational operations and constants which are
|
deba@1699
|
39 |
/// used in the Floyd-Warshall algorithm. The default implementation
|
deba@1699
|
40 |
/// is based on the numeric_limits class. If the numeric type does not
|
deba@1699
|
41 |
/// have infinity value then the maximum value is used as extremal
|
deba@1699
|
42 |
/// infinity value.
|
deba@1699
|
43 |
template <
|
deba@1699
|
44 |
typename Value,
|
deba@1699
|
45 |
bool has_infinity = std::numeric_limits<Value>::has_infinity>
|
deba@1699
|
46 |
struct FloydWarshallDefaultOperationTraits {
|
deba@1699
|
47 |
/// \brief Gives back the zero value of the type.
|
deba@1699
|
48 |
static Value zero() {
|
deba@1699
|
49 |
return static_cast<Value>(0);
|
deba@1699
|
50 |
}
|
deba@1699
|
51 |
/// \brief Gives back the positive infinity value of the type.
|
deba@1699
|
52 |
static Value infinity() {
|
deba@1699
|
53 |
return std::numeric_limits<Value>::infinity();
|
deba@1699
|
54 |
}
|
deba@1699
|
55 |
/// \brief Gives back the sum of the given two elements.
|
deba@1699
|
56 |
static Value plus(const Value& left, const Value& right) {
|
deba@1699
|
57 |
return left + right;
|
deba@1699
|
58 |
}
|
deba@1699
|
59 |
/// \brief Gives back true only if the first value less than the second.
|
deba@1699
|
60 |
static bool less(const Value& left, const Value& right) {
|
deba@1699
|
61 |
return left < right;
|
deba@1699
|
62 |
}
|
deba@1699
|
63 |
};
|
deba@1699
|
64 |
|
deba@1699
|
65 |
template <typename Value>
|
deba@1699
|
66 |
struct FloydWarshallDefaultOperationTraits<Value, false> {
|
deba@1699
|
67 |
static Value zero() {
|
deba@1699
|
68 |
return static_cast<Value>(0);
|
deba@1699
|
69 |
}
|
deba@1699
|
70 |
static Value infinity() {
|
deba@1699
|
71 |
return std::numeric_limits<Value>::max();
|
deba@1699
|
72 |
}
|
deba@1699
|
73 |
static Value plus(const Value& left, const Value& right) {
|
deba@1699
|
74 |
if (left == infinity() || right == infinity()) return infinity();
|
deba@1699
|
75 |
return left + right;
|
deba@1699
|
76 |
}
|
deba@1699
|
77 |
static bool less(const Value& left, const Value& right) {
|
deba@1699
|
78 |
return left < right;
|
deba@1699
|
79 |
}
|
deba@1699
|
80 |
};
|
deba@1699
|
81 |
|
deba@1699
|
82 |
/// \brief Default traits class of FloydWarshall class.
|
deba@1699
|
83 |
///
|
deba@1699
|
84 |
/// Default traits class of FloydWarshall class.
|
deba@1699
|
85 |
/// \param _Graph Graph type.
|
deba@1699
|
86 |
/// \param _LegthMap Type of length map.
|
deba@1699
|
87 |
template<class _Graph, class _LengthMap>
|
deba@1699
|
88 |
struct FloydWarshallDefaultTraits {
|
deba@1699
|
89 |
/// The graph type the algorithm runs on.
|
deba@1699
|
90 |
typedef _Graph Graph;
|
deba@1699
|
91 |
|
deba@1699
|
92 |
/// \brief The type of the map that stores the edge lengths.
|
deba@1699
|
93 |
///
|
deba@1699
|
94 |
/// The type of the map that stores the edge lengths.
|
deba@1699
|
95 |
/// It must meet the \ref concept::ReadMap "ReadMap" concept.
|
deba@1699
|
96 |
typedef _LengthMap LengthMap;
|
deba@1699
|
97 |
|
deba@1699
|
98 |
// The type of the length of the edges.
|
deba@1699
|
99 |
typedef typename _LengthMap::Value Value;
|
deba@1699
|
100 |
|
deba@1699
|
101 |
/// \brief Operation traits for belmann-ford algorithm.
|
deba@1699
|
102 |
///
|
deba@1699
|
103 |
/// It defines the infinity type on the given Value type
|
deba@1699
|
104 |
/// and the used operation.
|
deba@1699
|
105 |
/// \see FloydWarshallDefaultOperationTraits
|
deba@1699
|
106 |
typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
|
deba@1699
|
107 |
|
deba@1723
|
108 |
/// \brief The type of the matrix map that stores the last edges of the
|
deba@1699
|
109 |
/// shortest paths.
|
deba@1699
|
110 |
///
|
deba@1723
|
111 |
/// The type of the map that stores the last edges of the shortest paths.
|
deba@1699
|
112 |
/// It must be a matrix map with \c Graph::Edge value type.
|
deba@1699
|
113 |
///
|
deba@1723
|
114 |
typedef DynamicMatrixMap<Graph, typename Graph::Node,
|
deba@1723
|
115 |
typename Graph::Edge> PredMap;
|
deba@1699
|
116 |
|
deba@1699
|
117 |
/// \brief Instantiates a PredMap.
|
deba@1699
|
118 |
///
|
deba@1699
|
119 |
/// This function instantiates a \ref PredMap.
|
deba@1699
|
120 |
/// \param G is the graph, to which we would like to define the PredMap.
|
deba@1699
|
121 |
/// \todo The graph alone may be insufficient for the initialization
|
deba@1699
|
122 |
static PredMap *createPredMap(const _Graph& graph) {
|
deba@1699
|
123 |
return new PredMap(graph);
|
deba@1699
|
124 |
}
|
deba@1699
|
125 |
|
deba@1699
|
126 |
/// \brief The type of the map that stores the dists of the nodes.
|
deba@1699
|
127 |
///
|
deba@1699
|
128 |
/// The type of the map that stores the dists of the nodes.
|
deba@1723
|
129 |
/// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
|
deba@1699
|
130 |
///
|
deba@1723
|
131 |
typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
|
deba@1699
|
132 |
|
deba@1699
|
133 |
/// \brief Instantiates a DistMap.
|
deba@1699
|
134 |
///
|
deba@1699
|
135 |
/// This function instantiates a \ref DistMap.
|
deba@1699
|
136 |
/// \param G is the graph, to which we would like to define the
|
deba@1699
|
137 |
/// \ref DistMap
|
deba@1699
|
138 |
static DistMap *createDistMap(const _Graph& graph) {
|
deba@1699
|
139 |
return new DistMap(graph);
|
deba@1699
|
140 |
}
|
deba@1699
|
141 |
|
deba@1699
|
142 |
};
|
deba@1699
|
143 |
|
deba@1754
|
144 |
/// \brief %FloydWarshall algorithm class.
|
deba@1699
|
145 |
///
|
deba@1699
|
146 |
/// \ingroup flowalgs
|
deba@1754
|
147 |
/// This class provides an efficient implementation of \c Floyd-Warshall
|
deba@1699
|
148 |
/// algorithm. The edge lengths are passed to the algorithm using a
|
deba@1699
|
149 |
/// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
|
deba@1699
|
150 |
/// kind of length.
|
deba@1699
|
151 |
///
|
alpar@1757
|
152 |
/// The algorithm solves the shortest path problem for each pair
|
deba@1723
|
153 |
/// of node when the edges can have negative length but the graph should
|
deba@1754
|
154 |
/// not contain cycles with negative sum of length. If we can assume
|
deba@1723
|
155 |
/// that all edge is non-negative in the graph then the dijkstra algorithm
|
deba@1723
|
156 |
/// should be used from each node rather and if the graph is sparse and
|
deba@1754
|
157 |
/// there are negative circles then the johnson algorithm.
|
deba@1723
|
158 |
///
|
deba@1723
|
159 |
/// The complexity of this algorithm is O(n^3 + e).
|
deba@1723
|
160 |
///
|
deba@1699
|
161 |
/// The type of the length is determined by the
|
deba@1699
|
162 |
/// \ref concept::ReadMap::Value "Value" of the length map.
|
deba@1699
|
163 |
///
|
deba@1699
|
164 |
/// \param _Graph The graph type the algorithm runs on. The default value
|
deba@1699
|
165 |
/// is \ref ListGraph. The value of _Graph is not used directly by
|
deba@1699
|
166 |
/// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits.
|
deba@1699
|
167 |
/// \param _LengthMap This read-only EdgeMap determines the lengths of the
|
deba@1699
|
168 |
/// edges. It is read once for each edge, so the map may involve in
|
deba@1699
|
169 |
/// relatively time consuming process to compute the edge length if
|
deba@1699
|
170 |
/// it is necessary. The default map type is \ref
|
deba@1699
|
171 |
/// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
|
deba@1699
|
172 |
/// of _LengthMap is not used directly by FloydWarshall, it is only passed
|
deba@1699
|
173 |
/// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set
|
deba@1699
|
174 |
/// various data types used by the algorithm. The default traits
|
deba@1699
|
175 |
/// class is \ref FloydWarshallDefaultTraits
|
deba@1699
|
176 |
/// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref
|
deba@1699
|
177 |
/// FloydWarshallDefaultTraits for the documentation of a FloydWarshall
|
deba@1699
|
178 |
/// traits class.
|
deba@1699
|
179 |
///
|
deba@1699
|
180 |
/// \author Balazs Dezso
|
deba@1699
|
181 |
|
deba@1710
|
182 |
#ifdef DOXYGEN
|
deba@1710
|
183 |
template <typename _Graph, typename _LengthMap typename _Traits >
|
deba@1710
|
184 |
#else
|
deba@1699
|
185 |
template <typename _Graph=ListGraph,
|
deba@1699
|
186 |
typename _LengthMap=typename _Graph::template EdgeMap<int>,
|
deba@1699
|
187 |
typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
|
deba@1710
|
188 |
#endif
|
deba@1699
|
189 |
class FloydWarshall {
|
deba@1699
|
190 |
public:
|
deba@1699
|
191 |
|
deba@1699
|
192 |
/// \brief \ref Exception for uninitialized parameters.
|
deba@1699
|
193 |
///
|
deba@1699
|
194 |
/// This error represents problems in the initialization
|
deba@1699
|
195 |
/// of the parameters of the algorithms.
|
deba@1699
|
196 |
|
deba@1699
|
197 |
class UninitializedParameter : public lemon::UninitializedParameter {
|
deba@1699
|
198 |
public:
|
deba@1699
|
199 |
virtual const char* exceptionName() const {
|
deba@1699
|
200 |
return "lemon::FloydWarshall::UninitializedParameter";
|
deba@1699
|
201 |
}
|
deba@1699
|
202 |
};
|
deba@1699
|
203 |
|
deba@1699
|
204 |
typedef _Traits Traits;
|
deba@1699
|
205 |
///The type of the underlying graph.
|
deba@1699
|
206 |
typedef typename _Traits::Graph Graph;
|
deba@1699
|
207 |
|
deba@1699
|
208 |
typedef typename Graph::Node Node;
|
deba@1699
|
209 |
typedef typename Graph::NodeIt NodeIt;
|
deba@1699
|
210 |
typedef typename Graph::Edge Edge;
|
deba@1699
|
211 |
typedef typename Graph::EdgeIt EdgeIt;
|
deba@1699
|
212 |
|
deba@1699
|
213 |
/// \brief The type of the length of the edges.
|
deba@1699
|
214 |
typedef typename _Traits::LengthMap::Value Value;
|
deba@1699
|
215 |
/// \brief The type of the map that stores the edge lengths.
|
deba@1699
|
216 |
typedef typename _Traits::LengthMap LengthMap;
|
deba@1699
|
217 |
/// \brief The type of the map that stores the last
|
deba@1699
|
218 |
/// edges of the shortest paths. The type of the PredMap
|
deba@1699
|
219 |
/// is a matrix map for Edges
|
deba@1699
|
220 |
typedef typename _Traits::PredMap PredMap;
|
deba@1699
|
221 |
/// \brief The type of the map that stores the dists of the nodes.
|
deba@1699
|
222 |
/// The type of the DistMap is a matrix map for Values
|
deba@1699
|
223 |
typedef typename _Traits::DistMap DistMap;
|
deba@1699
|
224 |
/// \brief The operation traits.
|
deba@1699
|
225 |
typedef typename _Traits::OperationTraits OperationTraits;
|
deba@1699
|
226 |
private:
|
deba@1699
|
227 |
/// Pointer to the underlying graph.
|
deba@1699
|
228 |
const Graph *graph;
|
deba@1699
|
229 |
/// Pointer to the length map
|
deba@1699
|
230 |
const LengthMap *length;
|
deba@1699
|
231 |
///Pointer to the map of predecessors edges.
|
deba@1699
|
232 |
PredMap *_pred;
|
deba@1699
|
233 |
///Indicates if \ref _pred is locally allocated (\c true) or not.
|
deba@1699
|
234 |
bool local_pred;
|
deba@1699
|
235 |
///Pointer to the map of distances.
|
deba@1699
|
236 |
DistMap *_dist;
|
deba@1699
|
237 |
///Indicates if \ref _dist is locally allocated (\c true) or not.
|
deba@1699
|
238 |
bool local_dist;
|
deba@1699
|
239 |
|
deba@1699
|
240 |
/// Creates the maps if necessary.
|
deba@1699
|
241 |
void create_maps() {
|
deba@1699
|
242 |
if(!_pred) {
|
deba@1699
|
243 |
local_pred = true;
|
deba@1699
|
244 |
_pred = Traits::createPredMap(*graph);
|
deba@1699
|
245 |
}
|
deba@1699
|
246 |
if(!_dist) {
|
deba@1699
|
247 |
local_dist = true;
|
deba@1699
|
248 |
_dist = Traits::createDistMap(*graph);
|
deba@1699
|
249 |
}
|
deba@1699
|
250 |
}
|
deba@1699
|
251 |
|
deba@1699
|
252 |
public :
|
deba@1699
|
253 |
|
deba@1699
|
254 |
/// \name Named template parameters
|
deba@1699
|
255 |
|
deba@1699
|
256 |
///@{
|
deba@1699
|
257 |
|
deba@1699
|
258 |
template <class T>
|
deba@1699
|
259 |
struct DefPredMapTraits : public Traits {
|
deba@1699
|
260 |
typedef T PredMap;
|
deba@1699
|
261 |
static PredMap *createPredMap(const Graph& graph) {
|
deba@1699
|
262 |
throw UninitializedParameter();
|
deba@1699
|
263 |
}
|
deba@1699
|
264 |
};
|
deba@1699
|
265 |
|
deba@1699
|
266 |
/// \brief \ref named-templ-param "Named parameter" for setting PredMap
|
deba@1699
|
267 |
/// type
|
deba@1699
|
268 |
/// \ref named-templ-param "Named parameter" for setting PredMap type
|
deba@1699
|
269 |
///
|
deba@1699
|
270 |
template <class T>
|
deba@1710
|
271 |
struct DefPredMap
|
deba@1710
|
272 |
: public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
|
deba@1710
|
273 |
typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
|
deba@1710
|
274 |
};
|
deba@1699
|
275 |
|
deba@1699
|
276 |
template <class T>
|
deba@1699
|
277 |
struct DefDistMapTraits : public Traits {
|
deba@1699
|
278 |
typedef T DistMap;
|
deba@1699
|
279 |
static DistMap *createDistMap(const Graph& graph) {
|
deba@1699
|
280 |
throw UninitializedParameter();
|
deba@1699
|
281 |
}
|
deba@1699
|
282 |
};
|
deba@1699
|
283 |
/// \brief \ref named-templ-param "Named parameter" for setting DistMap
|
deba@1699
|
284 |
/// type
|
deba@1699
|
285 |
///
|
deba@1699
|
286 |
/// \ref named-templ-param "Named parameter" for setting DistMap type
|
deba@1699
|
287 |
///
|
deba@1699
|
288 |
template <class T>
|
deba@1710
|
289 |
struct DefDistMap
|
deba@1710
|
290 |
: public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
|
deba@1710
|
291 |
typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
|
deba@1710
|
292 |
};
|
deba@1699
|
293 |
|
deba@1699
|
294 |
template <class T>
|
deba@1699
|
295 |
struct DefOperationTraitsTraits : public Traits {
|
deba@1699
|
296 |
typedef T OperationTraits;
|
deba@1699
|
297 |
};
|
deba@1699
|
298 |
|
deba@1699
|
299 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
deba@1699
|
300 |
/// OperationTraits type
|
deba@1699
|
301 |
///
|
deba@1699
|
302 |
/// \ref named-templ-param "Named parameter" for setting PredMap type
|
deba@1699
|
303 |
template <class T>
|
deba@1710
|
304 |
struct DefOperationTraits
|
deba@1699
|
305 |
: public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
|
deba@1710
|
306 |
typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
|
deba@1710
|
307 |
Create;
|
deba@1699
|
308 |
};
|
deba@1699
|
309 |
|
deba@1699
|
310 |
///@}
|
deba@1699
|
311 |
|
deba@1710
|
312 |
protected:
|
deba@1710
|
313 |
|
deba@1710
|
314 |
FloydWarshall() {}
|
deba@1710
|
315 |
|
deba@1699
|
316 |
public:
|
deba@1710
|
317 |
|
deba@1710
|
318 |
typedef FloydWarshall Create;
|
deba@1699
|
319 |
|
deba@1699
|
320 |
/// \brief Constructor.
|
deba@1699
|
321 |
///
|
deba@1699
|
322 |
/// \param _graph the graph the algorithm will run on.
|
deba@1699
|
323 |
/// \param _length the length map used by the algorithm.
|
deba@1699
|
324 |
FloydWarshall(const Graph& _graph, const LengthMap& _length) :
|
deba@1699
|
325 |
graph(&_graph), length(&_length),
|
deba@1699
|
326 |
_pred(0), local_pred(false),
|
deba@1699
|
327 |
_dist(0), local_dist(false) {}
|
deba@1699
|
328 |
|
deba@1699
|
329 |
///Destructor.
|
deba@1699
|
330 |
~FloydWarshall() {
|
deba@1699
|
331 |
if(local_pred) delete _pred;
|
deba@1699
|
332 |
if(local_dist) delete _dist;
|
deba@1699
|
333 |
}
|
deba@1699
|
334 |
|
deba@1699
|
335 |
/// \brief Sets the length map.
|
deba@1699
|
336 |
///
|
deba@1699
|
337 |
/// Sets the length map.
|
deba@1699
|
338 |
/// \return \c (*this)
|
deba@1699
|
339 |
FloydWarshall &lengthMap(const LengthMap &m) {
|
deba@1699
|
340 |
length = &m;
|
deba@1699
|
341 |
return *this;
|
deba@1699
|
342 |
}
|
deba@1699
|
343 |
|
deba@1699
|
344 |
/// \brief Sets the map storing the predecessor edges.
|
deba@1699
|
345 |
///
|
deba@1699
|
346 |
/// Sets the map storing the predecessor edges.
|
deba@1699
|
347 |
/// If you don't use this function before calling \ref run(),
|
deba@1699
|
348 |
/// it will allocate one. The destuctor deallocates this
|
deba@1699
|
349 |
/// automatically allocated map, of course.
|
deba@1699
|
350 |
/// \return \c (*this)
|
deba@1699
|
351 |
FloydWarshall &predMap(PredMap &m) {
|
deba@1699
|
352 |
if(local_pred) {
|
deba@1699
|
353 |
delete _pred;
|
deba@1699
|
354 |
local_pred=false;
|
deba@1699
|
355 |
}
|
deba@1699
|
356 |
_pred = &m;
|
deba@1699
|
357 |
return *this;
|
deba@1699
|
358 |
}
|
deba@1699
|
359 |
|
deba@1699
|
360 |
/// \brief Sets the map storing the distances calculated by the algorithm.
|
deba@1699
|
361 |
///
|
deba@1699
|
362 |
/// Sets the map storing the distances calculated by the algorithm.
|
deba@1699
|
363 |
/// If you don't use this function before calling \ref run(),
|
deba@1699
|
364 |
/// it will allocate one. The destuctor deallocates this
|
deba@1699
|
365 |
/// automatically allocated map, of course.
|
deba@1699
|
366 |
/// \return \c (*this)
|
deba@1699
|
367 |
FloydWarshall &distMap(DistMap &m) {
|
deba@1699
|
368 |
if(local_dist) {
|
deba@1699
|
369 |
delete _dist;
|
deba@1699
|
370 |
local_dist=false;
|
deba@1699
|
371 |
}
|
deba@1699
|
372 |
_dist = &m;
|
deba@1699
|
373 |
return *this;
|
deba@1699
|
374 |
}
|
deba@1699
|
375 |
|
deba@1699
|
376 |
///\name Execution control
|
deba@1699
|
377 |
/// The simplest way to execute the algorithm is to use
|
deba@1699
|
378 |
/// one of the member functions called \c run(...).
|
deba@1699
|
379 |
/// \n
|
deba@1699
|
380 |
/// If you need more control on the execution,
|
deba@1699
|
381 |
/// Finally \ref start() will perform the actual path
|
deba@1699
|
382 |
/// computation.
|
deba@1699
|
383 |
|
deba@1699
|
384 |
///@{
|
deba@1699
|
385 |
|
deba@1699
|
386 |
/// \brief Initializes the internal data structures.
|
deba@1699
|
387 |
///
|
deba@1699
|
388 |
/// Initializes the internal data structures.
|
deba@1699
|
389 |
void init() {
|
deba@1699
|
390 |
create_maps();
|
deba@1699
|
391 |
for (NodeIt it(*graph); it != INVALID; ++it) {
|
deba@1699
|
392 |
for (NodeIt jt(*graph); jt != INVALID; ++jt) {
|
deba@1699
|
393 |
_pred->set(it, jt, INVALID);
|
deba@1741
|
394 |
_dist->set(it, jt, OperationTraits::infinity());
|
deba@1699
|
395 |
}
|
deba@1741
|
396 |
_dist->set(it, it, OperationTraits::zero());
|
deba@1699
|
397 |
}
|
deba@1699
|
398 |
for (EdgeIt it(*graph); it != INVALID; ++it) {
|
deba@1699
|
399 |
Node source = graph->source(it);
|
deba@1699
|
400 |
Node target = graph->target(it);
|
deba@1699
|
401 |
if (OperationTraits::less((*length)[it], (*_dist)(source, target))) {
|
deba@1699
|
402 |
_dist->set(source, target, (*length)[it]);
|
deba@1699
|
403 |
_pred->set(source, target, it);
|
deba@1699
|
404 |
}
|
deba@1699
|
405 |
}
|
deba@1699
|
406 |
}
|
deba@1699
|
407 |
|
deba@1699
|
408 |
/// \brief Executes the algorithm.
|
deba@1699
|
409 |
///
|
deba@1699
|
410 |
/// This method runs the %FloydWarshall algorithm in order to compute
|
deba@1699
|
411 |
/// the shortest path to each node pairs. The algorithm
|
deba@1699
|
412 |
/// computes
|
deba@1699
|
413 |
/// - The shortest path tree for each node.
|
deba@1699
|
414 |
/// - The distance between each node pairs.
|
deba@1699
|
415 |
void start() {
|
deba@1699
|
416 |
for (NodeIt kt(*graph); kt != INVALID; ++kt) {
|
deba@1699
|
417 |
for (NodeIt it(*graph); it != INVALID; ++it) {
|
deba@1699
|
418 |
for (NodeIt jt(*graph); jt != INVALID; ++jt) {
|
deba@1699
|
419 |
Value relaxed = OperationTraits::plus((*_dist)(it, kt),
|
deba@1699
|
420 |
(*_dist)(kt, jt));
|
deba@1699
|
421 |
if (OperationTraits::less(relaxed, (*_dist)(it, jt))) {
|
deba@1699
|
422 |
_dist->set(it, jt, relaxed);
|
deba@1699
|
423 |
_pred->set(it, jt, (*_pred)(kt, jt));
|
deba@1699
|
424 |
}
|
deba@1699
|
425 |
}
|
deba@1699
|
426 |
}
|
deba@1699
|
427 |
}
|
deba@1699
|
428 |
}
|
deba@1741
|
429 |
|
deba@1754
|
430 |
/// \brief Executes the algorithm and checks the negative cycles.
|
deba@1741
|
431 |
///
|
deba@1741
|
432 |
/// This method runs the %FloydWarshall algorithm in order to compute
|
deba@1754
|
433 |
/// the shortest path to each node pairs. If there is a negative cycle
|
deba@1741
|
434 |
/// in the graph it gives back false.
|
deba@1741
|
435 |
/// The algorithm computes
|
deba@1741
|
436 |
/// - The shortest path tree for each node.
|
deba@1741
|
437 |
/// - The distance between each node pairs.
|
deba@1741
|
438 |
bool checkedStart() {
|
deba@1741
|
439 |
start();
|
deba@1741
|
440 |
for (NodeIt it(*graph); it != INVALID; ++it) {
|
deba@1741
|
441 |
if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
|
deba@1741
|
442 |
return false;
|
deba@1741
|
443 |
}
|
deba@1741
|
444 |
}
|
deba@1741
|
445 |
return true;
|
deba@1741
|
446 |
}
|
deba@1699
|
447 |
|
deba@1699
|
448 |
/// \brief Runs %FloydWarshall algorithm.
|
deba@1699
|
449 |
///
|
deba@1699
|
450 |
/// This method runs the %FloydWarshall algorithm from a each node
|
deba@1699
|
451 |
/// in order to compute the shortest path to each node pairs.
|
deba@1699
|
452 |
/// The algorithm computes
|
deba@1699
|
453 |
/// - The shortest path tree for each node.
|
deba@1699
|
454 |
/// - The distance between each node pairs.
|
deba@1699
|
455 |
///
|
deba@1699
|
456 |
/// \note d.run(s) is just a shortcut of the following code.
|
deba@1699
|
457 |
/// \code
|
deba@1699
|
458 |
/// d.init();
|
deba@1699
|
459 |
/// d.start();
|
deba@1699
|
460 |
/// \endcode
|
deba@1699
|
461 |
void run() {
|
deba@1699
|
462 |
init();
|
deba@1699
|
463 |
start();
|
deba@1699
|
464 |
}
|
deba@1699
|
465 |
|
deba@1699
|
466 |
///@}
|
deba@1699
|
467 |
|
deba@1699
|
468 |
/// \name Query Functions
|
deba@1699
|
469 |
/// The result of the %FloydWarshall algorithm can be obtained using these
|
deba@1699
|
470 |
/// functions.\n
|
deba@1699
|
471 |
/// Before the use of these functions,
|
deba@1699
|
472 |
/// either run() or start() must be called.
|
deba@1699
|
473 |
|
deba@1699
|
474 |
///@{
|
deba@1699
|
475 |
|
deba@1699
|
476 |
/// \brief Copies the shortest path to \c t into \c p
|
deba@1699
|
477 |
///
|
deba@1699
|
478 |
/// This function copies the shortest path to \c t into \c p.
|
deba@1699
|
479 |
/// If it \c t is a source itself or unreachable, then it does not
|
deba@1699
|
480 |
/// alter \c p.
|
deba@1699
|
481 |
/// \return Returns \c true if a path to \c t was actually copied to \c p,
|
deba@1699
|
482 |
/// \c false otherwise.
|
deba@1699
|
483 |
/// \sa DirPath
|
deba@1699
|
484 |
template <typename Path>
|
deba@1699
|
485 |
bool getPath(Path &p, Node source, Node target) {
|
deba@1699
|
486 |
if (connected(source, target)) {
|
deba@1699
|
487 |
p.clear();
|
deba@1699
|
488 |
typename Path::Builder b(target);
|
deba@1763
|
489 |
for(b.setStartNode(target); predEdge(source, target) != INVALID;
|
deba@1699
|
490 |
target = predNode(target)) {
|
deba@1763
|
491 |
b.pushFront(predEdge(source, target));
|
deba@1699
|
492 |
}
|
deba@1699
|
493 |
b.commit();
|
deba@1699
|
494 |
return true;
|
deba@1699
|
495 |
}
|
deba@1699
|
496 |
return false;
|
deba@1699
|
497 |
}
|
deba@1699
|
498 |
|
deba@1699
|
499 |
/// \brief The distance between two nodes.
|
deba@1699
|
500 |
///
|
deba@1699
|
501 |
/// Returns the distance between two nodes.
|
deba@1699
|
502 |
/// \pre \ref run() must be called before using this function.
|
deba@1699
|
503 |
/// \warning If node \c v in unreachable from the root the return value
|
deba@1699
|
504 |
/// of this funcion is undefined.
|
deba@1699
|
505 |
Value dist(Node source, Node target) const {
|
deba@1699
|
506 |
return (*_dist)(source, target);
|
deba@1699
|
507 |
}
|
deba@1699
|
508 |
|
deba@1699
|
509 |
/// \brief Returns the 'previous edge' of the shortest path tree.
|
deba@1699
|
510 |
///
|
deba@1699
|
511 |
/// For the node \c node it returns the 'previous edge' of the shortest
|
deba@1699
|
512 |
/// path tree to direction of the node \c root
|
deba@1699
|
513 |
/// i.e. it returns the last edge of a shortest path from the node \c root
|
deba@1699
|
514 |
/// to \c node. It is \ref INVALID if \c node is unreachable from the root
|
deba@1699
|
515 |
/// or if \c node=root. The shortest path tree used here is equal to the
|
deba@1699
|
516 |
/// shortest path tree used in \ref predNode().
|
deba@1699
|
517 |
/// \pre \ref run() must be called before using this function.
|
deba@1763
|
518 |
Edge predEdge(Node root, Node node) const {
|
deba@1699
|
519 |
return (*_pred)(root, node);
|
deba@1699
|
520 |
}
|
deba@1699
|
521 |
|
deba@1699
|
522 |
/// \brief Returns the 'previous node' of the shortest path tree.
|
deba@1699
|
523 |
///
|
deba@1699
|
524 |
/// For a node \c node it returns the 'previous node' of the shortest path
|
deba@1699
|
525 |
/// tree to direction of the node \c root, i.e. it returns the last but
|
deba@1699
|
526 |
/// one node from a shortest path from the \c root to \c node. It is
|
deba@1699
|
527 |
/// INVALID if \c node is unreachable from the root or if \c node=root.
|
deba@1699
|
528 |
/// The shortest path tree used here is equal to the
|
deba@1763
|
529 |
/// shortest path tree used in \ref predEdge().
|
deba@1699
|
530 |
/// \pre \ref run() must be called before using this function.
|
deba@1699
|
531 |
Node predNode(Node root, Node node) const {
|
deba@1699
|
532 |
return (*_pred)(root, node) == INVALID ?
|
deba@1699
|
533 |
INVALID : graph->source((*_pred)(root, node));
|
deba@1699
|
534 |
}
|
deba@1699
|
535 |
|
deba@1699
|
536 |
/// \brief Returns a reference to the matrix node map of distances.
|
deba@1699
|
537 |
///
|
deba@1699
|
538 |
/// Returns a reference to the matrix node map of distances.
|
deba@1699
|
539 |
///
|
deba@1699
|
540 |
/// \pre \ref run() must be called before using this function.
|
deba@1699
|
541 |
const DistMap &distMap() const { return *_dist;}
|
deba@1699
|
542 |
|
deba@1699
|
543 |
/// \brief Returns a reference to the shortest path tree map.
|
deba@1699
|
544 |
///
|
deba@1699
|
545 |
/// Returns a reference to the matrix node map of the edges of the
|
deba@1699
|
546 |
/// shortest path tree.
|
deba@1699
|
547 |
/// \pre \ref run() must be called before using this function.
|
deba@1699
|
548 |
const PredMap &predMap() const { return *_pred;}
|
deba@1699
|
549 |
|
deba@1699
|
550 |
/// \brief Checks if a node is reachable from the root.
|
deba@1699
|
551 |
///
|
deba@1699
|
552 |
/// Returns \c true if \c v is reachable from the root.
|
deba@1699
|
553 |
/// \pre \ref run() must be called before using this function.
|
deba@1699
|
554 |
///
|
deba@1699
|
555 |
bool connected(Node source, Node target) {
|
deba@1699
|
556 |
return (*_dist)(source, target) != OperationTraits::infinity();
|
deba@1699
|
557 |
}
|
deba@1699
|
558 |
|
deba@1699
|
559 |
///@}
|
deba@1699
|
560 |
};
|
deba@1699
|
561 |
|
deba@1699
|
562 |
} //END OF NAMESPACE LEMON
|
deba@1699
|
563 |
|
deba@1699
|
564 |
#endif
|
deba@1699
|
565 |
|