COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bellman_ford.h @ 696:c9b9da1a90a0

Last change on this file since 696:c9b9da1a90a0 was 696:c9b9da1a90a0, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Port Bellman-Ford algorithm from SVN -r3524 (#51)

File size: 35.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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_BELMANN_FORD_H
20#define LEMON_BELMANN_FORD_H
21
22/// \ingroup shortest_path
23/// \file
24/// \brief Bellman-Ford algorithm.
25///
26
27#include <lemon/bits/path_dump.h>
28#include <lemon/core.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 BellmanFord algorithm class.
37  /// 
38  /// It defines all computational operations and constants which are
39  /// used in the Bellman-Ford 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 BellmanFordDefaultOperationTraits {
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 BellmanFordDefaultOperationTraits<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 BellmanFord class.
83  ///
84  /// Default traits class of BellmanFord class.
85  /// \param _Digraph Digraph type.
86  /// \param _LegthMap Type of length map.
87  template<class _Digraph, class _LengthMap>
88  struct BellmanFordDefaultTraits {
89    /// The digraph type the algorithm runs on.
90    typedef _Digraph Digraph;
91
92    /// \brief The type of the map that stores the arc lengths.
93    ///
94    /// The type of the map that stores the arc lengths.
95    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
96    typedef _LengthMap LengthMap;
97
98    // The type of the length of the arcs.
99    typedef typename _LengthMap::Value Value;
100
101    /// \brief Operation traits for Bellman-Ford algorithm.
102    ///
103    /// It defines the infinity type on the given Value type
104    /// and the used operation.
105    /// \see BellmanFordDefaultOperationTraits
106    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
107 
108    /// \brief The type of the map that stores the last arcs of the
109    /// shortest paths.
110    ///
111    /// The type of the map that stores the last
112    /// arcs of the shortest paths.
113    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
114    ///
115    typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;
116
117    /// \brief Instantiates a PredMap.
118    ///
119    /// This function instantiates a \ref PredMap.
120    /// \param digraph is the digraph, to which we would like to define the PredMap.
121    static PredMap *createPredMap(const _Digraph& digraph) {
122      return new PredMap(digraph);
123    }
124
125    /// \brief The type of the map that stores the dists of the nodes.
126    ///
127    /// The type of the map that stores the dists of the nodes.
128    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
129    ///
130    typedef typename Digraph::template NodeMap<typename _LengthMap::Value>
131    DistMap;
132
133    /// \brief Instantiates a DistMap.
134    ///
135    /// This function instantiates a \ref DistMap.
136    /// \param digraph is the digraph, to which we would like to define the
137    /// \ref DistMap
138    static DistMap *createDistMap(const _Digraph& digraph) {
139      return new DistMap(digraph);
140    }
141
142  };
143 
144  /// \brief %BellmanFord algorithm class.
145  ///
146  /// \ingroup shortest_path
147  /// This class provides an efficient implementation of \c Bellman-Ford
148  /// algorithm. The arc lengths are passed to the algorithm using a
149  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
150  /// kind of length.
151  ///
152  /// The Bellman-Ford algorithm solves the shortest path from one node
153  /// problem when the arcs can have negative length but the digraph should
154  /// not contain cycles with negative sum of length. If we can assume
155  /// that all arc is non-negative in the digraph then the dijkstra algorithm
156  /// should be used rather.
157  ///
158  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
159  ///
160  /// The type of the length is determined by the
161  /// \ref concepts::ReadMap::Value "Value" of the length map.
162  ///
163  /// \param _Digraph The digraph type the algorithm runs on. The default value
164  /// is \ref ListDigraph. The value of _Digraph is not used directly by
165  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
166  /// \param _LengthMap This read-only ArcMap determines the lengths of the
167  /// arcs. The default map type is \ref concepts::Digraph::ArcMap
168  /// "Digraph::ArcMap<int>".  The value of _LengthMap is not used directly
169  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 
170  /// \param _Traits Traits class to set various data types used by the
171  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
172  /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>".  See \ref
173  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
174  /// class.
175#ifdef DOXYGEN
176  template <typename _Digraph, typename _LengthMap, typename _Traits>
177#else
178  template <typename _Digraph,
179            typename _LengthMap=typename _Digraph::template ArcMap<int>,
180            typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >
181#endif
182  class BellmanFord {
183  public:
184
185    typedef _Traits Traits;
186    ///The type of the underlying digraph.
187    typedef typename _Traits::Digraph Digraph;
188
189    typedef typename Digraph::Node Node;
190    typedef typename Digraph::NodeIt NodeIt;
191    typedef typename Digraph::Arc Arc;
192    typedef typename Digraph::OutArcIt OutArcIt;
193   
194    /// \brief The type of the length of the arcs.
195    typedef typename _Traits::LengthMap::Value Value;
196    /// \brief The type of the map that stores the arc lengths.
197    typedef typename _Traits::LengthMap LengthMap;
198    /// \brief The type of the map that stores the last
199    /// arcs of the shortest paths.
200    typedef typename _Traits::PredMap PredMap;
201    /// \brief The type of the map that stores the dists of the nodes.
202    typedef typename _Traits::DistMap DistMap;
203    /// \brief The operation traits.
204    typedef typename _Traits::OperationTraits OperationTraits;
205  private:
206    /// Pointer to the underlying digraph.
207    const Digraph *digraph;
208    /// Pointer to the length map
209    const LengthMap *length;
210    ///Pointer to the map of predecessors arcs.
211    PredMap *_pred;
212    ///Indicates if \ref _pred is locally allocated (\c true) or not.
213    bool local_pred;
214    ///Pointer to the map of distances.
215    DistMap *_dist;
216    ///Indicates if \ref _dist is locally allocated (\c true) or not.
217    bool local_dist;
218
219    typedef typename Digraph::template NodeMap<bool> MaskMap;
220    MaskMap *_mask;
221
222    std::vector<Node> _process;
223
224    /// Creates the maps if necessary.
225    void create_maps() {
226      if(!_pred) {
227        local_pred = true;
228        _pred = Traits::createPredMap(*digraph);
229      }
230      if(!_dist) {
231        local_dist = true;
232        _dist = Traits::createDistMap(*digraph);
233      }
234      _mask = new MaskMap(*digraph, false);
235    }
236   
237  public :
238 
239    typedef BellmanFord Create;
240
241    /// \name Named template parameters
242
243    ///@{
244
245    template <class T>
246    struct DefPredMapTraits : public Traits {
247      typedef T PredMap;
248      static PredMap *createPredMap(const Digraph&) {
249        LEMON_ASSERT(false, "PredMap is not initialized");
250        return 0; // ignore warnings
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    struct SetPredMap
260      : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {
261      typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;
262    };
263   
264    template <class T>
265    struct DefDistMapTraits : public Traits {
266      typedef T DistMap;
267      static DistMap *createDistMap(const Digraph&) {
268        LEMON_ASSERT(false, "DistMap is not initialized");
269        return 0; // ignore warnings
270      }
271    };
272
273    /// \brief \ref named-templ-param "Named parameter" for setting DistMap
274    /// type
275    ///
276    /// \ref named-templ-param "Named parameter" for setting DistMap type
277    ///
278    template <class T>
279    struct SetDistMap
280      : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {
281      typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;
282    };
283   
284    template <class T>
285    struct DefOperationTraitsTraits : public Traits {
286      typedef T OperationTraits;
287    };
288   
289    /// \brief \ref named-templ-param "Named parameter" for setting
290    /// OperationTraits type
291    ///
292    /// \ref named-templ-param "Named parameter" for setting OperationTraits
293    /// type
294    template <class T>
295    struct SetOperationTraits
296      : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {
297      typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >
298      Create;
299    };
300   
301    ///@}
302
303  protected:
304   
305    BellmanFord() {}
306
307  public:     
308   
309    /// \brief Constructor.
310    ///
311    /// \param _graph the digraph the algorithm will run on.
312    /// \param _length the length map used by the algorithm.
313    BellmanFord(const Digraph& _graph, const LengthMap& _length) :
314      digraph(&_graph), length(&_length),
315      _pred(0), local_pred(false),
316      _dist(0), local_dist(false), _mask(0) {}
317   
318    ///Destructor.
319    ~BellmanFord() {
320      if(local_pred) delete _pred;
321      if(local_dist) delete _dist;
322      if(_mask) delete _mask;
323    }
324
325    /// \brief Sets the length map.
326    ///
327    /// Sets the length map.
328    /// \return \c (*this)
329    BellmanFord &lengthMap(const LengthMap &m) {
330      length = &m;
331      return *this;
332    }
333
334    /// \brief Sets the map storing the predecessor arcs.
335    ///
336    /// Sets the map storing the predecessor arcs.
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    BellmanFord &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    BellmanFord &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    /// first you must call \ref init(), then you can add several source nodes
372    /// with \ref addSource().
373    /// Finally \ref start() will perform the actual path
374    /// computation.
375
376    ///@{
377
378    /// \brief Initializes the internal data structures.
379    ///
380    /// Initializes the internal data structures.
381    void init(const Value value = OperationTraits::infinity()) {
382      create_maps();
383      for (NodeIt it(*digraph); it != INVALID; ++it) {
384        _pred->set(it, INVALID);
385        _dist->set(it, value);
386      }
387      _process.clear();
388      if (OperationTraits::less(value, OperationTraits::infinity())) {
389        for (NodeIt it(*digraph); it != INVALID; ++it) {
390          _process.push_back(it);
391          _mask->set(it, true);
392        }
393      }
394    }
395   
396    /// \brief Adds a new source node.
397    ///
398    /// Adds a new source node. The optional second parameter is the
399    /// initial distance of the node. It just sets the distance of the
400    /// node to the given value.
401    void addSource(Node source, Value dst = OperationTraits::zero()) {
402      _dist->set(source, dst);
403      if (!(*_mask)[source]) {
404        _process.push_back(source);
405        _mask->set(source, true);
406      }
407    }
408
409    /// \brief Executes one round from the Bellman-Ford algorithm.
410    ///
411    /// If the algoritm calculated the distances in the previous round
412    /// exactly for all at most \f$ k \f$ length path lengths then it will
413    /// calculate the distances exactly for all at most \f$ k + 1 \f$
414    /// length path lengths. With \f$ k \f$ iteration this function
415    /// calculates the at most \f$ k \f$ length path lengths.
416    ///
417    /// \warning The paths with limited arc number cannot be retrieved
418    /// easily with \ref path() or \ref predArc() functions. If you
419    /// need the shortest path and not just the distance you should store
420    /// after each iteration the \ref predMap() map and manually build
421    /// the path.
422    ///
423    /// \return \c true when the algorithm have not found more shorter
424    /// paths.
425    bool processNextRound() {
426      for (int i = 0; i < int(_process.size()); ++i) {
427        _mask->set(_process[i], false);
428      }
429      std::vector<Node> nextProcess;
430      std::vector<Value> values(_process.size());
431      for (int i = 0; i < int(_process.size()); ++i) {
432        values[i] = (*_dist)[_process[i]];
433      }
434      for (int i = 0; i < int(_process.size()); ++i) {
435        for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
436          Node target = digraph->target(it);
437          Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
438          if (OperationTraits::less(relaxed, (*_dist)[target])) {
439            _pred->set(target, it);
440            _dist->set(target, relaxed);
441            if (!(*_mask)[target]) {
442              _mask->set(target, true);
443              nextProcess.push_back(target);
444            }
445          }       
446        }
447      }
448      _process.swap(nextProcess);
449      return _process.empty();
450    }
451
452    /// \brief Executes one weak round from the Bellman-Ford algorithm.
453    ///
454    /// If the algorithm calculated the distances in the
455    /// previous round at least for all at most k length paths then it will
456    /// calculate the distances at least for all at most k + 1 length paths.
457    /// This function does not make it possible to calculate strictly the
458    /// at most k length minimal paths, this is why it is
459    /// called just weak round.
460    /// \return \c true when the algorithm have not found more shorter paths.
461    bool processNextWeakRound() {
462      for (int i = 0; i < int(_process.size()); ++i) {
463        _mask->set(_process[i], false);
464      }
465      std::vector<Node> nextProcess;
466      for (int i = 0; i < int(_process.size()); ++i) {
467        for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
468          Node target = digraph->target(it);
469          Value relaxed =
470            OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
471          if (OperationTraits::less(relaxed, (*_dist)[target])) {
472            _pred->set(target, it);
473            _dist->set(target, relaxed);
474            if (!(*_mask)[target]) {
475              _mask->set(target, true);
476              nextProcess.push_back(target);
477            }
478          }       
479        }
480      }
481      _process.swap(nextProcess);
482      return _process.empty();
483    }
484
485    /// \brief Executes the algorithm.
486    ///
487    /// \pre init() must be called and at least one node should be added
488    /// with addSource() before using this function.
489    ///
490    /// This method runs the %BellmanFord algorithm from the root node(s)
491    /// in order to compute the shortest path to each node. The algorithm
492    /// computes
493    /// - The shortest path tree.
494    /// - The distance of each node from the root(s).
495    void start() {
496      int num = countNodes(*digraph) - 1;
497      for (int i = 0; i < num; ++i) {
498        if (processNextWeakRound()) break;
499      }
500    }
501
502    /// \brief Executes the algorithm and checks the negative cycles.
503    ///
504    /// \pre init() must be called and at least one node should be added
505    /// with addSource() before using this function.
506    ///
507    /// This method runs the %BellmanFord algorithm from the root node(s)
508    /// in order to compute the shortest path to each node. The algorithm
509    /// computes
510    /// - The shortest path tree.
511    /// - The distance of each node from the root(s).
512    ///
513    /// \return \c false if there is a negative cycle in the digraph.
514    bool checkedStart() {
515      int num = countNodes(*digraph);
516      for (int i = 0; i < num; ++i) {
517        if (processNextWeakRound()) return true;
518      }
519      return _process.empty();
520    }
521
522    /// \brief Executes the algorithm with path length limit.
523    ///
524    /// \pre init() must be called and at least one node should be added
525    /// with addSource() before using this function.
526    ///
527    /// This method runs the %BellmanFord algorithm from the root
528    /// node(s) in order to compute the shortest path lengths with at
529    /// most \c num arc.
530    ///
531    /// \warning The paths with limited arc number cannot be retrieved
532    /// easily with \ref path() or \ref predArc() functions. If you
533    /// need the shortest path and not just the distance you should store
534    /// after each iteration the \ref predMap() map and manually build
535    /// the path.
536    ///
537    /// The algorithm computes
538    /// - The predecessor arc from each node.
539    /// - The limited distance of each node from the root(s).
540    void limitedStart(int num) {
541      for (int i = 0; i < num; ++i) {
542        if (processNextRound()) break;
543      }
544    }
545   
546    /// \brief Runs %BellmanFord algorithm from node \c s.
547    ///   
548    /// This method runs the %BellmanFord algorithm from a root node \c s
549    /// in order to compute the shortest path to each node. The algorithm
550    /// computes
551    /// - The shortest path tree.
552    /// - The distance of each node from the root.
553    ///
554    /// \note d.run(s) is just a shortcut of the following code.
555    ///\code
556    ///  d.init();
557    ///  d.addSource(s);
558    ///  d.start();
559    ///\endcode
560    void run(Node s) {
561      init();
562      addSource(s);
563      start();
564    }
565   
566    /// \brief Runs %BellmanFord algorithm with limited path length
567    /// from node \c s.
568    ///   
569    /// This method runs the %BellmanFord algorithm from a root node \c s
570    /// in order to compute the shortest path with at most \c len arcs
571    /// to each node. The algorithm computes
572    /// - The shortest path tree.
573    /// - The distance of each node from the root.
574    ///
575    /// \note d.run(s, num) is just a shortcut of the following code.
576    ///\code
577    ///  d.init();
578    ///  d.addSource(s);
579    ///  d.limitedStart(num);
580    ///\endcode
581    void run(Node s, int num) {
582      init();
583      addSource(s);
584      limitedStart(num);
585    }
586   
587    ///@}
588
589    /// \name Query Functions
590    /// The result of the %BellmanFord algorithm can be obtained using these
591    /// functions.\n
592    /// Before the use of these functions,
593    /// either run() or start() must be called.
594   
595    ///@{
596
597    /// \brief Lemon iterator for get the active nodes.
598    ///
599    /// Lemon iterator for get the active nodes. This class provides a
600    /// common style lemon iterator which gives back a subset of the
601    /// nodes. The iterated nodes are active in the algorithm after
602    /// the last phase so these should be checked in the next phase to
603    /// find augmenting arcs from these.
604    class ActiveIt {
605    public:
606
607      /// \brief Constructor.
608      ///
609      /// Constructor for get the nodeset of the variable.
610      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
611      {
612        _index = _algorithm->_process.size() - 1;
613      }
614
615      /// \brief Invalid constructor.
616      ///
617      /// Invalid constructor.
618      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
619
620      /// \brief Conversion to node.
621      ///
622      /// Conversion to node.
623      operator Node() const {
624        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
625      }
626
627      /// \brief Increment operator.
628      ///
629      /// Increment operator.
630      ActiveIt& operator++() {
631        --_index;
632        return *this;
633      }
634
635      bool operator==(const ActiveIt& it) const {
636        return static_cast<Node>(*this) == static_cast<Node>(it);
637      }
638      bool operator!=(const ActiveIt& it) const {
639        return static_cast<Node>(*this) != static_cast<Node>(it);
640      }
641      bool operator<(const ActiveIt& it) const {
642        return static_cast<Node>(*this) < static_cast<Node>(it);
643      }
644     
645    private:
646      const BellmanFord* _algorithm;
647      int _index;
648    };
649
650    typedef PredMapPath<Digraph, PredMap> Path;
651
652    /// \brief Gives back the shortest path.
653    ///   
654    /// Gives back the shortest path.
655    /// \pre The \c t should be reachable from the source.
656    Path path(Node t)
657    {
658      return Path(*digraph, *_pred, t);
659    }
660
661
662    // TODO : implement negative cycle
663//     /// \brief Gives back a negative cycle.
664//     ///   
665//     /// This function gives back a negative cycle.
666//     /// If the algorithm have not found yet negative cycle it will give back
667//     /// an empty path.
668//     Path negativeCycle() {
669//       typename Digraph::template NodeMap<int> state(*digraph, 0);
670//       for (ActiveIt it(*this); it != INVALID; ++it) {
671//         if (state[it] == 0) {
672//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
673//             if (state[t] == 0) {
674//               state[t] = 1;
675//             } else if (state[t] == 2) {
676//               break;
677//             } else {
678//               p.clear();
679//               typename Path::Builder b(p);
680//               b.setStartNode(t);
681//               b.pushFront(predArc(t));
682//               for(Node s = predNode(t); s != t; s = predNode(s)) {
683//                 b.pushFront(predArc(s));
684//               }
685//               b.commit();
686//               return true;
687//             }
688//           }
689//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
690//             if (state[t] == 1) {
691//               state[t] = 2;
692//             } else {
693//               break;
694//             }
695//           }
696//         }
697//       }
698//       return false;
699//     }
700         
701    /// \brief The distance of a node from the root.
702    ///
703    /// Returns the distance of a node from the root.
704    /// \pre \ref run() must be called before using this function.
705    /// \warning If node \c v in unreachable from the root the return value
706    /// of this funcion is undefined.
707    Value dist(Node v) const { return (*_dist)[v]; }
708
709    /// \brief Returns the 'previous arc' of the shortest path tree.
710    ///
711    /// For a node \c v it returns the 'previous arc' of the shortest path
712    /// tree, i.e. it returns the last arc of a shortest path from the root
713    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
714    /// if \c v=s. The shortest path tree used here is equal to the shortest
715    /// path tree used in \ref predNode().
716    /// \pre \ref run() must be called before using
717    /// this function.
718    Arc predArc(Node v) const { return (*_pred)[v]; }
719
720    /// \brief Returns the 'previous node' of the shortest path tree.
721    ///
722    /// For a node \c v it returns the 'previous node' of the shortest path
723    /// tree, i.e. it returns the last but one node from a shortest path from
724    /// the root to \c /v. It is INVALID if \c v is unreachable from the root
725    /// or if \c v=s. The shortest path tree used here is equal to the
726    /// shortest path tree used in \ref predArc().  \pre \ref run() must be
727    /// called before using this function.
728    Node predNode(Node v) const {
729      return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]);
730    }
731   
732    /// \brief Returns a reference to the NodeMap of distances.
733    ///
734    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
735    /// be called before using this function.
736    const DistMap &distMap() const { return *_dist;}
737 
738    /// \brief Returns a reference to the shortest path tree map.
739    ///
740    /// Returns a reference to the NodeMap of the arcs of the
741    /// shortest path tree.
742    /// \pre \ref run() must be called before using this function.
743    const PredMap &predMap() const { return *_pred; }
744 
745    /// \brief Checks if a node is reachable from the root.
746    ///
747    /// Returns \c true if \c v is reachable from the root.
748    /// \pre \ref run() must be called before using this function.
749    ///
750    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
751   
752    ///@}
753  };
754 
755  /// \brief Default traits class of BellmanFord function.
756  ///
757  /// Default traits class of BellmanFord function.
758  /// \param _Digraph Digraph type.
759  /// \param _LengthMap Type of length map.
760  template <typename _Digraph, typename _LengthMap>
761  struct BellmanFordWizardDefaultTraits {
762    /// \brief The digraph type the algorithm runs on.
763    typedef _Digraph Digraph;
764
765    /// \brief The type of the map that stores the arc lengths.
766    ///
767    /// The type of the map that stores the arc lengths.
768    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
769    typedef _LengthMap LengthMap;
770
771    /// \brief The value type of the length map.
772    typedef typename _LengthMap::Value Value;
773
774    /// \brief Operation traits for Bellman-Ford algorithm.
775    ///
776    /// It defines the infinity type on the given Value type
777    /// and the used operation.
778    /// \see BellmanFordDefaultOperationTraits
779    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
780
781    /// \brief The type of the map that stores the last
782    /// arcs of the shortest paths.
783    ///
784    /// The type of the map that stores the last
785    /// arcs of the shortest paths.
786    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
787    typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;
788
789    /// \brief Instantiates a PredMap.
790    ///
791    /// This function instantiates a \ref PredMap.
792    static PredMap *createPredMap(const _Digraph &) {
793      return new PredMap();
794    }
795    /// \brief The type of the map that stores the dists of the nodes.
796    ///
797    /// The type of the map that stores the dists of the nodes.
798    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
799    typedef NullMap<typename Digraph::Node, Value> DistMap;
800    /// \brief Instantiates a DistMap.
801    ///
802    /// This function instantiates a \ref DistMap.
803    static DistMap *createDistMap(const _Digraph &) {
804      return new DistMap();
805    }
806  };
807 
808  /// \brief Default traits used by \ref BellmanFordWizard
809  ///
810  /// To make it easier to use BellmanFord algorithm
811  /// we have created a wizard class.
812  /// This \ref BellmanFordWizard class needs default traits,
813  /// as well as the \ref BellmanFord class.
814  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
815  /// \ref BellmanFordWizard class.
816  /// \todo More named parameters are required...
817  template<class _Digraph,class _LengthMap>
818  class BellmanFordWizardBase
819    : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {
820
821    typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;
822  protected:
823    /// Type of the nodes in the digraph.
824    typedef typename Base::Digraph::Node Node;
825
826    /// Pointer to the underlying digraph.
827    void *_graph;
828    /// Pointer to the length map
829    void *_length;
830    ///Pointer to the map of predecessors arcs.
831    void *_pred;
832    ///Pointer to the map of distances.
833    void *_dist;
834    ///Pointer to the source node.
835    Node _source;
836
837    public:
838    /// Constructor.
839   
840    /// This constructor does not require parameters, therefore it initiates
841    /// all of the attributes to default values (0, INVALID).
842    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
843                           _dist(0), _source(INVALID) {}
844
845    /// Constructor.
846   
847    /// This constructor requires some parameters,
848    /// listed in the parameters list.
849    /// Others are initiated to 0.
850    /// \param digraph is the initial value of  \ref _graph
851    /// \param length is the initial value of  \ref _length
852    /// \param source is the initial value of  \ref _source
853    BellmanFordWizardBase(const _Digraph& digraph,
854                          const _LengthMap& length,
855                          Node source = INVALID) :
856      _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))),
857      _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))),
858      _pred(0), _dist(0), _source(source) {}
859
860  };
861 
862  /// A class to make the usage of BellmanFord algorithm easier
863
864  /// This class is created to make it easier to use BellmanFord algorithm.
865  /// It uses the functions and features of the plain \ref BellmanFord,
866  /// but it is much simpler to use it.
867  ///
868  /// Simplicity means that the way to change the types defined
869  /// in the traits class is based on functions that returns the new class
870  /// and not on templatable built-in classes.
871  /// When using the plain \ref BellmanFord
872  /// the new class with the modified type comes from
873  /// the original class by using the ::
874  /// operator. In the case of \ref BellmanFordWizard only
875  /// a function have to be called and it will
876  /// return the needed class.
877  ///
878  /// It does not have own \ref run method. When its \ref run method is called
879  /// it initiates a plain \ref BellmanFord class, and calls the \ref
880  /// BellmanFord::run method of it.
881  template<class _Traits>
882  class BellmanFordWizard : public _Traits {
883    typedef _Traits Base;
884
885    ///The type of the underlying digraph.
886    typedef typename _Traits::Digraph Digraph;
887
888    typedef typename Digraph::Node Node;
889    typedef typename Digraph::NodeIt NodeIt;
890    typedef typename Digraph::Arc Arc;
891    typedef typename Digraph::OutArcIt ArcIt;
892   
893    ///The type of the map that stores the arc lengths.
894    typedef typename _Traits::LengthMap LengthMap;
895
896    ///The type of the length of the arcs.
897    typedef typename LengthMap::Value Value;
898
899    ///\brief The type of the map that stores the last
900    ///arcs of the shortest paths.
901    typedef typename _Traits::PredMap PredMap;
902
903    ///The type of the map that stores the dists of the nodes.
904    typedef typename _Traits::DistMap DistMap;
905
906  public:
907    /// Constructor.
908    BellmanFordWizard() : _Traits() {}
909
910    /// \brief Constructor that requires parameters.
911    ///
912    /// Constructor that requires parameters.
913    /// These parameters will be the default values for the traits class.
914    BellmanFordWizard(const Digraph& digraph, const LengthMap& length,
915                      Node src = INVALID)
916      : _Traits(digraph, length, src) {}
917
918    /// \brief Copy constructor
919    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
920
921    ~BellmanFordWizard() {}
922
923    /// \brief Runs BellmanFord algorithm from a given node.
924    ///   
925    /// Runs BellmanFord algorithm from a given node.
926    /// The node can be given by the \ref source function.
927    void run() {
928      LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");
929      BellmanFord<Digraph,LengthMap,_Traits>
930        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
931           *reinterpret_cast<const LengthMap*>(Base::_length));
932      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
933      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
934      bf.run(Base::_source);
935    }
936
937    /// \brief Runs BellmanFord algorithm from the given node.
938    ///
939    /// Runs BellmanFord algorithm from the given node.
940    /// \param src is the given source.
941    void run(Node src) {
942      Base::_source = src;
943      run();
944    }
945
946    template<class T>
947    struct DefPredMapBase : public Base {
948      typedef T PredMap;
949      static PredMap *createPredMap(const Digraph &) { return 0; };
950      DefPredMapBase(const _Traits &b) : _Traits(b) {}
951    };
952   
953    ///\brief \ref named-templ-param "Named parameter"
954    ///function for setting PredMap type
955    ///
956    /// \ref named-templ-param "Named parameter"
957    ///function for setting PredMap type
958    ///
959    template<class T>
960    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
961    {
962      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
963      return BellmanFordWizard<DefPredMapBase<T> >(*this);
964    }
965   
966    template<class T>
967    struct DefDistMapBase : public Base {
968      typedef T DistMap;
969      static DistMap *createDistMap(const Digraph &) { return 0; };
970      DefDistMapBase(const _Traits &b) : _Traits(b) {}
971    };
972   
973    ///\brief \ref named-templ-param "Named parameter"
974    ///function for setting DistMap type
975    ///
976    /// \ref named-templ-param "Named parameter"
977    ///function for setting DistMap type
978    ///
979    template<class T>
980    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
981      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
982      return BellmanFordWizard<DefDistMapBase<T> >(*this);
983    }
984
985    template<class T>
986    struct DefOperationTraitsBase : public Base {
987      typedef T OperationTraits;
988      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
989    };
990   
991    ///\brief \ref named-templ-param "Named parameter"
992    ///function for setting OperationTraits type
993    ///
994    /// \ref named-templ-param "Named parameter"
995    ///function for setting OperationTraits type
996    ///
997    template<class T>
998    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
999      return BellmanFordWizard<DefDistMapBase<T> >(*this);
1000    }
1001   
1002    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
1003    ///
1004    /// Sets the source node, from which the BellmanFord algorithm runs.
1005    /// \param src is the source node.
1006    BellmanFordWizard<_Traits>& source(Node src) {
1007      Base::_source = src;
1008      return *this;
1009    }
1010   
1011  };
1012 
1013  /// \brief Function type interface for BellmanFord algorithm.
1014  ///
1015  /// \ingroup shortest_path
1016  /// Function type interface for BellmanFord algorithm.
1017  ///
1018  /// This function also has several \ref named-templ-func-param
1019  /// "named parameters", they are declared as the members of class
1020  /// \ref BellmanFordWizard.
1021  /// The following
1022  /// example shows how to use these parameters.
1023  ///\code
1024  /// bellmanford(g,length,source).predMap(preds).run();
1025  ///\endcode
1026  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1027  /// to the end of the parameter list.
1028  /// \sa BellmanFordWizard
1029  /// \sa BellmanFord
1030  template<class _Digraph, class _LengthMap>
1031  BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
1032  bellmanFord(const _Digraph& digraph,
1033              const _LengthMap& length,
1034              typename _Digraph::Node source = INVALID) {
1035    return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
1036      (digraph, length, source);
1037  }
1038
1039} //END OF NAMESPACE LEMON
1040
1041#endif
1042
Note: See TracBrowser for help on using the repository browser.