Small bugs in the documentation.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BELMANN_FORD_H
20 #define LEMON_BELMANN_FORD_H
24 /// \brief BellmanFord algorithm.
27 #include <lemon/list_graph.h>
28 #include <lemon/bits/invalid.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
36 /// \brief Default OperationTraits for the BellmanFord algorithm class.
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
45 bool has_infinity = std::numeric_limits<Value>::has_infinity>
46 struct BellmanFordDefaultOperationTraits {
47 /// \brief Gives back the zero value of the type.
49 return static_cast<Value>(0);
51 /// \brief Gives back the positive infinity value of the type.
52 static Value infinity() {
53 return std::numeric_limits<Value>::infinity();
55 /// \brief Gives back the sum of the given two elements.
56 static Value plus(const Value& left, const Value& right) {
59 /// \brief Gives back true only if the first value less than the second.
60 static bool less(const Value& left, const Value& right) {
65 template <typename Value>
66 struct BellmanFordDefaultOperationTraits<Value, false> {
68 return static_cast<Value>(0);
70 static Value infinity() {
71 return std::numeric_limits<Value>::max();
73 static Value plus(const Value& left, const Value& right) {
74 if (left == infinity() || right == infinity()) return infinity();
77 static bool less(const Value& left, const Value& right) {
82 /// \brief Default traits class of BellmanFord class.
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.
92 /// \brief The type of the map that stores the edge lengths.
94 /// The type of the map that stores the edge lengths.
95 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
96 typedef _LengthMap LengthMap;
98 // The type of the length of the edges.
99 typedef typename _LengthMap::Value Value;
101 /// \brief Operation traits for bellman-ford algorithm.
103 /// It defines the infinity type on the given Value type
104 /// and the used operation.
105 /// \see BellmanFordDefaultOperationTraits
106 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
108 /// \brief The type of the map that stores the last edges of the
111 /// The type of the map that stores the last
112 /// edges of the shortest paths.
113 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
115 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
117 /// \brief Instantiates a PredMap.
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);
125 /// \brief The type of the map that stores the dists of the nodes.
127 /// The type of the map that stores the dists of the nodes.
128 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
130 typedef typename Graph::template NodeMap<typename _LengthMap::Value>
133 /// \brief Instantiates a DistMap.
135 /// This function instantiates a \ref DistMap.
136 /// \param graph is the graph, to which we would like to define the
138 static DistMap *createDistMap(const _Graph& graph) {
139 return new DistMap(graph);
144 /// \brief %BellmanFord algorithm class.
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 concepts::ReadMap "ReadMap", so it is easy to change it to any
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.
158 /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
160 /// The type of the length is determined by the
161 /// \ref concepts::ReadMap::Value "Value" of the length map.
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 concepts::Graph::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
176 /// \author Balazs Dezso
179 template <typename _Graph, typename _LengthMap, typename _Traits>
181 template <typename _Graph=ListGraph,
182 typename _LengthMap=typename _Graph::template EdgeMap<int>,
183 typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
188 /// \brief \ref Exception for uninitialized parameters.
190 /// This error represents problems in the initialization
191 /// of the parameters of the algorithms.
193 class UninitializedParameter : public lemon::UninitializedParameter {
195 virtual const char* what() const throw() {
196 return "lemon::BellmanFord::UninitializedParameter";
200 typedef _Traits Traits;
201 ///The type of the underlying graph.
202 typedef typename _Traits::Graph Graph;
204 typedef typename Graph::Node Node;
205 typedef typename Graph::NodeIt NodeIt;
206 typedef typename Graph::Edge Edge;
207 typedef typename Graph::OutEdgeIt OutEdgeIt;
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;
221 /// Pointer to the underlying graph.
223 /// Pointer to the length map
224 const LengthMap *length;
225 ///Pointer to the map of predecessors edges.
227 ///Indicates if \ref _pred is locally allocated (\c true) or not.
229 ///Pointer to the map of distances.
231 ///Indicates if \ref _dist is locally allocated (\c true) or not.
234 typedef typename Graph::template NodeMap<bool> MaskMap;
237 std::vector<Node> _process;
239 /// Creates the maps if necessary.
243 _pred = Traits::createPredMap(*graph);
247 _dist = Traits::createDistMap(*graph);
249 _mask = new MaskMap(*graph, false);
254 typedef BellmanFord Create;
256 /// \name Named template parameters
261 struct DefPredMapTraits : public Traits {
263 static PredMap *createPredMap(const Graph&) {
264 throw UninitializedParameter();
268 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
270 /// \ref named-templ-param "Named parameter" for setting PredMap type
274 : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
275 typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
279 struct DefDistMapTraits : public Traits {
281 static DistMap *createDistMap(const Graph&) {
282 throw UninitializedParameter();
286 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
289 /// \ref named-templ-param "Named parameter" for setting DistMap type
293 : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
294 typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
298 struct DefOperationTraitsTraits : public Traits {
299 typedef T OperationTraits;
302 /// \brief \ref named-templ-param "Named parameter" for setting
303 /// OperationTraits type
305 /// \ref named-templ-param "Named parameter" for setting OperationTraits
308 struct DefOperationTraits
309 : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
310 typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
322 /// \brief Constructor.
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) {}
333 if(local_pred) delete _pred;
334 if(local_dist) delete _dist;
335 if(_mask) delete _mask;
338 /// \brief Sets the length map.
340 /// Sets the length map.
341 /// \return \c (*this)
342 BellmanFord &lengthMap(const LengthMap &m) {
347 /// \brief Sets the map storing the predecessor edges.
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) {
363 /// \brief Sets the map storing the distances calculated by the algorithm.
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) {
379 /// \name Execution control
380 /// The simplest way to execute the algorithm is to use
381 /// one of the member functions called \c run(...).
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
391 /// \brief Initializes the internal data structures.
393 /// Initializes the internal data structures.
394 void init(const Value value = OperationTraits::infinity()) {
396 for (NodeIt it(*graph); it != INVALID; ++it) {
397 _pred->set(it, INVALID);
398 _dist->set(it, value);
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);
409 /// \brief Adds a new source node.
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);
421 /// \brief Executes one round from the bellman ford algorithm.
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.
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
435 /// \return %True when the algorithm have not found more shorter
437 bool processNextRound() {
438 for (int i = 0; i < (int)_process.size(); ++i) {
439 _mask->set(_process[i], false);
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]];
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);
460 _process.swap(nextProcess);
461 return _process.empty();
464 /// \brief Executes one weak round from the bellman ford algorithm.
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);
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);
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);
493 _process.swap(nextProcess);
494 return _process.empty();
497 /// \brief Executes the algorithm.
499 /// \pre init() must be called and at least one node should be added
500 /// with addSource() before using this function.
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
505 /// - The shortest path tree.
506 /// - The distance of each node from the root(s).
508 int num = countNodes(*graph) - 1;
509 for (int i = 0; i < num; ++i) {
510 if (processNextWeakRound()) break;
514 /// \brief Executes the algorithm and checks the negative cycles.
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.
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
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;
533 /// \brief Executes the algorithm with path length limit.
535 /// \pre init() must be called and at least one node should be added
536 /// with addSource() before using this function.
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.
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
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;
557 /// \brief Runs %BellmanFord algorithm from node \c s.
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
562 /// - The shortest path tree.
563 /// - The distance of each node from the root.
565 /// \note d.run(s) is just a shortcut of the following code.
577 /// \brief Runs %BellmanFord algorithm with limited path length
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.
586 /// \note d.run(s, len) is just a shortcut of the following code.
590 /// d.limitedStart(len);
592 void run(Node s, int len) {
600 /// \name Query Functions
601 /// The result of the %BellmanFord algorithm can be obtained using these
603 /// Before the use of these functions,
604 /// either run() or start() must be called.
608 /// \brief Lemon iterator for get a active nodes.
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.
618 /// \brief Constructor.
620 /// Constructor for get the nodeset of the variable.
621 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
623 _index = _algorithm->_process.size() - 1;
626 /// \brief Invalid constructor.
628 /// Invalid constructor.
629 ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
631 /// \brief Conversion to node.
633 /// Conversion to node.
634 operator Node() const {
635 return _index >= 0 ? _algorithm->_process[_index] : INVALID;
638 /// \brief Increment operator.
640 /// Increment operator.
641 ActiveIt& operator++() {
646 bool operator==(const ActiveIt& it) const {
647 return (Node)(*this) == (Node)it;
649 bool operator!=(const ActiveIt& it) const {
650 return (Node)(*this) != (Node)it;
652 bool operator<(const ActiveIt& it) const {
653 return (Node)(*this) < (Node)it;
657 const BellmanFord* _algorithm;
661 /// \brief Copies the shortest path to \c t into \c p
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
667 /// \return Returns \c true if a path to \c t was actually copied to \c p,
668 /// \c false otherwise.
670 template <typename Path>
671 bool getPath(Path &p, Node t) {
674 typename Path::Builder b(p);
675 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
676 b.pushFront(predEdge(t));
683 /// \brief Copies a negative cycle into path \c p.
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.
689 /// \return Returns \c true if a cycle was actually copied to \c p,
690 /// \c false otherwise.
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)) {
700 } else if (state[t] == 2) {
704 typename Path::Builder b(p);
706 b.pushFront(predEdge(t));
707 for(Node s = predNode(t); s != t; s = predNode(s)) {
708 b.pushFront(predEdge(s));
714 for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
726 /// \brief The distance of a node from the root.
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]; }
734 /// \brief Returns the 'previous edge' of the shortest path tree.
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
743 Edge predEdge(Node v) const { return (*_pred)[v]; }
745 /// \brief Returns the 'previous node' of the shortest path tree.
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]);
757 /// \brief Returns a reference to the NodeMap of distances.
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;}
763 /// \brief Returns a reference to the shortest path tree map.
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; }
770 /// \brief Checks if a node is reachable from the root.
772 /// Returns \c true if \c v is reachable from the root.
773 /// \pre \ref run() must be called before using this function.
775 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
780 /// \brief Default traits class of BellmanFord function.
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;
790 /// \brief The type of the map that stores the edge lengths.
792 /// The type of the map that stores the edge lengths.
793 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
794 typedef _LengthMap LengthMap;
796 /// \brief The value type of the length map.
797 typedef typename _LengthMap::Value Value;
799 /// \brief Operation traits for bellman-ford algorithm.
801 /// It defines the infinity type on the given Value type
802 /// and the used operation.
803 /// \see BellmanFordDefaultOperationTraits
804 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
806 /// \brief The type of the map that stores the last
807 /// edges of the shortest paths.
809 /// The type of the map that stores the last
810 /// edges of the shortest paths.
811 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
812 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
814 /// \brief Instantiates a PredMap.
816 /// This function instantiates a \ref PredMap.
817 static PredMap *createPredMap(const _Graph &) {
818 return new PredMap();
820 /// \brief The type of the map that stores the dists of the nodes.
822 /// The type of the map that stores the dists of the nodes.
823 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
824 typedef NullMap<typename Graph::Node, Value> DistMap;
825 /// \brief Instantiates a DistMap.
827 /// This function instantiates a \ref DistMap.
828 static DistMap *createDistMap(const _Graph &) {
829 return new DistMap();
833 /// \brief Default traits used by \ref BellmanFordWizard
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> {
846 typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
848 /// Type of the nodes in the graph.
849 typedef typename Base::Graph::Node Node;
851 /// Pointer to the underlying graph.
853 /// Pointer to the length map
855 ///Pointer to the map of predecessors edges.
857 ///Pointer to the map of distances.
859 ///Pointer to the source node.
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) {}
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) {}
886 /// A class to make the usage of BellmanFord algorithm easier
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.
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.
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;
909 ///The type of the underlying graph.
910 typedef typename _Traits::Graph Graph;
912 typedef typename Graph::Node Node;
913 typedef typename Graph::NodeIt NodeIt;
914 typedef typename Graph::Edge Edge;
915 typedef typename Graph::OutEdgeIt EdgeIt;
917 ///The type of the map that stores the edge lengths.
918 typedef typename _Traits::LengthMap LengthMap;
920 ///The type of the length of the edges.
921 typedef typename LengthMap::Value Value;
923 ///\brief The type of the map that stores the last
924 ///edges of the shortest paths.
925 typedef typename _Traits::PredMap PredMap;
927 ///The type of the map that stores the dists of the nodes.
928 typedef typename _Traits::DistMap DistMap;
932 BellmanFordWizard() : _Traits() {}
934 /// \brief Constructor that requires parameters.
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) {}
942 /// \brief Copy constructor
943 BellmanFordWizard(const _Traits &b) : _Traits(b) {}
945 ~BellmanFordWizard() {}
947 /// \brief Runs BellmanFord algorithm from a given node.
949 /// Runs BellmanFord algorithm from a given node.
950 /// The node can be given by the \ref source function.
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);
960 /// \brief Runs BellmanFord algorithm from the given node.
962 /// Runs BellmanFord algorithm from the given node.
963 /// \param source is the given source.
964 void run(Node source) {
965 Base::_source = source;
970 struct DefPredMapBase : public Base {
972 static PredMap *createPredMap(const Graph &) { return 0; };
973 DefPredMapBase(const _Traits &b) : _Traits(b) {}
976 ///\brief \ref named-templ-param "Named parameter"
977 ///function for setting PredMap type
979 /// \ref named-templ-param "Named parameter"
980 ///function for setting PredMap type
983 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
985 Base::_pred=(void *)&t;
986 return BellmanFordWizard<DefPredMapBase<T> >(*this);
990 struct DefDistMapBase : public Base {
992 static DistMap *createDistMap(const Graph &) { return 0; };
993 DefDistMapBase(const _Traits &b) : _Traits(b) {}
996 ///\brief \ref named-templ-param "Named parameter"
997 ///function for setting DistMap type
999 /// \ref named-templ-param "Named parameter"
1000 ///function for setting DistMap type
1003 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
1004 Base::_dist=(void *)&t;
1005 return BellmanFordWizard<DefDistMapBase<T> >(*this);
1009 struct DefOperationTraitsBase : public Base {
1010 typedef T OperationTraits;
1011 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1014 ///\brief \ref named-templ-param "Named parameter"
1015 ///function for setting OperationTraits type
1017 /// \ref named-templ-param "Named parameter"
1018 ///function for setting OperationTraits type
1021 BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
1022 return BellmanFordWizard<DefDistMapBase<T> >(*this);
1025 /// \brief Sets the source node, from which the BellmanFord algorithm runs.
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;
1036 /// \brief Function type interface for BellmanFord algorithm.
1038 /// \ingroup flowalgs
1039 /// Function type interface for BellmanFord algorithm.
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.
1045 /// example shows how to use these parameters.
1047 /// bellmanford(g,length,source).predMap(preds).run();
1049 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1050 /// to the end of the parameter list.
1051 /// \sa BellmanFordWizard
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);
1062 } //END OF NAMESPACE LEMON