36 |
36 |
37 ///Default traits class of Prim class. |
37 ///Default traits class of Prim class. |
38 |
38 |
39 ///Default traits class of Prim class. |
39 ///Default traits class of Prim class. |
40 ///\param GR Graph type. |
40 ///\param GR Graph type. |
41 ///\param LM Type of cost map. |
41 ///\param CM Type of cost map. |
42 template<class GR, class LM> |
42 template<class GR, class CM> |
43 struct PrimDefaultTraits{ |
43 struct PrimDefaultTraits{ |
44 ///The graph type the algorithm runs on. |
44 ///The graph type the algorithm runs on. |
45 typedef GR UGraph; |
45 typedef GR UGraph; |
46 ///The type of the map that stores the edge costs. |
46 ///The type of the map that stores the edge costs. |
47 |
47 |
48 ///The type of the map that stores the edge costs. |
48 ///The type of the map that stores the edge costs. |
49 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
49 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
50 typedef LM CostMap; |
50 typedef CM CostMap; |
51 //The type of the cost of the edges. |
51 //The type of the cost of the edges. |
52 typedef typename LM::Value Value; |
52 typedef typename CM::Value Value; |
53 /// The cross reference type used by heap. |
53 /// The cross reference type used by heap. |
54 |
54 |
55 /// The cross reference type used by heap. |
55 /// The cross reference type used by heap. |
56 /// Usually it is \c UGraph::NodeMap<int>. |
56 /// Usually it is \c UGraph::NodeMap<int>. |
57 typedef typename UGraph::template NodeMap<int> HeapCrossRef; |
57 typedef typename UGraph::template NodeMap<int> HeapCrossRef; |
68 |
68 |
69 ///The heap type used by Prim algorithm. |
69 ///The heap type used by Prim algorithm. |
70 /// |
70 /// |
71 ///\sa BinHeap |
71 ///\sa BinHeap |
72 ///\sa Prim |
72 ///\sa Prim |
73 typedef BinHeap<typename UGraph::Node, typename LM::Value, |
73 typedef BinHeap<typename UGraph::Node, typename CM::Value, |
74 HeapCrossRef, std::less<Value> > Heap; |
74 HeapCrossRef, std::less<Value> > Heap; |
75 |
75 |
76 static Heap *createHeap(HeapCrossRef& _ref){ |
76 static Heap *createHeap(HeapCrossRef& _ref){ |
77 return new Heap(_ref); |
77 return new Heap(_ref); |
78 } |
78 } |
150 /// |
150 /// |
151 ///\param GR The graph type the algorithm runs on. The default value |
151 ///\param GR The graph type the algorithm runs on. The default value |
152 ///is \ref ListUGraph. The value of GR is not used directly by |
152 ///is \ref ListUGraph. The value of GR is not used directly by |
153 ///Prim, it is only passed to \ref PrimDefaultTraits. |
153 ///Prim, it is only passed to \ref PrimDefaultTraits. |
154 /// |
154 /// |
155 ///\param LM This read-only UEdgeMap determines the costs of the |
155 ///\param CM This read-only UEdgeMap determines the costs of the |
156 ///edges. It is read once for each edge, so the map may involve in |
156 ///edges. It is read once for each edge, so the map may involve in |
157 ///relatively time consuming process to compute the edge cost if |
157 ///relatively time consuming process to compute the edge cost if |
158 ///it is necessary. The default map type is \ref |
158 ///it is necessary. The default map type is \ref |
159 ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value |
159 ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value |
160 ///of LM is not used directly by Prim, it is only passed to \ref |
160 ///of CM is not used directly by Prim, it is only passed to \ref |
161 ///PrimDefaultTraits. |
161 ///PrimDefaultTraits. |
162 /// |
162 /// |
163 ///\param TR Traits class to set |
163 ///\param TR Traits class to set |
164 ///various data types used by the algorithm. The default traits |
164 ///various data types used by the algorithm. The default traits |
165 ///class is \ref PrimDefaultTraits |
165 ///class is \ref PrimDefaultTraits |
166 ///"PrimDefaultTraits<GR,LM>". See \ref |
166 ///"PrimDefaultTraits<GR,CM>". See \ref |
167 ///PrimDefaultTraits for the documentation of a Prim traits |
167 ///PrimDefaultTraits for the documentation of a Prim traits |
168 ///class. |
168 ///class. |
169 /// |
169 /// |
170 ///\author Balazs Attila Mihaly |
170 ///\author Balazs Attila Mihaly |
171 |
171 |
172 #ifdef DOXYGEN |
172 #ifdef DOXYGEN |
173 template <typename GR, |
173 template <typename GR, |
174 typename LM, |
174 typename CM, |
175 typename TR> |
175 typename TR> |
176 #else |
176 #else |
177 template <typename GR=ListUGraph, |
177 template <typename GR=ListUGraph, |
178 typename LM=typename GR::template UEdgeMap<int>, |
178 typename CM=typename GR::template UEdgeMap<int>, |
179 typename TR=PrimDefaultTraits<GR,LM> > |
179 typename TR=PrimDefaultTraits<GR,CM> > |
180 #endif |
180 #endif |
181 class Prim { |
181 class Prim { |
182 public: |
182 public: |
183 /** |
183 |
184 * \brief \ref Exception for uninitialized parameters. |
184 /// \brief \ref Exception for uninitialized parameters. |
185 * |
185 /// |
186 * This error represents problems in the initialization |
186 /// This error represents problems in the initialization |
187 * of the parameters of the algorithms. |
187 /// of the parameters of the algorithms. |
188 */ |
|
189 class UninitializedParameter : public lemon::UninitializedParameter { |
188 class UninitializedParameter : public lemon::UninitializedParameter { |
190 public: |
189 public: |
191 virtual const char* exceptionName() const { |
190 virtual const char* exceptionName() const { |
192 return "lemon::Prim::UninitializedParameter"; |
191 return "lemon::Prim::UninitializedParameter"; |
193 } |
192 } |