62 auto bipartitions = std::vector<Bipartition>( tree.
edge_count() );
68 if (it.is_last_iteration()) {
76 auto const leaf_idx = node_to_leafs[ it.node().index() ];
77 assert( leaf_idx != std::numeric_limits<std::size_t>::max() );
78 bp.bitvector().set(leaf_idx);
82 auto l = &it.link().next();
83 while( l != &it.link() ) {
84 assert( ! bipartitions[ l->edge().index() ].empty() );
85 bp.bitvector() |= bipartitions[ l->edge().index() ].leaf_nodes();
91 assert( bipartitions[ it.edge().index() ].empty() );
92 bipartitions[ it.edge().index() ] = bp;
98 for(
auto const& bip : bipartitions ) {
115 bool const sort_leaves =
true;
118 std::vector<size_t> nodes_to_leafs;
122 std::vector<size_t> name_order;
127 for(
auto const& node : tree.
nodes() ) {
138 for(
size_t i = 1; i < ordered.size(); ++i ) {
139 if( node_names[ ordered[ i ]] == node_names[ ordered[ i - 1 ]] ) {
140 throw std::runtime_error(
141 "Cannot build bipartitions for Tree that has duplicate node names." 147 name_order.resize( ordered.size() );
148 for(
size_t i = 0; i < ordered.size(); ++i ) {
149 name_order[ ordered[i] ] = i;
155 for(
auto const& node : tree.
nodes() ) {
160 assert( leaf_idx < name_order.size() );
161 nodes_to_leafs[ node.index() ] = name_order[ leaf_idx ];
165 nodes_to_leafs[ node.index() ] = leaf_idx;
169 nodes_to_leafs[ node.index() ] = std::numeric_limits<std::size_t>::max();
173 return nodes_to_leafs;
180 for(
auto n : leaf_nodes ) {
181 auto const leaf_idx = node_to_leafs[ n->index() ];
182 if( leaf_idx == std::numeric_limits<std::size_t>::max() ) {
183 throw std::runtime_error(
184 "Node at index " +
std::to_string( n->index() ) +
" is not a leaf." 187 result.
set( leaf_idx );
194 std::vector<size_t> ret;
202 auto it = Preorder( subtree.
next() );
203 it != Preorder() && &it.link() != &subtree.
outer();
206 if (it.is_first_iteration()) {
209 ret.push_back( it.edge().index() );
217 std::vector<Bipartition>
const& bipartitions,
218 std::vector<TreeNode const*>
const& nodes
221 if( bipartitions.size() != tree.
edge_count() ) {
222 throw std::runtime_error(
223 "Cannot find smallest subtree, as the nunber of given bipartitions does not match " 224 "the number of edges in the given tree. Use bipartition_set( tree ) to obtain a valid " 225 "set of bipartitions for the tree." 234 size_t min_count = 0;
243 throw std::runtime_error(
244 "Cannot find smallest subtree, as the bipartitions were not extracted for the given " 245 "tree. Use bipartition_set( tree ) to obtain a valid " 246 "set of bipartitions for the tree." 250 auto const inverted = ~(bip.leaf_nodes());
252 if( min_count == 0 || bip.leaf_nodes().count() < min_count ) {
258 if (min_count == 0 || inverted.count() < min_count) {
261 min_count = bip.leaf_nodes().count();
275 std::vector<Bipartition>
const& bipartitions,
276 std::vector<TreeNode const*>
const& nodes,
277 bool include_splitting_edges,
278 bool include_leaf_edges
284 auto set_result_edges = [&](
Bipartition const& bip ){
290 auto it = Preorder( bip.link().next() );
291 it != Preorder() && &it.link() != &bip.link().outer();
294 if (it.is_first_iteration()) {
297 result_edges.set( it.edge().index() );
302 if( include_splitting_edges || ( include_leaf_edges &&
is_leaf( bip.link().edge() ) )) {
303 result_edges.set( bip.link().edge().index() );
312 for(
auto const& bip : bipartitions ) {
318 if( ( bip.leaf_nodes() & leaves ) == bip.leaf_nodes() ) {
319 set_result_edges( bip );
325 if( ( inverted.leaf_nodes() & leaves ) == inverted.leaf_nodes() ) {
326 set_result_edges( inverted );
331 std::vector<size_t> edges;
332 for(
size_t i = 0; i < result_edges.size(); ++i ) {
333 if( result_edges.get( i ) ) {
334 edges.push_back( i );
342 std::vector<TreeNode const*>
const& nodes,
343 bool include_splitting_edges,
344 bool include_leaf_edges
348 tree, bipartitions, nodes, include_splitting_edges, include_leaf_edges
355 bool include_splitting_edges,
356 bool include_leaf_edges
359 auto const nodes =
find_nodes( tree, node_names,
true );
361 tree, bipartitions, nodes, include_splitting_edges, include_leaf_edges
371 std::vector< tree::TreeNode const* >
const& nodes
Provides some valuable algorithms that are not part of the C++ 11 STL.
size_t count() const
Count the number of set bits in the Bitvector, that is, its Hamming weight, or population count (popc...
Bipartition find_smallest_subtree(Tree const &tree, std::vector< Bipartition > const &bipartitions, std::vector< TreeNode const *> const &nodes)
Find the smallest subtree (measured in number of nodes) that contains all given nodes.
std::vector< size_t > get_clade_edges(Tree const &tree, std::vector< tree::TreeNode const * > const &nodes)
size_t edge_count() const
Return the number of TreeEdges of the Tree.
utils::Bitvector leaf_node_bitvector(Tree const &tree, std::vector< TreeNode const *> leaf_nodes)
Return a Bitvector that has as many entries as the tree has leaf nodes, and is true where the given l...
void set(size_t index)
Set the value of a single bit to true, with boundary check.
utils::Bitvector const & leaf_nodes() const
std::vector< TreeNode const * > find_nodes(Tree const &tree, std::vector< std::string > const &node_names, bool throw_on_failure, bool replace_underscores)
Find TreeNodes in a Tree, given their name.
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
TreeLink & next()
Return the next TreeLink within the TreeNode of this link.
std::vector< size_t > sort_indices(RandomAccessIterator first, RandomAccessIterator last, Comparator comparator)
Get the indices to the sorted order of the given range.
utils::Range< IteratorPostorder< true > > postorder(ElementType const &element)
bool is_subset(Bitvector const &sub, Bitvector const &super)
Subset or equal.
std::vector< size_t > node_to_leaf_map(Tree const &tree)
size_t leaf_node_count(Tree const &tree)
Count the number of leaf Nodes of a Tree.
utils::Range< IteratorNodes > nodes()
Class for representing phylogenetic trees.
std::vector< Bipartition > bipartition_set(Tree const &tree)
Provides some commonly used string utility functions.
bool belongs_to(Tree const &tree, TreeNode const &node)
Return whether the TreeNode belongs to the Tree, i.e., whether it is owned by the Tree...
std::string name
Name of the node.
size_t node_count() const
Return the number of TreeNodes of the Tree.
std::vector< size_t > get_subtree_edges(TreeLink const &subtree)
std::vector< size_t > find_monophyletic_subtree_edges(Tree const &tree, std::vector< Bipartition > const &bipartitions, std::vector< TreeNode const *> const &nodes, bool include_splitting_edges, bool include_leaf_edges)
Find clades of the tree that are monophyletic with respect to the given list of nodes, that is, clades that only contain nodes from that list. Return all edge indices of those clades.
Common class containing the commonly needed data for tree nodes.
std::shared_ptr< BaseOutputTarget > to_string(std::string &target_string)
Obtain an output target for writing to a string.
TreeLink & outer()
Return the TreeLink of the adjacent TreeNode.
bool is_leaf(TreeLink const &link)
Return true iff the node of the given link is a leaf node.
std::vector< std::string > node_names(Tree const &tree, bool leaves_only)
Returns a list of all TreeNode names of a Tree.