TreeTemplateTools.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: The Bio++ Development Group
//
// SPDX-License-Identifier: CECILL-2.1
 
#ifndef BPP_PHYL_TREE_TREETEMPLATETOOLS_H
#define BPP_PHYL_TREE_TREETEMPLATETOOLS_H
 
#include <Bpp/Numeric/Random/RandomTools.h>
 
#include "TreeTools.h"
#include "Node.h"
 
// From the STL:
#include <string>
#include <vector>
 
 
namespace bpp
{
template<class N> class TreeTemplate;
 
class PhyloTree;
 
class TreeTemplateTools
{
public:
  TreeTemplateTools() {}
  virtual ~TreeTemplateTools() {}
 
public:
  template<class N>
  static std::vector<N*> getLeaves(N& node)
  {
    std::vector<N*> leaves;
    getLeaves<N>(node, leaves);
    return leaves;
  }
 
  template<class N>
  static void getLeaves(N& node, std::vector<N*>& leaves)
  {
    if (node.isLeaf())
    {
      leaves.push_back(&node);
    }
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getLeaves<N>(*dynamic_cast<N*>(node.getSon(i)), leaves);
    }
  }
 
  static std::vector<int> getLeavesId(const Node& node)
  {
    std::vector<int> ids;
    getLeavesId(node, ids);
    return ids;
  }
 
  static void getLeavesId(const Node& node, std::vector<int>& ids);
 
  static std::vector<int> getAncestorsId(const Node& node);
 
  static int getLeafId(const Node& node, const std::string& name)
  {
    int* id = 0;
    searchLeaf(node, name, id);
    if (id == 0) throw NodeNotFoundException("TreeTemplateTools::getLeafId().", name);
    else
    {
      int i = *id;
      delete id;
      return i;
    }
  }
 
  static void searchLeaf(const Node& node, const std::string& name, int*& id);
 
  template<class N>
  static void dropLeaf(TreeTemplate<N>& tree, const std::string& leafName)
  {
    N* leaf = tree.getNode(leafName);
    if (!leaf->hasFather())
      throw Exception("TreeTemplateTools::dropLeaf(). Leaf is the only node in the tree, can't remove it.");
    N* parent = leaf->getFather();
    if (parent->getNumberOfSons() > 2)
    {
      // The easy case:
      parent->removeSon(leaf);
      delete leaf;
    }
    else if (parent->getNumberOfSons() == 2)
    {
      // We have to delete the parent node as well:
      N* brother = parent->getSon(0);
      if (brother == leaf) brother = parent->getSon(1);
      if (!parent->hasFather())
      {
        // The brother becomes the root:
        if (leaf->hasDistanceToFather() && brother->hasDistanceToFather())
        {
          brother->setDistanceToFather(brother->getDistanceToFather() + leaf->getDistanceToFather());
        }
        brother->removeFather();
        tree.setRootNode(brother);
        delete parent;
        delete leaf;
      }
      else
      {
        N* gParent = parent->getFather();
        if (brother->hasDistanceToFather() && parent->hasDistanceToFather())
        {
          brother->setDistanceToFather(brother->getDistanceToFather() + parent->getDistanceToFather());
        }
        size_t pos = gParent->getSonPosition(parent);
        gParent->setSon(pos, brother);
        delete parent;
        delete leaf;
      }
    }
    else
    {
      // Dunno what to do in that case :(
      throw Exception("TreeTemplateTools::dropLeaf. Parent node as only one child, I don't know what to do in that case :(");
    }
  }
 
  template<class N>
  static void dropSubtree(TreeTemplate<N>& tree, Node* subtree)
  {
    if (!subtree->hasFather())
      throw Exception("TreeTemplateTools::dropSubtree(). Trying to remove the full tree!");
    N* parent = subtree->getFather();
    if (parent->getNumberOfSons() > 2)
    {
      // The easy case:
      parent->removeSon(subtree);
      deleteSubtree(subtree);
    }
    else if (parent->getNumberOfSons() == 2)
    {
      // We have to delete the parent node as well:
      N* brother = parent->getSon(0);
      if (brother == subtree) brother = parent->getSon(1);
      if (!parent->hasFather())
      {
        // The brother becomes the root:
        if (subtree->hasDistanceToFather() && brother->hasDistanceToFather())
        {
          brother->setDistanceToFather(brother->getDistanceToFather() + subtree->getDistanceToFather());
        }
        tree.setRootNode(brother);
        delete parent;
        deleteSubtree(subtree);
      }
      else
      {
        N* gParent = parent->getFather();
        if (brother->hasDistanceToFather() && parent->hasDistanceToFather())
        {
          brother->setDistanceToFather(brother->getDistanceToFather() + parent->getDistanceToFather());
        }
        size_t pos = gParent->getSonPosition(parent);
        gParent->setSon(pos, brother);
        delete parent;
        deleteSubtree(subtree);
      }
    }
    else
    {
      // Dunno what to do in that case :(
      throw Exception("TreeTemplateTools::dropSubtree. Parent node as only one child, I don't know what to do in that case :(");
    }
  }
 
