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 ) {
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 ) {
277 std::vector<Bipartition>
const& bipartitions,
278 std::vector<TreeNode const*>
const& nodes,
279 bool include_splitting_edges,
280 bool include_leaf_edges
286 auto set_result_edges = [&](
Bipartition const& bip ){
292 auto it = Preorder( bip.link().next() );
293 it != Preorder() && &it.link() != &bip.link().outer();
296 if (it.is_first_iteration()) {
299 result_edges.set( it.edge().index() );
304 if( include_splitting_edges || ( include_leaf_edges &&
is_leaf( bip.link().edge() ) )) {
305 result_edges.set( bip.link().edge().index() );
314 for(
auto const& bip : bipartitions ) {
320 if( ( bip.leaf_nodes() & leaves ) == bip.leaf_nodes() ) {
321 set_result_edges( bip );
327 if( ( inverted.leaf_nodes() & leaves ) == inverted.leaf_nodes() ) {
328 set_result_edges( inverted );
333 std::vector<size_t> edges;
334 for(
size_t i = 0; i < result_edges.size(); ++i ) {
335 if( result_edges.get( i ) ) {
336 edges.push_back( i );
344 std::vector<TreeNode const*>
const& nodes,
345 bool include_splitting_edges,
346 bool include_leaf_edges
350 tree, bipartitions, nodes, include_splitting_edges, include_leaf_edges
357 bool include_splitting_edges,
358 bool include_leaf_edges
363 tree, bipartitions, nodes, include_splitting_edges, include_leaf_edges
373 std::vector< tree::TreeNode const* >
const& nodes