equal
deleted
inserted
replaced
15 */ |
15 */ |
16 |
16 |
17 #ifndef LEMON_BELMANN_FORD_H |
17 #ifndef LEMON_BELMANN_FORD_H |
18 #define LEMON_BELMANN_FORD_H |
18 #define LEMON_BELMANN_FORD_H |
19 |
19 |
20 ///\ingroup flowalgs |
20 /// \ingroup flowalgs |
21 /// \file |
21 /// \file |
22 /// \brief BelmannFord algorithm. |
22 /// \brief BelmannFord algorithm. |
23 /// |
23 /// |
24 |
24 |
25 #include <lemon/list_graph.h> |
25 #include <lemon/list_graph.h> |
113 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
113 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
114 |
114 |
115 /// \brief Instantiates a PredMap. |
115 /// \brief Instantiates a PredMap. |
116 /// |
116 /// |
117 /// This function instantiates a \ref PredMap. |
117 /// This function instantiates a \ref PredMap. |
118 /// \param G is the graph, to which we would like to define the PredMap. |
118 /// \param graph 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) { |
119 static PredMap *createPredMap(const _Graph& graph) { |
121 return new PredMap(graph); |
120 return new PredMap(graph); |
122 } |
121 } |
123 |
122 |
124 /// \brief The type of the map that stores the dists of the nodes. |
123 /// \brief The type of the map that stores the dists of the nodes. |
130 DistMap; |
129 DistMap; |
131 |
130 |
132 /// \brief Instantiates a DistMap. |
131 /// \brief Instantiates a DistMap. |
133 /// |
132 /// |
134 /// This function instantiates a \ref DistMap. |
133 /// This function instantiates a \ref DistMap. |
135 /// \param G is the graph, to which we would like to define the |
134 /// \param graph is the graph, to which we would like to define the |
136 /// \ref DistMap |
135 /// \ref DistMap |
137 static DistMap *createDistMap(const _Graph& graph) { |
136 static DistMap *createDistMap(const _Graph& graph) { |
138 return new DistMap(graph); |
137 return new DistMap(graph); |
139 } |
138 } |
140 |
139 |
267 /// \brief \ref named-templ-param "Named parameter" for setting PredMap |
266 /// \brief \ref named-templ-param "Named parameter" for setting PredMap |
268 /// type |
267 /// type |
269 /// \ref named-templ-param "Named parameter" for setting PredMap type |
268 /// \ref named-templ-param "Named parameter" for setting PredMap type |
270 /// |
269 /// |
271 template <class T> |
270 template <class T> |
272 struct DefPredMap { |
271 struct DefPredMap |
|
272 : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > { |
273 typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create; |
273 typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create; |
274 }; |
274 }; |
275 |
275 |
276 template <class T> |
276 template <class T> |
277 struct DefDistMapTraits : public Traits { |
277 struct DefDistMapTraits : public Traits { |
420 /// |
420 /// |
421 /// If the algoritm calculated the distances in the previous round |
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 |
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 |
423 /// distances strictly for all at most k + 1 length paths. With k |
424 /// iteration this function calculates the at most k length paths. |
424 /// iteration this function calculates the at most k length paths. |
425 ///\todo what is the return value? |
425 /// \return %True when the algorithm have not found more shorter paths. |
426 bool processNextRound() { |
426 bool processNextRound() { |
427 for (int i = 0; i < (int)_process.size(); ++i) { |
427 for (int i = 0; i < (int)_process.size(); ++i) { |
428 _mask->set(_process[i], false); |
428 _mask->set(_process[i], false); |
429 } |
429 } |
430 std::vector<Node> nextProcess; |
430 std::vector<Node> nextProcess; |
456 /// previous round at least for all at most k length paths then it will |
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. |
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 |
458 /// This function does not make it possible to calculate strictly the |
459 /// at most k length minimal paths, this is why it is |
459 /// at most k length minimal paths, this is why it is |
460 /// called just weak round. |
460 /// called just weak round. |
461 ///\todo what is the return value? |
461 /// \return %True when the algorithm have not found more shorter paths. |
462 bool processNextWeakRound() { |
462 bool processNextWeakRound() { |
463 for (int i = 0; i < (int)_process.size(); ++i) { |
463 for (int i = 0; i < (int)_process.size(); ++i) { |
464 _mask->set(_process[i], false); |
464 _mask->set(_process[i], false); |
465 } |
465 } |
466 std::vector<Node> nextProcess; |
466 std::vector<Node> nextProcess; |
843 } |
843 } |
844 |
844 |
845 /// \brief Runs BelmannFord algorithm from the given node. |
845 /// \brief Runs BelmannFord algorithm from the given node. |
846 /// |
846 /// |
847 /// Runs BelmannFord algorithm from the given node. |
847 /// Runs BelmannFord algorithm from the given node. |
848 /// \param s is the given source. |
848 /// \param source is the given source. |
849 void run(Node source) { |
849 void run(Node source) { |
850 Base::_source = source; |
850 Base::_source = source; |
851 run(); |
851 run(); |
852 } |
852 } |
853 |
853 |
908 } |
908 } |
909 |
909 |
910 /// \brief Sets the source node, from which the BelmannFord algorithm runs. |
910 /// \brief Sets the source node, from which the BelmannFord algorithm runs. |
911 /// |
911 /// |
912 /// Sets the source node, from which the BelmannFord algorithm runs. |
912 /// Sets the source node, from which the BelmannFord algorithm runs. |
913 /// \param s is the source node. |
913 /// \param source is the source node. |
914 BelmannFordWizard<_Traits>& source(Node source) { |
914 BelmannFordWizard<_Traits>& source(Node source) { |
915 Base::_source = source; |
915 Base::_source = source; |
916 return *this; |
916 return *this; |
917 } |
917 } |
918 |
918 |