COIN-OR::LEMON - Graph Library

source: lemon/lemon/bellman_ford.h @ 955:7f6e2bd76654

Last change on this file since 955:7f6e2bd76654 was 917:a6eb9698c321, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Support tolerance technique for BellmanFord? (#51)

A new operation traits class BellmanFordToleranceOperationTraits?
is introduced, which uses the tolerance technique in its less()
function. This class can be used with the SetOperationTraits?
named template parameter.

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