COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/bellman_ford.h

Last change on this file was 1131:4add05447ca0, checked in by Alpar Juttner <alpar@…>, 5 years ago

Tests and bugfixes for the STL style iterators (#325)

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