# source:lemon-0.x/lemon/bellman_ford.h@2552:5f711e4668f5

Last change on this file since 2552:5f711e4668f5 was 2517:d9cfac072869, checked in by Peter Kovacs, 12 years ago

Small changes in the documentation.

File size: 35.4 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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.
97    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
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),
331      _dist(0), local_dist(false), _mask(0) {}
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
387    /// with \ref addSource().
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);
418      if (!(*_mask)[source]) {
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 predMap() map and manually build
436    /// the path.
437    ///
438    /// \return \c 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);
456            if (!(*_mask)[target]) {
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 \c 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);
489            if (!(*_mask)[target]) {
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.
521    ///
522    /// This method runs the %BellmanFord algorithm from the root node(s)
523    /// in order to compute the shortest path to each node. The algorithm
524    /// computes
525    /// - The shortest path tree.
526    /// - The distance of each node from the root(s).
527    ///
528    /// \return \c false if there is a negative cycle in the graph.
529    bool checkedStart() {
530      int num = countNodes(*graph);
531      for (int i = 0; i < num; ++i) {
532        if (processNextWeakRound()) return true;
533      }
534      return _process.empty();
535    }
536
537    /// \brief Executes the algorithm with path length limit.
538    ///
539    /// \pre init() must be called and at least one node should be added
540    /// with addSource() before using this function.
541    ///
542    /// This method runs the %BellmanFord algorithm from the root
543    /// node(s) in order to compute the shortest path lengths with at
544    /// most \c num edge.
545    ///
546    /// \warning The paths with limited edge number cannot be retrieved
547    /// easily with \ref path() or \ref predEdge() functions. If you
548    /// need the shortest path and not just the distance you should store
549    /// after each iteration the \ref predMap() map and manually build
550    /// the path.
551    ///
552    /// The algorithm computes
553    /// - The predecessor edge from each node.
554    /// - The limited distance of each node from the root(s).
555    void limitedStart(int num) {
556      for (int i = 0; i < num; ++i) {
557        if (processNextRound()) break;
558      }
559    }
560
561    /// \brief Runs %BellmanFord algorithm from node \c s.
562    ///
563    /// This method runs the %BellmanFord algorithm from a root node \c s
564    /// in order to compute the shortest path to each node. The algorithm
565    /// computes
566    /// - The shortest path tree.
567    /// - The distance of each node from the root.
568    ///
569    /// \note d.run(s) is just a shortcut of the following code.
570    ///\code
571    ///  d.init();
573    ///  d.start();
574    ///\endcode
575    void run(Node s) {
576      init();
578      start();
579    }
580
581    /// \brief Runs %BellmanFord algorithm with limited path length
582    /// from node \c s.
583    ///
584    /// This method runs the %BellmanFord algorithm from a root node \c s
585    /// in order to compute the shortest path with at most \c len edges
586    /// to each node. The algorithm computes
587    /// - The shortest path tree.
588    /// - The distance of each node from the root.
589    ///
590    /// \note d.run(s, num) is just a shortcut of the following code.
591    ///\code
592    ///  d.init();
594    ///  d.limitedStart(num);
595    ///\endcode
596    void run(Node s, int num) {
597      init();
599      limitedStart(num);
600    }
601
602    ///@}
603
604    /// \name Query Functions
605    /// The result of the %BellmanFord algorithm can be obtained using these
606    /// functions.\n
607    /// Before the use of these functions,
608    /// either run() or start() must be called.
609
610    ///@{
611
612    /// \brief Lemon iterator for get the active nodes.
613    ///
614    /// Lemon iterator for get the active nodes. This class provides a
615    /// common style lemon iterator which gives back a subset of the
616    /// nodes. The iterated nodes are active in the algorithm after
617    /// the last phase so these should be checked in the next phase to
618    /// find augmenting edges from these.
619    class ActiveIt {
620    public:
621
622      /// \brief Constructor.
623      ///
624      /// Constructor for get the nodeset of the variable.
625      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
626      {
627        _index = _algorithm->_process.size() - 1;
628      }
629
630      /// \brief Invalid constructor.
631      ///
632      /// Invalid constructor.
633      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
634
635      /// \brief Conversion to node.
636      ///
637      /// Conversion to node.
638      operator Node() const {
639        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
640      }
641
642      /// \brief Increment operator.
643      ///
644      /// Increment operator.
645      ActiveIt& operator++() {
646        --_index;
647        return *this;
648      }
649
650      bool operator==(const ActiveIt& it) const {
651        return static_cast<Node>(*this) == static_cast<Node>(it);
652      }
653      bool operator!=(const ActiveIt& it) const {
654        return static_cast<Node>(*this) != static_cast<Node>(it);
655      }
656      bool operator<(const ActiveIt& it) const {
657        return static_cast<Node>(*this) < static_cast<Node>(it);
658      }
659
660    private:
661      const BellmanFord* _algorithm;
662      int _index;
663    };
664
665    typedef PredMapPath<Graph, PredMap> Path;
666
667    /// \brief Gives back the shortest path.
668    ///
669    /// Gives back the shortest path.
670    /// \pre The \c t should be reachable from the source.
671    Path path(Node t)
672    {
673      return Path(*graph, *_pred, t);
674    }
675
676
677    // TODO : implement negative cycle
678//     /// \brief Gives back a negative cycle.
679//     ///
680//     /// This function gives back a negative cycle.
681//     /// If the algorithm have not found yet negative cycle it will give back
682//     /// an empty path.
683//     Path negativeCycle() {
684//       typename Graph::template NodeMap<int> state(*graph, 0);
685//       for (ActiveIt it(*this); it != INVALID; ++it) {
686//         if (state[it] == 0) {
687//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
688//             if (state[t] == 0) {
689//               state[t] = 1;
690//             } else if (state[t] == 2) {
691//               break;
692//             } else {
693//               p.clear();
694//               typename Path::Builder b(p);
695//               b.setStartNode(t);
696//               b.pushFront(predEdge(t));
697//               for(Node s = predNode(t); s != t; s = predNode(s)) {
698//                 b.pushFront(predEdge(s));
699//               }
700//               b.commit();
701//               return true;
702//             }
703//           }
704//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
705//             if (state[t] == 1) {
706//               state[t] = 2;
707//             } else {
708//               break;
709//             }
710//           }
711//         }
712//       }
713//       return false;
714//     }
715
716    /// \brief The distance of a node from the root.
717    ///
718    /// Returns the distance of a node from the root.
719    /// \pre \ref run() must be called before using this function.
720    /// \warning If node \c v in unreachable from the root the return value
721    /// of this funcion is undefined.
722    Value dist(Node v) const { return (*_dist)[v]; }
723
724    /// \brief Returns the 'previous edge' of the shortest path tree.
725    ///
726    /// For a node \c v it returns the 'previous edge' of the shortest path
727    /// tree, i.e. it returns the last edge of a shortest path from the root
728    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
729    /// if \c v=s. The shortest path tree used here is equal to the shortest
730    /// path tree used in \ref predNode().
731    /// \pre \ref run() must be called before using
732    /// this function.
733    Edge predEdge(Node v) const { return (*_pred)[v]; }
734
735    /// \brief Returns the 'previous node' of the shortest path tree.
736    ///
737    /// For a node \c v it returns the 'previous node' of the shortest path
738    /// tree, i.e. it returns the last but one node from a shortest path from
739    /// the root to \c /v. It is INVALID if \c v is unreachable from the root
740    /// or if \c v=s. The shortest path tree used here is equal to the
741    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be
742    /// called before using this function.
743    Node predNode(Node v) const {
744      return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
745    }
746
747    /// \brief Returns a reference to the NodeMap of distances.
748    ///
749    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
750    /// be called before using this function.
751    const DistMap &distMap() const { return *_dist;}
752
753    /// \brief Returns a reference to the shortest path tree map.
754    ///
755    /// Returns a reference to the NodeMap of the edges of the
756    /// shortest path tree.
757    /// \pre \ref run() must be called before using this function.
758    const PredMap &predMap() const { return *_pred; }
759
760    /// \brief Checks if a node is reachable from the root.
761    ///
762    /// Returns \c true if \c v is reachable from the root.
763    /// \pre \ref run() must be called before using this function.
764    ///
765    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
766
767    ///@}
768  };
769
770  /// \brief Default traits class of BellmanFord function.
771  ///
772  /// Default traits class of BellmanFord function.
773  /// \param _Graph Graph type.
774  /// \param _LengthMap Type of length map.
775  template <typename _Graph, typename _LengthMap>
776  struct BellmanFordWizardDefaultTraits {
777    /// \brief The graph type the algorithm runs on.
778    typedef _Graph Graph;
779
780    /// \brief The type of the map that stores the edge lengths.
781    ///
782    /// The type of the map that stores the edge lengths.
783    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
784    typedef _LengthMap LengthMap;
785
786    /// \brief The value type of the length map.
787    typedef typename _LengthMap::Value Value;
788
789    /// \brief Operation traits for Bellman-Ford algorithm.
790    ///
791    /// It defines the infinity type on the given Value type
792    /// and the used operation.
793    /// \see BellmanFordDefaultOperationTraits
794    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
795
796    /// \brief The type of the map that stores the last
797    /// edges of the shortest paths.
798    ///
799    /// The type of the map that stores the last
800    /// edges of the shortest paths.
801    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
802    typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
803
804    /// \brief Instantiates a PredMap.
805    ///
806    /// This function instantiates a \ref PredMap.
807    static PredMap *createPredMap(const _Graph &) {
808      return new PredMap();
809    }
810    /// \brief The type of the map that stores the dists of the nodes.
811    ///
812    /// The type of the map that stores the dists of the nodes.
813    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
814    typedef NullMap<typename Graph::Node, Value> DistMap;
815    /// \brief Instantiates a DistMap.
816    ///
817    /// This function instantiates a \ref DistMap.
818    static DistMap *createDistMap(const _Graph &) {
819      return new DistMap();
820    }
821  };
822
823  /// \brief Default traits used by \ref BellmanFordWizard
824  ///
825  /// To make it easier to use BellmanFord algorithm
826  /// we have created a wizard class.
827  /// This \ref BellmanFordWizard class needs default traits,
828  /// as well as the \ref BellmanFord class.
829  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
830  /// \ref BellmanFordWizard class.
831  /// \todo More named parameters are required...
832  template<class _Graph,class _LengthMap>
833  class BellmanFordWizardBase
834    : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
835
836    typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
837  protected:
838    /// Type of the nodes in the graph.
839    typedef typename Base::Graph::Node Node;
840
841    /// Pointer to the underlying graph.
842    void *_graph;
843    /// Pointer to the length map
844    void *_length;
845    ///Pointer to the map of predecessors edges.
846    void *_pred;
847    ///Pointer to the map of distances.
848    void *_dist;
849    ///Pointer to the source node.
850    Node _source;
851
852    public:
853    /// Constructor.
854
855    /// This constructor does not require parameters, therefore it initiates
856    /// all of the attributes to default values (0, INVALID).
857    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
858                           _dist(0), _source(INVALID) {}
859
860    /// Constructor.
861
862    /// This constructor requires some parameters,
863    /// listed in the parameters list.
864    /// Others are initiated to 0.
865    /// \param graph is the initial value of  \ref _graph
866    /// \param length is the initial value of  \ref _length
867    /// \param source is the initial value of  \ref _source
868    BellmanFordWizardBase(const _Graph& graph,
869                          const _LengthMap& length,
870                          Node source = INVALID) :
871      _graph(reinterpret_cast<void*>(const_cast<_Graph*>(&graph))),
872      _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))),
873      _pred(0), _dist(0), _source(source) {}
874
875  };
876
877  /// A class to make the usage of BellmanFord algorithm easier
878
879  /// This class is created to make it easier to use BellmanFord algorithm.
880  /// It uses the functions and features of the plain \ref BellmanFord,
881  /// but it is much simpler to use it.
882  ///
883  /// Simplicity means that the way to change the types defined
884  /// in the traits class is based on functions that returns the new class
885  /// and not on templatable built-in classes.
886  /// When using the plain \ref BellmanFord
887  /// the new class with the modified type comes from
888  /// the original class by using the ::
889  /// operator. In the case of \ref BellmanFordWizard only
890  /// a function have to be called and it will
891  /// return the needed class.
892  ///
893  /// It does not have own \ref run method. When its \ref run method is called
894  /// it initiates a plain \ref BellmanFord class, and calls the \ref
895  /// BellmanFord::run method of it.
896  template<class _Traits>
897  class BellmanFordWizard : public _Traits {
898    typedef _Traits Base;
899
900    ///The type of the underlying graph.
901    typedef typename _Traits::Graph Graph;
902
903    typedef typename Graph::Node Node;
904    typedef typename Graph::NodeIt NodeIt;
905    typedef typename Graph::Edge Edge;
906    typedef typename Graph::OutEdgeIt EdgeIt;
907
908    ///The type of the map that stores the edge lengths.
909    typedef typename _Traits::LengthMap LengthMap;
910
911    ///The type of the length of the edges.
912    typedef typename LengthMap::Value Value;
913
914    ///\brief The type of the map that stores the last
915    ///edges of the shortest paths.
916    typedef typename _Traits::PredMap PredMap;
917
918    ///The type of the map that stores the dists of the nodes.
919    typedef typename _Traits::DistMap DistMap;
920
921  public:
922    /// Constructor.
923    BellmanFordWizard() : _Traits() {}
924
925    /// \brief Constructor that requires parameters.
926    ///
927    /// Constructor that requires parameters.
928    /// These parameters will be the default values for the traits class.
929    BellmanFordWizard(const Graph& graph, const LengthMap& length,
930                      Node src = INVALID)
931      : _Traits(graph, length, src) {}
932
933    /// \brief Copy constructor
934    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
935
936    ~BellmanFordWizard() {}
937
938    /// \brief Runs BellmanFord algorithm from a given node.
939    ///
940    /// Runs BellmanFord algorithm from a given node.
941    /// The node can be given by the \ref source function.
942    void run() {
943      if(Base::_source == INVALID) throw UninitializedParameter();
944      BellmanFord<Graph,LengthMap,_Traits>
945        bf(*reinterpret_cast<const Graph*>(Base::_graph),
946           *reinterpret_cast<const LengthMap*>(Base::_length));
947      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
948      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
949      bf.run(Base::_source);
950    }
951
952    /// \brief Runs BellmanFord algorithm from the given node.
953    ///
954    /// Runs BellmanFord algorithm from the given node.
955    /// \param src is the given source.
956    void run(Node src) {
957      Base::_source = src;
958      run();
959    }
960
961    template<class T>
962    struct DefPredMapBase : public Base {
963      typedef T PredMap;
964      static PredMap *createPredMap(const Graph &) { return 0; };
965      DefPredMapBase(const _Traits &b) : _Traits(b) {}
966    };
967
968    ///\brief \ref named-templ-param "Named parameter"
969    ///function for setting PredMap type
970    ///
971    /// \ref named-templ-param "Named parameter"
972    ///function for setting PredMap type
973    ///
974    template<class T>
975    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
976    {
977      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
978      return BellmanFordWizard<DefPredMapBase<T> >(*this);
979    }
980
981    template<class T>
982    struct DefDistMapBase : public Base {
983      typedef T DistMap;
984      static DistMap *createDistMap(const Graph &) { return 0; };
985      DefDistMapBase(const _Traits &b) : _Traits(b) {}
986    };
987
988    ///\brief \ref named-templ-param "Named parameter"
989    ///function for setting DistMap type
990    ///
991    /// \ref named-templ-param "Named parameter"
992    ///function for setting DistMap type
993    ///
994    template<class T>
995    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
996      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
997      return BellmanFordWizard<DefDistMapBase<T> >(*this);
998    }
999
1000    template<class T>
1001    struct DefOperationTraitsBase : public Base {
1002      typedef T OperationTraits;
1003      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1004    };
1005
1006    ///\brief \ref named-templ-param "Named parameter"
1007    ///function for setting OperationTraits type
1008    ///
1009    /// \ref named-templ-param "Named parameter"
1010    ///function for setting OperationTraits type
1011    ///
1012    template<class T>
1013    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
1014      return BellmanFordWizard<DefDistMapBase<T> >(*this);
1015    }
1016
1017    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
1018    ///
1019    /// Sets the source node, from which the BellmanFord algorithm runs.
1020    /// \param src is the source node.
1021    BellmanFordWizard<_Traits>& source(Node src) {
1022      Base::_source = src;
1023      return *this;
1024    }
1025
1026  };
1027
1028  /// \brief Function type interface for BellmanFord algorithm.
1029  ///
1030  /// \ingroup shortest_path
1031  /// Function type interface for BellmanFord algorithm.
1032  ///
1033  /// This function also has several \ref named-templ-func-param
1034  /// "named parameters", they are declared as the members of class
1035  /// \ref BellmanFordWizard.
1036  /// The following
1037  /// example shows how to use these parameters.
1038  ///\code
1039  /// bellmanford(g,length,source).predMap(preds).run();
1040  ///\endcode
1041  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1042  /// to the end of the parameter list.
1043  /// \sa BellmanFordWizard
1044  /// \sa BellmanFord
1045  template<class _Graph, class _LengthMap>
1046  BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1047  bellmanFord(const _Graph& graph,
1048              const _LengthMap& length,
1049              typename _Graph::Node source = INVALID) {
1050    return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1051      (graph, length, source);
1052  }
1053
1054} //END OF NAMESPACE LEMON
1055
1056#endif
1057
Note: See TracBrowser for help on using the repository browser.