CompactTree
compact_tree Class Reference

Classes

class  children_iterator
 
class  leaves_iterator
 
class  levelorder_iterator
 
class  postorder_iterator
 
class  preorder_iterator
 

Public Member Functions

 compact_tree (const char *const input, bool is_fn=true, bool store_labels=true, bool store_lengths=true, size_t reserve=0)
 
 compact_tree (const std::string &input, bool is_fn=true, bool store_labels=true, bool store_lengths=true, size_t reserve=0)
 
 compact_tree (const compact_tree &o)
 
CT_NODE_T add_child (const CT_NODE_T parent_node, const std::string &new_label=EMPTY_STRING, CT_LENGTH_T new_length=ZERO_LENGTH)
 
void print_newick (std::ostream &out, CT_NODE_T node=ROOT_NODE, bool include_semicolon=true)
 
std::string get_newick (CT_NODE_T node=ROOT_NODE, bool include_semicolon=true)
 
size_t get_num_nodes () const
 
size_t get_num_leaves ()
 
size_t get_num_internal ()
 
CT_NODE_T get_root () const
 
bool is_root (CT_NODE_T node) const
 
bool is_leaf (CT_NODE_T node) const
 
CT_NODE_T get_parent (CT_NODE_T node) const
 
const std::vector< CT_NODE_T > & get_children (CT_NODE_T node) const
 
bool has_edge_lengths () const
 
void clear_edge_lengths (bool shrink=true)
 
CT_LENGTH_T get_edge_length (CT_NODE_T node) const
 
const std::vector< CT_LENGTH_T > & get_edge_lengths () const
 
void set_edge_length (CT_NODE_T node, CT_LENGTH_T new_length)
 
bool has_labels () const
 
void clear_labels (bool shrink=true)
 
const std::string & get_label (CT_NODE_T node) const
 
void set_label (CT_NODE_T node, const std::string &new_label)
 
const std::vector< std::string > & get_labels () const
 
void replace_labels (const std::unordered_map< std::string, std::string > &label_map, bool include_internal=true)
 
std::tuple< const std::string *, CT_LENGTH_T, CT_NODE_T, const std::vector< CT_NODE_T > * > operator[] (CT_NODE_T i) const
 
preorder_iterator preorder_begin ()
 
preorder_iterator preorder_end ()
 
postorder_iterator postorder_begin ()
 
postorder_iterator postorder_end ()
 
levelorder_iterator levelorder_begin ()
 
levelorder_iterator levelorder_end ()
 
leaves_iterator leaves_begin ()
 
leaves_iterator leaves_end ()
 
children_iterator children_begin (CT_NODE_T node)
 
children_iterator children_end (CT_NODE_T node)
 
CT_NODE_T find_mrca (const std::unordered_set< CT_NODE_T > &nodes) const
 
compact_tree extract_subtree (CT_NODE_T node)
 
double calc_total_bl (bool include_internal=true, bool include_leaves=true) const
 
double calc_avg_bl (bool include_internal=true, bool include_leaves=true) const
 
double calc_dist (CT_NODE_T u, CT_NODE_T v) const
 
std::vector< std::pair< std::pair< CT_NODE_T, CT_NODE_T >, double > > calc_distance_matrix ()
 

Constructor & Destructor Documentation

◆ compact_tree() [1/3]

compact_tree::compact_tree ( const char *const  input,
bool  is_fn = true,
bool  store_labels = true,
bool  store_lengths = true,
size_t  reserve = 0 
)

Load a tree from a Newick file or C string

Parameters
inputThe filename or C string of the tree to load
is_fntrue if input is a filename (default), otherwise false if input is the Newick tree as a C string
store_labelstrue to store node labels (default), otherwise false (saves memory)
store_lengthstrue to store edge lengths (default), otherwise false (saves memory)
reserveHow many nodes to reserve memory for up-front to avoid std::vector resizes. It's fine if the true number of nodes in the tree exceeds this value (the std::vector will resize automatically), but get as close as possible for speed.

◆ compact_tree() [2/3]

compact_tree::compact_tree ( const std::string &  input,
bool  is_fn = true,
bool  store_labels = true,
bool  store_lengths = true,
size_t  reserve = 0 
)
inline

Load a tree from a Newick file or std::string

Parameters
inputThe filename or std::string of the tree to load
is_fntrue if input is a filename (default), otherwise false if input is the Newick tree as an std::string
store_labelstrue to store node labels (default), otherwise false (saves memory)
store_lengthstrue to store edge lengths (default), otherwise false (saves memory)
reserveHow many nodes to reserve memory for up-front to avoid std::vector resizes. It's fine if the true number of nodes in the tree exceeds this value (the std::vector will resize automatically), but get as close as possible for speed.

◆ compact_tree() [3/3]

compact_tree::compact_tree ( const compact_tree o)
inline

Copy constructor

Parameters
oThe other compact_tree to copy

Member Function Documentation

◆ add_child()

