COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/floyd_warshall.h @ 1699:29428f7b8b66

Last change on this file since 1699:29428f7b8b66 was 1699:29428f7b8b66, checked in by Balazs Dezso, 15 years ago

Some shortest path algorithms
All-pair-shortest path algorithms without function interface
we may need it

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