COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/floyd_warshall.h @ 1723:fb4f801dd692

Last change on this file since 1723:fb4f801dd692 was 1723:fb4f801dd692, checked in by Balazs Dezso, 14 years ago

Really short description of these shortest path algorithms

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