CT_NODE_T compact_tree::add_child ( const CT_NODE_T  parent_node,
const std::string &  new_label = EMPTY_STRING,
CT_LENGTH_T  new_length = ZERO_LENGTH 
)
inline

Add a child to an existing node

Parameters
parent_nodeThe parent node
new_labelThe label of the new child node
new_lengthThe length of edge incident to the new child node
Returns
The newly-created child node

◆ calc_avg_bl()

double compact_tree::calc_avg_bl ( bool  include_internal = true,
bool  include_leaves = true 
) const
inline

Calculate the average branch length of this tree

Parameters
include_internaltrue to include internal nodes, otherwise false
include_leavestrue to include leaves, otherwise false
Returns
The average branch length of this tree

◆ calc_dist()

double compact_tree::calc_dist ( CT_NODE_T  u,
CT_NODE_T  v 
) const
inline

Calculate the (weighted) distance between two nodes

Parameters
uThe first node
vThe second node
Returns
The (weighted) distance between u and v

◆ calc_distance_matrix()

std::vector< std::pair< std::pair< CT_NODE_T, CT_NODE_T >, double > > compact_tree::calc_distance_matrix ( )

Calculate the (weighted) distance matrix between all pairs of leaves

Returns
A vector<pair<pair<node,node>,double>> containing all pairwise leaf distances as ((u,v), distance)

◆ calc_total_bl()

double compact_tree::calc_total_bl ( bool  include_internal = true,
bool  include_leaves = true 
) const
inline

Calculate the total branch length of this tree

Parameters
include_internaltrue to include internal nodes, otherwise false
include_leavestrue to include leaves, otherwise false
Returns
The total branch length of this tree

◆ children_begin()

children_iterator compact_tree::children_begin ( CT_NODE_T  node)
inline

Return an iterator referring to the first child of a node

Parameters
nodeThe node to iterate over the children of
Returns
An iterator referring to the first child of node

◆ children_end()

children_iterator compact_tree::children_end ( CT_NODE_T  node)
inline

Return an iterator referring to just past the last child of a node

Parameters
nodeThe node to iterate over the children of
Returns
An iterator referring to just past the last child of node

◆ clear_edge_lengths()

void compact_tree::clear_edge_lengths ( bool  shrink = true)
inline

Clear all edge lengths in this tree

Parameters
shrinktrue to deallocate the memory that was allocated to store the edge lengths, otherwise false

◆ clear_labels()

void compact_tree::clear_labels ( bool  shrink = true)
inline

Clear all labels in this tree

Parameters
shrinktrue to deallocate the memory that was allocated to store the labels, otherwise false

◆ extract_subtree()

compact_tree compact_tree::extract_subtree ( CT_NODE_T  node)

Extract the subtree rooted at a given node

Parameters
nodeThe node that is the root of the desired subtree
Returns
The subtree rooted at node

◆ find_mrca()

CT_NODE_T compact_tree::find_mrca ( const std::unordered_set< CT_NODE_T > &  nodes) const

Find and return the Most Recent Common Ancestor (MRCA) of a collection of nodes

Parameters
nodesThe nodes to find the MRCA of
Returns
The MRCA of the nodes in nodes

◆ get_children()

const std::vector<CT_NODE_T>& compact_tree::get_children ( CT_NODE_T  node) const
inline

Get the children of a node

Parameters
nodeThe node to get the children of
Returns
The children of node

◆ get_edge_length()

CT_LENGTH_T compact_tree::get_edge_length ( CT_NODE_T  node) const
inline

Get the incident edge length of a node

Parameters
nodeThe node to get the incident edge length of
Returns
The incident edge length of node

◆ get_edge_lengths()

const std::vector<CT_LENGTH_T>& compact_tree::get_edge_lengths ( ) const
inline

Get all edge lengths (return by reference)

◆ get_label()

const std::string& compact_tree::get_label ( CT_NODE_T  node) const
inline

Get the label of a node

Parameters
nodeThe node to get the label of
Returns
The label of node

◆ get_labels()

const std::vector<std::string>& compact_tree::get_labels ( ) const
inline

Get all labels (return by reference)

Returns
A vector<string> where the i-th value is the label of node i

◆ get_newick()

std::string compact_tree::get_newick ( CT_NODE_T  node = ROOT_NODE,
bool  include_semicolon = true 
)
inline

Return the Newick string of the subtree rooted at a specific node (defaults to the root = entire tree)

Parameters
nodeThe root of the subtree to print the Newick string of
include_semicolontrue to print a semicolon at the end of the Newick string (to end the tree), otherwise false (e.g. subtree)

◆ get_num_internal()

size_t compact_tree::get_num_internal ( )
inline

Get the total number of internal nodes in the tree. First time is O(n) scan; subsequent times are O(1) lookup

Returns
The number of internal nodes in the tree

◆ get_num_leaves()

size_t compact_tree::get_num_leaves ( )
inline

Get the total number of leaves in the tree. First time is O(n) scan; subsequent times are O(1) lookup

