# source:lemon-0.x/lemon/bellman_ford.h@2408:467ca6d16556

Last change on this file since 2408:467ca6d16556 was 2408:467ca6d16556, checked in by Alpar Juttner, 13 years ago

Doc improvements contributed by Peter Kovacs.

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