245 node = (*_pred)[node] != INVALID ? |
247 node = (*_pred)[node] != INVALID ? |
246 _graph.source((*_pred)[node]) : INVALID; |
248 _graph.source((*_pred)[node]) : INVALID; |
247 } |
249 } |
248 } |
250 } |
249 |
251 |
250 prim(nodeSubUGraphAdaptor(_graph, *_filter), _cost, *_tree); |
252 _value = prim(nodeSubUGraphAdaptor(_graph, *_filter), _cost, *_tree); |
251 |
253 |
252 } |
254 } |
253 |
255 |
254 /// \brief Checks if an edge is in the Steiner-tree or not. |
256 /// \brief Checks if an edge is in the Steiner-tree or not. |
255 /// |
257 /// |
266 /// \param n is the node that will be checked |
268 /// \param n is the node that will be checked |
267 /// \return \c true if n is in the Steiner-tree, \c false otherwise |
269 /// \return \c true if n is in the Steiner-tree, \c false otherwise |
268 bool tree(Node n){ |
270 bool tree(Node n){ |
269 return (*_filter)[n]; |
271 return (*_filter)[n]; |
270 } |
272 } |
271 |
273 |
272 |
274 /// \brief Checks if the node is a Steiner-node. |
|
275 /// |
|
276 /// Checks if the node is a Steiner-node (i.e. a tree node but |
|
277 /// not terminal). |
|
278 /// \param n is the node that will be checked |
|
279 /// \return \c true if n is a Steiner-node, \c false otherwise |
|
280 bool steiner(Node n){ |
|
281 return (*_filter)[n] && (*_pred)[n] != INVALID; |
|
282 } |
|
283 |
|
284 /// \brief Checks if the node is a terminal. |
|
285 /// |
|
286 /// Checks if the node is a terminal. |
|
287 /// \param n is the node that will be checked |
|
288 /// \return \c true if n is a terminal, \c false otherwise |
|
289 bool terminal(Node n){ |
|
290 return _dijkstra.reached(n) && (*_pred)[n] == INVALID; |
|
291 } |
|
292 |
|
293 /// \brief The total cost of the tree |
|
294 /// |
|
295 /// The total cost of the constructed tree. The calculated value does |
|
296 /// not exceed the double of the optimal value. |
|
297 Value treeValue() const { |
|
298 return _value; |
|
299 } |
|
300 |
273 }; |
301 }; |
274 |
302 |
275 } //END OF NAMESPACE LEMON |
303 } //END OF NAMESPACE LEMON |
276 |
304 |
277 #endif |
305 #endif |