Lemon Graph Format uses label instead of id named map.
2 * lemon/bellman_ford.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_BELMANN_FORD_H
18 #define LEMON_BELMANN_FORD_H
22 /// \brief BellmanFord algorithm.
25 #include <lemon/list_graph.h>
26 #include <lemon/invalid.h>
27 #include <lemon/error.h>
28 #include <lemon/maps.h>
34 /// \brief Default OperationTraits for the BellmanFord algorithm class.
36 /// It defines all computational operations and constants which are
37 /// used in the bellman ford algorithm. The default implementation
38 /// is based on the numeric_limits class. If the numeric type does not
39 /// have infinity value then the maximum value is used as extremal
43 bool has_infinity = std::numeric_limits<Value>::has_infinity>
44 struct BellmanFordDefaultOperationTraits {
45 /// \brief Gives back the zero value of the type.
47 return static_cast<Value>(0);
49 /// \brief Gives back the positive infinity value of the type.
50 static Value infinity() {
51 return std::numeric_limits<Value>::infinity();
53 /// \brief Gives back the sum of the given two elements.
54 static Value plus(const Value& left, const Value& right) {
57 /// \brief Gives back true only if the first value less than the second.
58 static bool less(const Value& left, const Value& right) {
63 template <typename Value>
64 struct BellmanFordDefaultOperationTraits<Value, false> {
66 return static_cast<Value>(0);
68 static Value infinity() {
69 return std::numeric_limits<Value>::max();
71 static Value plus(const Value& left, const Value& right) {
72 if (left == infinity() || right == infinity()) return infinity();
75 static bool less(const Value& left, const Value& right) {
80 /// \brief Default traits class of BellmanFord class.
82 /// Default traits class of BellmanFord class.
83 /// \param _Graph Graph type.
84 /// \param _LegthMap Type of length map.
85 template<class _Graph, class _LengthMap>
86 struct BellmanFordDefaultTraits {
87 /// The graph type the algorithm runs on.
90 /// \brief The type of the map that stores the edge lengths.
92 /// The type of the map that stores the edge lengths.
93 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
94 typedef _LengthMap LengthMap;
96 // The type of the length of the edges.
97 typedef typename _LengthMap::Value Value;
99 /// \brief Operation traits for bellman-ford algorithm.
101 /// It defines the infinity type on the given Value type
102 /// and the used operation.
103 /// \see BellmanFordDefaultOperationTraits
104 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
106 /// \brief The type of the map that stores the last edges of the
109 /// The type of the map that stores the last
110 /// edges of the shortest paths.
111 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
113 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
115 /// \brief Instantiates a PredMap.
117 /// This function instantiates a \ref PredMap.
118 /// \param graph is the graph, to which we would like to define the PredMap.
119 static PredMap *createPredMap(const _Graph& graph) {
120 return new PredMap(graph);
123 /// \brief The type of the map that stores the dists of the nodes.
125 /// The type of the map that stores the dists of the nodes.
126 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
128 typedef typename Graph::template NodeMap<typename _LengthMap::Value>
131 /// \brief Instantiates a DistMap.
133 /// This function instantiates a \ref DistMap.
134 /// \param graph is the graph, to which we would like to define the
136 static DistMap *createDistMap(const _Graph& graph) {
137 return new DistMap(graph);
142 /// \brief %BellmanFord algorithm class.
144 /// \ingroup flowalgs
145 /// This class provides an efficient implementation of \c Bellman-Ford
146 /// algorithm. The edge lengths are passed to the algorithm using a
147 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
150 /// The Bellman-Ford algorithm solves the shortest path from one node
151 /// problem when the edges can have negative length but the graph should
152 /// not contain cycles with negative sum of length. If we can assume
153 /// that all edge is non-negative in the graph then the dijkstra algorithm
154 /// should be used rather.
156 /// The complexity of the algorithm is O(n * e).
158 /// The type of the length is determined by the
159 /// \ref concept::ReadMap::Value "Value" of the length map.
161 /// \param _Graph The graph type the algorithm runs on. The default value
162 /// is \ref ListGraph. The value of _Graph is not used directly by
163 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
164 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
165 /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
166 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
167 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
168 /// \param _Traits Traits class to set various data types used by the
169 /// algorithm. The default traits class is \ref BellmanFordDefaultTraits
170 /// "BellmanFordDefaultTraits<_Graph,_LengthMap>". See \ref
171 /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
174 /// \author Balazs Dezso
177 template <typename _Graph, typename _LengthMap, typename _Traits>
179 template <typename _Graph=ListGraph,
180 typename _LengthMap=typename _Graph::template EdgeMap<int>,
181 typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
186 /// \brief \ref Exception for uninitialized parameters.
188 /// This error represents problems in the initialization
189 /// of the parameters of the algorithms.
191 class UninitializedParameter : public lemon::UninitializedParameter {
193 virtual const char* exceptionName() const {
194 return "lemon::BellmanFord::UninitializedParameter";
198 typedef _Traits Traits;
199 ///The type of the underlying graph.
200 typedef typename _Traits::Graph Graph;
202 typedef typename Graph::Node Node;
203 typedef typename Graph::NodeIt NodeIt;
204 typedef typename Graph::Edge Edge;
205 typedef typename Graph::OutEdgeIt OutEdgeIt;
207 /// \brief The type of the length of the edges.
208 typedef typename _Traits::LengthMap::Value Value;
209 /// \brief The type of the map that stores the edge lengths.
210 typedef typename _Traits::LengthMap LengthMap;
211 /// \brief The type of the map that stores the last
212 /// edges of the shortest paths.
213 typedef typename _Traits::PredMap PredMap;
214 /// \brief The type of the map that stores the dists of the nodes.
215 typedef typename _Traits::DistMap DistMap;
216 /// \brief The operation traits.
217 typedef typename _Traits::OperationTraits OperationTraits;
219 /// Pointer to the underlying graph.
221 /// Pointer to the length map
222 const LengthMap *length;
223 ///Pointer to the map of predecessors edges.
225 ///Indicates if \ref _pred is locally allocated (\c true) or not.
227 ///Pointer to the map of distances.
229 ///Indicates if \ref _dist is locally allocated (\c true) or not.
232 typedef typename Graph::template NodeMap<bool> MaskMap;
235 std::vector<Node> _process;
237 /// Creates the maps if necessary.
241 _pred = Traits::createPredMap(*graph);
245 _dist = Traits::createDistMap(*graph);
247 _mask = new MaskMap(*graph, false);
252 typedef BellmanFord Create;
254 /// \name Named template parameters
259 struct DefPredMapTraits : public Traits {
261 static PredMap *createPredMap(const Graph&) {
262 throw UninitializedParameter();
266 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
268 /// \ref named-templ-param "Named parameter" for setting PredMap type
272 : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
273 typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
277 struct DefDistMapTraits : public Traits {
279 static DistMap *createDistMap(const Graph& graph) {
280 throw UninitializedParameter();
284 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
287 /// \ref named-templ-param "Named parameter" for setting DistMap type
291 : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
292 typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
296 struct DefOperationTraitsTraits : public Traits {
297 typedef T OperationTraits;
300 /// \brief \ref named-templ-param "Named parameter" for setting
301 /// OperationTraits type
303 /// \ref named-templ-param "Named parameter" for setting OperationTraits
306 struct DefOperationTraits
307 : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
308 typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
320 /// \brief Constructor.
322 /// \param _graph the graph the algorithm will run on.
323 /// \param _length the length map used by the algorithm.
324 BellmanFord(const Graph& _graph, const LengthMap& _length) :
325 graph(&_graph), length(&_length),
326 _pred(0), local_pred(false),
327 _dist(0), local_dist(false) {}
331 if(local_pred) delete _pred;
332 if(local_dist) delete _dist;
336 /// \brief Sets the length map.
338 /// Sets the length map.
339 /// \return \c (*this)
340 BellmanFord &lengthMap(const LengthMap &m) {
345 /// \brief Sets the map storing the predecessor edges.
347 /// Sets the map storing the predecessor edges.
348 /// If you don't use this function before calling \ref run(),
349 /// it will allocate one. The destuctor deallocates this
350 /// automatically allocated map, of course.
351 /// \return \c (*this)
352 BellmanFord &predMap(PredMap &m) {
361 /// \brief Sets the map storing the distances calculated by the algorithm.
363 /// Sets the map storing the distances calculated by the algorithm.
364 /// If you don't use this function before calling \ref run(),
365 /// it will allocate one. The destuctor deallocates this
366 /// automatically allocated map, of course.
367 /// \return \c (*this)
368 BellmanFord &distMap(DistMap &m) {
377 /// \name Execution control
378 /// The simplest way to execute the algorithm is to use
379 /// one of the member functions called \c run(...).
381 /// If you need more control on the execution,
382 /// first you must call \ref init(), then you can add several source nodes
383 /// with \ref addSource().
384 /// Finally \ref start() will perform the actual path
389 /// \brief Initializes the internal data structures.
391 /// Initializes the internal data structures.
392 void init(const Value value = OperationTraits::infinity()) {
394 for (NodeIt it(*graph); it != INVALID; ++it) {
395 _pred->set(it, INVALID);
396 _dist->set(it, value);
399 if (OperationTraits::less(value, OperationTraits::infinity())) {
400 for (NodeIt it(*graph); it != INVALID; ++it) {
401 _process.push_back(it);
402 _mask->set(it, true);
407 /// \brief Adds a new source node.
409 /// The optional second parameter is the initial distance of the node.
410 /// It just sets the distance of the node to the given value.
411 void addSource(Node source, Value dst = OperationTraits::zero()) {
412 _dist->set(source, dst);
413 if (!(*_mask)[source]) {
414 _process.push_back(source);
415 _mask->set(source, true);
419 /// \brief Executes one round from the bellman ford algorithm.
421 /// If the algoritm calculated the distances in the previous round
422 /// strictly for all at most k length paths then it will calculate the
423 /// distances strictly for all at most k + 1 length paths. With k
424 /// iteration this function calculates the at most k length paths.
425 /// \return %True when the algorithm have not found more shorter paths.
426 bool processNextRound() {
427 for (int i = 0; i < (int)_process.size(); ++i) {
428 _mask->set(_process[i], false);
430 std::vector<Node> nextProcess;
431 std::vector<Value> values(_process.size());
432 for (int i = 0; i < (int)_process.size(); ++i) {
433 values[i] = (*_dist)[_process[i]];
435 for (int i = 0; i < (int)_process.size(); ++i) {
436 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
437 Node target = graph->target(it);
438 Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
439 if (OperationTraits::less(relaxed, (*_dist)[target])) {
440 _pred->set(target, it);
441 _dist->set(target, relaxed);
442 if (!(*_mask)[target]) {
443 _mask->set(target, true);
444 nextProcess.push_back(target);
449 _process.swap(nextProcess);
450 return _process.empty();
453 /// \brief Executes one weak round from the bellman ford algorithm.
455 /// If the algorithm calculated the distances in the
456 /// previous round at least for all at most k length paths then it will
457 /// calculate the distances at least for all at most k + 1 length paths.
458 /// This function does not make it possible to calculate strictly the
459 /// at most k length minimal paths, this is why it is
460 /// called just weak round.
461 /// \return %True when the algorithm have not found more shorter paths.
462 bool processNextWeakRound() {
463 for (int i = 0; i < (int)_process.size(); ++i) {
464 _mask->set(_process[i], false);
466 std::vector<Node> nextProcess;
467 for (int i = 0; i < (int)_process.size(); ++i) {
468 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
469 Node target = graph->target(it);
471 OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
472 if (OperationTraits::less(relaxed, (*_dist)[target])) {
473 _pred->set(target, it);
474 _dist->set(target, relaxed);
475 if (!(*_mask)[target]) {
476 _mask->set(target, true);
477 nextProcess.push_back(target);
482 _process.swap(nextProcess);
483 return _process.empty();
486 /// \brief Executes the algorithm.
488 /// \pre init() must be called and at least one node should be added
489 /// with addSource() before using this function.
491 /// This method runs the %BellmanFord algorithm from the root node(s)
492 /// in order to compute the shortest path to each node. The algorithm
494 /// - The shortest path tree.
495 /// - The distance of each node from the root(s).
497 int num = countNodes(*graph) - 1;
498 for (int i = 0; i < num; ++i) {
499 if (processNextWeakRound()) break;
503 /// \brief Executes the algorithm and checks the negative cycles.
505 /// \pre init() must be called and at least one node should be added
506 /// with addSource() before using this function. If there is
507 /// a negative cycles in the graph it gives back false.
509 /// This method runs the %BellmanFord algorithm from the root node(s)
510 /// in order to compute the shortest path to each node. The algorithm
512 /// - The shortest path tree.
513 /// - The distance of each node from the root(s).
514 bool checkedStart() {
515 int num = countNodes(*graph);
516 for (int i = 0; i < num; ++i) {
517 if (processNextWeakRound()) return true;
522 /// \brief Executes the algorithm with path length limit.
524 /// \pre init() must be called and at least one node should be added
525 /// with addSource() before using this function.
527 /// This method runs the %BellmanFord algorithm from the root node(s)
528 /// in order to compute the shortest path with at most \c length edge
529 /// long paths to each node. The algorithm computes
530 /// - The shortest path tree.
531 /// - The limited distance of each node from the root(s).
532 void limitedStart(int length) {
533 for (int i = 0; i < length; ++i) {
534 if (processNextRound()) break;
538 /// \brief Runs %BellmanFord algorithm from node \c s.
540 /// This method runs the %BellmanFord algorithm from a root node \c s
541 /// in order to compute the shortest path to each node. The algorithm
543 /// - The shortest path tree.
544 /// - The distance of each node from the root.
546 /// \note d.run(s) is just a shortcut of the following code.
558 /// \brief Runs %BellmanFord algorithm with limited path length
561 /// This method runs the %BellmanFord algorithm from a root node \c s
562 /// in order to compute the shortest path with at most \c len edges
563 /// to each node. The algorithm computes
564 /// - The shortest path tree.
565 /// - The distance of each node from the root.
567 /// \note d.run(s, len) is just a shortcut of the following code.
571 /// d.limitedStart(len);
573 void run(Node s, int len) {
581 /// \name Query Functions
582 /// The result of the %BellmanFord algorithm can be obtained using these
584 /// Before the use of these functions,
585 /// either run() or start() must be called.
589 /// \brief Copies the shortest path to \c t into \c p
591 /// This function copies the shortest path to \c t into \c p.
592 /// If it \c t is a source itself or unreachable, then it does not
595 /// \return Returns \c true if a path to \c t was actually copied to \c p,
596 /// \c false otherwise.
598 template <typename Path>
599 bool getPath(Path &p, Node t) {
602 typename Path::Builder b(p);
603 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
604 b.pushFront(predEdge(t));
611 /// \brief The distance of a node from the root.
613 /// Returns the distance of a node from the root.
614 /// \pre \ref run() must be called before using this function.
615 /// \warning If node \c v in unreachable from the root the return value
616 /// of this funcion is undefined.
617 Value dist(Node v) const { return (*_dist)[v]; }
619 /// \brief Returns the 'previous edge' of the shortest path tree.
621 /// For a node \c v it returns the 'previous edge' of the shortest path
622 /// tree, i.e. it returns the last edge of a shortest path from the root
623 /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
624 /// if \c v=s. The shortest path tree used here is equal to the shortest
625 /// path tree used in \ref predNode().
626 /// \pre \ref run() must be called before using
628 Edge predEdge(Node v) const { return (*_pred)[v]; }
630 /// \brief Returns the 'previous node' of the shortest path tree.
632 /// For a node \c v it returns the 'previous node' of the shortest path
633 /// tree, i.e. it returns the last but one node from a shortest path from
634 /// the root to \c /v. It is INVALID if \c v is unreachable from the root
635 /// or if \c v=s. The shortest path tree used here is equal to the
636 /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
637 /// called before using this function.
638 Node predNode(Node v) const {
639 return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
642 /// \brief Returns a reference to the NodeMap of distances.
644 /// Returns a reference to the NodeMap of distances. \pre \ref run() must
645 /// be called before using this function.
646 const DistMap &distMap() const { return *_dist;}
648 /// \brief Returns a reference to the shortest path tree map.
650 /// Returns a reference to the NodeMap of the edges of the
651 /// shortest path tree.
652 /// \pre \ref run() must be called before using this function.
653 const PredMap &predMap() const { return *_pred; }
655 /// \brief Checks if a node is reachable from the root.
657 /// Returns \c true if \c v is reachable from the root.
658 /// \pre \ref run() must be called before using this function.
660 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
665 /// \brief Default traits class of BellmanFord function.
667 /// Default traits class of BellmanFord function.
668 /// \param _Graph Graph type.
669 /// \param _LengthMap Type of length map.
670 template <typename _Graph, typename _LengthMap>
671 struct BellmanFordWizardDefaultTraits {
672 /// \brief The graph type the algorithm runs on.
673 typedef _Graph Graph;
675 /// \brief The type of the map that stores the edge lengths.
677 /// The type of the map that stores the edge lengths.
678 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
679 typedef _LengthMap LengthMap;
681 /// \brief The value type of the length map.
682 typedef typename _LengthMap::Value Value;
684 /// \brief Operation traits for bellman-ford algorithm.
686 /// It defines the infinity type on the given Value type
687 /// and the used operation.
688 /// \see BellmanFordDefaultOperationTraits
689 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
691 /// \brief The type of the map that stores the last
692 /// edges of the shortest paths.
694 /// The type of the map that stores the last
695 /// edges of the shortest paths.
696 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
697 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
699 /// \brief Instantiates a PredMap.
701 /// This function instantiates a \ref PredMap.
702 static PredMap *createPredMap(const _Graph &) {
703 return new PredMap();
705 /// \brief The type of the map that stores the dists of the nodes.
707 /// The type of the map that stores the dists of the nodes.
708 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
709 typedef NullMap<typename Graph::Node, Value> DistMap;
710 /// \brief Instantiates a DistMap.
712 /// This function instantiates a \ref DistMap.
713 static DistMap *createDistMap(const _Graph &) {
714 return new DistMap();
718 /// \brief Default traits used by \ref BellmanFordWizard
720 /// To make it easier to use BellmanFord algorithm
721 /// we have created a wizard class.
722 /// This \ref BellmanFordWizard class needs default traits,
723 /// as well as the \ref BellmanFord class.
724 /// The \ref BellmanFordWizardBase is a class to be the default traits of the
725 /// \ref BellmanFordWizard class.
726 /// \todo More named parameters are required...
727 template<class _Graph,class _LengthMap>
728 class BellmanFordWizardBase
729 : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
731 typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
733 /// Type of the nodes in the graph.
734 typedef typename Base::Graph::Node Node;
736 /// Pointer to the underlying graph.
738 /// Pointer to the length map
740 ///Pointer to the map of predecessors edges.
742 ///Pointer to the map of distances.
744 ///Pointer to the source node.
750 /// This constructor does not require parameters, therefore it initiates
751 /// all of the attributes to default values (0, INVALID).
752 BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
753 _dist(0), _source(INVALID) {}
757 /// This constructor requires some parameters,
758 /// listed in the parameters list.
759 /// Others are initiated to 0.
760 /// \param graph is the initial value of \ref _graph
761 /// \param length is the initial value of \ref _length
762 /// \param source is the initial value of \ref _source
763 BellmanFordWizardBase(const _Graph& graph,
764 const _LengthMap& length,
765 Node source = INVALID) :
766 _graph((void *)&graph), _length((void *)&length), _pred(0),
767 _dist(0), _source(source) {}
771 /// A class to make the usage of BellmanFord algorithm easier
773 /// This class is created to make it easier to use BellmanFord algorithm.
774 /// It uses the functions and features of the plain \ref BellmanFord,
775 /// but it is much simpler to use it.
777 /// Simplicity means that the way to change the types defined
778 /// in the traits class is based on functions that returns the new class
779 /// and not on templatable built-in classes.
780 /// When using the plain \ref BellmanFord
781 /// the new class with the modified type comes from
782 /// the original class by using the ::
783 /// operator. In the case of \ref BellmanFordWizard only
784 /// a function have to be called and it will
785 /// return the needed class.
787 /// It does not have own \ref run method. When its \ref run method is called
788 /// it initiates a plain \ref BellmanFord class, and calls the \ref
789 /// BellmanFord::run method of it.
790 template<class _Traits>
791 class BellmanFordWizard : public _Traits {
792 typedef _Traits Base;
794 ///The type of the underlying graph.
795 typedef typename _Traits::Graph Graph;
797 typedef typename Graph::Node Node;
798 typedef typename Graph::NodeIt NodeIt;
799 typedef typename Graph::Edge Edge;
800 typedef typename Graph::OutEdgeIt EdgeIt;
802 ///The type of the map that stores the edge lengths.
803 typedef typename _Traits::LengthMap LengthMap;
805 ///The type of the length of the edges.
806 typedef typename LengthMap::Value Value;
808 ///\brief The type of the map that stores the last
809 ///edges of the shortest paths.
810 typedef typename _Traits::PredMap PredMap;
812 ///The type of the map that stores the dists of the nodes.
813 typedef typename _Traits::DistMap DistMap;
817 BellmanFordWizard() : _Traits() {}
819 /// \brief Constructor that requires parameters.
821 /// Constructor that requires parameters.
822 /// These parameters will be the default values for the traits class.
823 BellmanFordWizard(const Graph& graph, const LengthMap& length,
824 Node source = INVALID)
825 : _Traits(graph, length, source) {}
827 /// \brief Copy constructor
828 BellmanFordWizard(const _Traits &b) : _Traits(b) {}
830 ~BellmanFordWizard() {}
832 /// \brief Runs BellmanFord algorithm from a given node.
834 /// Runs BellmanFord algorithm from a given node.
835 /// The node can be given by the \ref source function.
837 if(Base::_source == INVALID) throw UninitializedParameter();
838 BellmanFord<Graph,LengthMap,_Traits>
839 bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
840 if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
841 if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
842 bf.run(Base::_source);
845 /// \brief Runs BellmanFord algorithm from the given node.
847 /// Runs BellmanFord algorithm from the given node.
848 /// \param source is the given source.
849 void run(Node source) {
850 Base::_source = source;
855 struct DefPredMapBase : public Base {
857 static PredMap *createPredMap(const Graph &) { return 0; };
858 DefPredMapBase(const _Traits &b) : _Traits(b) {}
861 ///\brief \ref named-templ-param "Named parameter"
862 ///function for setting PredMap type
864 /// \ref named-templ-param "Named parameter"
865 ///function for setting PredMap type
868 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
870 Base::_pred=(void *)&t;
871 return BellmanFordWizard<DefPredMapBase<T> >(*this);
875 struct DefDistMapBase : public Base {
877 static DistMap *createDistMap(const Graph &) { return 0; };
878 DefDistMapBase(const _Traits &b) : _Traits(b) {}
881 ///\brief \ref named-templ-param "Named parameter"
882 ///function for setting DistMap type
884 /// \ref named-templ-param "Named parameter"
885 ///function for setting DistMap type
888 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
889 Base::_dist=(void *)&t;
890 return BellmanFordWizard<DefDistMapBase<T> >(*this);
894 struct DefOperationTraitsBase : public Base {
895 typedef T OperationTraits;
896 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
899 ///\brief \ref named-templ-param "Named parameter"
900 ///function for setting OperationTraits type
902 /// \ref named-templ-param "Named parameter"
903 ///function for setting OperationTraits type
906 BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
907 return BellmanFordWizard<DefDistMapBase<T> >(*this);
910 /// \brief Sets the source node, from which the BellmanFord algorithm runs.
912 /// Sets the source node, from which the BellmanFord algorithm runs.
913 /// \param source is the source node.
914 BellmanFordWizard<_Traits>& source(Node source) {
915 Base::_source = source;
921 /// \brief Function type interface for BellmanFord algorithm.
923 /// \ingroup flowalgs
924 /// Function type interface for BellmanFord algorithm.
926 /// This function also has several \ref named-templ-func-param
927 /// "named parameters", they are declared as the members of class
928 /// \ref BellmanFordWizard.
930 /// example shows how to use these parameters.
932 /// bellmanford(g,length,source).predMap(preds).run();
934 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
935 /// to the end of the parameter list.
936 /// \sa BellmanFordWizard
938 template<class _Graph, class _LengthMap>
939 BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
940 bellmanFord(const _Graph& graph,
941 const _LengthMap& length,
942 typename _Graph::Node source = INVALID) {
943 return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
944 (graph, length, source);
947 } //END OF NAMESPACE LEMON