90 typedef _Graph Graph; |
90 typedef _Graph Graph; |
91 |
91 |
92 /// \brief The type of the map that stores the edge lengths. |
92 /// \brief The type of the map that stores the edge lengths. |
93 /// |
93 /// |
94 /// The type of the map that stores the edge lengths. |
94 /// The type of the map that stores the edge lengths. |
95 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
95 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
96 typedef _LengthMap LengthMap; |
96 typedef _LengthMap LengthMap; |
97 |
97 |
98 // The type of the length of the edges. |
98 // The type of the length of the edges. |
99 typedef typename _LengthMap::Value Value; |
99 typedef typename _LengthMap::Value Value; |
100 |
100 |
108 /// \brief The type of the map that stores the last edges of the |
108 /// \brief The type of the map that stores the last edges of the |
109 /// shortest paths. |
109 /// shortest paths. |
110 /// |
110 /// |
111 /// The type of the map that stores the last |
111 /// The type of the map that stores the last |
112 /// edges of the shortest paths. |
112 /// edges of the shortest paths. |
113 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
113 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
114 /// |
114 /// |
115 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
115 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap; |
116 |
116 |
117 /// \brief Instantiates a PredMap. |
117 /// \brief Instantiates a PredMap. |
118 /// |
118 /// |
123 } |
123 } |
124 |
124 |
125 /// \brief The type of the map that stores the dists of the nodes. |
125 /// \brief The type of the map that stores the dists of the nodes. |
126 /// |
126 /// |
127 /// The type of the map that stores the dists of the nodes. |
127 /// The type of the map that stores the dists of the nodes. |
128 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
128 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
129 /// |
129 /// |
130 typedef typename Graph::template NodeMap<typename _LengthMap::Value> |
130 typedef typename Graph::template NodeMap<typename _LengthMap::Value> |
131 DistMap; |
131 DistMap; |
132 |
132 |
133 /// \brief Instantiates a DistMap. |
133 /// \brief Instantiates a DistMap. |
144 /// \brief %BellmanFord algorithm class. |
144 /// \brief %BellmanFord algorithm class. |
145 /// |
145 /// |
146 /// \ingroup flowalgs |
146 /// \ingroup flowalgs |
147 /// This class provides an efficient implementation of \c Bellman-Ford |
147 /// This class provides an efficient implementation of \c Bellman-Ford |
148 /// algorithm. The edge lengths are passed to the algorithm using a |
148 /// algorithm. The edge lengths are passed to the algorithm using a |
149 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
149 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any |
150 /// kind of length. |
150 /// kind of length. |
151 /// |
151 /// |
152 /// The Bellman-Ford algorithm solves the shortest path from one node |
152 /// The Bellman-Ford algorithm solves the shortest path from one node |
153 /// problem when the edges can have negative length but the graph should |
153 /// problem when the edges can have negative length but the graph should |
154 /// not contain cycles with negative sum of length. If we can assume |
154 /// not contain cycles with negative sum of length. If we can assume |
156 /// should be used rather. |
156 /// should be used rather. |
157 /// |
157 /// |
158 /// The maximal time complexity of the algorithm is \f$ O(ne) \f$. |
158 /// The maximal time complexity of the algorithm is \f$ O(ne) \f$. |
159 /// |
159 /// |
160 /// The type of the length is determined by the |
160 /// The type of the length is determined by the |
161 /// \ref concept::ReadMap::Value "Value" of the length map. |
161 /// \ref concepts::ReadMap::Value "Value" of the length map. |
162 /// |
162 /// |
163 /// \param _Graph The graph type the algorithm runs on. The default value |
163 /// \param _Graph The graph type the algorithm runs on. The default value |
164 /// is \ref ListGraph. The value of _Graph is not used directly by |
164 /// is \ref ListGraph. The value of _Graph is not used directly by |
165 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. |
165 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. |
166 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
166 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
167 /// edges. The default map type is \ref concept::Graph::EdgeMap |
167 /// edges. The default map type is \ref concepts::Graph::EdgeMap |
168 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly |
168 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly |
169 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. |
169 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. |
170 /// \param _Traits Traits class to set various data types used by the |
170 /// \param _Traits Traits class to set various data types used by the |
171 /// algorithm. The default traits class is \ref BellmanFordDefaultTraits |
171 /// algorithm. The default traits class is \ref BellmanFordDefaultTraits |
172 /// "BellmanFordDefaultTraits<_Graph,_LengthMap>". See \ref |
172 /// "BellmanFordDefaultTraits<_Graph,_LengthMap>". See \ref |
788 typedef _Graph Graph; |
788 typedef _Graph Graph; |
789 |
789 |
790 /// \brief The type of the map that stores the edge lengths. |
790 /// \brief The type of the map that stores the edge lengths. |
791 /// |
791 /// |
792 /// The type of the map that stores the edge lengths. |
792 /// The type of the map that stores the edge lengths. |
793 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
793 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
794 typedef _LengthMap LengthMap; |
794 typedef _LengthMap LengthMap; |
795 |
795 |
796 /// \brief The value type of the length map. |
796 /// \brief The value type of the length map. |
797 typedef typename _LengthMap::Value Value; |
797 typedef typename _LengthMap::Value Value; |
798 |
798 |
806 /// \brief The type of the map that stores the last |
806 /// \brief The type of the map that stores the last |
807 /// edges of the shortest paths. |
807 /// edges of the shortest paths. |
808 /// |
808 /// |
809 /// The type of the map that stores the last |
809 /// The type of the map that stores the last |
810 /// edges of the shortest paths. |
810 /// edges of the shortest paths. |
811 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
811 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
812 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap; |
812 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap; |
813 |
813 |
814 /// \brief Instantiates a PredMap. |
814 /// \brief Instantiates a PredMap. |
815 /// |
815 /// |
816 /// This function instantiates a \ref PredMap. |
816 /// This function instantiates a \ref PredMap. |
818 return new PredMap(); |
818 return new PredMap(); |
819 } |
819 } |
820 /// \brief The type of the map that stores the dists of the nodes. |
820 /// \brief The type of the map that stores the dists of the nodes. |
821 /// |
821 /// |
822 /// The type of the map that stores the dists of the nodes. |
822 /// The type of the map that stores the dists of the nodes. |
823 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
823 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
824 typedef NullMap<typename Graph::Node, Value> DistMap; |
824 typedef NullMap<typename Graph::Node, Value> DistMap; |
825 /// \brief Instantiates a DistMap. |
825 /// \brief Instantiates a DistMap. |
826 /// |
826 /// |
827 /// This function instantiates a \ref DistMap. |
827 /// This function instantiates a \ref DistMap. |
828 static DistMap *createDistMap(const _Graph &) { |
828 static DistMap *createDistMap(const _Graph &) { |