COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/floyd_warshall.h @ 1710:f531c16dd923

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

Bug solved in named parameters
Simplify my Johnson algorithm

File size: 17.8 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#ifdef DOXYGEN
174  template <typename _Graph, typename _LengthMap typename _Traits >
175#else
176  template <typename _Graph=ListGraph,
177            typename _LengthMap=typename _Graph::template EdgeMap<int>,
178            typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
179#endif
180  class FloydWarshall {
181  public:
182   
183    /// \brief \ref Exception for uninitialized parameters.
184    ///
185    /// This error represents problems in the initialization
186    /// of the parameters of the algorithms.
187
188    class UninitializedParameter : public lemon::UninitializedParameter {
189    public:
190      virtual const char* exceptionName() const {
191        return "lemon::FloydWarshall::UninitializedParameter";
192      }
193    };
194
195    typedef _Traits Traits;
196    ///The type of the underlying graph.
197    typedef typename _Traits::Graph Graph;
198
199    typedef typename Graph::Node Node;
200    typedef typename Graph::NodeIt NodeIt;
201    typedef typename Graph::Edge Edge;
202    typedef typename Graph::EdgeIt EdgeIt;
203   
204    /// \brief The type of the length of the edges.
205    typedef typename _Traits::LengthMap::Value Value;
206    /// \brief The type of the map that stores the edge lengths.
207    typedef typename _Traits::LengthMap LengthMap;
208    /// \brief The type of the map that stores the last
209    /// edges of the shortest paths. The type of the PredMap
210    /// is a matrix map for Edges
211    typedef typename _Traits::PredMap PredMap;
212    /// \brief The type of the map that stores the dists of the nodes.
213    /// The type of the DistMap is a matrix map for Values
214    typedef typename _Traits::DistMap DistMap;
215    /// \brief The operation traits.
216    typedef typename _Traits::OperationTraits OperationTraits;
217  private:
218    /// Pointer to the underlying graph.
219    const Graph *graph;
220    /// Pointer to the length map
221    const LengthMap *length;
222    ///Pointer to the map of predecessors edges.
223    PredMap *_pred;
224    ///Indicates if \ref _pred is locally allocated (\c true) or not.
225    bool local_pred;
226    ///Pointer to the map of distances.
227    DistMap *_dist;
228    ///Indicates if \ref _dist is locally allocated (\c true) or not.
229    bool local_dist;
230
231    /// Creates the maps if necessary.
232    void create_maps() {
233      if(!_pred) {
234        local_pred = true;
235        _pred = Traits::createPredMap(*graph);
236      }
237      if(!_dist) {
238        local_dist = true;
239        _dist = Traits::createDistMap(*graph);
240      }
241    }
242   
243  public :
244 
245    /// \name Named template parameters
246
247    ///@{
248
249    template <class T>
250    struct DefPredMapTraits : public Traits {
251      typedef T PredMap;
252      static PredMap *createPredMap(const Graph& graph) {
253        throw UninitializedParameter();
254      }
255    };
256
257    /// \brief \ref named-templ-param "Named parameter" for setting PredMap
258    /// type
259    /// \ref named-templ-param "Named parameter" for setting PredMap type
260    ///
261    template <class T>
262    struct DefPredMap
263      : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
264      typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
265    };
266   
267    template <class T>
268    struct DefDistMapTraits : public Traits {
269      typedef T DistMap;
270      static DistMap *createDistMap(const Graph& graph) {
271        throw UninitializedParameter();
272      }
273    };
274    /// \brief \ref named-templ-param "Named parameter" for setting DistMap
275    /// type
276    ///
277    /// \ref named-templ-param "Named parameter" for setting DistMap type
278    ///
279    template <class T>
280    struct DefDistMap
281      : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
282      typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
283    };
284   
285    template <class T>
286    struct DefOperationTraitsTraits : public Traits {
287      typedef T OperationTraits;
288    };
289   
290    /// \brief \ref named-templ-param "Named parameter" for setting
291    /// OperationTraits type
292    ///
293    /// \ref named-templ-param "Named parameter" for setting PredMap type
294    template <class T>
295    struct DefOperationTraits
296      : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
297      typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
298      Create;
299    };
300   
301    ///@}
302
303  protected:
304
305    FloydWarshall() {}
306
307  public:     
308
309    typedef FloydWarshall Create;
310   
311    /// \brief Constructor.
312    ///
313    /// \param _graph the graph the algorithm will run on.
314    /// \param _length the length map used by the algorithm.
315    FloydWarshall(const Graph& _graph, const LengthMap& _length) :
316      graph(&_graph), length(&_length),
317      _pred(0), local_pred(false),
318      _dist(0), local_dist(false) {}
319   
320    ///Destructor.
321    ~FloydWarshall() {
322      if(local_pred) delete _pred;
323      if(local_dist) delete _dist;
324    }
325
326    /// \brief Sets the length map.
327    ///
328    /// Sets the length map.
329    /// \return \c (*this)
330    FloydWarshall &lengthMap(const LengthMap &m) {
331      length = &m;
332      return *this;
333    }
334
335    /// \brief Sets the map storing the predecessor edges.
336    ///
337    /// Sets the map storing the predecessor edges.
338    /// If you don't use this function before calling \ref run(),
339    /// it will allocate one. The destuctor deallocates this
340    /// automatically allocated map, of course.
341    /// \return \c (*this)
342    FloydWarshall &predMap(PredMap &m) {
343      if(local_pred) {
344        delete _pred;
345        local_pred=false;
346      }
347      _pred = &m;
348      return *this;
349    }
350
351    /// \brief Sets the map storing the distances calculated by the algorithm.
352    ///
353    /// Sets the map storing the distances calculated by the algorithm.
354    /// If you don't use this function before calling \ref run(),
355    /// it will allocate one. The destuctor deallocates this
356    /// automatically allocated map, of course.
357    /// \return \c (*this)
358    FloydWarshall &distMap(DistMap &m) {
359      if(local_dist) {
360        delete _dist;
361        local_dist=false;
362      }
363      _dist = &m;
364      return *this;
365    }
366
367    ///\name Execution control
368    /// The simplest way to execute the algorithm is to use
369    /// one of the member functions called \c run(...).
370    /// \n
371    /// If you need more control on the execution,
372    /// Finally \ref start() will perform the actual path
373    /// computation.
374
375    ///@{
376
377    /// \brief Initializes the internal data structures.
378    ///
379    /// Initializes the internal data structures.
380    void init() {
381      create_maps();
382      for (NodeIt it(*graph); it != INVALID; ++it) {
383        for (NodeIt jt(*graph); jt != INVALID; ++jt) {
384          _pred->set(it, jt, INVALID);
385          _dist->set(it, jt, it == jt ?
386                     OperationTraits::zero() : OperationTraits::infinity());
387        }
388      }
389      for (EdgeIt it(*graph); it != INVALID; ++it) {
390        Node source = graph->source(it);
391        Node target = graph->target(it);       
392        if (OperationTraits::less((*length)[it], (*_dist)(source, target))) {
393          _dist->set(source, target, (*length)[it]);
394          _pred->set(source, target, it);
395        }
396      }
397    }
398   
399    /// \brief Executes the algorithm.
400    ///
401    /// This method runs the %FloydWarshall algorithm in order to compute
402    /// the shortest path to each node pairs. The algorithm
403    /// computes
404    /// - The shortest path tree for each node.
405    /// - The distance between each node pairs.
406    void start() {
407      for (NodeIt kt(*graph); kt != INVALID; ++kt) {
408        for (NodeIt it(*graph); it != INVALID; ++it) {
409          for (NodeIt jt(*graph); jt != INVALID; ++jt) {
410            Value relaxed = OperationTraits::plus((*_dist)(it, kt),
411                                                  (*_dist)(kt, jt));
412            if (OperationTraits::less(relaxed, (*_dist)(it, jt))) {
413              _dist->set(it, jt, relaxed);
414              _pred->set(it, jt, (*_pred)(kt, jt));
415            }
416          }
417        }
418      }
419    }
420   
421    /// \brief Runs %FloydWarshall algorithm.
422    ///   
423    /// This method runs the %FloydWarshall algorithm from a each node
424    /// in order to compute the shortest path to each node pairs.
425    /// The algorithm computes
426    /// - The shortest path tree for each node.
427    /// - The distance between each node pairs.
428    ///
429    /// \note d.run(s) is just a shortcut of the following code.
430    /// \code
431    ///  d.init();
432    ///  d.start();
433    /// \endcode
434    void run() {
435      init();
436      start();
437    }
438   
439    ///@}
440
441    /// \name Query Functions
442    /// The result of the %FloydWarshall algorithm can be obtained using these
443    /// functions.\n
444    /// Before the use of these functions,
445    /// either run() or start() must be called.
446   
447    ///@{
448
449    /// \brief Copies the shortest path to \c t into \c p
450    ///   
451    /// This function copies the shortest path to \c t into \c p.
452    /// If it \c t is a source itself or unreachable, then it does not
453    /// alter \c p.
454    /// \todo Is it the right way to handle unreachable nodes?
455    /// \return Returns \c true if a path to \c t was actually copied to \c p,
456    /// \c false otherwise.
457    /// \sa DirPath
458    template <typename Path>
459    bool getPath(Path &p, Node source, Node target) {
460      if (connected(source, target)) {
461        p.clear();
462        typename Path::Builder b(target);
463        for(b.setStartNode(target); pred(source, target) != INVALID;
464            target = predNode(target)) {
465          b.pushFront(pred(source, target));
466        }
467        b.commit();
468        return true;
469      }
470      return false;
471    }
472         
473    /// \brief The distance between two nodes.
474    ///
475    /// Returns the distance between two nodes.
476    /// \pre \ref run() must be called before using this function.
477    /// \warning If node \c v in unreachable from the root the return value
478    /// of this funcion is undefined.
479    Value dist(Node source, Node target) const {
480      return (*_dist)(source, target);
481    }
482
483    /// \brief Returns the 'previous edge' of the shortest path tree.
484    ///
485    /// For the node \c node it returns the 'previous edge' of the shortest
486    /// path tree to direction of the node \c root
487    /// i.e. it returns the last edge of a shortest path from the node \c root
488    /// to \c node. It is \ref INVALID if \c node is unreachable from the root
489    /// or if \c node=root. The shortest path tree used here is equal to the
490    /// shortest path tree used in \ref predNode().
491    /// \pre \ref run() must be called before using this function.
492    /// \todo predEdge could be a better name.
493    Edge pred(Node root, Node node) const {
494      return (*_pred)(root, node);
495    }
496
497    /// \brief Returns the 'previous node' of the shortest path tree.
498    ///
499    /// For a node \c node it returns the 'previous node' of the shortest path
500    /// tree to direction of the node \c root, i.e. it returns the last but
501    /// one node from a shortest path from the \c root to \c node. It is
502    /// INVALID if \c node is unreachable from the root or if \c node=root.
503    /// The shortest path tree used here is equal to the
504    /// shortest path tree used in \ref pred(). 
505    /// \pre \ref run() must be called before using this function.
506    Node predNode(Node root, Node node) const {
507      return (*_pred)(root, node) == INVALID ?
508      INVALID : graph->source((*_pred)(root, node));
509    }
510   
511    /// \brief Returns a reference to the matrix node map of distances.
512    ///
513    /// Returns a reference to the matrix node map of distances.
514    ///
515    /// \pre \ref run() must be called before using this function.
516    const DistMap &distMap() const { return *_dist;}
517 
518    /// \brief Returns a reference to the shortest path tree map.
519    ///
520    /// Returns a reference to the matrix node map of the edges of the
521    /// shortest path tree.
522    /// \pre \ref run() must be called before using this function.
523    const PredMap &predMap() const { return *_pred;}
524 
525    /// \brief Checks if a node is reachable from the root.
526    ///
527    /// Returns \c true if \c v is reachable from the root.
528    /// \pre \ref run() must be called before using this function.
529    ///
530    bool connected(Node source, Node target) {
531      return (*_dist)(source, target) != OperationTraits::infinity();
532    }
533   
534    ///@}
535  };
536 
537} //END OF NAMESPACE LEMON
538
539#endif
540
Note: See TracBrowser for help on using the repository browser.