TreeTools.h

Go to the documentation of this file.

//
// File: TreeTools.h
// Created by:  Julien Dutheil
// 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 _TREETOOLS_H_
#define _TREETOOLS_H_

#include "TreeExceptions.h"
#include "Node.h"
#include "Tree.h"
#include "BipartitionList.h"

#include <Bpp/Exceptions.h>
#include <Bpp/Numeric/VectorTools.h>

// From SeqLib:
#include <Bpp/Seq/Container/VectorSiteContainer.h>
#include <Bpp/Seq/DistanceMatrix.h>

namespace bpp
{

class TreeTools
{
  public:
    TreeTools() {}
    virtual ~TreeTools() {}
  
  public:

    static std::vector<int> getLeavesId(const Tree& tree, int nodeId) throw (NodeNotFoundException);

    static void getLeavesId(const Tree& tree, int nodeId, std::vector<int>& leaves) throw (NodeNotFoundException);
 
    static size_t getNumberOfLeaves(const Tree& tree, int nodeId) throw (NodeNotFoundException);
 
    static int getLeafId(const Tree& tree, int nodeId, const std::string& name) throw (NodeNotFoundException);

    static void searchLeaf(const Tree& tree, int nodeId, const std::string& name, int*& id) throw (NodeNotFoundException);

    static std::vector<int> getPathBetweenAnyTwoNodes(const Tree& tree, int nodeId1, int nodeId2, bool includeAncestor = true) throw (NodeNotFoundException);
 
    static std::vector<int> getAncestors(const Tree& tree, int nodeId) throw (NodeNotFoundException);

    static int getLastCommonAncestor(const Tree& tree, const std::vector<int>& nodeIds) throw (NodeNotFoundException, Exception);

    static size_t getDepth(const Tree& tree, int nodeId) throw (NodeNotFoundException);

    static size_t getDepths(const Tree& tree, int nodeId, std::map<int, size_t>& depths) throw (NodeNotFoundException);

    static double getHeight(const Tree& tree, int nodeId) throw (NodeNotFoundException,NodeException);

    static double getHeights(const Tree& tree, int nodeId, std::map<int, double>& heights) throw (NodeNotFoundException,NodeException);

    static Vdouble getBranchLengths(const Tree& tree, int nodeId) throw (NodeNotFoundException,NodeException);
    
    static double getTotalLength(const Tree& tree, int nodeId, bool includeAncestor = true) throw (NodeNotFoundException,NodeException);

    static void setBranchLengths(Tree& tree, int nodeId, double brLen) throw (NodeNotFoundException);
          
    static void setVoidBranchLengths(Tree& tree, int nodeId, double brLen) throw (NodeNotFoundException);
        
    static void scaleTree(Tree& tree, int nodeId, double factor) throw (NodeNotFoundException,NodeException);

    static void initBranchLengthsGrafen(Tree& tree);
    
    static void computeBranchLengthsGrafen(Tree& tree, double power = 1, bool init = true) throw (NodeException);
   
  private:
    static size_t initBranchLengthsGrafen(Tree& tree, int nodeId) throw (NodeNotFoundException);
    static void computeBranchLengthsGrafen(Tree& tree, int nodeId, double power, double total, double& height, double& heightRaised) throw (NodeNotFoundException,NodeException);

  public:
    static double convertToClockTree(Tree& tree, int nodeId, bool noneg = false);
    
    static double convertToClockTree2(Tree& tree, int nodeId);
 
    static double getDistanceBetweenAnyTwoNodes(const Tree& tree, int nodeId1, int nodeId2);
    
    static DistanceMatrix* getDistanceMatrix(const Tree& tree);

    static void midpointRooting(Tree& tree);
    static std::string nodeToParenthesis(const Tree& tree, int nodeId, bool writeId = false) throw (NodeNotFoundException);

    static std::string nodeToParenthesis(const Tree& tree, int nodeId, bool bootstrap, const std::string& propertyName) throw (NodeNotFoundException);

    static std::string treeToParenthesis(const Tree& tree, bool writeId = false);
    
    static std::string treeToParenthesis(const Tree& tree, bool bootstrap, const std::string& propertyName);
    
    static std::vector<int> getNodesId(const Tree& tree, int nodeId) throw (NodeNotFoundException);

    static void getNodesId(const Tree& tree, int nodeId, std::vector<int>& nodes) throw (NodeNotFoundException);

    static int getMaxId(const Tree& tree, int id);

    static int getMPNUId(const Tree& tree, int id);

    static bool checkIds(const Tree& tree, bool throwException) throw (Exception);

    static VectorSiteContainer* MRPEncode(const std::vector<Tree*>& vecTr);

    static VectorSiteContainer* MRPEncodeMultilabel(const std::vector<Tree*>& vecTr);

    static bool haveSameTopology(const Tree& tr1, const Tree& tr2);

    static int robinsonFouldsDistance(const Tree& tr1, const Tree& tr2, bool checkNames = true, int* missing_in_tr2 = NULL, int* missing_in_tr1 = NULL) throw (Exception);

    static BipartitionList* bipartitionOccurrences(const std::vector<Tree*>& vecTr, std::vector<size_t>& bipScore);

    static TreeTemplate<Node>* thresholdConsensus(const std::vector<Tree*>& vecTr, double threshold, bool checkNames = true) throw (Exception);

    static TreeTemplate<Node>* fullyResolvedConsensus(const std::vector<Tree*>& vecTr, bool checkNames = true);

    static TreeTemplate<Node>* majorityConsensus(const std::vector<Tree*>& vecTr, bool checkNames = true);

    static TreeTemplate<Node>* strictConsensus(const std::vector<Tree*>& vecTr, bool checkNames = true);

    static Tree* MRP(const std::vector<Tree*>& vecTr);

    static void computeBootstrapValues(Tree& tree, const std::vector<Tree*>& vecTr, bool verbose = true, int format = 0);
  
    static void constrainedMidPointRooting(Tree& tree);
    
    static Tree* MRPMultilabel(const std::vector<Tree*>& vecTr);

  
    static const std::string BOOTSTRAP;

  private:
    struct Moments_ {
      double N;
      double sum, squaredSum;
      Moments_(): N(0), sum(0), squaredSum(0) {}
    };    

    static Moments_ statFromNode_(Tree& tree, int rootId);
    static double bestRootPosition_(Tree& tree, int nodeId1, int nodeId2, double length);


};

} //end of namespace bpp.

#endif  //_TREETOOLS_H_