COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/floyd_warshall.h @ 2376:0ed45a6c74b1

Last change on this file since 2376:0ed45a6c74b1 was 2376:0ed45a6c74b1, checked in by Balazs Dezso, 13 years ago

Reorganization of the modules and groups

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