Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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
22 /// \ingroup shortest_path
24 /// \brief BellmanFord algorithm.
27 #include <lemon/list_graph.h>
28 #include <lemon/bits/path_dump.h>
29 #include <lemon/bits/invalid.h>
30 #include <lemon/graph_utils.h>
31 #include <lemon/error.h>
32 #include <lemon/maps.h>
38 /// \brief Default OperationTraits for the BellmanFord algorithm class.
40 /// It defines all computational operations and constants which are
41 /// used in the Bellman-Ford algorithm. The default implementation
42 /// is based on the numeric_limits class. If the numeric type does not
43 /// have infinity value then the maximum value is used as extremal
47 bool has_infinity = std::numeric_limits<Value>::has_infinity>
48 struct BellmanFordDefaultOperationTraits {
49 /// \brief Gives back the zero value of the type.
51 return static_cast<Value>(0);
53 /// \brief Gives back the positive infinity value of the type.
54 static Value infinity() {
55 return std::numeric_limits<Value>::infinity();
57 /// \brief Gives back the sum of the given two elements.
58 static Value plus(const Value& left, const Value& right) {
61 /// \brief Gives back true only if the first value less than the second.
62 static bool less(const Value& left, const Value& right) {
67 template <typename Value>
68 struct BellmanFordDefaultOperationTraits<Value, false> {
70 return static_cast<Value>(0);
72 static Value infinity() {
73 return std::numeric_limits<Value>::max();
75 static Value plus(const Value& left, const Value& right) {
76 if (left == infinity() || right == infinity()) return infinity();
79 static bool less(const Value& left, const Value& right) {
84 /// \brief Default traits class of BellmanFord class.
86 /// Default traits class of BellmanFord class.
87 /// \param _Graph Graph type.
88 /// \param _LegthMap Type of length map.
89 template<class _Graph, class _LengthMap>
90 struct BellmanFordDefaultTraits {
91 /// The graph type the algorithm runs on.
94 /// \brief The type of the map that stores the edge lengths.
96 /// The type of the map that stores the edge lengths.
97 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
98 typedef _LengthMap LengthMap;
100 // The type of the length of the edges.
101 typedef typename _LengthMap::Value Value;
103 /// \brief Operation traits for Bellman-Ford algorithm.
105 /// It defines the infinity type on the given Value type
106 /// and the used operation.
107 /// \see BellmanFordDefaultOperationTraits
108 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
110 /// \brief The type of the map that stores the last edges of the
113 /// The type of the map that stores the last
114 /// edges of the shortest paths.
115 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
117 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
119 /// \brief Instantiates a PredMap.
121 /// This function instantiates a \ref PredMap.
122 /// \param graph is the graph, to which we would like to define the PredMap.
123 static PredMap *createPredMap(const _Graph& graph) {
124 return new PredMap(graph);
127 /// \brief The type of the map that stores the dists of the nodes.
129 /// The type of the map that stores the dists of the nodes.
130 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
132 typedef typename Graph::template NodeMap<typename _LengthMap::Value>
135 /// \brief Instantiates a DistMap.
137 /// This function instantiates a \ref DistMap.
138 /// \param graph is the graph, to which we would like to define the
140 static DistMap *createDistMap(const _Graph& graph) {
141 return new DistMap(graph);
146 /// \brief %BellmanFord algorithm class.
148 /// \ingroup shortest_path
149 /// This class provides an efficient implementation of \c Bellman-Ford
150 /// algorithm. The edge lengths are passed to the algorithm using a
151 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
154 /// The Bellman-Ford algorithm solves the shortest path from one node
155 /// problem when the edges can have negative length but the graph should
156 /// not contain cycles with negative sum of length. If we can assume
157 /// that all edge is non-negative in the graph then the dijkstra algorithm
158 /// should be used rather.
160 /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
162 /// The type of the length is determined by the
163 /// \ref concepts::ReadMap::Value "Value" of the length map.
165 /// \param _Graph The graph type the algorithm runs on. The default value
166 /// is \ref ListGraph. The value of _Graph is not used directly by
167 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
168 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
169 /// edges. The default map type is \ref concepts::Graph::EdgeMap
170 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
171 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
172 /// \param _Traits Traits class to set various data types used by the
173 /// algorithm. The default traits class is \ref BellmanFordDefaultTraits
174 /// "BellmanFordDefaultTraits<_Graph,_LengthMap>". See \ref
175 /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
178 /// \author Balazs Dezso
181 template <typename _Graph, typename _LengthMap, typename _Traits>
183 template <typename _Graph=ListGraph,
184 typename _LengthMap=typename _Graph::template EdgeMap<int>,
185 typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
190 /// \brief \ref Exception for uninitialized parameters.
192 /// This error represents problems in the initialization
193 /// of the parameters of the algorithms.
195 class UninitializedParameter : public lemon::UninitializedParameter {
197 virtual const char* what() const throw() {
198 return "lemon::BellmanFord::UninitializedParameter";
202 typedef _Traits Traits;
203 ///The type of the underlying graph.
204 typedef typename _Traits::Graph Graph;
206 typedef typename Graph::Node Node;
207 typedef typename Graph::NodeIt NodeIt;
208 typedef typename Graph::Edge Edge;
209 typedef typename Graph::OutEdgeIt OutEdgeIt;
211 /// \brief The type of the length of the edges.
212 typedef typename _Traits::LengthMap::Value Value;
213 /// \brief The type of the map that stores the edge lengths.
214 typedef typename _Traits::LengthMap LengthMap;
215 /// \brief The type of the map that stores the last
216 /// edges of the shortest paths.
217 typedef typename _Traits::PredMap PredMap;
218 /// \brief The type of the map that stores the dists of the nodes.
219 typedef typename _Traits::DistMap DistMap;
220 /// \brief The operation traits.
221 typedef typename _Traits::OperationTraits OperationTraits;
223 /// Pointer to the underlying graph.
225 /// Pointer to the length map
226 const LengthMap *length;
227 ///Pointer to the map of predecessors edges.
229 ///Indicates if \ref _pred is locally allocated (\c true) or not.
231 ///Pointer to the map of distances.
233 ///Indicates if \ref _dist is locally allocated (\c true) or not.
236 typedef typename Graph::template NodeMap<bool> MaskMap;
239 std::vector<Node> _process;
241 /// Creates the maps if necessary.
245 _pred = Traits::createPredMap(*graph);
249 _dist = Traits::createDistMap(*graph);
251 _mask = new MaskMap(*graph, false);
256 typedef BellmanFord Create;
258 /// \name Named template parameters
263 struct DefPredMapTraits : public Traits {
265 static PredMap *createPredMap(const Graph&) {
266 throw UninitializedParameter();
270 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
272 /// \ref named-templ-param "Named parameter" for setting PredMap type
276 : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
277 typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
281 struct DefDistMapTraits : public Traits {
283 static DistMap *createDistMap(const Graph&) {
284 throw UninitializedParameter();
288 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
291 /// \ref named-templ-param "Named parameter" for setting DistMap type
295 : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
296 typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
300 struct DefOperationTraitsTraits : public Traits {
301 typedef T OperationTraits;
304 /// \brief \ref named-templ-param "Named parameter" for setting
305 /// OperationTraits type
307 /// \ref named-templ-param "Named parameter" for setting OperationTraits
310 struct DefOperationTraits
311 : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
312 typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
324 /// \brief Constructor.
326 /// \param _graph the graph the algorithm will run on.
327 /// \param _length the length map used by the algorithm.
328 BellmanFord(const Graph& _graph, const LengthMap& _length) :
329 graph(&_graph), length(&_length),
330 _pred(0), local_pred(false),
331 _dist(0), local_dist(false), _mask(0) {}
335 if(local_pred) delete _pred;
336 if(local_dist) delete _dist;
337 if(_mask) delete _mask;
340 /// \brief Sets the length map.
342 /// Sets the length map.
343 /// \return \c (*this)
344 BellmanFord &lengthMap(const LengthMap &m) {
349 /// \brief Sets the map storing the predecessor edges.
351 /// Sets the map storing the predecessor edges.
352 /// If you don't use this function before calling \ref run(),
353 /// it will allocate one. The destuctor deallocates this
354 /// automatically allocated map, of course.
355 /// \return \c (*this)
356 BellmanFord &predMap(PredMap &m) {
365 /// \brief Sets the map storing the distances calculated by the algorithm.
367 /// Sets the map storing the distances calculated by the algorithm.
368 /// If you don't use this function before calling \ref run(),
369 /// it will allocate one. The destuctor deallocates this
370 /// automatically allocated map, of course.
371 /// \return \c (*this)
372 BellmanFord &distMap(DistMap &m) {
381 /// \name Execution control
382 /// The simplest way to execute the algorithm is to use
383 /// one of the member functions called \c run(...).
385 /// If you need more control on the execution,
386 /// first you must call \ref init(), then you can add several source nodes
387 /// with \ref addSource().
388 /// Finally \ref start() will perform the actual path
393 /// \brief Initializes the internal data structures.
395 /// Initializes the internal data structures.
396 void init(const Value value = OperationTraits::infinity()) {
398 for (NodeIt it(*graph); it != INVALID; ++it) {
399 _pred->set(it, INVALID);
400 _dist->set(it, value);
403 if (OperationTraits::less(value, OperationTraits::infinity())) {
404 for (NodeIt it(*graph); it != INVALID; ++it) {
405 _process.push_back(it);
406 _mask->set(it, true);
411 /// \brief Adds a new source node.
413 /// Adds a new source node. The optional second parameter is the
414 /// initial distance of the node. It just sets the distance of the
415 /// node to the given value.
416 void addSource(Node source, Value dst = OperationTraits::zero()) {
417 _dist->set(source, dst);
418 if (!(*_mask)[source]) {
419 _process.push_back(source);
420 _mask->set(source, true);
424 /// \brief Executes one round from the Bellman-Ford algorithm.
426 /// If the algoritm calculated the distances in the previous round
427 /// exactly for all at most \f$ k \f$ length path lengths then it will
428 /// calculate the distances exactly for all at most \f$ k + 1 \f$
429 /// length path lengths. With \f$ k \f$ iteration this function
430 /// calculates the at most \f$ k \f$ length path lengths.
432 /// \warning The paths with limited edge number cannot be retrieved
433 /// easily with \ref path() or \ref predEdge() functions. If you
434 /// need the shortest path and not just the distance you should store
435 /// after each iteration the \ref predMap() map and manually build
438 /// \return \c true when the algorithm have not found more shorter
440 bool processNextRound() {
441 for (int i = 0; i < int(_process.size()); ++i) {
442 _mask->set(_process[i], false);
444 std::vector<Node> nextProcess;
445 std::vector<Value> values(_process.size());
446 for (int i = 0; i < int(_process.size()); ++i) {
447 values[i] = (*_dist)[_process[i]];
449 for (int i = 0; i < int(_process.size()); ++i) {
450 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
451 Node target = graph->target(it);
452 Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
453 if (OperationTraits::less(relaxed, (*_dist)[target])) {
454 _pred->set(target, it);
455 _dist->set(target, relaxed);
456 if (!(*_mask)[target]) {
457 _mask->set(target, true);
458 nextProcess.push_back(target);
463 _process.swap(nextProcess);
464 return _process.empty();
467 /// \brief Executes one weak round from the Bellman-Ford algorithm.
469 /// If the algorithm calculated the distances in the
470 /// previous round at least for all at most k length paths then it will
471 /// calculate the distances at least for all at most k + 1 length paths.
472 /// This function does not make it possible to calculate strictly the
473 /// at most k length minimal paths, this is why it is
474 /// called just weak round.
475 /// \return \c true when the algorithm have not found more shorter paths.
476 bool processNextWeakRound() {
477 for (int i = 0; i < int(_process.size()); ++i) {
478 _mask->set(_process[i], false);
480 std::vector<Node> nextProcess;
481 for (int i = 0; i < int(_process.size()); ++i) {
482 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
483 Node target = graph->target(it);
485 OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
486 if (OperationTraits::less(relaxed, (*_dist)[target])) {
487 _pred->set(target, it);
488 _dist->set(target, relaxed);
489 if (!(*_mask)[target]) {
490 _mask->set(target, true);
491 nextProcess.push_back(target);
496 _process.swap(nextProcess);
497 return _process.empty();
500 /// \brief Executes the algorithm.
502 /// \pre init() must be called and at least one node should be added
503 /// with addSource() before using this function.
505 /// This method runs the %BellmanFord algorithm from the root node(s)
506 /// in order to compute the shortest path to each node. The algorithm
508 /// - The shortest path tree.
509 /// - The distance of each node from the root(s).
511 int num = countNodes(*graph) - 1;
512 for (int i = 0; i < num; ++i) {
513 if (processNextWeakRound()) break;
517 /// \brief Executes the algorithm and checks the negative cycles.
519 /// \pre init() must be called and at least one node should be added
520 /// with addSource() before using this function.
522 /// This method runs the %BellmanFord algorithm from the root node(s)
523 /// in order to compute the shortest path to each node. The algorithm
525 /// - The shortest path tree.
526 /// - The distance of each node from the root(s).
528 /// \return \c false if there is a negative cycle in the graph.
529 bool checkedStart() {
530 int num = countNodes(*graph);
531 for (int i = 0; i < num; ++i) {
532 if (processNextWeakRound()) return true;
534 return _process.empty();
537 /// \brief Executes the algorithm with path length limit.
539 /// \pre init() must be called and at least one node should be added
540 /// with addSource() before using this function.
542 /// This method runs the %BellmanFord algorithm from the root
543 /// node(s) in order to compute the shortest path lengths with at
544 /// most \c num edge.
546 /// \warning The paths with limited edge number cannot be retrieved
547 /// easily with \ref path() or \ref predEdge() functions. If you
548 /// need the shortest path and not just the distance you should store
549 /// after each iteration the \ref predMap() map and manually build
552 /// The algorithm computes
553 /// - The predecessor edge from each node.
554 /// - The limited distance of each node from the root(s).
555 void limitedStart(int num) {
556 for (int i = 0; i < num; ++i) {
557 if (processNextRound()) break;
561 /// \brief Runs %BellmanFord algorithm from node \c s.
563 /// This method runs the %BellmanFord algorithm from a root node \c s
564 /// in order to compute the shortest path to each node. The algorithm
566 /// - The shortest path tree.
567 /// - The distance of each node from the root.
569 /// \note d.run(s) is just a shortcut of the following code.
581 /// \brief Runs %BellmanFord algorithm with limited path length
584 /// This method runs the %BellmanFord algorithm from a root node \c s
585 /// in order to compute the shortest path with at most \c len edges
586 /// to each node. The algorithm computes
587 /// - The shortest path tree.
588 /// - The distance of each node from the root.
590 /// \note d.run(s, num) is just a shortcut of the following code.
594 /// d.limitedStart(num);
596 void run(Node s, int num) {
604 /// \name Query Functions
605 /// The result of the %BellmanFord algorithm can be obtained using these
607 /// Before the use of these functions,
608 /// either run() or start() must be called.
612 /// \brief Lemon iterator for get the active nodes.
614 /// Lemon iterator for get the active nodes. This class provides a
615 /// common style lemon iterator which gives back a subset of the
616 /// nodes. The iterated nodes are active in the algorithm after
617 /// the last phase so these should be checked in the next phase to
618 /// find augmenting edges from these.
622 /// \brief Constructor.
624 /// Constructor for get the nodeset of the variable.
625 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
627 _index = _algorithm->_process.size() - 1;
630 /// \brief Invalid constructor.
632 /// Invalid constructor.
633 ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
635 /// \brief Conversion to node.
637 /// Conversion to node.
638 operator Node() const {
639 return _index >= 0 ? _algorithm->_process[_index] : INVALID;
642 /// \brief Increment operator.
644 /// Increment operator.
645 ActiveIt& operator++() {
650 bool operator==(const ActiveIt& it) const {
651 return static_cast<Node>(*this) == static_cast<Node>(it);
653 bool operator!=(const ActiveIt& it) const {
654 return static_cast<Node>(*this) != static_cast<Node>(it);
656 bool operator<(const ActiveIt& it) const {
657 return static_cast<Node>(*this) < static_cast<Node>(it);
661 const BellmanFord* _algorithm;
665 typedef PredMapPath<Graph, PredMap> Path;
667 /// \brief Gives back the shortest path.
669 /// Gives back the shortest path.
670 /// \pre The \c t should be reachable from the source.
673 return Path(*graph, *_pred, t);
677 // TODO : implement negative cycle
678 // /// \brief Gives back a negative cycle.
680 // /// This function gives back a negative cycle.
681 // /// If the algorithm have not found yet negative cycle it will give back
682 // /// an empty path.
683 // Path negativeCycle() {
684 // typename Graph::template NodeMap<int> state(*graph, 0);
685 // for (ActiveIt it(*this); it != INVALID; ++it) {
686 // if (state[it] == 0) {
687 // for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
688 // if (state[t] == 0) {
690 // } else if (state[t] == 2) {
694 // typename Path::Builder b(p);
695 // b.setStartNode(t);
696 // b.pushFront(predEdge(t));
697 // for(Node s = predNode(t); s != t; s = predNode(s)) {
698 // b.pushFront(predEdge(s));
704 // for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
705 // if (state[t] == 1) {
716 /// \brief The distance of a node from the root.
718 /// Returns the distance of a node from the root.
719 /// \pre \ref run() must be called before using this function.
720 /// \warning If node \c v in unreachable from the root the return value
721 /// of this funcion is undefined.
722 Value dist(Node v) const { return (*_dist)[v]; }
724 /// \brief Returns the 'previous edge' of the shortest path tree.
726 /// For a node \c v it returns the 'previous edge' of the shortest path
727 /// tree, i.e. it returns the last edge of a shortest path from the root
728 /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
729 /// if \c v=s. The shortest path tree used here is equal to the shortest
730 /// path tree used in \ref predNode().
731 /// \pre \ref run() must be called before using
733 Edge predEdge(Node v) const { return (*_pred)[v]; }
735 /// \brief Returns the 'previous node' of the shortest path tree.
737 /// For a node \c v it returns the 'previous node' of the shortest path
738 /// tree, i.e. it returns the last but one node from a shortest path from
739 /// the root to \c /v. It is INVALID if \c v is unreachable from the root
740 /// or if \c v=s. The shortest path tree used here is equal to the
741 /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
742 /// called before using this function.
743 Node predNode(Node v) const {
744 return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
747 /// \brief Returns a reference to the NodeMap of distances.
749 /// Returns a reference to the NodeMap of distances. \pre \ref run() must
750 /// be called before using this function.
751 const DistMap &distMap() const { return *_dist;}
753 /// \brief Returns a reference to the shortest path tree map.
755 /// Returns a reference to the NodeMap of the edges of the
756 /// shortest path tree.
757 /// \pre \ref run() must be called before using this function.
758 const PredMap &predMap() const { return *_pred; }
760 /// \brief Checks if a node is reachable from the root.
762 /// Returns \c true if \c v is reachable from the root.
763 /// \pre \ref run() must be called before using this function.
765 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
770 /// \brief Default traits class of BellmanFord function.
772 /// Default traits class of BellmanFord function.
773 /// \param _Graph Graph type.
774 /// \param _LengthMap Type of length map.
775 template <typename _Graph, typename _LengthMap>
776 struct BellmanFordWizardDefaultTraits {
777 /// \brief The graph type the algorithm runs on.
778 typedef _Graph Graph;
780 /// \brief The type of the map that stores the edge lengths.
782 /// The type of the map that stores the edge lengths.
783 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
784 typedef _LengthMap LengthMap;
786 /// \brief The value type of the length map.
787 typedef typename _LengthMap::Value Value;
789 /// \brief Operation traits for Bellman-Ford algorithm.
791 /// It defines the infinity type on the given Value type
792 /// and the used operation.
793 /// \see BellmanFordDefaultOperationTraits
794 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
796 /// \brief The type of the map that stores the last
797 /// edges of the shortest paths.
799 /// The type of the map that stores the last
800 /// edges of the shortest paths.
801 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
802 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
804 /// \brief Instantiates a PredMap.
806 /// This function instantiates a \ref PredMap.
807 static PredMap *createPredMap(const _Graph &) {
808 return new PredMap();
810 /// \brief The type of the map that stores the dists of the nodes.
812 /// The type of the map that stores the dists of the nodes.
813 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
814 typedef NullMap<typename Graph::Node, Value> DistMap;
815 /// \brief Instantiates a DistMap.
817 /// This function instantiates a \ref DistMap.
818 static DistMap *createDistMap(const _Graph &) {
819 return new DistMap();
823 /// \brief Default traits used by \ref BellmanFordWizard
825 /// To make it easier to use BellmanFord algorithm
826 /// we have created a wizard class.
827 /// This \ref BellmanFordWizard class needs default traits,
828 /// as well as the \ref BellmanFord class.
829 /// The \ref BellmanFordWizardBase is a class to be the default traits of the
830 /// \ref BellmanFordWizard class.
831 /// \todo More named parameters are required...
832 template<class _Graph,class _LengthMap>
833 class BellmanFordWizardBase
834 : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
836 typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
838 /// Type of the nodes in the graph.
839 typedef typename Base::Graph::Node Node;
841 /// Pointer to the underlying graph.
843 /// Pointer to the length map
845 ///Pointer to the map of predecessors edges.
847 ///Pointer to the map of distances.
849 ///Pointer to the source node.
855 /// This constructor does not require parameters, therefore it initiates
856 /// all of the attributes to default values (0, INVALID).
857 BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
858 _dist(0), _source(INVALID) {}
862 /// This constructor requires some parameters,
863 /// listed in the parameters list.
864 /// Others are initiated to 0.
865 /// \param graph is the initial value of \ref _graph
866 /// \param length is the initial value of \ref _length
867 /// \param source is the initial value of \ref _source
868 BellmanFordWizardBase(const _Graph& graph,
869 const _LengthMap& length,
870 Node source = INVALID) :
871 _graph(reinterpret_cast<void*>(const_cast<_Graph*>(&graph))),
872 _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))),
873 _pred(0), _dist(0), _source(source) {}
877 /// A class to make the usage of BellmanFord algorithm easier
879 /// This class is created to make it easier to use BellmanFord algorithm.
880 /// It uses the functions and features of the plain \ref BellmanFord,
881 /// but it is much simpler to use it.
883 /// Simplicity means that the way to change the types defined
884 /// in the traits class is based on functions that returns the new class
885 /// and not on templatable built-in classes.
886 /// When using the plain \ref BellmanFord
887 /// the new class with the modified type comes from
888 /// the original class by using the ::
889 /// operator. In the case of \ref BellmanFordWizard only
890 /// a function have to be called and it will
891 /// return the needed class.
893 /// It does not have own \ref run method. When its \ref run method is called
894 /// it initiates a plain \ref BellmanFord class, and calls the \ref
895 /// BellmanFord::run method of it.
896 template<class _Traits>
897 class BellmanFordWizard : public _Traits {
898 typedef _Traits Base;
900 ///The type of the underlying graph.
901 typedef typename _Traits::Graph Graph;
903 typedef typename Graph::Node Node;
904 typedef typename Graph::NodeIt NodeIt;
905 typedef typename Graph::Edge Edge;
906 typedef typename Graph::OutEdgeIt EdgeIt;
908 ///The type of the map that stores the edge lengths.
909 typedef typename _Traits::LengthMap LengthMap;
911 ///The type of the length of the edges.
912 typedef typename LengthMap::Value Value;
914 ///\brief The type of the map that stores the last
915 ///edges of the shortest paths.
916 typedef typename _Traits::PredMap PredMap;
918 ///The type of the map that stores the dists of the nodes.
919 typedef typename _Traits::DistMap DistMap;
923 BellmanFordWizard() : _Traits() {}
925 /// \brief Constructor that requires parameters.
927 /// Constructor that requires parameters.
928 /// These parameters will be the default values for the traits class.
929 BellmanFordWizard(const Graph& graph, const LengthMap& length,
931 : _Traits(graph, length, src) {}
933 /// \brief Copy constructor
934 BellmanFordWizard(const _Traits &b) : _Traits(b) {}
936 ~BellmanFordWizard() {}
938 /// \brief Runs BellmanFord algorithm from a given node.
940 /// Runs BellmanFord algorithm from a given node.
941 /// The node can be given by the \ref source function.
943 if(Base::_source == INVALID) throw UninitializedParameter();
944 BellmanFord<Graph,LengthMap,_Traits>
945 bf(*reinterpret_cast<const Graph*>(Base::_graph),
946 *reinterpret_cast<const LengthMap*>(Base::_length));
947 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
948 if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
949 bf.run(Base::_source);
952 /// \brief Runs BellmanFord algorithm from the given node.
954 /// Runs BellmanFord algorithm from the given node.
955 /// \param src is the given source.
962 struct DefPredMapBase : public Base {
964 static PredMap *createPredMap(const Graph &) { return 0; };
965 DefPredMapBase(const _Traits &b) : _Traits(b) {}
968 ///\brief \ref named-templ-param "Named parameter"
969 ///function for setting PredMap type
971 /// \ref named-templ-param "Named parameter"
972 ///function for setting PredMap type
975 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
977 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
978 return BellmanFordWizard<DefPredMapBase<T> >(*this);
982 struct DefDistMapBase : public Base {
984 static DistMap *createDistMap(const Graph &) { return 0; };
985 DefDistMapBase(const _Traits &b) : _Traits(b) {}
988 ///\brief \ref named-templ-param "Named parameter"
989 ///function for setting DistMap type
991 /// \ref named-templ-param "Named parameter"
992 ///function for setting DistMap type
995 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
996 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
997 return BellmanFordWizard<DefDistMapBase<T> >(*this);
1001 struct DefOperationTraitsBase : public Base {
1002 typedef T OperationTraits;
1003 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1006 ///\brief \ref named-templ-param "Named parameter"
1007 ///function for setting OperationTraits type
1009 /// \ref named-templ-param "Named parameter"
1010 ///function for setting OperationTraits type
1013 BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
1014 return BellmanFordWizard<DefDistMapBase<T> >(*this);
1017 /// \brief Sets the source node, from which the BellmanFord algorithm runs.
1019 /// Sets the source node, from which the BellmanFord algorithm runs.
1020 /// \param src is the source node.
1021 BellmanFordWizard<_Traits>& source(Node src) {
1022 Base::_source = src;
1028 /// \brief Function type interface for BellmanFord algorithm.
1030 /// \ingroup shortest_path
1031 /// Function type interface for BellmanFord algorithm.
1033 /// This function also has several \ref named-templ-func-param
1034 /// "named parameters", they are declared as the members of class
1035 /// \ref BellmanFordWizard.
1037 /// example shows how to use these parameters.
1039 /// bellmanford(g,length,source).predMap(preds).run();
1041 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1042 /// to the end of the parameter list.
1043 /// \sa BellmanFordWizard
1045 template<class _Graph, class _LengthMap>
1046 BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1047 bellmanFord(const _Graph& graph,
1048 const _LengthMap& length,
1049 typename _Graph::Node source = INVALID) {
1050 return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1051 (graph, length, source);
1054 } //END OF NAMESPACE LEMON