434 /// the path. |
434 /// the path. |
435 /// |
435 /// |
436 /// \return %True when the algorithm have not found more shorter |
436 /// \return %True when the algorithm have not found more shorter |
437 /// paths. |
437 /// paths. |
438 bool processNextRound() { |
438 bool processNextRound() { |
439 for (int i = 0; i < (int)_process.size(); ++i) { |
439 for (int i = 0; i < int(_process.size()); ++i) { |
440 _mask->set(_process[i], false); |
440 _mask->set(_process[i], false); |
441 } |
441 } |
442 std::vector<Node> nextProcess; |
442 std::vector<Node> nextProcess; |
443 std::vector<Value> values(_process.size()); |
443 std::vector<Value> values(_process.size()); |
444 for (int i = 0; i < (int)_process.size(); ++i) { |
444 for (int i = 0; i < int(_process.size()); ++i) { |
445 values[i] = (*_dist)[_process[i]]; |
445 values[i] = (*_dist)[_process[i]]; |
446 } |
446 } |
447 for (int i = 0; i < (int)_process.size(); ++i) { |
447 for (int i = 0; i < int(_process.size()); ++i) { |
448 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) { |
448 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) { |
449 Node target = graph->target(it); |
449 Node target = graph->target(it); |
450 Value relaxed = OperationTraits::plus(values[i], (*length)[it]); |
450 Value relaxed = OperationTraits::plus(values[i], (*length)[it]); |
451 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
451 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
452 _pred->set(target, it); |
452 _pred->set(target, it); |
470 /// This function does not make it possible to calculate strictly the |
470 /// This function does not make it possible to calculate strictly the |
471 /// at most k length minimal paths, this is why it is |
471 /// at most k length minimal paths, this is why it is |
472 /// called just weak round. |
472 /// called just weak round. |
473 /// \return %True when the algorithm have not found more shorter paths. |
473 /// \return %True when the algorithm have not found more shorter paths. |
474 bool processNextWeakRound() { |
474 bool processNextWeakRound() { |
475 for (int i = 0; i < (int)_process.size(); ++i) { |
475 for (int i = 0; i < int(_process.size()); ++i) { |
476 _mask->set(_process[i], false); |
476 _mask->set(_process[i], false); |
477 } |
477 } |
478 std::vector<Node> nextProcess; |
478 std::vector<Node> nextProcess; |
479 for (int i = 0; i < (int)_process.size(); ++i) { |
479 for (int i = 0; i < int(_process.size()); ++i) { |
480 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) { |
480 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) { |
481 Node target = graph->target(it); |
481 Node target = graph->target(it); |
482 Value relaxed = |
482 Value relaxed = |
483 OperationTraits::plus((*_dist)[_process[i]], (*length)[it]); |
483 OperationTraits::plus((*_dist)[_process[i]], (*length)[it]); |
484 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
484 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
643 --_index; |
643 --_index; |
644 return *this; |
644 return *this; |
645 } |
645 } |
646 |
646 |
647 bool operator==(const ActiveIt& it) const { |
647 bool operator==(const ActiveIt& it) const { |
648 return (Node)(*this) == (Node)it; |
648 return static_cast<Node>(*this) == static_cast<Node>(it); |
649 } |
649 } |
650 bool operator!=(const ActiveIt& it) const { |
650 bool operator!=(const ActiveIt& it) const { |
651 return (Node)(*this) != (Node)it; |
651 return static_cast<Node>(*this) != static_cast<Node>(it); |
652 } |
652 } |
653 bool operator<(const ActiveIt& it) const { |
653 bool operator<(const ActiveIt& it) const { |
654 return (Node)(*this) < (Node)it; |
654 return static_cast<Node>(*this) < static_cast<Node>(it); |
655 } |
655 } |
656 |
656 |
657 private: |
657 private: |
658 const BellmanFord* _algorithm; |
658 const BellmanFord* _algorithm; |
659 int _index; |
659 int _index; |
863 /// \param length is the initial value of \ref _length |
863 /// \param length is the initial value of \ref _length |
864 /// \param source is the initial value of \ref _source |
864 /// \param source is the initial value of \ref _source |
865 BellmanFordWizardBase(const _Graph& graph, |
865 BellmanFordWizardBase(const _Graph& graph, |
866 const _LengthMap& length, |
866 const _LengthMap& length, |
867 Node source = INVALID) : |
867 Node source = INVALID) : |
868 _graph((void *)&graph), _length((void *)&length), _pred(0), |
868 _graph(reinterpret_cast<void*>(const_cast<_Graph*>(&graph))), |
869 _dist(0), _source(source) {} |
869 _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), |
|
870 _pred(0), _dist(0), _source(source) {} |
870 |
871 |
871 }; |
872 }; |
872 |
873 |
873 /// A class to make the usage of BellmanFord algorithm easier |
874 /// A class to make the usage of BellmanFord algorithm easier |
874 |
875 |
921 /// \brief Constructor that requires parameters. |
922 /// \brief Constructor that requires parameters. |
922 /// |
923 /// |
923 /// Constructor that requires parameters. |
924 /// Constructor that requires parameters. |
924 /// These parameters will be the default values for the traits class. |
925 /// These parameters will be the default values for the traits class. |
925 BellmanFordWizard(const Graph& graph, const LengthMap& length, |
926 BellmanFordWizard(const Graph& graph, const LengthMap& length, |
926 Node source = INVALID) |
927 Node src = INVALID) |
927 : _Traits(graph, length, source) {} |
928 : _Traits(graph, length, src) {} |
928 |
929 |
929 /// \brief Copy constructor |
930 /// \brief Copy constructor |
930 BellmanFordWizard(const _Traits &b) : _Traits(b) {} |
931 BellmanFordWizard(const _Traits &b) : _Traits(b) {} |
931 |
932 |
932 ~BellmanFordWizard() {} |
933 ~BellmanFordWizard() {} |
936 /// Runs BellmanFord algorithm from a given node. |
937 /// Runs BellmanFord algorithm from a given node. |
937 /// The node can be given by the \ref source function. |
938 /// The node can be given by the \ref source function. |
938 void run() { |
939 void run() { |
939 if(Base::_source == INVALID) throw UninitializedParameter(); |
940 if(Base::_source == INVALID) throw UninitializedParameter(); |
940 BellmanFord<Graph,LengthMap,_Traits> |
941 BellmanFord<Graph,LengthMap,_Traits> |
941 bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length); |
942 bf(*reinterpret_cast<const Graph*>(Base::_graph), |
942 if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred); |
943 *reinterpret_cast<const LengthMap*>(Base::_length)); |
943 if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist); |
944 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
|
945 if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
944 bf.run(Base::_source); |
946 bf.run(Base::_source); |
945 } |
947 } |
946 |
948 |
947 /// \brief Runs BellmanFord algorithm from the given node. |
949 /// \brief Runs BellmanFord algorithm from the given node. |
948 /// |
950 /// |
949 /// Runs BellmanFord algorithm from the given node. |
951 /// Runs BellmanFord algorithm from the given node. |
950 /// \param source is the given source. |
952 /// \param source is the given source. |
951 void run(Node source) { |
953 void run(Node src) { |
952 Base::_source = source; |
954 Base::_source = src; |
953 run(); |
955 run(); |
954 } |
956 } |
955 |
957 |
956 template<class T> |
958 template<class T> |
957 struct DefPredMapBase : public Base { |
959 struct DefPredMapBase : public Base { |
967 ///function for setting PredMap type |
969 ///function for setting PredMap type |
968 /// |
970 /// |
969 template<class T> |
971 template<class T> |
970 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) |
972 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) |
971 { |
973 { |
972 Base::_pred=(void *)&t; |
974 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
973 return BellmanFordWizard<DefPredMapBase<T> >(*this); |
975 return BellmanFordWizard<DefPredMapBase<T> >(*this); |
974 } |
976 } |
975 |
977 |
976 template<class T> |
978 template<class T> |
977 struct DefDistMapBase : public Base { |
979 struct DefDistMapBase : public Base { |
986 /// \ref named-templ-param "Named parameter" |
988 /// \ref named-templ-param "Named parameter" |
987 ///function for setting DistMap type |
989 ///function for setting DistMap type |
988 /// |
990 /// |
989 template<class T> |
991 template<class T> |
990 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) { |
992 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) { |
991 Base::_dist=(void *)&t; |
993 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
992 return BellmanFordWizard<DefDistMapBase<T> >(*this); |
994 return BellmanFordWizard<DefDistMapBase<T> >(*this); |
993 } |
995 } |
994 |
996 |
995 template<class T> |
997 template<class T> |
996 struct DefOperationTraitsBase : public Base { |
998 struct DefOperationTraitsBase : public Base { |
1011 |
1013 |
1012 /// \brief Sets the source node, from which the BellmanFord algorithm runs. |
1014 /// \brief Sets the source node, from which the BellmanFord algorithm runs. |
1013 /// |
1015 /// |
1014 /// Sets the source node, from which the BellmanFord algorithm runs. |
1016 /// Sets the source node, from which the BellmanFord algorithm runs. |
1015 /// \param source is the source node. |
1017 /// \param source is the source node. |
1016 BellmanFordWizard<_Traits>& source(Node source) { |
1018 BellmanFordWizard<_Traits>& source(Node src) { |
1017 Base::_source = source; |
1019 Base::_source = src; |
1018 return *this; |
1020 return *this; |
1019 } |
1021 } |
1020 |
1022 |
1021 }; |
1023 }; |
1022 |
1024 |