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