NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/floyd_warshall.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_FLOYD_WARSHALL_H
18 #define LEMON_FLOYD_WARSHALL_H
22 /// \brief FloydWarshall algorithm.
25 #include <lemon/list_graph.h>
26 #include <lemon/graph_utils.h>
27 #include <lemon/invalid.h>
28 #include <lemon/error.h>
29 #include <lemon/matrix_maps.h>
30 #include <lemon/maps.h>
36 /// \brief Default OperationTraits for the FloydWarshall algorithm class.
38 /// It defines all computational operations and constants which are
39 /// used in the Floyd-Warshall algorithm. The default implementation
40 /// is based on the numeric_limits class. If the numeric type does not
41 /// have infinity value then the maximum value is used as extremal
45 bool has_infinity = std::numeric_limits<Value>::has_infinity>
46 struct FloydWarshallDefaultOperationTraits {
47 /// \brief Gives back the zero value of the type.
49 return static_cast<Value>(0);
51 /// \brief Gives back the positive infinity value of the type.
52 static Value infinity() {
53 return std::numeric_limits<Value>::infinity();
55 /// \brief Gives back the sum of the given two elements.
56 static Value plus(const Value& left, const Value& right) {
59 /// \brief Gives back true only if the first value less than the second.
60 static bool less(const Value& left, const Value& right) {
65 template <typename Value>
66 struct FloydWarshallDefaultOperationTraits<Value, false> {
68 return static_cast<Value>(0);
70 static Value infinity() {
71 return std::numeric_limits<Value>::max();
73 static Value plus(const Value& left, const Value& right) {
74 if (left == infinity() || right == infinity()) return infinity();
77 static bool less(const Value& left, const Value& right) {
82 /// \brief Default traits class of FloydWarshall class.
84 /// Default traits class of FloydWarshall class.
85 /// \param _Graph Graph type.
86 /// \param _LegthMap Type of length map.
87 template<class _Graph, class _LengthMap>
88 struct FloydWarshallDefaultTraits {
89 /// The graph type the algorithm runs on.
92 /// \brief The type of the map that stores the edge lengths.
94 /// The type of the map that stores the edge lengths.
95 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
96 typedef _LengthMap LengthMap;
98 // The type of the length of the edges.
99 typedef typename _LengthMap::Value Value;
101 /// \brief Operation traits for belmann-ford algorithm.
103 /// It defines the infinity type on the given Value type
104 /// and the used operation.
105 /// \see FloydWarshallDefaultOperationTraits
106 typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
108 /// \brief The type of the matrix map that stores the last edges of the
111 /// The type of the map that stores the last edges of the shortest paths.
112 /// It must be a matrix map with \c Graph::Edge value type.
114 typedef DynamicMatrixMap<Graph, typename Graph::Node,
115 typename Graph::Edge> PredMap;
117 /// \brief Instantiates a PredMap.
119 /// This function instantiates a \ref PredMap.
120 /// \param G is the graph, to which we would like to define the PredMap.
121 /// \todo The graph alone may be insufficient for the initialization
122 static PredMap *createPredMap(const _Graph& graph) {
123 return new PredMap(graph);
126 /// \brief The type of the map that stores the dists of the nodes.
128 /// The type of the map that stores the dists of the nodes.
129 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
131 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
133 /// \brief Instantiates a DistMap.
135 /// This function instantiates a \ref DistMap.
136 /// \param G is the graph, to which we would like to define the
138 static DistMap *createDistMap(const _Graph& graph) {
139 return new DistMap(graph);
144 /// \brief %FloydWarshall algorithm class.
146 /// \ingroup flowalgs
147 /// This class provides an efficient implementation of \c Floyd-Warshall
148 /// algorithm. The edge lengths are passed to the algorithm using a
149 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
152 /// The algorithm solves the shortest path problem for each pair
153 /// of node when the edges can have negative length but the graph should
154 /// not contain cycles with negative sum of length. If we can assume
155 /// that all edge is non-negative in the graph then the dijkstra algorithm
156 /// should be used from each node rather and if the graph is sparse and
157 /// there are negative circles then the johnson algorithm.
159 /// The complexity of this algorithm is O(n^3 + e).
161 /// The type of the length is determined by the
162 /// \ref concept::ReadMap::Value "Value" of the length map.
164 /// \param _Graph The graph type the algorithm runs on. The default value
165 /// is \ref ListGraph. The value of _Graph is not used directly by
166 /// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits.
167 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
168 /// edges. It is read once for each edge, so the map may involve in
169 /// relatively time consuming process to compute the edge length if
170 /// it is necessary. The default map type is \ref
171 /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
172 /// of _LengthMap is not used directly by FloydWarshall, it is only passed
173 /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set
174 /// various data types used by the algorithm. The default traits
175 /// class is \ref FloydWarshallDefaultTraits
176 /// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref
177 /// FloydWarshallDefaultTraits for the documentation of a FloydWarshall
180 /// \author Balazs Dezso
183 template <typename _Graph, typename _LengthMap typename _Traits >
185 template <typename _Graph=ListGraph,
186 typename _LengthMap=typename _Graph::template EdgeMap<int>,
187 typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
189 class FloydWarshall {
192 /// \brief \ref Exception for uninitialized parameters.
194 /// This error represents problems in the initialization
195 /// of the parameters of the algorithms.
197 class UninitializedParameter : public lemon::UninitializedParameter {
199 virtual const char* exceptionName() const {
200 return "lemon::FloydWarshall::UninitializedParameter";
204 typedef _Traits Traits;
205 ///The type of the underlying graph.
206 typedef typename _Traits::Graph Graph;
208 typedef typename Graph::Node Node;
209 typedef typename Graph::NodeIt NodeIt;
210 typedef typename Graph::Edge Edge;
211 typedef typename Graph::EdgeIt EdgeIt;
213 /// \brief The type of the length of the edges.
214 typedef typename _Traits::LengthMap::Value Value;
215 /// \brief The type of the map that stores the edge lengths.
216 typedef typename _Traits::LengthMap LengthMap;
217 /// \brief The type of the map that stores the last
218 /// edges of the shortest paths. The type of the PredMap
219 /// is a matrix map for Edges
220 typedef typename _Traits::PredMap PredMap;
221 /// \brief The type of the map that stores the dists of the nodes.
222 /// The type of the DistMap is a matrix map for Values
223 typedef typename _Traits::DistMap DistMap;
224 /// \brief The operation traits.
225 typedef typename _Traits::OperationTraits OperationTraits;
227 /// Pointer to the underlying graph.
229 /// Pointer to the length map
230 const LengthMap *length;
231 ///Pointer to the map of predecessors edges.
233 ///Indicates if \ref _pred is locally allocated (\c true) or not.
235 ///Pointer to the map of distances.
237 ///Indicates if \ref _dist is locally allocated (\c true) or not.
240 /// Creates the maps if necessary.
244 _pred = Traits::createPredMap(*graph);
248 _dist = Traits::createDistMap(*graph);
254 /// \name Named template parameters
259 struct DefPredMapTraits : public Traits {
261 static PredMap *createPredMap(const Graph& graph) {
262 throw UninitializedParameter();
266 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
268 /// \ref named-templ-param "Named parameter" for setting PredMap type
272 : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
273 typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
277 struct DefDistMapTraits : public Traits {
279 static DistMap *createDistMap(const Graph& graph) {
280 throw UninitializedParameter();
283 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
286 /// \ref named-templ-param "Named parameter" for setting DistMap type
290 : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
291 typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
295 struct DefOperationTraitsTraits : public Traits {
296 typedef T OperationTraits;
299 /// \brief \ref named-templ-param "Named parameter" for setting
300 /// OperationTraits type
302 /// \ref named-templ-param "Named parameter" for setting PredMap type
304 struct DefOperationTraits
305 : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
306 typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
318 typedef FloydWarshall Create;
320 /// \brief Constructor.
322 /// \param _graph the graph the algorithm will run on.
323 /// \param _length the length map used by the algorithm.
324 FloydWarshall(const Graph& _graph, const LengthMap& _length) :
325 graph(&_graph), length(&_length),
326 _pred(0), local_pred(false),
327 _dist(0), local_dist(false) {}
331 if(local_pred) delete _pred;
332 if(local_dist) delete _dist;
335 /// \brief Sets the length map.
337 /// Sets the length map.
338 /// \return \c (*this)
339 FloydWarshall &lengthMap(const LengthMap &m) {
344 /// \brief Sets the map storing the predecessor edges.
346 /// Sets the map storing the predecessor edges.
347 /// If you don't use this function before calling \ref run(),
348 /// it will allocate one. The destuctor deallocates this
349 /// automatically allocated map, of course.
350 /// \return \c (*this)
351 FloydWarshall &predMap(PredMap &m) {
360 /// \brief Sets the map storing the distances calculated by the algorithm.
362 /// Sets the map storing the distances calculated by the algorithm.
363 /// If you don't use this function before calling \ref run(),
364 /// it will allocate one. The destuctor deallocates this
365 /// automatically allocated map, of course.
366 /// \return \c (*this)
367 FloydWarshall &distMap(DistMap &m) {
376 ///\name Execution control
377 /// The simplest way to execute the algorithm is to use
378 /// one of the member functions called \c run(...).
380 /// If you need more control on the execution,
381 /// Finally \ref start() will perform the actual path
386 /// \brief Initializes the internal data structures.
388 /// Initializes the internal data structures.
391 for (NodeIt it(*graph); it != INVALID; ++it) {
392 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
393 _pred->set(it, jt, INVALID);
394 _dist->set(it, jt, OperationTraits::infinity());
396 _dist->set(it, it, OperationTraits::zero());
398 for (EdgeIt it(*graph); it != INVALID; ++it) {
399 Node source = graph->source(it);
400 Node target = graph->target(it);
401 if (OperationTraits::less((*length)[it], (*_dist)(source, target))) {
402 _dist->set(source, target, (*length)[it]);
403 _pred->set(source, target, it);
408 /// \brief Executes the algorithm.
410 /// This method runs the %FloydWarshall algorithm in order to compute
411 /// the shortest path to each node pairs. The algorithm
413 /// - The shortest path tree for each node.
414 /// - The distance between each node pairs.
416 for (NodeIt kt(*graph); kt != INVALID; ++kt) {
417 for (NodeIt it(*graph); it != INVALID; ++it) {
418 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
419 Value relaxed = OperationTraits::plus((*_dist)(it, kt),
421 if (OperationTraits::less(relaxed, (*_dist)(it, jt))) {
422 _dist->set(it, jt, relaxed);
423 _pred->set(it, jt, (*_pred)(kt, jt));
430 /// \brief Executes the algorithm and checks the negative cycles.
432 /// This method runs the %FloydWarshall algorithm in order to compute
433 /// the shortest path to each node pairs. If there is a negative cycle
434 /// in the graph it gives back false.
435 /// The algorithm computes
436 /// - The shortest path tree for each node.
437 /// - The distance between each node pairs.
438 bool checkedStart() {
440 for (NodeIt it(*graph); it != INVALID; ++it) {
441 if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
448 /// \brief Runs %FloydWarshall algorithm.
450 /// This method runs the %FloydWarshall algorithm from a each node
451 /// in order to compute the shortest path to each node pairs.
452 /// The algorithm computes
453 /// - The shortest path tree for each node.
454 /// - The distance between each node pairs.
456 /// \note d.run(s) is just a shortcut of the following code.
468 /// \name Query Functions
469 /// The result of the %FloydWarshall algorithm can be obtained using these
471 /// Before the use of these functions,
472 /// either run() or start() must be called.
476 /// \brief Copies the shortest path to \c t into \c p
478 /// This function copies the shortest path to \c t into \c p.
479 /// If it \c t is a source itself or unreachable, then it does not
481 /// \return Returns \c true if a path to \c t was actually copied to \c p,
482 /// \c false otherwise.
484 template <typename Path>
485 bool getPath(Path &p, Node source, Node target) {
486 if (connected(source, target)) {
488 typename Path::Builder b(target);
489 for(b.setStartNode(target); predEdge(source, target) != INVALID;
490 target = predNode(target)) {
491 b.pushFront(predEdge(source, target));
499 /// \brief The distance between two nodes.
501 /// Returns the distance between two nodes.
502 /// \pre \ref run() must be called before using this function.
503 /// \warning If node \c v in unreachable from the root the return value
504 /// of this funcion is undefined.
505 Value dist(Node source, Node target) const {
506 return (*_dist)(source, target);
509 /// \brief Returns the 'previous edge' of the shortest path tree.
511 /// For the node \c node it returns the 'previous edge' of the shortest
512 /// path tree to direction of the node \c root
513 /// i.e. it returns the last edge of a shortest path from the node \c root
514 /// to \c node. It is \ref INVALID if \c node is unreachable from the root
515 /// or if \c node=root. The shortest path tree used here is equal to the
516 /// shortest path tree used in \ref predNode().
517 /// \pre \ref run() must be called before using this function.
518 Edge predEdge(Node root, Node node) const {
519 return (*_pred)(root, node);
522 /// \brief Returns the 'previous node' of the shortest path tree.
524 /// For a node \c node it returns the 'previous node' of the shortest path
525 /// tree to direction of the node \c root, i.e. it returns the last but
526 /// one node from a shortest path from the \c root to \c node. It is
527 /// INVALID if \c node is unreachable from the root or if \c node=root.
528 /// The shortest path tree used here is equal to the
529 /// shortest path tree used in \ref predEdge().
530 /// \pre \ref run() must be called before using this function.
531 Node predNode(Node root, Node node) const {
532 return (*_pred)(root, node) == INVALID ?
533 INVALID : graph->source((*_pred)(root, node));
536 /// \brief Returns a reference to the matrix node map of distances.
538 /// Returns a reference to the matrix node map of distances.
540 /// \pre \ref run() must be called before using this function.
541 const DistMap &distMap() const { return *_dist;}
543 /// \brief Returns a reference to the shortest path tree map.
545 /// Returns a reference to the matrix node map of the edges of the
546 /// shortest path tree.
547 /// \pre \ref run() must be called before using this function.
548 const PredMap &predMap() const { return *_pred;}
550 /// \brief Checks if a node is reachable from the root.
552 /// Returns \c true if \c v is reachable from the root.
553 /// \pre \ref run() must be called before using this function.
555 bool connected(Node source, Node target) {
556 return (*_dist)(source, target) != OperationTraits::infinity();
562 } //END OF NAMESPACE LEMON