Unionfind changes induced some bugs here. Also some augmentations made.
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 concept::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 concept::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 concept::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 concept::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 complexity of the algorithm is O(n * e).
160 /// The type of the length is determined by the
161 /// \ref concept::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 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
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* exceptionName() const {
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) {}
333 if(local_pred) delete _pred;
334 if(local_dist) delete _dist;
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 /// strictly for all at most k length paths then it will calculate the
425 /// distances strictly for all at most k + 1 length paths. With k
426 /// iteration this function calculates the at most k length paths.
427 /// \return %True when the algorithm have not found more shorter paths.
428 bool processNextRound() {
429 for (int i = 0; i < (int)_process.size(); ++i) {
430 _mask->set(_process[i], false);
432 std::vector<Node> nextProcess;
433 std::vector<Value> values(_process.size());
434 for (int i = 0; i < (int)_process.size(); ++i) {
435 values[i] = (*_dist)[_process[i]];
437 for (int i = 0; i < (int)_process.size(); ++i) {
438 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
439 Node target = graph->target(it);
440 Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
441 if (OperationTraits::less(relaxed, (*_dist)[target])) {
442 _pred->set(target, it);
443 _dist->set(target, relaxed);
444 if (!(*_mask)[target]) {
445 _mask->set(target, true);
446 nextProcess.push_back(target);
451 _process.swap(nextProcess);
452 return _process.empty();
455 /// \brief Executes one weak round from the bellman ford algorithm.
457 /// If the algorithm calculated the distances in the
458 /// previous round at least for all at most k length paths then it will
459 /// calculate the distances at least for all at most k + 1 length paths.
460 /// This function does not make it possible to calculate strictly the
461 /// at most k length minimal paths, this is why it is
462 /// called just weak round.
463 /// \return %True when the algorithm have not found more shorter paths.
464 bool processNextWeakRound() {
465 for (int i = 0; i < (int)_process.size(); ++i) {
466 _mask->set(_process[i], false);
468 std::vector<Node> nextProcess;
469 for (int i = 0; i < (int)_process.size(); ++i) {
470 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
471 Node target = graph->target(it);
473 OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
474 if (OperationTraits::less(relaxed, (*_dist)[target])) {
475 _pred->set(target, it);
476 _dist->set(target, relaxed);
477 if (!(*_mask)[target]) {
478 _mask->set(target, true);
479 nextProcess.push_back(target);
484 _process.swap(nextProcess);
485 return _process.empty();
488 /// \brief Executes the algorithm.
490 /// \pre init() must be called and at least one node should be added
491 /// with addSource() before using this function.
493 /// This method runs the %BellmanFord algorithm from the root node(s)
494 /// in order to compute the shortest path to each node. The algorithm
496 /// - The shortest path tree.
497 /// - The distance of each node from the root(s).
499 int num = countNodes(*graph) - 1;
500 for (int i = 0; i < num; ++i) {
501 if (processNextWeakRound()) break;
505 /// \brief Executes the algorithm and checks the negative cycles.
507 /// \pre init() must be called and at least one node should be added
508 /// with addSource() before using this function. If there is
509 /// a negative cycles in the graph it gives back false.
511 /// This method runs the %BellmanFord algorithm from the root node(s)
512 /// in order to compute the shortest path to each node. The algorithm
514 /// - The shortest path tree.
515 /// - The distance of each node from the root(s).
516 bool checkedStart() {
517 int num = countNodes(*graph);
518 for (int i = 0; i < num; ++i) {
519 if (processNextWeakRound()) return true;
524 /// \brief Executes the algorithm with path length limit.
526 /// \pre init() must be called and at least one node should be added
527 /// with addSource() before using this function.
529 /// This method runs the %BellmanFord algorithm from the root node(s)
530 /// in order to compute the shortest path with at most \c length edge
531 /// long paths to each node. The algorithm computes
532 /// - The shortest path tree.
533 /// - The limited distance of each node from the root(s).
534 void limitedStart(int length) {
535 for (int i = 0; i < length; ++i) {
536 if (processNextRound()) break;
540 /// \brief Runs %BellmanFord algorithm from node \c s.
542 /// This method runs the %BellmanFord algorithm from a root node \c s
543 /// in order to compute the shortest path to each node. The algorithm
545 /// - The shortest path tree.
546 /// - The distance of each node from the root.
548 /// \note d.run(s) is just a shortcut of the following code.
560 /// \brief Runs %BellmanFord algorithm with limited path length
563 /// This method runs the %BellmanFord algorithm from a root node \c s
564 /// in order to compute the shortest path with at most \c len edges
565 /// to each node. The algorithm computes
566 /// - The shortest path tree.
567 /// - The distance of each node from the root.
569 /// \note d.run(s, len) is just a shortcut of the following code.
573 /// d.limitedStart(len);
575 void run(Node s, int len) {
583 /// \name Query Functions
584 /// The result of the %BellmanFord algorithm can be obtained using these
586 /// Before the use of these functions,
587 /// either run() or start() must be called.
591 /// \brief Copies the shortest path to \c t into \c p
593 /// This function copies the shortest path to \c t into \c p.
594 /// If it \c t is a source itself or unreachable, then it does not
597 /// \return Returns \c true if a path to \c t was actually copied to \c p,
598 /// \c false otherwise.
600 template <typename Path>
601 bool getPath(Path &p, Node t) {
604 typename Path::Builder b(p);
605 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
606 b.pushFront(predEdge(t));
613 /// \brief The distance of a node from the root.
615 /// Returns the distance of a node from the root.
616 /// \pre \ref run() must be called before using this function.
617 /// \warning If node \c v in unreachable from the root the return value
618 /// of this funcion is undefined.
619 Value dist(Node v) const { return (*_dist)[v]; }
621 /// \brief Returns the 'previous edge' of the shortest path tree.
623 /// For a node \c v it returns the 'previous edge' of the shortest path
624 /// tree, i.e. it returns the last edge of a shortest path from the root
625 /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
626 /// if \c v=s. The shortest path tree used here is equal to the shortest
627 /// path tree used in \ref predNode().
628 /// \pre \ref run() must be called before using
630 Edge predEdge(Node v) const { return (*_pred)[v]; }
632 /// \brief Returns the 'previous node' of the shortest path tree.
634 /// For a node \c v it returns the 'previous node' of the shortest path
635 /// tree, i.e. it returns the last but one node from a shortest path from
636 /// the root to \c /v. It is INVALID if \c v is unreachable from the root
637 /// or if \c v=s. The shortest path tree used here is equal to the
638 /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
639 /// called before using this function.
640 Node predNode(Node v) const {
641 return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
644 /// \brief Returns a reference to the NodeMap of distances.
646 /// Returns a reference to the NodeMap of distances. \pre \ref run() must
647 /// be called before using this function.
648 const DistMap &distMap() const { return *_dist;}
650 /// \brief Returns a reference to the shortest path tree map.
652 /// Returns a reference to the NodeMap of the edges of the
653 /// shortest path tree.
654 /// \pre \ref run() must be called before using this function.
655 const PredMap &predMap() const { return *_pred; }
657 /// \brief Checks if a node is reachable from the root.
659 /// Returns \c true if \c v is reachable from the root.
660 /// \pre \ref run() must be called before using this function.
662 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
667 /// \brief Default traits class of BellmanFord function.
669 /// Default traits class of BellmanFord function.
670 /// \param _Graph Graph type.
671 /// \param _LengthMap Type of length map.
672 template <typename _Graph, typename _LengthMap>
673 struct BellmanFordWizardDefaultTraits {
674 /// \brief The graph type the algorithm runs on.
675 typedef _Graph Graph;
677 /// \brief The type of the map that stores the edge lengths.
679 /// The type of the map that stores the edge lengths.
680 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
681 typedef _LengthMap LengthMap;
683 /// \brief The value type of the length map.
684 typedef typename _LengthMap::Value Value;
686 /// \brief Operation traits for bellman-ford algorithm.
688 /// It defines the infinity type on the given Value type
689 /// and the used operation.
690 /// \see BellmanFordDefaultOperationTraits
691 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
693 /// \brief The type of the map that stores the last
694 /// edges of the shortest paths.
696 /// The type of the map that stores the last
697 /// edges of the shortest paths.
698 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
699 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
701 /// \brief Instantiates a PredMap.
703 /// This function instantiates a \ref PredMap.
704 static PredMap *createPredMap(const _Graph &) {
705 return new PredMap();
707 /// \brief The type of the map that stores the dists of the nodes.
709 /// The type of the map that stores the dists of the nodes.
710 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
711 typedef NullMap<typename Graph::Node, Value> DistMap;
712 /// \brief Instantiates a DistMap.
714 /// This function instantiates a \ref DistMap.
715 static DistMap *createDistMap(const _Graph &) {
716 return new DistMap();
720 /// \brief Default traits used by \ref BellmanFordWizard
722 /// To make it easier to use BellmanFord algorithm
723 /// we have created a wizard class.
724 /// This \ref BellmanFordWizard class needs default traits,
725 /// as well as the \ref BellmanFord class.
726 /// The \ref BellmanFordWizardBase is a class to be the default traits of the
727 /// \ref BellmanFordWizard class.
728 /// \todo More named parameters are required...
729 template<class _Graph,class _LengthMap>
730 class BellmanFordWizardBase
731 : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
733 typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
735 /// Type of the nodes in the graph.
736 typedef typename Base::Graph::Node Node;
738 /// Pointer to the underlying graph.
740 /// Pointer to the length map
742 ///Pointer to the map of predecessors edges.
744 ///Pointer to the map of distances.
746 ///Pointer to the source node.
752 /// This constructor does not require parameters, therefore it initiates
753 /// all of the attributes to default values (0, INVALID).
754 BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
755 _dist(0), _source(INVALID) {}
759 /// This constructor requires some parameters,
760 /// listed in the parameters list.
761 /// Others are initiated to 0.
762 /// \param graph is the initial value of \ref _graph
763 /// \param length is the initial value of \ref _length
764 /// \param source is the initial value of \ref _source
765 BellmanFordWizardBase(const _Graph& graph,
766 const _LengthMap& length,
767 Node source = INVALID) :
768 _graph((void *)&graph), _length((void *)&length), _pred(0),
769 _dist(0), _source(source) {}
773 /// A class to make the usage of BellmanFord algorithm easier
775 /// This class is created to make it easier to use BellmanFord algorithm.
776 /// It uses the functions and features of the plain \ref BellmanFord,
777 /// but it is much simpler to use it.
779 /// Simplicity means that the way to change the types defined
780 /// in the traits class is based on functions that returns the new class
781 /// and not on templatable built-in classes.
782 /// When using the plain \ref BellmanFord
783 /// the new class with the modified type comes from
784 /// the original class by using the ::
785 /// operator. In the case of \ref BellmanFordWizard only
786 /// a function have to be called and it will
787 /// return the needed class.
789 /// It does not have own \ref run method. When its \ref run method is called
790 /// it initiates a plain \ref BellmanFord class, and calls the \ref
791 /// BellmanFord::run method of it.
792 template<class _Traits>
793 class BellmanFordWizard : public _Traits {
794 typedef _Traits Base;
796 ///The type of the underlying graph.
797 typedef typename _Traits::Graph Graph;
799 typedef typename Graph::Node Node;
800 typedef typename Graph::NodeIt NodeIt;
801 typedef typename Graph::Edge Edge;
802 typedef typename Graph::OutEdgeIt EdgeIt;
804 ///The type of the map that stores the edge lengths.
805 typedef typename _Traits::LengthMap LengthMap;
807 ///The type of the length of the edges.
808 typedef typename LengthMap::Value Value;
810 ///\brief The type of the map that stores the last
811 ///edges of the shortest paths.
812 typedef typename _Traits::PredMap PredMap;
814 ///The type of the map that stores the dists of the nodes.
815 typedef typename _Traits::DistMap DistMap;
819 BellmanFordWizard() : _Traits() {}
821 /// \brief Constructor that requires parameters.
823 /// Constructor that requires parameters.
824 /// These parameters will be the default values for the traits class.
825 BellmanFordWizard(const Graph& graph, const LengthMap& length,
826 Node source = INVALID)
827 : _Traits(graph, length, source) {}
829 /// \brief Copy constructor
830 BellmanFordWizard(const _Traits &b) : _Traits(b) {}
832 ~BellmanFordWizard() {}
834 /// \brief Runs BellmanFord algorithm from a given node.
836 /// Runs BellmanFord algorithm from a given node.
837 /// The node can be given by the \ref source function.
839 if(Base::_source == INVALID) throw UninitializedParameter();
840 BellmanFord<Graph,LengthMap,_Traits>
841 bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
842 if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
843 if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
844 bf.run(Base::_source);
847 /// \brief Runs BellmanFord algorithm from the given node.
849 /// Runs BellmanFord algorithm from the given node.
850 /// \param source is the given source.
851 void run(Node source) {
852 Base::_source = source;
857 struct DefPredMapBase : public Base {
859 static PredMap *createPredMap(const Graph &) { return 0; };
860 DefPredMapBase(const _Traits &b) : _Traits(b) {}
863 ///\brief \ref named-templ-param "Named parameter"
864 ///function for setting PredMap type
866 /// \ref named-templ-param "Named parameter"
867 ///function for setting PredMap type
870 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
872 Base::_pred=(void *)&t;
873 return BellmanFordWizard<DefPredMapBase<T> >(*this);
877 struct DefDistMapBase : public Base {
879 static DistMap *createDistMap(const Graph &) { return 0; };
880 DefDistMapBase(const _Traits &b) : _Traits(b) {}
883 ///\brief \ref named-templ-param "Named parameter"
884 ///function for setting DistMap type
886 /// \ref named-templ-param "Named parameter"
887 ///function for setting DistMap type
890 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
891 Base::_dist=(void *)&t;
892 return BellmanFordWizard<DefDistMapBase<T> >(*this);
896 struct DefOperationTraitsBase : public Base {
897 typedef T OperationTraits;
898 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
901 ///\brief \ref named-templ-param "Named parameter"
902 ///function for setting OperationTraits type
904 /// \ref named-templ-param "Named parameter"
905 ///function for setting OperationTraits type
908 BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
909 return BellmanFordWizard<DefDistMapBase<T> >(*this);
912 /// \brief Sets the source node, from which the BellmanFord algorithm runs.
914 /// Sets the source node, from which the BellmanFord algorithm runs.
915 /// \param source is the source node.
916 BellmanFordWizard<_Traits>& source(Node source) {
917 Base::_source = source;
923 /// \brief Function type interface for BellmanFord algorithm.
925 /// \ingroup flowalgs
926 /// Function type interface for BellmanFord algorithm.
928 /// This function also has several \ref named-templ-func-param
929 /// "named parameters", they are declared as the members of class
930 /// \ref BellmanFordWizard.
932 /// example shows how to use these parameters.
934 /// bellmanford(g,length,source).predMap(preds).run();
936 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
937 /// to the end of the parameter list.
938 /// \sa BellmanFordWizard
940 template<class _Graph, class _LengthMap>
941 BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
942 bellmanFord(const _Graph& graph,
943 const _LengthMap& length,
944 typename _Graph::Node source = INVALID) {
945 return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
946 (graph, length, source);
949 } //END OF NAMESPACE LEMON