1.1 --- a/lemon/prim.h Wed Mar 07 11:56:14 2007 +0000
1.2 +++ b/lemon/prim.h Wed Mar 07 11:56:53 2007 +0000
1.3 @@ -401,16 +401,16 @@
1.4 public:
1.5
1.6 ///Constructor.
1.7 -
1.8 + ///
1.9 ///\param _graph the graph the algorithm will run on.
1.10 ///\param _cost the cost map used by the algorithm.
1.11 Prim(const UGraph& _graph, const CostMap& _cost) :
1.12 graph(&_graph), cost(&_cost),
1.13 - _pred(NULL), local_pred(false),
1.14 - _tree(NULL), local_tree(false),
1.15 - _processed(NULL), local_processed(false),
1.16 - _heap_cross_ref(NULL), local_heap_cross_ref(false),
1.17 - _heap(NULL), local_heap(false)
1.18 + _pred(0), local_pred(false),
1.19 + _tree(0), local_tree(false),
1.20 + _processed(0), local_processed(false),
1.21 + _heap_cross_ref(0), local_heap_cross_ref(false),
1.22 + _heap(0), local_heap(false)
1.23 {
1.24 checkConcept<concepts::UGraph, UGraph>();
1.25 }
1.26 @@ -425,7 +425,7 @@
1.27 }
1.28
1.29 ///\brief Sets the cost map.
1.30 -
1.31 + ///
1.32 ///Sets the cost map.
1.33 ///\return <tt> (*this) </tt>
1.34 Prim &costMap(const CostMap &m){
1.35 @@ -434,7 +434,7 @@
1.36 }
1.37
1.38 ///\brief Sets the map storing the predecessor edges.
1.39 -
1.40 + ///
1.41 ///Sets the map storing the predecessor edges.
1.42 ///If you don't use this function before calling \ref run(),
1.43 ///it will allocate one. The destuctor deallocates this
1.44 @@ -450,7 +450,7 @@
1.45 }
1.46
1.47 ///\brief Sets the map storing the tree edges.
1.48 -
1.49 + ///
1.50 ///Sets the map storing the tree edges.
1.51 ///If you don't use this function before calling \ref run(),
1.52 ///it will allocate one. The destuctor deallocates this
1.53 @@ -467,7 +467,7 @@
1.54 }
1.55
1.56 ///\brief Sets the heap and the cross reference used by algorithm.
1.57 -
1.58 + ///
1.59 ///Sets the heap and the cross reference used by algorithm.
1.60 ///If you don't use this function before calling \ref run(),
1.61 ///it will allocate one. The destuctor deallocates this
1.62 @@ -501,7 +501,7 @@
1.63 ///@{
1.64
1.65 ///\brief Initializes the internal data structures.
1.66 -
1.67 + ///
1.68 ///Initializes the internal data structures.
1.69 ///
1.70 void init(){
1.71 @@ -515,7 +515,7 @@
1.72 }
1.73
1.74 ///\brief Adds a new source node.
1.75 -
1.76 + ///
1.77 ///Adds a new source node to the priority heap.
1.78 ///
1.79 ///It checks if the node has already been added to the heap and
1.80 @@ -526,7 +526,7 @@
1.81 }
1.82 }
1.83 ///\brief Processes the next node in the priority heap
1.84 -
1.85 + ///
1.86 ///Processes the next node in the priority heap.
1.87 ///
1.88 ///\return The processed node.
1.89 @@ -559,7 +559,7 @@
1.90 }
1.91
1.92 ///\brief Next node to be processed.
1.93 -
1.94 + ///
1.95 ///Next node to be processed.
1.96 ///
1.97 ///\return The next node to be processed or INVALID if the priority heap
1.98 @@ -568,19 +568,22 @@
1.99 return _heap->empty()?_heap->top():INVALID;
1.100 }
1.101
1.102 - ///\brief Returns \c false if there are nodes to be processed in the priority heap
1.103 + ///\brief Returns \c false if there are nodes to be processed in
1.104 + ///the priority heap
1.105 ///
1.106 ///Returns \c false if there are nodes
1.107 ///to be processed in the priority heap
1.108 bool emptyQueue() { return _heap->empty(); }
1.109 - ///\brief Returns the number of the nodes to be processed in the priority heap
1.110
1.111 + ///\brief Returns the number of the nodes to be processed in the
1.112 + ///priority heap
1.113 + ///
1.114 ///Returns the number of the nodes to be processed in the priority heap
1.115 ///
1.116 int queueSize() { return _heap->size(); }
1.117
1.118 ///\brief Executes the algorithm.
1.119 -
1.120 + ///
1.121 ///Executes the algorithm.
1.122 ///
1.123 ///\pre init() must be called and at least one node should be added
1.124 @@ -595,7 +598,7 @@
1.125 }
1.126
1.127 ///\brief Executes the algorithm until a condition is met.
1.128 -
1.129 + ///
1.130 ///Executes the algorithm until a condition is met.
1.131 ///
1.132 ///\pre init() must be called and at least one node should be added
1.133 @@ -610,7 +613,7 @@
1.134 }
1.135
1.136 ///\brief Runs %Prim algorithm.
1.137 -
1.138 + ///
1.139 ///This method runs the %Prim algorithm
1.140 ///in order to compute the
1.141 ///minimum spanning tree (or minimum spanning forest).
1.142 @@ -627,17 +630,17 @@
1.143 }
1.144
1.145 ///\brief Runs %Prim algorithm from node \c s.
1.146 -
1.147 + ///
1.148 ///This method runs the %Prim algorithm from node \c s
1.149 ///in order to
1.150 ///compute the
1.151 ///minimun spanning tree
1.152 ///
1.153 - ///\note d.run(s) is just a shortcut of the following code.
1.154 + ///\note p.run(s) is just a shortcut of the following code.
1.155 ///\code
1.156 - /// d.init();
1.157 - /// d.addSource(s);
1.158 - /// d.start();
1.159 + /// p.init();
1.160 + /// p.addSource(s);
1.161 + /// p.start();
1.162 ///\endcode
1.163 ///\note If the graph has more than one components, the method
1.164 ///will compute the minimun spanning tree for only one component.
1.165 @@ -661,111 +664,127 @@
1.166
1.167 ///\brief Returns the 'previous edge' of the minimum spanning tree.
1.168
1.169 - ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
1.170 - ///i.e. it returns the edge from where \c v was reached. For a source node
1.171 - ///or an unreachable node it is \ref INVALID.
1.172 - ///The minimum spanning tree used here is equal to the minimum spanning tree used
1.173 - ///in \ref predNode(). \pre \ref run() or \ref start() must be called before
1.174 - ///using this function.
1.175 + ///For a node \c v it returns the 'previous edge' of the minimum
1.176 + ///spanning tree, i.e. it returns the edge from where \c v was
1.177 + ///reached. For a source node or an unreachable node it is \ref
1.178 + ///INVALID. The minimum spanning tree used here is equal to the
1.179 + ///minimum spanning tree used in \ref predNode().
1.180 + ///\pre \ref run() or \ref start() must be called before using
1.181 + ///this function.
1.182 UEdge predEdge(Node v) const { return (*_pred)[v]; }
1.183
1.184 - ///\brief Returns the 'previous node' of the minimum spanning tree.
1.185 -
1.186 - ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
1.187 - ///i.e. it returns the node from where \c v was reached. For a source node
1.188 - ///or an unreachable node it is \ref INVALID.
1.189 - //The minimum spanning tree used here is equal to the minimum spanning
1.190 - ///tree used in \ref predEdge(). \pre \ref run() or \ref start() must be called
1.191 - ///before using this function.
1.192 + ///\brief Returns the 'previous node' of the minimum spanning
1.193 + ///tree.
1.194 + ///
1.195 + ///For a node \c v it returns the 'previous node' of the minimum
1.196 + ///spanning tree, i.e. it returns the node from where \c v was
1.197 + ///reached. For a source node or an unreachable node it is \ref
1.198 + ///INVALID. //The minimum spanning tree used here is equal to the
1.199 + ///minimum spanning tree used in \ref predEdge().
1.200 + ///\pre \ref run() or \ref start() must be called before using
1.201 + ///this function.
1.202 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.203 graph->source((*_pred)[v]); }
1.204
1.205 - ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
1.206 -
1.207 - ///Returns a reference to the NodeMap of the edges of the
1.208 + ///\brief Returns a reference to the NodeMap of the edges of the
1.209 ///minimum spanning tree.
1.210 - ///\pre \ref run() or \ref start() must be called before using this function.
1.211 + ///
1.212 + ///Returns a reference to the NodeMap of the edges of the minimum
1.213 + ///spanning tree.
1.214 + ///\pre \ref run() or \ref start() must be called before using
1.215 + ///this function.
1.216 const PredMap &predMap() const { return *_pred;}
1.217
1.218 ///\brief Returns a reference to the tree edges map.
1.219
1.220 ///Returns a reference to the TreeEdgeMap of the edges of the
1.221 - ///minimum spanning tree. The value of the map is \c true only if the edge is in
1.222 - ///the minimum spanning tree.
1.223 + ///minimum spanning tree. The value of the map is \c true only if
1.224 + ///the edge is in the minimum spanning tree.
1.225 + ///
1.226 ///\warning By default, the TreeEdgeMap is a NullMap.
1.227 ///
1.228 - ///If it is not set before the execution of the algorithm, use the \ref
1.229 - ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
1.230 - ///edges of the minimum spanning tree in O(n) time where n is the number of
1.231 - ///nodes in the graph.
1.232 - ///\pre \ref run() or \ref start() must be called before using this function.
1.233 + ///If it is not set before the execution of the algorithm, use the
1.234 + ///\ref treeMap(TreeMap&) function (after the execution) to set an
1.235 + ///UEdgeMap with the edges of the minimum spanning tree in O(n)
1.236 + ///time where n is the number of nodes in the graph.
1.237 + ///\pre \ref run() or \ref start() must be called before using
1.238 + ///this function.
1.239 const TreeMap &treeMap() const { return *_tree;}
1.240
1.241 ///\brief Sets the tree edges map.
1.242 -
1.243 + ///
1.244 ///Sets the TreeMap of the edges of the minimum spanning tree.
1.245 ///The map values belonging to the edges of the minimum
1.246 ///spanning tree are set to \c tree_edge_value or \c true by default,
1.247 ///the other map values remain untouched.
1.248 ///
1.249 - ///\pre \ref run() or \ref start() must be called before using this function.
1.250 + ///\pre \ref run() or \ref start() must be called before using
1.251 + ///this function.
1.252
1.253 template<class TreeMap>
1.254 - void quickTreeEdges(
1.255 - TreeMap& tree,
1.256 - const typename TreeMap::Value& tree_edge_value=true) const {
1.257 + void quickTreeEdges(TreeMap& tree) const {
1.258 for(NodeIt i(*graph);i!=INVALID;++i){
1.259 - if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
1.260 + if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true);
1.261 }
1.262 }
1.263
1.264 ///\brief Sets the tree edges map.
1.265 -
1.266 + ///
1.267 ///Sets the TreeMap of the edges of the minimum spanning tree.
1.268 ///The map values belonging to the edges of the minimum
1.269 ///spanning tree are set to \c tree_edge_value or \c true by default while
1.270 ///the edge values not belonging to the minimum spanning tree are set to
1.271 ///\c tree_default_value or \c false by default.
1.272 ///
1.273 - ///\pre \ref run() or \ref start() must be called before using this function.
1.274 -
1.275 - template<class TreeMap>
1.276 - void treeEdges(
1.277 - TreeMap& tree,
1.278 - const typename TreeMap::Value& tree_edge_value=true,
1.279 - const typename TreeMap::Value& tree_default_value=false) const {
1.280 - for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
1.281 - tree.set(i,tree_default_value);
1.282 - for(NodeIt i(*graph);i!=INVALID;++i){
1.283 - if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
1.284 + ///\pre \ref run() or \ref start() must be called before using
1.285 + ///this function.
1.286 + template <class TreeMap>
1.287 + void treeEdges(TreeMap& tree) const {
1.288 + typedef typename ItemSetTraits<UGraph,UEdge>::ItemIt TreeMapIt;
1.289 + for(TreeMapIt i(*graph); i != INVALID; ++i) {
1.290 + tree.set(i,false);
1.291 + }
1.292 + for(NodeIt i(*graph); i != INVALID; ++i){
1.293 + if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
1.294 }
1.295 }
1.296
1.297 ///\brief Checks if a node is reachable from the starting node.
1.298 -
1.299 + ///
1.300 ///Returns \c true if \c v is reachable from the starting node.
1.301 ///\warning The source nodes are inditated as unreached.
1.302 - ///\pre \ref run() or \ref start() must be called before using this function.
1.303 + ///\pre \ref run() or \ref start() must be called before using
1.304 + ///this function.
1.305 ///
1.306 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
1.307
1.308 ///\brief Checks if a node is processed.
1.309 -
1.310 - ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
1.311 - ///minimum spanning tree.
1.312 - ///\pre \ref run() or \ref start() must be called before using this function.
1.313 ///
1.314 + ///Returns \c true if \c v is processed, i.e. \c v is already
1.315 + ///connencted to the minimum spanning tree. \pre \ref run() or
1.316 + ///\ref start() must be called before using this function.
1.317 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
1.318
1.319
1.320 ///\brief Checks if an edge is in the spanning tree or not.
1.321 -
1.322 + ///
1.323 ///Checks if an edge is in the spanning tree or not.
1.324 ///\param e is the edge that will be checked
1.325 ///\return \c true if e is in the spanning tree, \c false otherwise
1.326 bool tree(UEdge e){
1.327 return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
1.328 }
1.329 +
1.330 + ///\brief Returns the value of the total cost of the spanning tree.
1.331 + ///
1.332 + /// Returns the value of the total cost of the spanning tree.
1.333 + Value treeValue() const {
1.334 + Value value = 0;
1.335 + for(NodeIt i(*graph); i!= INVALID; ++i){
1.336 + if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
1.337 + }
1.338 + return value;
1.339 + }
1.340 ///@}
1.341 };
1.342
1.343 @@ -779,14 +798,39 @@
1.344 /// \param cost the CostMap of the edges
1.345 /// \retval tree the EdgeMap that contains whether an edge is in
1.346 /// the spanning tree or not
1.347 + /// \return The total cost of the spanning tree
1.348 ///
1.349 ///\sa Prim
1.350 template<class Graph,class CostMap,class TreeMap>
1.351 - void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
1.352 - typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
1.353 + typename CostMap::Value prim(const Graph& graph,
1.354 + const CostMap& cost,
1.355 + TreeMap& tree){
1.356 + typename Prim<Graph,CostMap>::
1.357 + template DefTreeMap<TreeMap>::
1.358 Create prm(graph,cost);
1.359 prm.treeMap(tree);
1.360 prm.run();
1.361 + return prm.treeValue();
1.362 + }
1.363 +
1.364 + /// \ingroup spantree
1.365 + ///
1.366 + /// \brief Function type interface for Prim algorithm.
1.367 + ///
1.368 + /// Function type interface for Prim algorithm.
1.369 + /// \param graph the UGraph that the algorithm runs on
1.370 + /// \param cost the CostMap of the edges
1.371 + /// the spanning tree or not
1.372 + /// \return The total cost of the spanning tree
1.373 + ///
1.374 + ///\sa Prim
1.375 + template<class Graph,class CostMap,class TreeMap>
1.376 + typename CostMap::Value prim(const Graph& graph,
1.377 + const CostMap& cost){
1.378 + typename Prim<Graph,CostMap>::
1.379 + Create prm(graph,cost);
1.380 + prm.run();
1.381 + return prm.treeValue();
1.382 }
1.383
1.384 } //END OF NAMESPACE LEMON