  template<class N>
  static void sampleSubtree(TreeTemplate<N>& tree, const std::vector<std::string>& leaves, size_t size)
  {
    std::vector<std::string> names = leaves;
    for (size_t n = names.size(); n > size; --n)
    {
      size_t i = RandomTools::giveIntRandomNumberBetweenZeroAndEntry(n);
      dropLeaf(tree, names[i]);
      names.erase(names.begin() + static_cast<ptrdiff_t>(i));
    }
  }
 
  template<class N>
  static std::vector<N*> getNodes(N& node)
  {
    std::vector<N*> nodes;
    getNodes<N>(node, nodes);
    return nodes;
  }
 
  template<class N>
  static void getNodes(N& node, std::vector<N*>& nodes)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getNodes<N>(*dynamic_cast<N*>(node.getSon(i)), nodes);
    }
    nodes.push_back(&node);
  }
 
  static std::vector<int> getNodesId(const Node& node)
  {
    std::vector<int> ids;
    getNodesId(node, ids);
    return ids;
  }
 
  static void getNodesId(const Node& node, std::vector<int>& ids)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getNodesId(*node.getSon(i), ids);
    }
    ids.push_back(node.getId());
  }
 
  template<class N>
  static std::vector<N*> getInnerNodes(N& node)
  {
    std::vector<N*> nodes;
    getInnerNodes<N>(node, nodes);
    return nodes;
  }
 
  template<class N>
  static void getInnerNodes(N& node, std::vector<N*>& nodes)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getInnerNodes<N>(*dynamic_cast<N*>(node.getSon(i)), nodes);
    }
    if (!node.isLeaf())
      nodes.push_back(&node); // Do not add leaves!
  }
 
  static std::vector<int> getInnerNodesId(const Node& node)
  {
    std::vector<int> ids;
    getInnerNodesId(node, ids);
    return ids;
  }
 
  static void getInnerNodesId(const Node& node, std::vector<int>& ids)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getInnerNodesId(*node.getSon(i), ids);
    }
    if (!node.isLeaf())
      ids.push_back(node.getId()); // Do not add leaves!
  }
 
  template<class N>
  static std::vector<N*> searchNodeWithId(N& node, int id)
  {
    std::vector<N*> nodes;
    searchNodeWithId<N>(node, id, nodes);
    return nodes;
  }
 
  template<class N>
  static void searchNodeWithId(N& node, int id, std::vector<N*>& nodes)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); ++i)
    {
      searchNodeWithId<N>(*dynamic_cast<N*>(node.getSon(i)), id, nodes);
    }
    if (node.getId() == id) nodes.push_back(&node);
  }
 
  static Node* searchFirstNodeWithId(Node& node, int id)
  {
    if (node.getId() == id)
      return &node;
    else
    {
      for (size_t i = 0; i < node.getNumberOfSons(); ++i)
      {
        Node* result = searchFirstNodeWithId(*node.getSon(i), id);
        if (result)
          return result;
      }
    }
    return 0;
  }
 
  static const Node* searchFirstNodeWithId(const Node& node, int id)
  {
    if (node.getId() == id)
      return &node;
    else
    {
      for (size_t i = 0; i < node.getNumberOfSons(); ++i)
      {
        const Node* result = searchFirstNodeWithId(*node.getSon(i), id);
        if (result)
          return result;
      }
    }
    return 0;
  }
 
  template<class N>
  static bool hasNodeWithId(const N& node, int id)
  {
    if (node.getId() == id) return true;
    else
    {
      for (size_t i = 0; i < node.getNumberOfSons(); i++)
      {
        if (hasNodeWithId(*node.getSon(i), id)) return true;
      }
      return false;
    }
  }
 
  template<class N>
  static std::vector<N*> searchNodeWithName(N& node, const std::string& name)
  {
    std::vector<N*> nodes;
    searchNodeWithId<N>(node, name, nodes);
    return nodes;
  }
 
  template<class N>
  static void searchNodeWithName(N& node, const std::string& name, std::vector<N*>& nodes)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      searchNodeWithName<N>(*dynamic_cast<N*>(node.getSon(i)), name, nodes);
    }
    if (node.hasName() && node.getName() == name) nodes.push_back(&node);
  }
 
  template<class N>
  static bool hasNodeWithName(const N& node, const std::string& name)
  {
    if (node.hasName() & node.getName() == name) return true;
    else
    {
      for (size_t i = 0; i < node.getNumberOfSons(); i++)
      {
        if (hasNodeWithName(*node.getSon(i), name)) return true;
      }
      return false;
    }
  }
 
  static bool isRoot(const Node& node) { return !node.hasFather(); }
 
  static size_t getNumberOfBranches(const Node& node)
  {
    size_t nbBranches = 0; // Basal node has no branch
    for (int i = 0; i < static_cast<int>(node.getNumberOfSons()); i++)
    {
      nbBranches += getNumberOfNodes(*node[i]); // All son nodes define one branch each
    }
    return nbBranches;
  }
 
  static size_t getNumberOfLeaves(const Node& node);
 
  static size_t getNumberOfNodes(const Node& node)
  {
    size_t nbNodes = 1;
    for (int i = 0; i < static_cast<int>(node.getNumberOfSons()); i++)
    {
      nbNodes += getNumberOfNodes(*node[i]);
    }
    return nbNodes;
  }
 
 
  static std::vector<std::string> getLeavesNames(const Node& node);
 
  static unsigned int getDepth(const Node& node);
 
  static unsigned int getDepths(const Node& node, std::map<const Node*, unsigned int>& depths);
 
  static double getHeight(const Node& node);
 
  static double getHeights(const Node& node, std::map<const Node*, double>& heights);
 
  static bool isMultifurcating(const Node& node);
 
  static bool haveSameOrderedTopology(const Node& n1, const Node& n2);
 
  static std::vector<Node*> getPathBetweenAnyTwoNodes(Node& node1, Node& node2, bool includeAncestor = true, bool includeAncestorAtEndOfPath = true);
 
  static std::vector<const Node*> getPathBetweenAnyTwoNodes(const Node& node1, const Node& node2, bool includeAncestor = true, bool includeAncestorAtEndOfPath = true);
 
  template<class N>
  static N* cloneSubtree(const Node& node)
  {
    // First we copy this node using default copy constructor:
    N* clone = new N(node);
    // We remove the link toward the father:
    // clone->removeFather();
 
    // Now we perform a hard copy:
    for (int i = 0; i < static_cast<int>(node.getNumberOfSons()); i++)
    {
      clone->addSon(cloneSubtree<N>(*node[i]));
    }
    return clone;
  }
 
  template<class N>
  static void deleteSubtree(N* node)
  {
    for (size_t i = 0; i < node->getNumberOfSons(); ++i)
    {
      N* son = dynamic_cast<N*>(node->getSon(i));
      deleteSubtree(son);
      delete son;
    }
  }
 
 
  template<class N>
  static N* cloneSubtree(const Tree& tree, int nodeId)
  {
    // First we copy this node using default copy constructor:
    N* clone = tree.hasNodeName(nodeId) ? new N(nodeId, tree.getNodeName(nodeId)) : new N(nodeId);
    // Then we set the length:
    if (tree.hasDistanceToFather(nodeId))
      clone->setDistanceToFather(tree.getDistanceToFather(nodeId));
    // Now we copy all sons:
    std::vector<int> sonsId = tree.getSonsId(nodeId);
    for (size_t i = 0; i < sonsId.size(); i++)
    {
      clone->addSon(cloneSubtree<N>(tree, sonsId[i]));
    }
    // Must copy all properties too:
    std::vector<std::string> names;
    names = tree.getNodePropertyNames(nodeId);
    for (size_t i = 0; i < names.size(); i++)
    {
      clone->setNodeProperty(names[i], *tree.getNodeProperty(nodeId, names[i]));
    }
    names = tree.getBranchPropertyNames(nodeId);
    for (size_t i = 0; i < names.size(); i++)
    {
      clone->setBranchProperty(names[i], *tree.getBranchProperty(nodeId, names[i]));
    }
 
    return clone;
  }
  static Vdouble getBranchLengths(const Node& node);
 
  static double getTotalLength(const Node& node, bool includeAncestor = true);
 
  static void setBranchLengths(Node& node, double brLen);
 
  static void deleteBranchLengths(Node& node);
 
  static void setVoidBranchLengths(Node& node, double brLen);
 
  static void scaleTree(Node& node, double factor);
 
  static double getDistanceBetweenAnyTwoNodes(const Node& node1, const Node& node2);
 
  static std::unique_ptr<DistanceMatrix> getDistanceMatrix(const TreeTemplate<Node>& tree);
 
