equal
deleted
inserted
replaced
28 #include <lemon/bits/invalid.h> |
28 #include <lemon/bits/invalid.h> |
29 #include <lemon/error.h> |
29 #include <lemon/error.h> |
30 #include <lemon/maps.h> |
30 #include <lemon/maps.h> |
31 #include <lemon/bits/traits.h> |
31 #include <lemon/bits/traits.h> |
32 |
32 |
33 #include <lemon/concept/ugraph.h> |
33 #include <lemon/concepts/ugraph.h> |
34 |
34 |
35 namespace lemon { |
35 namespace lemon { |
36 |
36 |
37 ///Default traits class of Prim class. |
37 ///Default traits class of Prim class. |
38 |
38 |
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 concepts::ReadMap "ReadMap" concept. |
50 typedef CM 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 CM::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 |
80 ///\brief The type of the map that stores the last |
80 ///\brief The type of the map that stores the last |
81 ///edges of the minimum spanning tree. |
81 ///edges of the minimum spanning tree. |
82 /// |
82 /// |
83 ///The type of the map that stores the last |
83 ///The type of the map that stores the last |
84 ///edges of the minimum spanning tree. |
84 ///edges of the minimum spanning tree. |
85 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
85 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
86 /// |
86 /// |
87 typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap; |
87 typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap; |
88 ///Instantiates a PredMap. |
88 ///Instantiates a PredMap. |
89 |
89 |
90 ///This function instantiates a \ref PredMap. |
90 ///This function instantiates a \ref PredMap. |
111 } |
111 } |
112 |
112 |
113 ///The type of the map that stores whether a nodes is processed. |
113 ///The type of the map that stores whether a nodes is processed. |
114 |
114 |
115 ///The type of the map that stores whether a nodes is processed. |
115 ///The type of the map that stores whether a nodes is processed. |
116 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
116 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
117 ///By default it is a NodeMap<bool>. |
117 ///By default it is a NodeMap<bool>. |
118 typedef NullMap<typename UGraph::Node,bool> ProcessedMap; |
118 typedef NullMap<typename UGraph::Node,bool> ProcessedMap; |
119 ///Instantiates a ProcessedMap. |
119 ///Instantiates a ProcessedMap. |
120 |
120 |
121 ///This function instantiates a \ref ProcessedMap. |
121 ///This function instantiates a \ref ProcessedMap. |
138 /// |
138 /// |
139 ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and |
139 ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and |
140 ///n is the number of nodes in the graph. |
140 ///n is the number of nodes in the graph. |
141 /// |
141 /// |
142 ///The edge costs are passed to the algorithm using a |
142 ///The edge costs are passed to the algorithm using a |
143 ///\ref concept::ReadMap "ReadMap", |
143 ///\ref concepts::ReadMap "ReadMap", |
144 ///so it is easy to change it to any kind of cost. |
144 ///so it is easy to change it to any kind of cost. |
145 /// |
145 /// |
146 ///The type of the cost is determined by the |
146 ///The type of the cost is determined by the |
147 ///\ref concept::ReadMap::Value "Value" of the cost map. |
147 ///\ref concepts::ReadMap::Value "Value" of the cost map. |
148 /// |
148 /// |
149 ///It is also possible to change the underlying priority heap. |
149 ///It is also possible to change the underlying priority heap. |
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 |
154 /// |
154 /// |
155 ///\param CM 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 ///concepts::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value |
160 ///of CM 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 |
410 _tree(NULL), local_tree(false), |
410 _tree(NULL), local_tree(false), |
411 _processed(NULL), local_processed(false), |
411 _processed(NULL), local_processed(false), |
412 _heap_cross_ref(NULL), local_heap_cross_ref(false), |
412 _heap_cross_ref(NULL), local_heap_cross_ref(false), |
413 _heap(NULL), local_heap(false) |
413 _heap(NULL), local_heap(false) |
414 { |
414 { |
415 checkConcept<concept::UGraph, UGraph>(); |
415 checkConcept<concepts::UGraph, UGraph>(); |
416 } |
416 } |
417 |
417 |
418 ///Destructor. |
418 ///Destructor. |
419 ~Prim(){ |
419 ~Prim(){ |
420 if(local_pred) delete _pred; |
420 if(local_pred) delete _pred; |