43 #include <Bpp/Text/TextTools.h> 44 #include <Bpp/App/ApplicationTools.h> 45 #include <Bpp/Numeric/VectorTools.h> 60 searchableTree_->topologyChangePerformed(event);
61 for (
size_t i = 0; i < topoListeners_.size(); i++)
63 topoListeners_[i]->topologyChangePerformed(event);
69 searchableTree_->topologyChangeTested(event);
70 for (
size_t i = 0; i < topoListeners_.size(); i++)
72 topoListeners_[i]->topologyChangeTested(event);
78 searchableTree_->topologyChangeSuccessful(event);
79 for (
size_t i = 0; i < topoListeners_.size(); i++)
81 topoListeners_[i]->topologyChangeSuccessful(event);
87 if (algorithm_ == FAST)
89 else if (algorithm_ == BETTER)
91 else if (algorithm_ == PHYML)
94 throw Exception(
"Unknown NNI algorithm: " + algorithm_ +
".\n");
103 vector<Node*> nodes = tree.
getNodes();
105 vector<Node*> nodesSub = nodes;
106 for (
size_t i = nodesSub.size(); i > 0; i--)
109 if (!(nodesSub[i - 1]->hasFather()))
110 nodesSub.erase(nodesSub.begin() +
static_cast<ptrdiff_t
>(i - 1));
111 else if (!(nodesSub[i - 1]->getFather()->hasFather()))
112 nodesSub.erase(nodesSub.begin() +
static_cast<ptrdiff_t
>(i - 1));
117 for (
size_t i = 0; !test && i < nodesSub.size(); i++)
119 Node* node = nodesSub[i];
120 double diff = searchableTree_->testNNI(node->
getId());
123 ApplicationTools::displayResult(
" Testing node " + TextTools::toString(node->
getId())
125 TextTools::toString(diff));
132 ApplicationTools::displayResult(
" Swapping node " + TextTools::toString(node->
getId())
134 TextTools::toString(diff));
136 searchableTree_->doNNI(node->
getId());
142 ApplicationTools::displayResult(
" Current value", TextTools::toString(searchableTree_->getTopologyValue(), 10));
155 vector<Node*> nodes = tree.
getNodes();
158 ApplicationTools::displayTask(
"Test all possible NNIs...");
160 vector<Node*> nodesSub = nodes;
161 for (
size_t i = nodesSub.size(); i > 0; i--)
163 if (!(nodesSub[i - 1]->hasFather()))
164 nodesSub.erase(nodesSub.begin() +
static_cast<ptrdiff_t
>(i - 1));
165 else if (!(nodesSub[i - 1]->getFather()->hasFather()))
166 nodesSub.erase(nodesSub.begin() +
static_cast<ptrdiff_t
>(i - 1));
170 vector<Node*> improving;
171 vector<double> improvement;
172 if (verbose_ >= 2 && ApplicationTools::message)
173 ApplicationTools::message->endLine();
174 for (
size_t i = 0; i < nodesSub.size(); i++)
176 Node* node = nodesSub[i];
177 double diff = searchableTree_->testNNI(node->
getId());
180 ApplicationTools::displayResult(
" Testing node " + TextTools::toString(node->
getId())
182 TextTools::toString(diff));
187 improving.push_back(node);
188 improvement.push_back(diff);
192 ApplicationTools::displayTaskDone();
193 test = improving.size() > 0;
196 size_t nodeMin = VectorTools::whichMin(improvement);
197 Node* node = improving[nodeMin];
199 ApplicationTools::displayResult(
" Swapping node " + TextTools::toString(node->
getId())
201 TextTools::toString(improvement[nodeMin]));
202 searchableTree_->doNNI(node->
getId());
208 ApplicationTools::displayResult(
" Current value", TextTools::toString(searchableTree_->getTopologyValue(), 10));
220 ApplicationTools::displayTask(
"Test all possible NNIs...");
222 vector<Node*> nodes = tree.
getNodes();
223 vector<Node*> nodesSub = nodes;
224 for (
size_t i = nodesSub.size(); i > 0; i--)
227 if (!(nodesSub[i - 1]->hasFather()))
228 nodesSub.erase(nodesSub.begin() +
static_cast<ptrdiff_t
>(i - 1));
229 else if (!(nodesSub[i - 1]->getFather()->hasFather()))
230 nodesSub.erase(nodesSub.begin() +
static_cast<ptrdiff_t
>(i - 1));
234 vector<int> improving;
235 vector<Node*> improvingNodes;
236 vector<double> improvement;
237 if (verbose_ >= 2 && ApplicationTools::message)
238 ApplicationTools::message->endLine();
239 for (
size_t i = 0; i < nodesSub.size(); i++)
241 Node* node = nodesSub[i];
242 double diff = searchableTree_->testNNI(node->
getId());
245 ApplicationTools::displayResult(
" Testing node " + TextTools::toString(node->
getId())
247 TextTools::toString(diff));
254 for (
size_t j = improving.size(); j > 0; j--)
256 if (improvingNodes[j - 1]->getFather()->getId() == node->
getFather()->
getId()
258 || improvingNodes[j - 1]->getId() == node->
getFather()->
getId() || improvingNodes[j - 1]->getFather()->getId() == node->
getId()
259 || improvingNodes[j - 1]->getId() == node->
getFather()->
getFather()->
getId() || improvingNodes[j - 1]->getFather()->getFather()->getId() == node->
getId()
263 if (diff < improvement[j - 1])
265 improvingNodes.erase(improvingNodes.begin() +
static_cast<ptrdiff_t
>(j - 1));
266 improving.erase(improving.begin() +
static_cast<ptrdiff_t
>(j - 1));
267 improvement.erase(improvement.begin() +
static_cast<ptrdiff_t
>(j - 1));
278 size_t pos = improvement.size();
279 for (
size_t j = 0; j < improvement.size(); j++)
281 if (diff < improvement[j])
286 if (pos < improvement.size())
288 improvingNodes.insert(improvingNodes.begin() +
static_cast<ptrdiff_t
>(pos), node);
289 improving.insert(improving.begin() +
static_cast<ptrdiff_t
>(pos), node->
getId());
290 improvement.insert(improvement.begin() +
static_cast<ptrdiff_t
>(pos), diff);
294 improvingNodes.insert(improvingNodes.end(), node);
295 improving.insert(improving.end(), node->
getId());
296 improvement.insert(improvement.end(), diff);
304 improvingNodes.clear();
306 ApplicationTools::displayTaskDone();
307 test = improving.size() > 0;
310 double currentValue = searchableTree_->getTopologyValue();
317 ApplicationTools::displayMessage(
"Trying to perform " + TextTools::toString(improving.size()) +
" NNI(s).");
318 for (
size_t i = 0; i < improving.size(); i++)
320 int nodeId = improving[i];
323 ApplicationTools::displayResult(
string(
" Swapping node ") + TextTools::toString(nodeId)
324 +
string(
" at ") + TextTools::toString(searchableTree_->getTopology().getFatherId(nodeId)),
325 TextTools::toString(improvement[i]));
327 searchableTree_->doNNI(improving[i]);
333 ApplicationTools::displayResult(
" Current value", TextTools::toString(searchableTree_->getTopologyValue(), 10));
334 if (searchableTree_->getTopologyValue() >= currentValue)
338 delete searchableTree_;
342 ApplicationTools::displayResult(
"Score >= current score! Moving backward", TextTools::toString(searchableTree_->getTopologyValue()));
345 if (improving.size() == 1)
348 throw Exception(
"NNITopologySearch::searchPhyML. Error, no improving NNI!\n This may be due to a change in parameters between testNNI and doNNI. Check your code!");
350 size_t n = (size_t)ceil((
double)improving.size() / 2.);
351 improving.erase(improving.begin() +
static_cast<ptrdiff_t
>(n), improving.end());
352 improvement.erase(improvement.begin() +
static_cast<ptrdiff_t
>(n), improvement.end());
void notifyAllTested(const TopologyChangeEvent &event)
Process a TopologyChangeEvent to all listeners.
static const std::string FAST
void search()
Performs the search.
void notifyAllPerformed(const TopologyChangeEvent &event)
Process a TopologyChangeEvent to all listeners.
Interface for Nearest Neighbor Interchanges algorithms.
The phylogenetic tree class.
virtual const Node * getFather() const
Get the father of this node is there is one.
virtual int getId() const
Get the node's id.
virtual NNISearchable * clone() const =0
Class for notifying new toplogy change events.
The phylogenetic node class.
static const std::string BETTER
static const std::string PHYML
void notifyAllSuccessful(const TopologyChangeEvent &event)
Process a TopologyChangeEvent to all listeners.
virtual std::vector< const N * > getNodes() const