Returns
The number of leaves in the tree

◆ get_num_nodes()

size_t compact_tree::get_num_nodes ( ) const
inline

Get the total number of nodes in the tree using a O(1) lookup

Returns
The number of nodes in the tree

◆ get_parent()

CT_NODE_T compact_tree::get_parent ( CT_NODE_T  node) const
inline

Get the parent of a node

Parameters
nodeThe node to get the parent of
Returns
The parent of node

◆ get_root()

CT_NODE_T compact_tree::get_root ( ) const
inline

Get the root of this tree (should always be 0)

Returns
The root of this tree

◆ has_edge_lengths()

bool compact_tree::has_edge_lengths ( ) const
inline

Check if this tree is storing edge lengths

Returns
true if this tree is storing edge lengths, otherwise false

◆ has_labels()

bool compact_tree::has_labels ( ) const
inline

Check if this tree is storing labels

Returns
true if this tree is storing labels, otherwise false

◆ is_leaf()

bool compact_tree::is_leaf ( CT_NODE_T  node) const
inline

Check if a node is a leaf

Parameters
nodeThe node to check
Returns
true if node is a leaf, otherwise false

◆ is_root()

bool compact_tree::is_root ( CT_NODE_T  node) const
inline

Check if a node is the root

Parameters
nodeThe node to check
Returns
true if node is the root, otherwise false

◆ leaves_begin()

leaves_iterator compact_tree::leaves_begin ( )
inline

Return an iterator referring to the first node of a leaf iteration

Returns
An iterator referring to the first node of a leaf iteration

◆ leaves_end()

leaves_iterator compact_tree::leaves_end ( )
inline

Return an iterator referring to just past the last node of a leaf iteration

Returns
An iterator referring to just past the last node of a leaf iteration

◆ levelorder_begin()

levelorder_iterator compact_tree::levelorder_begin ( )
inline

Return an iterator referring to the first node of a level-order traversal

Returns
An iterator referring to the first node of a level-order traversal

◆ levelorder_end()

levelorder_iterator compact_tree::levelorder_end ( )
inline

Return an iterator referring just past the last node of a level-order traversal

Returns
An iterator referring just past the last node of a level-order traversal

◆ operator[]()

std::tuple<const std::string*, CT_LENGTH_T, CT_NODE_T, const std::vector<CT_NODE_T>*> compact_tree::operator[] ( CT_NODE_T  i) const
inline

Return the data associated with a given node

Parameters
iThe node whose data to return
Returns
A tuple<const string*, CT_LENGTH_T, CT_NODE_T, const vector<CT_NODE_T>*> containing (1) a pointer to the label, (2) the incident edge length, (3) the parent, and (4) a pointer to the collection of children of node i

◆ postorder_begin()

postorder_iterator compact_tree::postorder_begin ( )
inline

Return an iterator referring to the first node of a post-order traversal

Returns
An iterator referring to the first node of a post-order traversal

◆ postorder_end()

postorder_iterator compact_tree::postorder_end ( )
inline

Return an iterator referring just past the last node of a post-order traversal

Returns
An iterator referring just past the last node of a post-order traversal

◆ preorder_begin()

preorder_iterator compact_tree::preorder_begin ( )
inline

Return an iterator referring to the first node of a pre-order traversal

Returns
An iterator referring to the first node of a pre-order traversal

◆ preorder_end()

preorder_iterator compact_tree::preorder_end ( )
inline

Return an iterator referring just past the last node of a pre-order traversal

Returns
An iterator referring just past the last node of a pre-order traversal

◆ print_newick()

void compact_tree::print_newick ( std::ostream &  out,
CT_NODE_T  node = ROOT_NODE,
bool  include_semicolon = true 
)

Print the Newick string of the subtree rooted at a specific node (defaults to the root = entire tree)

Parameters
outThe output stream to print the Newick string to
nodeThe root of the subtree to print the Newick string of
include_semicolontrue to print a semicolon at the end of the Newick string (to end the tree), otherwise false (e.g. subtree)

◆ replace_labels()

void compact_tree::replace_labels ( const std::unordered_map< std::string, std::string > &  label_map,
bool  include_internal = true 
)
inline

Replace all labels that match a user-provided mapping

Parameters
label_mapA mapping where keys are old labels and values are new labels (i.e., replace all occurrences of label s with label_map[s])
include_internaltrue to include internal nodes in the label replacement, otherwise false to only replace leaf labels

◆ set_edge_length()

void compact_tree::set_edge_length ( CT_NODE_T  node,
CT_LENGTH_T  new_length 
)
inline

Set the incident edge length of a node

Parameters
nodeThe node to set the incident edge length of
new_lengthThe new edge length to set

◆ set_label()

void compact_tree::set_label ( CT_NODE_T  node,
const std::string &  new_label 
)
inline

Set the label of a node

Parameters
nodeThe node to set the label of
new_labelThe new label to set

The documentation for this class was generated from the following file: