64 auto link1_u = utils::make_unique< TreeLink >();
65 auto link2_u = utils::make_unique< TreeLink >();
66 auto node1_u = utils::make_unique< TreeNode >();
67 auto node2_u = utils::make_unique< TreeNode >();
68 auto edge0_u = utils::make_unique< TreeEdge >();
71 link1_u->reset_index( 0 );
72 link1_u->reset_next( link1_u.get() );
73 link1_u->reset_outer( link2_u.get() );
74 link1_u->reset_node( node1_u.get() );
75 link1_u->reset_edge( edge0_u.get() );
77 link2_u->reset_index( 1 );
78 link2_u->reset_next( link2_u.get() );
79 link2_u->reset_outer( link1_u.get() );
80 link2_u->reset_node( node2_u.get() );
81 link2_u->reset_edge( edge0_u.get() );
83 node1_u->reset_index( 0 );
84 node1_u->reset_primary_link( link1_u.get() );
86 node2_u->reset_index( 1 );
87 node2_u->reset_primary_link( link2_u.get() );
89 edge0_u->reset_index( 0 );
90 edge0_u->reset_primary_link( link1_u.get() );
91 edge0_u->reset_secondary_link( link2_u.get() );
94 links.push_back( std::move( link1_u ));
95 links.push_back( std::move( link2_u ));
96 nodes.push_back( std::move( node1_u ));
97 nodes.push_back( std::move( node2_u ));
98 edges.push_back( std::move( edge0_u ));
112 throw std::runtime_error(
113 "Cannot add Node to a Tree where the given Node is not part of the Tree." 127 auto con_link_u = utils::make_unique< TreeLink >();
128 auto end_link_u = utils::make_unique< TreeLink >();
129 auto end_node_u = utils::make_unique< TreeNode >();
130 auto con_edge_u = utils::make_unique< TreeEdge >();
133 auto const con_link = con_link_u.get();
134 auto const end_link = end_link_u.get();
135 auto const end_node = end_node_u.get();
136 auto const con_edge = con_edge_u.get();
139 con_link->reset_index( links.size() );
140 con_link->reset_node( &target_node );
141 con_link->reset_edge( con_edge );
142 con_link->reset_outer( end_link );
146 auto last_link = up_link;
147 while( &last_link->next() != up_link ) {
148 last_link = &last_link->
next();
152 assert( &last_link->next() == up_link );
155 assert( &last_link->next() == con_link );
156 assert( &con_link->next() == up_link );
160 links.push_back( std::move( con_link_u ));
168 links.push_back( std::move( end_link_u ));
172 end_node->reset_primary_link( end_link );
174 nodes.push_back( std::move( end_node_u ));
178 con_edge->reset_primary_link( con_link );
179 con_edge->reset_secondary_link( end_link );
181 edges.push_back( std::move( con_edge_u ));
190 std::function<
void(
TreeEdge& target_edge,
TreeEdge& new_edge )> adjust_edges
194 throw std::runtime_error(
195 "Cannot add Node to Tree on an Edge that is not part of the Tree." 208 auto pri_link_u = utils::make_unique< TreeLink >();
209 auto sec_link_u = utils::make_unique< TreeLink >();
210 auto mid_node_u = utils::make_unique< TreeNode >();
211 auto sec_edge_u = utils::make_unique< TreeEdge >();
214 auto const pri_link = pri_link_u.get();
215 auto const sec_link = sec_link_u.get();
216 auto const mid_node = mid_node_u.get();
217 auto const sec_edge = sec_edge_u.get();
220 pri_link->reset_index( links.size() );
221 pri_link->reset_next( sec_link );
223 pri_link->reset_node( mid_node );
224 pri_link->reset_edge( &target_edge );
225 links.push_back( std::move( pri_link_u ));
228 sec_link->reset_index( links.size() );
229 sec_link->reset_next( pri_link );
231 sec_link->reset_node( mid_node );
232 sec_link->reset_edge( sec_edge );
233 links.push_back( std::move( sec_link_u ));
236 mid_node->reset_index( nodes.size() );
237 mid_node->reset_primary_link( pri_link );
239 nodes.push_back( std::move( mid_node_u ));
242 sec_edge->reset_index( edges.size() );
243 sec_edge->reset_primary_link( sec_link );
246 edges.push_back( std::move( sec_edge_u ));
256 adjust_edges( target_edge, *sec_edge );
265 std::function<
void(
TreeEdge& target_edge,
TreeEdge& new_edge )> adjust_edges
268 auto& mid_node =
add_new_node( tree, target_edge, adjust_edges );
280 throw std::runtime_error(
281 "Cannot delete Node from a Tree that is not part of the Tree." 285 auto const deg =
degree( target_node );
288 }
else if( deg == 2 ) {
299 throw std::runtime_error(
300 "Cannot delete node from a tree that is not part of the tree." 303 if(
degree( target_node ) != 1 ) {
304 throw std::runtime_error(
305 "Cannot delete leaf node if the node is not actually a leaf." 310 throw std::runtime_error(
311 "Cannot delete leaf node from a minmal tree that only contains two nodes." 316 assert( &target_node.
link().
next() == &target_node.
link() );
336 assert( &root_link->node() == &target_node.
link().
outer().
node() );
343 edges.erase( edges.begin() + edge_idx );
344 for(
size_t i = edge_idx; i < tree.
edge_count(); ++i ) {
350 auto& attach_link = target_node.
link().
outer();
351 assert( &attach_link.edge() == &target_node.
link().
edge() );
352 assert( &attach_link.outer() == &target_node.
link() );
353 auto link_ptr = &( attach_link.next() );
354 while( &link_ptr->next() != &attach_link ) {
355 link_ptr = &link_ptr->
next();
357 assert( &link_ptr->next() == &attach_link );
358 assert( &link_ptr->next().next() == &attach_link.next() );
359 link_ptr->
reset_next( &link_ptr->next().next() );
363 auto const minmax_link_idx =
utils::minmax_value( attach_link.index(), attach_link.outer().index() );
364 links.erase( links.begin() + minmax_link_idx.first );
365 links.erase( links.begin() + minmax_link_idx.second - 1 );
366 for(
size_t i = minmax_link_idx.first; i < links.size(); ++i ) {
372 auto const node_idx = target_node.
index();
373 nodes.erase( nodes.begin() + node_idx );
374 for(
size_t i = node_idx; i < tree.
node_count(); ++i ) {
387 std::function<
void(
TreeEdge& remaining_edge,
TreeEdge& deleted_edge )> adjust_edges
391 throw std::runtime_error(
392 "Cannot delete Node from a Tree that is not part of the Tree." 395 if(
degree( target_node ) != 2 ) {
396 throw std::runtime_error(
397 "Cannot delete linear Node if the Node is not actually linear (degree 2)." 419 auto& pr_link = target_node.
link();
420 auto& adj_link_p = pr_link.
outer();
421 auto& adj_link_d = pr_link.
next().
outer();
422 assert( &adj_link_p.outer().node() == &adj_link_d.outer().node() );
430 assert( &adj_link_p.edge().secondary_node() == &target_node || root_link != &tree.
root_link() );
431 assert( &adj_link_p.edge() == &target_node.
link().
edge() );
432 assert( &adj_link_d.edge() == &target_node.
link().
next().
edge() );
433 assert( &adj_link_d.edge().primary_node() == &target_node );
439 auto const edge_idx = pr_link.next().edge().
index();
440 edges.erase( edges.begin() + edge_idx );
441 for(
size_t i = edge_idx; i < tree.
edge_count(); ++i ) {
448 auto const minmax_link_idx =
utils::minmax_value( pr_link.index(), pr_link.next().index() );
449 links.erase( links.begin() + minmax_link_idx.first );
450 links.erase( links.begin() + minmax_link_idx.second - 1 );
451 for(
size_t i = minmax_link_idx.first; i < links.size(); ++i ) {
457 auto const node_idx = target_node.
index();
458 nodes.erase( nodes.begin() + node_idx );
459 for(
size_t i = node_idx; i < tree.
node_count(); ++i ) {
478 std::sort( del_elems.begin(), del_elems.end() );
479 assert( std::adjacent_find( del_elems.begin(), del_elems.end()) == del_elems.end() );
482 assert( del_elems.size() < old_elems.size() );
487 auto new_elems = T{};
488 new_elems.reserve( old_elems.size() - del_elems.size() );
491 size_t del_elems_idx = 0;
492 for(
size_t i = 0; i < old_elems.size(); ++i ) {
493 assert( i == old_elems[i]->index() );
494 if( del_elems_idx < del_elems.size() && del_elems[del_elems_idx] == i ) {
502 assert( old_elems[i]->index() == i );
503 assert( new_elems.size() == i - del_elems_idx );
504 old_elems[i]->reset_index( i - del_elems_idx );
505 new_elems.emplace_back( std::move( old_elems[i] ));
506 assert( new_elems.back()->index() == new_elems.size() - 1 );
512 assert( new_elems.size() + del_elems.size() == old_elems.size() );
521 throw std::runtime_error(
522 "Cannot delete Subtree from a Tree that is not part of the Tree." 526 throw std::runtime_error(
527 "Cannot delete Subtree from Tree if this leads to a singluar Node." 535 std::vector<size_t> del_nodes;
536 std::vector<size_t> del_edges;
537 std::vector<size_t> del_links;
538 bool contains_root =
false;
539 for(
auto it :
preorder( subtree )) {
540 del_nodes.push_back( it.node().index() );
541 del_edges.push_back( it.edge().index() );
542 del_links.push_back( it.link().index() );
543 del_links.push_back( it.link().outer().index() );
546 contains_root =
true;
565 auto& attach_link = subtree.
link().
outer();
566 assert( &attach_link.edge() == &subtree.
link().
edge() );
567 assert( &attach_link.outer() == &subtree.
link() );
568 auto link_ptr = &( attach_link.next() );
569 while( &link_ptr->next() != &attach_link ) {
570 link_ptr = &link_ptr->
next();
572 assert( &link_ptr->next() == &attach_link );
573 assert( &link_ptr->next().next() == &attach_link.next() );
574 auto& link_nc = tree.
link_at( link_ptr->index() );
577 if( &link_nc.node().primary_link() == &link_nc.next() ) {
578 assert( &attach_link.node().primary_link() == &attach_link );
584 link_nc.reset_next( &link_nc.next().next() );
611 std::function<
void(
TreeEdge& target_edge,
TreeEdge& new_edge )> adjust_edges
614 throw std::runtime_error(
"Cannot make a Tree rooted if it is already rooted." );
617 auto& mid_node =
add_new_node( tree, target_edge, adjust_edges );
624 std::function<
void(
TreeEdge& target_edge,
TreeEdge& new_edge )> adjust_edges
631 std::function<
void(
TreeEdge& remaining_edge,
TreeEdge& deleted_edge )> adjust_edges
634 throw std::runtime_error(
"Cannot make a Tree unrooted if it is already unrooted." );
643 throw std::runtime_error(
"Cannot reroot Tree on a Link that is not part of the Tree." );
660 while( &cur_link->
node() != old_root ) {
685 cur_link = to_root_link;
692 throw std::runtime_error(
"Cannot reroot Tree on a Node that is not part of the Tree." );
708 for(
auto& node : tree.
nodes() ) {
716 std::vector<size_t> child_sizes;
717 std::vector<TreeLink*> child_links;
722 if( link_it.is_first_iteration() ) {
723 assert( &link_it.link() == &node.primary_link() );
727 child_sizes.push_back( sub_sizes[ link_it.link().outer().node().index() ] );
728 child_links.push_back( &link_it.link() );
738 assert( child_order.size() == child_sizes.size() );
739 assert( child_order.size() == child_links.size() );
740 assert( child_order.size() ==
degree( node ) - 1 );
743 auto cur_link = &node.primary_link();
744 for(
auto child_order_i : child_order ) {
748 assert( child_links[ child_order_i ] );
751 cur_link->reset_next( child_links[ child_order_i ] );
752 cur_link = child_links[ child_order_i ];
756 child_links[ child_order_i ] =
nullptr;
761 cur_link->reset_next( &node.primary_link() );
764 for(
auto const& cl : child_links ) {
TreeEdge & edge()
Return the TreeEdge of this TreeLink.
void delete_node(Tree &tree, TreeNode &target_node)
Delete a TreeNode from a Tree.
utils::Range< IteratorNodeLinks< true > > node_links(ElementType const &element)
TreeLink & secondary_link()
Return the TreeLink of this TreeEdge that points away from the root.
bool is_rooted(Tree const &tree)
Return whether the Tree is rooted, that is, whether the root node has two neighbors.
Provides some valuable algorithms that are not part of the C++ 11 STL.
TreeLink & reset_edge(TreeEdge *val)
Reset the internal pointer to the TreeEdge of this TreeLink.
TreeNode & reset_primary_link(TreeLink *val)
Reset the internal pointer to the TreeLink of this TreeNode.
TreeLink & reset_next(TreeLink *val)
Reset the internal pointer to the next TreeLink of this TreeLink.
void ladderize(Tree &tree, LadderizeOrder order)
Ladderize a Tree, that is, order its subtrees by size.
virtual std::unique_ptr< BaseEdgeData > recreate() const
Polymorphically create a default-constructed instance of this class with the same derived type as it ...
bool is_root(TreeLink const &link)
Return whether the link belongs to the root node of its Tree.
void make_unrooted(Tree &tree, std::function< void(TreeEdge &remaining_edge, TreeEdge &deleted_edge)> adjust_edges)
Unroot a Tree.
TreeNode & node()
Return the TreeNode of this TreeLink.
void swap(SequenceSet &lhs, SequenceSet &rhs)
void delete_subtree(Tree &tree, Subtree const &subtree)
Delete a complete Subtree from a Tree.
TreeLink & primary_link()
Return the TreeLink that points towards the root.
size_t index() const
Return the index of this Link.
Tree minimal_tree_topology()
Create a minimal Tree that can be used with manipulation functions such as add_new_node() or add_new_...
size_t edge_count() const
Return the number of TreeEdges of the Tree.
size_t index() const
Return the index of this Edge.
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
Reference to a subtree of a Tree.
TreeLink & reset_index(size_t val)
Reset the internal index of this TreeLink.
Provides some valuable additions to STD.
TreeLink & next()
Return the next TreeLink within the TreeNode of this link.
TreeNode & make_rooted(Tree &tree, TreeEdge &target_edge, std::function< void(TreeEdge &target_edge, TreeEdge &new_edge)> adjust_edges)
Root a Tree at a given TreeEdge.
TreeNode & primary_node()
Return the TreeNode of this TreeEdge that points towards the root.
TreeLink & reset_outer(TreeLink *val)
Reset the internal pointer to the outer TreeLink of this TreeLink.
static void delete_from_tree_container_(T &old_elems, std::vector< size_t > &del_elems)
Local helper function template that takes one of the tree element containers and deletes all elements...
BaseEdgeData * data_ptr()
Return a pointer to the data.
utils::Range< IteratorNodes > nodes()
Class for representing phylogenetic trees.
size_t link_count() const
Return the number of TreeLinks of the Tree.
TreeEdge & reset_index(size_t val)
Reset the internal index of this TreeEdge.
TreeLink & link()
Return the TreeLink that points towards the root.
Tree & reset_root_link(TreeLink *root_link)
Reset the link that is considered to be the root of the Tree.
virtual std::unique_ptr< BaseNodeData > recreate() const
Polymorphically create a default-constructed instance of this class with the same derived type as it ...
TreeNode & node_at(size_t index)
Return the TreeNode at a certain index.
TreeLink & root_link()
Return the TreeLink at the current root of the Tree.
LinkContainerType & expose_link_container()
Get the container that stores all TreeLinks of the Tree.
TreeEdge & reset_primary_link(TreeLink *val)
Reset the internal pointer to the primary TreeLink of this TreeEdge.
TreeNode & add_new_leaf_node(Tree &tree, TreeEdge &target_edge, std::function< void(TreeEdge &target_edge, TreeEdge &new_edge)> adjust_edges)
Add a new Node as a leaf to an existing Edge, by also adding a new Node in the middle of that Edge...
TreeEdge & edge_at(size_t index)
Return the TreeEdge at a certain index.
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...
TreeLink const & link() const
Get the TreeLink that separates the subtree from the rest of the tree.
TreeNode & add_new_node(Tree &tree, TreeNode &target_node)
Add a new Node as a leaf to an existing Node.
std::vector< size_t > stable_sort_indices(RandomAccessIterator first, RandomAccessIterator last, Comparator comparator)
Get the indices to the stable sorted order of the given range.
size_t node_count() const
Return the number of TreeNodes of the Tree.
utils::Range< IteratorPreorder< true > > preorder(ElementType const &element)
TreeLink & link_at(size_t index)
Return the TreeLink at a certain index.
TreeNode & root_node()
Return the TreeNode at the current root of the Tree.
void delete_leaf_node(Tree &tree, TreeNode &target_node)
Delete a leaf TreeNode.
TreeLink & reset_node(TreeNode *val)
Reset the internal pointer to the TreeNode of this TreeLink.
std::pair< T, T > minmax_value(T const &a, T const &b)
Returns the lowest and the greatest of the given values, by value.
TreeLink & outer()
Return the TreeLink of the adjacent TreeNode.
size_t index() const
Return the index of this Node.
TreeLink & primary_link()
Return the TreeLink of this TreeEdge that points towards the root.
size_t degree(TreeLink const &link)
Return the degree of the node for a given TreeLink, i.e. how many neighbouring nodes it has...
void change_rooting(Tree &tree, TreeLink &at_link)
"Reroot" the Tree at the given TreeLink.
void delete_linear_node(Tree &tree, TreeNode &target_node, std::function< void(TreeEdge &remaining_edge, TreeEdge &deleted_edge)> adjust_edges)
Delete a "linear" TreeNode from a Tree, that is, a node with two neighbours.
TreeNode & reset_index(size_t val)
Reset the internal index of this TreeNode.
EdgeContainerType & expose_edge_container()
Get the container that stores all TreeEdges of the Tree.
BaseNodeData * data_ptr()
Return a pointer to the data.
bool is_leaf(TreeLink const &link)
Return true iff the node of the given link is a leaf node.
TreeEdge & reset_secondary_link(TreeLink *val)
Reset the internal pointer to the secondary TreeLink of this TreeEdge.
NodeContainerType & expose_node_container()
Get the container that stores all TreeNodes of the Tree.
std::vector< size_t > subtree_sizes(Tree const &tree, TreeNode const &node)
Calculate the sizes of all subtrees as seen from the given TreeNode.