COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bellman_ford.h @ 2360:72c7075ad5ba

Last change on this file since 2360:72c7075ad5ba was 2335:27aa03cd3121, checked in by Balazs Dezso, 17 years ago

New path concept and path structures

TODO: BellmanFord::negativeCycle()

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