NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/belmann_ford.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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 BelmannFord 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 BelmannFord algorithm class.
36 /// It defines all computational operations and constants which are
37 /// used in the belmann 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 BelmannFordDefaultOperationTraits {
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 BelmannFordDefaultOperationTraits<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 BelmannFord class.
82 /// Default traits class of BelmannFord class.
83 /// \param _Graph Graph type.
84 /// \param _LegthMap Type of length map.
85 template<class _Graph, class _LengthMap>
86 struct BelmannFordDefaultTraits {
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 belmann-ford algorithm.
101 /// It defines the infinity type on the given Value type
102 /// and the used operation.
103 /// \see BelmannFordDefaultOperationTraits
104 typedef BelmannFordDefaultOperationTraits<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 G is the graph, to which we would like to define the PredMap.
119 /// \todo The graph alone may be insufficient for the initialization
120 static PredMap *createPredMap(const _Graph& graph) {
121 return new PredMap(graph);
124 /// \brief The type of the map that stores the dists of the nodes.
126 /// The type of the map that stores the dists of the nodes.
127 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
129 typedef typename Graph::template NodeMap<typename _LengthMap::Value>
132 /// \brief Instantiates a DistMap.
134 /// This function instantiates a \ref DistMap.
135 /// \param G is the graph, to which we would like to define the
137 static DistMap *createDistMap(const _Graph& graph) {
138 return new DistMap(graph);
143 /// \brief %BelmannFord algorithm class.
145 /// \ingroup flowalgs
146 /// This class provides an efficient implementation of \c Belmann-Ford
147 /// algorithm. The edge lengths are passed to the algorithm using a
148 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
151 /// The Belmann-Ford algorithm solves the shortest path from one node
152 /// problem when the edges can have negative length but the graph should
153 /// not contain cycles with negative sum of length. If we can assume
154 /// that all edge is non-negative in the graph then the dijkstra algorithm
155 /// should be used rather.
157 /// The complexity of the algorithm is O(n * e).
159 /// The type of the length is determined by the
160 /// \ref concept::ReadMap::Value "Value" of the length map.
162 /// \param _Graph The graph type the algorithm runs on. The default value
163 /// is \ref ListGraph. The value of _Graph is not used directly by
164 /// BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
165 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
166 /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
167 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
168 /// by BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
169 /// \param _Traits Traits class to set various data types used by the
170 /// algorithm. The default traits class is \ref BelmannFordDefaultTraits
171 /// "BelmannFordDefaultTraits<_Graph,_LengthMap>". See \ref
172 /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits
175 /// \author Balazs Dezso
178 template <typename _Graph, typename _LengthMap, typename _Traits>
180 template <typename _Graph=ListGraph,
181 typename _LengthMap=typename _Graph::template EdgeMap<int>,
182 typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
187 /// \brief \ref Exception for uninitialized parameters.
189 /// This error represents problems in the initialization
190 /// of the parameters of the algorithms.
192 class UninitializedParameter : public lemon::UninitializedParameter {
194 virtual const char* exceptionName() const {
195 return "lemon::BelmannFord::UninitializedParameter";
199 typedef _Traits Traits;
200 ///The type of the underlying graph.
201 typedef typename _Traits::Graph Graph;
203 typedef typename Graph::Node Node;
204 typedef typename Graph::NodeIt NodeIt;
205 typedef typename Graph::Edge Edge;
206 typedef typename Graph::OutEdgeIt OutEdgeIt;
208 /// \brief The type of the length of the edges.
209 typedef typename _Traits::LengthMap::Value Value;
210 /// \brief The type of the map that stores the edge lengths.
211 typedef typename _Traits::LengthMap LengthMap;
212 /// \brief The type of the map that stores the last
213 /// edges of the shortest paths.
214 typedef typename _Traits::PredMap PredMap;
215 /// \brief The type of the map that stores the dists of the nodes.
216 typedef typename _Traits::DistMap DistMap;
217 /// \brief The operation traits.
218 typedef typename _Traits::OperationTraits OperationTraits;
220 /// Pointer to the underlying graph.
222 /// Pointer to the length map
223 const LengthMap *length;
224 ///Pointer to the map of predecessors edges.
226 ///Indicates if \ref _pred is locally allocated (\c true) or not.
228 ///Pointer to the map of distances.
230 ///Indicates if \ref _dist is locally allocated (\c true) or not.
233 typedef typename Graph::template NodeMap<bool> MaskMap;
236 std::vector<Node> _process;
238 /// Creates the maps if necessary.
242 _pred = Traits::createPredMap(*graph);
246 _dist = Traits::createDistMap(*graph);
248 _mask = new MaskMap(*graph, false);
253 typedef BelmannFord Create;
255 /// \name Named template parameters
260 struct DefPredMapTraits : public Traits {
262 static PredMap *createPredMap(const Graph&) {
263 throw UninitializedParameter();
267 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
269 /// \ref named-templ-param "Named parameter" for setting PredMap type
273 typedef BelmannFord< 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 BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
292 typedef BelmannFord< 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 BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
308 typedef BelmannFord< 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 BelmannFord(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 BelmannFord &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 BelmannFord &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 BelmannFord &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 belmann 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 ///\todo what is the return value?
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 belmann 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 ///\todo what is the return value?
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 %BelmannFord 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 %BelmannFord 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 %BelmannFord 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 %BelmannFord algorithm from node \c s.
540 /// This method runs the %BelmannFord 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.
560 /// \name Query Functions
561 /// The result of the %BelmannFord algorithm can be obtained using these
563 /// Before the use of these functions,
564 /// either run() or start() must be called.
568 /// \brief Copies the shortest path to \c t into \c p
570 /// This function copies the shortest path to \c t into \c p.
571 /// If it \c t is a source itself or unreachable, then it does not
574 /// \return Returns \c true if a path to \c t was actually copied to \c p,
575 /// \c false otherwise.
577 template <typename Path>
578 bool getPath(Path &p, Node t) {
581 typename Path::Builder b(p);
582 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
583 b.pushFront(predEdge(t));
590 /// \brief The distance of a node from the root.
592 /// Returns the distance of a node from the root.
593 /// \pre \ref run() must be called before using this function.
594 /// \warning If node \c v in unreachable from the root the return value
595 /// of this funcion is undefined.
596 Value dist(Node v) const { return (*_dist)[v]; }
598 /// \brief Returns the 'previous edge' of the shortest path tree.
600 /// For a node \c v it returns the 'previous edge' of the shortest path
601 /// tree, i.e. it returns the last edge of a shortest path from the root
602 /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
603 /// if \c v=s. The shortest path tree used here is equal to the shortest
604 /// path tree used in \ref predNode().
605 /// \pre \ref run() must be called before using
607 Edge predEdge(Node v) const { return (*_pred)[v]; }
609 /// \brief Returns the 'previous node' of the shortest path tree.
611 /// For a node \c v it returns the 'previous node' of the shortest path
612 /// tree, i.e. it returns the last but one node from a shortest path from
613 /// the root to \c /v. It is INVALID if \c v is unreachable from the root
614 /// or if \c v=s. The shortest path tree used here is equal to the
615 /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
616 /// called before using this function.
617 Node predNode(Node v) const {
618 return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
621 /// \brief Returns a reference to the NodeMap of distances.
623 /// Returns a reference to the NodeMap of distances. \pre \ref run() must
624 /// be called before using this function.
625 const DistMap &distMap() const { return *_dist;}
627 /// \brief Returns a reference to the shortest path tree map.
629 /// Returns a reference to the NodeMap of the edges of the
630 /// shortest path tree.
631 /// \pre \ref run() must be called before using this function.
632 const PredMap &predMap() const { return *_pred; }
634 /// \brief Checks if a node is reachable from the root.
636 /// Returns \c true if \c v is reachable from the root.
637 /// \pre \ref run() must be called before using this function.
639 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
644 /// \brief Default traits class of BelmannFord function.
646 /// Default traits class of BelmannFord function.
647 /// \param _Graph Graph type.
648 /// \param _LengthMap Type of length map.
649 template <typename _Graph, typename _LengthMap>
650 struct BelmannFordWizardDefaultTraits {
651 /// \brief The graph type the algorithm runs on.
652 typedef _Graph Graph;
654 /// \brief The type of the map that stores the edge lengths.
656 /// The type of the map that stores the edge lengths.
657 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
658 typedef _LengthMap LengthMap;
660 /// \brief The value type of the length map.
661 typedef typename _LengthMap::Value Value;
663 /// \brief Operation traits for belmann-ford algorithm.
665 /// It defines the infinity type on the given Value type
666 /// and the used operation.
667 /// \see BelmannFordDefaultOperationTraits
668 typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
670 /// \brief The type of the map that stores the last
671 /// edges of the shortest paths.
673 /// The type of the map that stores the last
674 /// edges of the shortest paths.
675 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
676 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
678 /// \brief Instantiates a PredMap.
680 /// This function instantiates a \ref PredMap.
681 static PredMap *createPredMap(const _Graph &) {
682 return new PredMap();
684 /// \brief The type of the map that stores the dists of the nodes.
686 /// The type of the map that stores the dists of the nodes.
687 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
688 typedef NullMap<typename Graph::Node, Value> DistMap;
689 /// \brief Instantiates a DistMap.
691 /// This function instantiates a \ref DistMap.
692 static DistMap *createDistMap(const _Graph &) {
693 return new DistMap();
697 /// \brief Default traits used by \ref BelmannFordWizard
699 /// To make it easier to use BelmannFord algorithm
700 /// we have created a wizard class.
701 /// This \ref BelmannFordWizard class needs default traits,
702 /// as well as the \ref BelmannFord class.
703 /// The \ref BelmannFordWizardBase is a class to be the default traits of the
704 /// \ref BelmannFordWizard class.
705 /// \todo More named parameters are required...
706 template<class _Graph,class _LengthMap>
707 class BelmannFordWizardBase
708 : public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> {
710 typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base;
712 /// Type of the nodes in the graph.
713 typedef typename Base::Graph::Node Node;
715 /// Pointer to the underlying graph.
717 /// Pointer to the length map
719 ///Pointer to the map of predecessors edges.
721 ///Pointer to the map of distances.
723 ///Pointer to the source node.
729 /// This constructor does not require parameters, therefore it initiates
730 /// all of the attributes to default values (0, INVALID).
731 BelmannFordWizardBase() : _graph(0), _length(0), _pred(0),
732 _dist(0), _source(INVALID) {}
736 /// This constructor requires some parameters,
737 /// listed in the parameters list.
738 /// Others are initiated to 0.
739 /// \param graph is the initial value of \ref _graph
740 /// \param length is the initial value of \ref _length
741 /// \param source is the initial value of \ref _source
742 BelmannFordWizardBase(const _Graph& graph,
743 const _LengthMap& length,
744 Node source = INVALID) :
745 _graph((void *)&graph), _length((void *)&length), _pred(0),
746 _dist(0), _source(source) {}
750 /// A class to make the usage of BelmannFord algorithm easier
752 /// This class is created to make it easier to use BelmannFord algorithm.
753 /// It uses the functions and features of the plain \ref BelmannFord,
754 /// but it is much simpler to use it.
756 /// Simplicity means that the way to change the types defined
757 /// in the traits class is based on functions that returns the new class
758 /// and not on templatable built-in classes.
759 /// When using the plain \ref BelmannFord
760 /// the new class with the modified type comes from
761 /// the original class by using the ::
762 /// operator. In the case of \ref BelmannFordWizard only
763 /// a function have to be called and it will
764 /// return the needed class.
766 /// It does not have own \ref run method. When its \ref run method is called
767 /// it initiates a plain \ref BelmannFord class, and calls the \ref
768 /// BelmannFord::run method of it.
769 template<class _Traits>
770 class BelmannFordWizard : public _Traits {
771 typedef _Traits Base;
773 ///The type of the underlying graph.
774 typedef typename _Traits::Graph Graph;
776 typedef typename Graph::Node Node;
777 typedef typename Graph::NodeIt NodeIt;
778 typedef typename Graph::Edge Edge;
779 typedef typename Graph::OutEdgeIt EdgeIt;
781 ///The type of the map that stores the edge lengths.
782 typedef typename _Traits::LengthMap LengthMap;
784 ///The type of the length of the edges.
785 typedef typename LengthMap::Value Value;
787 ///\brief The type of the map that stores the last
788 ///edges of the shortest paths.
789 typedef typename _Traits::PredMap PredMap;
791 ///The type of the map that stores the dists of the nodes.
792 typedef typename _Traits::DistMap DistMap;
796 BelmannFordWizard() : _Traits() {}
798 /// \brief Constructor that requires parameters.
800 /// Constructor that requires parameters.
801 /// These parameters will be the default values for the traits class.
802 BelmannFordWizard(const Graph& graph, const LengthMap& length,
803 Node source = INVALID)
804 : _Traits(graph, length, source) {}
806 /// \brief Copy constructor
807 BelmannFordWizard(const _Traits &b) : _Traits(b) {}
809 ~BelmannFordWizard() {}
811 /// \brief Runs BelmannFord algorithm from a given node.
813 /// Runs BelmannFord algorithm from a given node.
814 /// The node can be given by the \ref source function.
816 if(Base::_source == INVALID) throw UninitializedParameter();
817 BelmannFord<Graph,LengthMap,_Traits>
818 bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
819 if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
820 if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
821 bf.run(Base::_source);
824 /// \brief Runs BelmannFord algorithm from the given node.
826 /// Runs BelmannFord algorithm from the given node.
827 /// \param s is the given source.
828 void run(Node source) {
829 Base::_source = source;
834 struct DefPredMapBase : public Base {
836 static PredMap *createPredMap(const Graph &) { return 0; };
837 DefPredMapBase(const _Traits &b) : _Traits(b) {}
840 ///\brief \ref named-templ-param "Named parameter"
841 ///function for setting PredMap type
843 /// \ref named-templ-param "Named parameter"
844 ///function for setting PredMap type
847 BelmannFordWizard<DefPredMapBase<T> > predMap(const T &t)
849 Base::_pred=(void *)&t;
850 return BelmannFordWizard<DefPredMapBase<T> >(*this);
854 struct DefDistMapBase : public Base {
856 static DistMap *createDistMap(const Graph &) { return 0; };
857 DefDistMapBase(const _Traits &b) : _Traits(b) {}
860 ///\brief \ref named-templ-param "Named parameter"
861 ///function for setting DistMap type
863 /// \ref named-templ-param "Named parameter"
864 ///function for setting DistMap type
867 BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) {
868 Base::_dist=(void *)&t;
869 return BelmannFordWizard<DefDistMapBase<T> >(*this);
873 struct DefOperationTraitsBase : public Base {
874 typedef T OperationTraits;
875 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
878 ///\brief \ref named-templ-param "Named parameter"
879 ///function for setting OperationTraits type
881 /// \ref named-templ-param "Named parameter"
882 ///function for setting OperationTraits type
885 BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
886 return BelmannFordWizard<DefDistMapBase<T> >(*this);
889 /// \brief Sets the source node, from which the BelmannFord algorithm runs.
891 /// Sets the source node, from which the BelmannFord algorithm runs.
892 /// \param s is the source node.
893 BelmannFordWizard<_Traits>& source(Node source) {
894 Base::_source = source;
900 /// \brief Function type interface for BelmannFord algorithm.
902 /// \ingroup flowalgs
903 /// Function type interface for BelmannFord algorithm.
905 /// This function also has several \ref named-templ-func-param
906 /// "named parameters", they are declared as the members of class
907 /// \ref BelmannFordWizard.
909 /// example shows how to use these parameters.
911 /// belmannford(g,length,source).predMap(preds).run();
913 /// \warning Don't forget to put the \ref BelmannFordWizard::run() "run()"
914 /// to the end of the parameter list.
915 /// \sa BelmannFordWizard
917 template<class _Graph, class _LengthMap>
918 BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
919 belmannFord(const _Graph& graph,
920 const _LengthMap& length,
921 typename _Graph::Node source = INVALID) {
922 return BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
923 (graph, length, source);
926 } //END OF NAMESPACE LEMON