private:
  static void processDistsInSubtree_(const Node* node, DistanceMatrix& matrix, std::vector< std::pair<std::string, double>>& distsToNodeFather);
 
public:
  struct Element
  {
public:
    std::string content;
    std::string length;
    std::string bootstrap;
    bool isLeaf;
 
public:
    Element() : content(),
      length(),
      bootstrap(),
      isLeaf(false) {}
  };
 
  static Element getElement(const std::string& elt);
 
  static Node* parenthesisToNode(const std::string& description, unsigned int& nodeCounter, bool bootstrap = true, const std::string& propertyName = TreeTools::BOOTSTRAP, bool withId = false, bool verbose = true);
 
  static std::unique_ptr<TreeTemplate<Node>> parenthesisToTree(const std::string& description, bool bootstrap = true, const std::string& propertyName = TreeTools::BOOTSTRAP, bool withId = false, bool verbose = true);
 
  static std::string nodeToParenthesis(const Node& node, bool writeId = false);
 
  static std::string nodeToParenthesis(const Node& node, bool bootstrap, const std::string& propertyName);
 
  static std::string treeToParenthesis(const TreeTemplate<Node>& tree, bool writeId = false);
 
  static std::string treeToParenthesis(const TreeTemplate<Node>& tree, bool bootstrap, const std::string& propertyName);
 
  static std::unique_ptr<TreeTemplate<Node>> buildFromPhyloTree(const PhyloTree& treetemp);
 
  static std::unique_ptr<TreeTemplate<Node>> getRandomTree(std::vector<std::string>& leavesNames, bool rooted = true);
 
  static std::vector<const Node*> getRemainingNeighbors(const Node* node1, const Node* node2, const Node* node3);
 
  static void incrementAllIds(Node* node, int increment);
 
  static void getNodePropertyNames(const Node& node, std::vector<std::string>& propertyNames);
 
  static void getNodeProperties(const Node& node, const std::string& propertyName, std::map<int, const Clonable*>& properties);
 
  static void getNodeProperties(Node& node, const std::string& propertyName, std::map<int, Clonable*>& properties);
 
  static void deleteNodeProperties(Node& node, const std::vector<std::string>& propertyNames);
 
  static void getBranchPropertyNames(const Node& node, std::vector<std::string>& propertyNames);
 
  static void getBranchProperties(const Node& node, const std::string& propertyName, std::map<int, const Clonable*>& properties);
 
  static void getBranchProperties(Node& node, const std::string& propertyName, std::map<int, Clonable*>& properties);
 
  static void deleteBranchProperties(Node& node, const std::vector<std::string>& propertyNames);
 
  static void orderTree(Node& node, bool downward = true, bool orderLeaves = false)
  {
    orderTree_(node, downward, orderLeaves);
  }
 
  static void midRoot(TreeTemplate<Node>& tree, short criterion, bool forceBranchRoot);
 
  static double getRadius(TreeTemplate<Node>& tree);
 
 
  static void unresolveUncertainNodes(Node& subtree, double threshold, const std::string& property = TreeTools::BOOTSTRAP);
 
private:
  struct OrderTreeData_
  {
    size_t size;
    std::string firstLeaf;
    OrderTreeData_() : size(0),
      firstLeaf("") {}
  };
 
  static OrderTreeData_ orderTree_(Node& node, bool downward, bool orderLeaves);
 
  struct Moments_
  {
    double sum;
    double squaresSum;
    int numberOfLeaves;
  };
 
  static Moments_ getSubtreeMoments_(const Node* node);
 
  static void getBestRootInSubtree_(bpp::TreeTemplate<bpp::Node>& tree, short criterion,  bpp::Node* node, std::pair<bpp::Node*, std::map<std::string, double>>& bestRoot);
 
public:
  static const short MIDROOT_VARIANCE;
  static const short MIDROOT_SUM_OF_SQUARES;
};
} // end of namespace bpp.
#endif // BPP_PHYL_TREE_TREETEMPLATETOOLS_H