COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bellman_ford.h @ 2091:c8ccc1f8fd51

Last change on this file since 2091:c8ccc1f8fd51 was 2074:c7ee2a2a3cff, checked in by Balazs Dezso, 14 years ago

Bug fix

Do not delete the not constructed map

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