COIN-OR::LEMON - Graph Library

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
RevLine 
[1699]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2391]5 * Copyright (C) 2003-2007
[1956]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1699]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
[2376]22/// \ingroup shortest_path
[1699]23/// \file
[1864]24/// \brief BellmanFord algorithm.
[1699]25///
26
27#include <lemon/list_graph.h>
[2335]28#include <lemon/bits/path_dump.h>
[1993]29#include <lemon/bits/invalid.h>
[2394]30#include <lemon/graph_utils.h>
[1699]31#include <lemon/error.h>
32#include <lemon/maps.h>
33
34#include <limits>
35
36namespace lemon {
37
[1864]38  /// \brief Default OperationTraits for the BellmanFord algorithm class.
[1699]39  /// 
40  /// It defines all computational operations and constants which are
[2408]41  /// used in the Bellman-Ford algorithm. The default implementation
[1699]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>
[1864]48  struct BellmanFordDefaultOperationTraits {
[1699]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>
[1864]68  struct BellmanFordDefaultOperationTraits<Value, false> {
[1699]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 
[1864]84  /// \brief Default traits class of BellmanFord class.
[1699]85  ///
[1864]86  /// Default traits class of BellmanFord class.
[1699]87  /// \param _Graph Graph type.
88  /// \param _LegthMap Type of length map.
89  template<class _Graph, class _LengthMap>
[1864]90  struct BellmanFordDefaultTraits {
[1699]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.
[2260]97    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
[1699]98    typedef _LengthMap LengthMap;
99
100    // The type of the length of the edges.
101    typedef typename _LengthMap::Value Value;
102
[2408]103    /// \brief Operation traits for Bellman-Ford algorithm.
[1699]104    ///
105    /// It defines the infinity type on the given Value type
106    /// and the used operation.
[1864]107    /// \see BellmanFordDefaultOperationTraits
108    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
[1699]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.
[2260]115    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
[1699]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.
[1858]122    /// \param graph is the graph, to which we would like to define the PredMap.
[1699]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.
[2260]130    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
[1699]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.
[1858]138    /// \param graph is the graph, to which we would like to define the
[1699]139    /// \ref DistMap
140    static DistMap *createDistMap(const _Graph& graph) {
141      return new DistMap(graph);
142    }
143
144  };
145 
[1864]146  /// \brief %BellmanFord algorithm class.
[1699]147  ///
[2376]148  /// \ingroup shortest_path
[1864]149  /// This class provides an efficient implementation of \c Bellman-Ford
[1699]150  /// algorithm. The edge lengths are passed to the algorithm using a
[2260]151  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
[1699]152  /// kind of length.
153  ///
[1864]154  /// The Bellman-Ford algorithm solves the shortest path from one node
[1723]155  /// problem when the edges can have negative length but the graph should
[1754]156  /// not contain cycles with negative sum of length. If we can assume
[1723]157  /// that all edge is non-negative in the graph then the dijkstra algorithm
158  /// should be used rather.
159  ///
[2042]160  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
[1723]161  ///
[1699]162  /// The type of the length is determined by the
[2260]163  /// \ref concepts::ReadMap::Value "Value" of the length map.
[1699]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
[1864]167  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
[1699]168  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
[2260]169  /// edges. The default map type is \ref concepts::Graph::EdgeMap
[1699]170  /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly
[1864]171  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 
[1699]172  /// \param _Traits Traits class to set various data types used by the
[1864]173  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
174  /// "BellmanFordDefaultTraits<_Graph,_LengthMap>".  See \ref
175  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
[1699]176  /// class.
177  ///
178  /// \author Balazs Dezso
179
[1710]180#ifdef DOXYGEN
181  template <typename _Graph, typename _LengthMap, typename _Traits>
182#else
[1699]183  template <typename _Graph=ListGraph,
184            typename _LengthMap=typename _Graph::template EdgeMap<int>,
[1864]185            typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
[1710]186#endif
[1864]187  class BellmanFord {
[1699]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:
[2151]197      virtual const char* what() const throw() {
[1864]198        return "lemon::BellmanFord::UninitializedParameter";
[1699]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;
[1781]209    typedef typename Graph::OutEdgeIt OutEdgeIt;
[1699]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
[1781]236    typedef typename Graph::template NodeMap<bool> MaskMap;
237    MaskMap *_mask;
238
239    std::vector<Node> _process;
240
[1699]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      }
[1781]251      _mask = new MaskMap(*graph, false);
[1699]252    }
253   
254  public :
255 
[1864]256    typedef BellmanFord Create;
[1710]257
[1699]258    /// \name Named template parameters
259
260    ///@{
261
262    template <class T>
263    struct DefPredMapTraits : public Traits {
264      typedef T PredMap;
[1710]265      static PredMap *createPredMap(const Graph&) {
[1699]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>
[1858]275    struct DefPredMap
[1864]276      : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
277      typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
[1710]278    };
[1699]279   
280    template <class T>
281    struct DefDistMapTraits : public Traits {
282      typedef T DistMap;
[2010]283      static DistMap *createDistMap(const Graph&) {
[1699]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>
[1710]294    struct DefDistMap
[1864]295      : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
296      typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
[1710]297    };
[1699]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    ///
[1710]307    /// \ref named-templ-param "Named parameter" for setting OperationTraits
308    /// type
[1699]309    template <class T>
[1710]310    struct DefOperationTraits
[1864]311      : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
312      typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
[1710]313      Create;
[1699]314    };
315   
316    ///@}
317
[1710]318  protected:
319   
[1864]320    BellmanFord() {}
[1710]321
[1699]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.
[1864]328    BellmanFord(const Graph& _graph, const LengthMap& _length) :
[1699]329      graph(&_graph), length(&_length),
330      _pred(0), local_pred(false),
[2074]331      _dist(0), local_dist(false), _mask(0) {}
[1699]332   
333    ///Destructor.
[1864]334    ~BellmanFord() {
[1699]335      if(local_pred) delete _pred;
336      if(local_dist) delete _dist;
[2074]337      if(_mask) delete _mask;
[1699]338    }
339
340    /// \brief Sets the length map.
341    ///
342    /// Sets the length map.
343    /// \return \c (*this)
[1864]344    BellmanFord &lengthMap(const LengthMap &m) {
[1699]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)
[1864]356    BellmanFord &predMap(PredMap &m) {
[1699]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)
[1864]372    BellmanFord &distMap(DistMap &m) {
[1699]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.
[1710]396    void init(const Value value = OperationTraits::infinity()) {
[1699]397      create_maps();
398      for (NodeIt it(*graph); it != INVALID; ++it) {
399        _pred->set(it, INVALID);
[1710]400        _dist->set(it, value);
[1699]401      }
[1781]402      _process.clear();
403      if (OperationTraits::less(value, OperationTraits::infinity())) {
404        for (NodeIt it(*graph); it != INVALID; ++it) {
405          _process.push_back(it);
[1783]406          _mask->set(it, true);
[1781]407        }
408      }
[1699]409    }
410   
411    /// \brief Adds a new source node.
412    ///
[2408]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.
[1699]416    void addSource(Node source, Value dst = OperationTraits::zero()) {
417      _dist->set(source, dst);
[1781]418      if (!(*_mask)[source]) {
419        _process.push_back(source);
420        _mask->set(source, true);
421      }
422    }
423
[2408]424    /// \brief Executes one round from the Bellman-Ford algorithm.
[1781]425    ///
[2059]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
[2335]433    /// easily with \ref path() or \ref predEdge() functions. If you
[2059]434    /// need the shortest path and not just the distance you should store
[2476]435    /// after each iteration the \ref predMap() map and manually build
[2059]436    /// the path.
437    ///
[2517]438    /// \return \c true when the algorithm have not found more shorter
[2059]439    /// paths.
[1781]440    bool processNextRound() {
[2386]441      for (int i = 0; i < int(_process.size()); ++i) {
[1781]442        _mask->set(_process[i], false);
443      }
444      std::vector<Node> nextProcess;
445      std::vector<Value> values(_process.size());
[2386]446      for (int i = 0; i < int(_process.size()); ++i) {
[1857]447        values[i] = (*_dist)[_process[i]];
[1781]448      }
[2386]449      for (int i = 0; i < int(_process.size()); ++i) {
[1781]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]) {
457              _mask->set(target, true);
458              nextProcess.push_back(target);
459            }
460          }       
461        }
462      }
463      _process.swap(nextProcess);
464      return _process.empty();
465    }
466
[2408]467    /// \brief Executes one weak round from the Bellman-Ford algorithm.
[1781]468    ///
469    /// If the algorithm calculated the distances in the
[1816]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.
[2517]475    /// \return \c true when the algorithm have not found more shorter paths.
[1781]476    bool processNextWeakRound() {
[2386]477      for (int i = 0; i < int(_process.size()); ++i) {
[1781]478        _mask->set(_process[i], false);
479      }
480      std::vector<Node> nextProcess;
[2386]481      for (int i = 0; i < int(_process.size()); ++i) {
[1781]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]) {
490              _mask->set(target, true);
491              nextProcess.push_back(target);
492            }
493          }       
494        }
495      }
496      _process.swap(nextProcess);
497      return _process.empty();
[1699]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    ///
[1864]505    /// This method runs the %BellmanFord algorithm from the root node(s)
[1699]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() {
[1723]511      int num = countNodes(*graph) - 1;
512      for (int i = 0; i < num; ++i) {
[1781]513        if (processNextWeakRound()) break;
[1699]514      }
515    }
[1723]516
[1754]517    /// \brief Executes the algorithm and checks the negative cycles.
[1723]518    ///
519    /// \pre init() must be called and at least one node should be added
[2517]520    /// with addSource() before using this function.
[1723]521    ///
[1864]522    /// This method runs the %BellmanFord algorithm from the root node(s)
[1723]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).
[2517]527    ///
528    /// \return \c false if there is a negative cycle in the graph.
[1723]529    bool checkedStart() {
[2393]530      int num = countNodes(*graph);
[1723]531      for (int i = 0; i < num; ++i) {
[1781]532        if (processNextWeakRound()) return true;
[1723]533      }
[2362]534      return _process.empty();
[1723]535    }
[1781]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    ///
[2059]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
[2335]547    /// easily with \ref path() or \ref predEdge() functions. If you
[2059]548    /// need the shortest path and not just the distance you should store
[2476]549    /// after each iteration the \ref predMap() map and manually build
[2059]550    /// the path.
551    ///
552    /// The algorithm computes
553    /// - The predecessor edge from each node.
[1781]554    /// - The limited distance of each node from the root(s).
[2059]555    void limitedStart(int num) {
556      for (int i = 0; i < num; ++i) {
[1781]557        if (processNextRound()) break;
558      }
559    }
[1699]560   
[1864]561    /// \brief Runs %BellmanFord algorithm from node \c s.
[1699]562    ///   
[1864]563    /// This method runs the %BellmanFord algorithm from a root node \c s
[1699]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.
[1946]570    ///\code
[1699]571    ///  d.init();
572    ///  d.addSource(s);
573    ///  d.start();
[1946]574    ///\endcode
[1699]575    void run(Node s) {
576      init();
577      addSource(s);
578      start();
579    }
580   
[1864]581    /// \brief Runs %BellmanFord algorithm with limited path length
[1857]582    /// from node \c s.
583    ///   
[1864]584    /// This method runs the %BellmanFord algorithm from a root node \c s
[1857]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    ///
[2362]590    /// \note d.run(s, num) is just a shortcut of the following code.
[1946]591    ///\code
[1857]592    ///  d.init();
593    ///  d.addSource(s);
[2362]594    ///  d.limitedStart(num);
[1946]595    ///\endcode
[2362]596    void run(Node s, int num) {
[1857]597      init();
598      addSource(s);
[2362]599      limitedStart(num);
[1857]600    }
601   
[1699]602    ///@}
603
604    /// \name Query Functions
[1864]605    /// The result of the %BellmanFord algorithm can be obtained using these
[1699]606    /// functions.\n
607    /// Before the use of these functions,
608    /// either run() or start() must be called.
609   
610    ///@{
611
[2408]612    /// \brief Lemon iterator for get the active nodes.
[2070]613    ///
[2362]614    /// Lemon iterator for get the active nodes. This class provides a
[2070]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 {
[2386]651        return static_cast<Node>(*this) == static_cast<Node>(it);
[2070]652      }
653      bool operator!=(const ActiveIt& it) const {
[2386]654        return static_cast<Node>(*this) != static_cast<Node>(it);
[2070]655      }
656      bool operator<(const ActiveIt& it) const {
[2386]657        return static_cast<Node>(*this) < static_cast<Node>(it);
[2070]658      }
659     
660    private:
661      const BellmanFord* _algorithm;
662      int _index;
663    };
664
[2335]665    typedef PredMapPath<Graph, PredMap> Path;
666
667    /// \brief Gives back the shortest path.
[1699]668    ///   
[2335]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);
[1699]674    }
[2070]675
[2335]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//     }
[1699]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.
[1763]733    Edge predEdge(Node v) const { return (*_pred)[v]; }
[1699]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
[1763]741    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be
[1699]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 
[1864]770  /// \brief Default traits class of BellmanFord function.
[1699]771  ///
[1864]772  /// Default traits class of BellmanFord function.
[1699]773  /// \param _Graph Graph type.
774  /// \param _LengthMap Type of length map.
775  template <typename _Graph, typename _LengthMap>
[1864]776  struct BellmanFordWizardDefaultTraits {
[1699]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.
[2260]783    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
[1699]784    typedef _LengthMap LengthMap;
785
786    /// \brief The value type of the length map.
787    typedef typename _LengthMap::Value Value;
788
[2408]789    /// \brief Operation traits for Bellman-Ford algorithm.
[1699]790    ///
791    /// It defines the infinity type on the given Value type
792    /// and the used operation.
[1864]793    /// \see BellmanFordDefaultOperationTraits
794    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
[1699]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.
[2260]801    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
[1699]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.
[2260]813    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
[1699]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 
[1864]823  /// \brief Default traits used by \ref BellmanFordWizard
[1699]824  ///
[1864]825  /// To make it easier to use BellmanFord algorithm
[1699]826  /// we have created a wizard class.
[1864]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.
[1699]831  /// \todo More named parameters are required...
832  template<class _Graph,class _LengthMap>
[1864]833  class BellmanFordWizardBase
834    : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
[1699]835
[1864]836    typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
[1699]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).
[1864]857    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
[1699]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
[1864]868    BellmanFordWizardBase(const _Graph& graph,
[1699]869                          const _LengthMap& length,
870                          Node source = INVALID) :
[2386]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) {}
[1699]874
875  };
876 
[1864]877  /// A class to make the usage of BellmanFord algorithm easier
[1699]878
[1864]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,
[1699]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.
[1864]886  /// When using the plain \ref BellmanFord
[1699]887  /// the new class with the modified type comes from
888  /// the original class by using the ::
[1864]889  /// operator. In the case of \ref BellmanFordWizard only
[1699]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
[1864]894  /// it initiates a plain \ref BellmanFord class, and calls the \ref
895  /// BellmanFord::run method of it.
[1699]896  template<class _Traits>
[1864]897  class BellmanFordWizard : public _Traits {
[1699]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.
[1864]923    BellmanFordWizard() : _Traits() {}
[1699]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.
[1864]929    BellmanFordWizard(const Graph& graph, const LengthMap& length,
[2386]930                      Node src = INVALID)
931      : _Traits(graph, length, src) {}
[1699]932
933    /// \brief Copy constructor
[1864]934    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
[1699]935
[1864]936    ~BellmanFordWizard() {}
[1699]937
[1864]938    /// \brief Runs BellmanFord algorithm from a given node.
[1699]939    ///   
[1864]940    /// Runs BellmanFord algorithm from a given node.
[1699]941    /// The node can be given by the \ref source function.
942    void run() {
943      if(Base::_source == INVALID) throw UninitializedParameter();
[1864]944      BellmanFord<Graph,LengthMap,_Traits>
[2386]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));
[1699]949      bf.run(Base::_source);
950    }
951
[1864]952    /// \brief Runs BellmanFord algorithm from the given node.
[1699]953    ///
[1864]954    /// Runs BellmanFord algorithm from the given node.
[2476]955    /// \param src is the given source.
[2386]956    void run(Node src) {
957      Base::_source = src;
[1699]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>
[1864]975    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
[1699]976    {
[2386]977      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
[1864]978      return BellmanFordWizard<DefPredMapBase<T> >(*this);
[1699]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>
[1864]995    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
[2386]996      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
[1864]997      return BellmanFordWizard<DefDistMapBase<T> >(*this);
[1699]998    }
[1710]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>
[1864]1013    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
1014      return BellmanFordWizard<DefDistMapBase<T> >(*this);
[1710]1015    }
[1699]1016   
[1864]1017    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
[1699]1018    ///
[1864]1019    /// Sets the source node, from which the BellmanFord algorithm runs.
[2476]1020    /// \param src is the source node.
[2386]1021    BellmanFordWizard<_Traits>& source(Node src) {
1022      Base::_source = src;
[1699]1023      return *this;
1024    }
1025   
1026  };
1027 
[1864]1028  /// \brief Function type interface for BellmanFord algorithm.
[1699]1029  ///
[2376]1030  /// \ingroup shortest_path
[1864]1031  /// Function type interface for BellmanFord algorithm.
[1699]1032  ///
1033  /// This function also has several \ref named-templ-func-param
1034  /// "named parameters", they are declared as the members of class
[1864]1035  /// \ref BellmanFordWizard.
[1699]1036  /// The following
1037  /// example shows how to use these parameters.
[1946]1038  ///\code
[1864]1039  /// bellmanford(g,length,source).predMap(preds).run();
[1946]1040  ///\endcode
[1864]1041  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
[1699]1042  /// to the end of the parameter list.
[1864]1043  /// \sa BellmanFordWizard
1044  /// \sa BellmanFord
[1699]1045  template<class _Graph, class _LengthMap>
[1864]1046  BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1047  bellmanFord(const _Graph& graph,
[1699]1048              const _LengthMap& length,
1049              typename _Graph::Node source = INVALID) {
[1864]1050    return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
[1699]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.