TreeTemplateTools.h

Go to the documentation of this file.

//
// File: TreeTemplateTools.h
// Created by:  Julien Dutheil
// Created on: Fri Oct  13 13:00 2006
// From file TreeTools.h
// Created on: Wed Aug  6 13:45:28 2003
//

/*
   Copyright or © or Copr. Bio++ Development Team, (November 16, 2004)

   This software is a computer program whose purpose is to provide classes
   for phylogenetic data analysis.

   This software is governed by the CeCILL  license under French law and
   abiding by the rules of distribution of free software.  You can  use,
   modify and/ or redistribute the software under the terms of the CeCILL
   license as circulated by CEA, CNRS and INRIA at the following URL
   "http://www.cecill.info".

   As a counterpart to the access to the source code and  rights to copy,
   modify and redistribute granted by the license, users are provided only
   with a limited warranty  and the software's author,  the holder of the
   economic rights,  and the successive licensors  have only  limited
   liability.

   In this respect, the user's attention is drawn to the risks associated
   with loading,  using,  modifying and/or developing or reproducing the
   software by the user in light of its specific status of free software,
   that may mean  that it is complicated to manipulate,  and  that  also
   therefore means  that it is reserved for developers  and  experienced
   professionals having in-depth computer knowledge. Users are therefore
   encouraged to load and test the software's suitability as regards their
   requirements in conditions enabling the security of their systems and/or
   data to be ensured and,  more generally, to use and operate it in the
   same conditions as regards security.

   The fact that you are presently reading this means that you have had
   knowledge of the CeCILL license and that you accept its terms.
 */

#ifndef _TREETEMPLATETOOLS_H_
#define _TREETEMPLATETOOLS_H_

#include "TreeTools.h"
#include <Bpp/Numeric/Random/RandomTools.h>

// From the STL:
#include <string>
#include <vector>

namespace bpp
{
template<class N> class TreeTemplate;


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>(*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)
  {
    if (node.isLeaf())
    {
      ids.push_back(node.getId());
    }
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getLeavesId(*node.getSon(i), ids);
    }
  }

  static std::vector<int> getAncestorsId(const Node& node)
  {
    std::vector<int> ids;
    const Node* n = &node;
    while (n->hasFather())
    {
      n = n->getFather();
      ids.push_back(n->getId());
    }
    return ids;
  }

  static int getLeafId(const Node& node, const std::string& name) throw (NodeNotFoundException)
  {
    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) throw (NodeNotFoundException)
  {
    if (node.isLeaf())
    {
      if (node.getName() == name)
      {
        id = new int(node.getId());
        return;
      }
    }
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      searchLeaf(*node.getSon(i), name, id);
    }
  }

  template<class N>
  static void dropLeaf(TreeTemplate<N>& tree, const std::string& leafName) throw (NodeNotFoundException, Exception)
  {
    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) throw (Exception)
  {
    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>(*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 std::vector<int> getBranchesId(const Node& node)
  {
    std::vector<int> ids;
    getBranchesId(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());
  }

  static void getBranchesId(const Node& node, std::vector<int>& ids)
  {
    for (size_t i = 0; i < node.getNumberOfSons(); i++)
    {
      getNodesId(*node.getSon(i), ids);
    }
  }

  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>(*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>(*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>(*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 unsigned int getNumberOfLeaves(const Node& node);

  static unsigned int getNumberOfNodes(const Node& node);

  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);

  static std::vector<const Node*> getPathBetweenAnyTwoNodes(const Node& node1, const Node& node2, bool includeAncestor = true);

  template<class N>
  static N* cloneSubtree(const Node& node)
  {
    // First we copy this node using default copy constuctor:
    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 = 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 constuctor:
    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) throw (NodePException);

  static double getTotalLength(const Node& node, bool includeAncestor = true) throw (NodePException);

  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) throw (NodePException);

  static double getDistanceBetweenAnyTwoNodes(const Node& node1, const Node& node2);

  static 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) throw (IOException);

  static Node* parenthesisToNode(const std::string& description, bool bootstrap = true, const std::string& propertyName = TreeTools::BOOTSTRAP, bool withId = false);

  static TreeTemplate<Node>* parenthesisToTree(const std::string& description, bool bootstrap = true, const std::string& propertyName = TreeTools::BOOTSTRAP, bool withId = false) throw (Exception);

  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 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 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 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 // _TREETEMPLATETOOLS_H_