create rooted phylo tree struct and impl generic rooted tree traits

[sriram98v]

No description provided.

[sriram98v]

@swagle8987 Could you implement mrca for a set of nodes?

[swagle8987]

@sriram98v Any reason why the children hashmaps in the struct have HashSet(Option,NodeID) instead of the tuple directly? AFAIK rust hashsets are simply hashmaps with () as the key, wouldn't simply storing the tuple be better?

[swagle8987]

Nevermind, I thought children stored all the edges instead of just an adjancency list for each node.

[swagle8987]

@sriram98v Would it be better to replace the Option with just edgeweight, with unweighted graphs having a weight of 0? Having option means that the trait bounds for Hash and Eq are not implemented for the hashset.

[sriram98v]

The problem was Hash was not implemented for f64. I switched it to a vec of tuples. it should work fine now. I implemented create node, add child and add leaf as well.

[sriram98v]

Add_child needs to be implemented, which should panic if the node is identical to an existing node. Identical means children, parent and taxa are the same.

[sriram98v]

The clean method also appears to be incorrectly implemented and needs to be replace. It is essentially a method that mutates self and removes half nodes (nodes with only one child).

Another method to add is a balance_tree.

[swagle8987]

I had a question regarding simplertree.rs

Wouldn't it be simpler if we just defined the bare-bones version of what we think a tree should be?
i.e. we don't restrict or assume responsibility for node structs or edges just that each tree must have some idea of a node, some idea of an edge and related methods to those
For example:

pub trait SimpleTree{
    type Node = Hash + Debug + PartialEq
    type Edge = Debug + PartialEq
    type EdgeWeight
    fn add_node(&mut self) -> Node;
    fn add_edge(&mut self, node1:Node, node2:Node, distance:Option<EdgeWeight>) -> Edge
    fn remove_node(&mut self, node:Node) -> Node
    fn remove_edge(&mut self,edge:Edge) -> Edge
    fn set_edge_weight(&mut self, edge:Edge, distance:Option<EdgeWeight>);
}

Even better imo would be to make the simple tree trait bound explicit

pub trait SimpleTree<Node,Edge,EdgeWeight> where
Node : Hash+Debug+PartialEq
Edge : Debug+PartialEq
EdgeWeight : Debug+Add+Sub+PartialOrd{
    fn add_node(&mut self) -> Node;
    fn add_edge(&mut self, node1:Node, node2:Node, distance:Option<EdgeWeight>) -> Edge
    fn remove_node(&mut self, node:Node) -> Node
    fn remove_edge(&mut self,edge:Edge) -> Edge
    fn set_edge_weight(&mut self, edge:Edge, distance:Option<EdgeWeight>);
}

SimpleRTree would then inherit from SimpleTree and simply be concerned with defining the required methods for rooted tree traits. The aim would be to cut methods that are not always necessary for a tree like spr and nni. These can then be defined as methods of a struct and the scope of these is up to the implementation of those structs i.e. if someone wants just a barebones tree struct that simply iterates over the nodes in a tree-like manner, they do not need to implement graft or prune or any of the other methods.

[sriram98v]

Normally, that would make sense. I am currently refactoring the simpletree and node modules in another branch, where there will exist a default implementation for more advanced methods. That would resolve the issue of using a tree-struct with barebone methods.

I would also like to add that if the use case is simply basic tree iterations, why not use the struct that is also provided?

[swagle8987]

Our tree struct makes opinionated choices regarding what a node/edge is, I believe. So if someone wants tree iterations with their own node structs (say they represent nodes as clusters instead of actual nodes) but they still want to use our iterators they can still use it. Or someone else extends our modules by creating a method that only requires basic tree iteration (for example for calculating infix expressions or something) it would be unfair to ask them to implement all possible methods.

Edit:: I see that Rust only allows trait inheritance. In which scenario would it make more sense to have multiple traits instead? i.e. Tree is a trait that only defines the basic methods of a tree, Rooted only defines methods that make sense for rooted structures and EditableTree defines Tree edit methods. A similar idea would be to not put edit operations in tree traits at all and let them be free floating functions under a tree operations module (the function itself would be the same but we'd replace self with a parameter of Editable or something).

[sriram98v]

Our tree struct makes opinionated choices regarding what a node/edge is, I believe. So if someone wants tree iterations with their own node structs (say they represent nodes as clusters instead of actual nodes) but they still want to use our iterators they can still use it. Or someone else extends our modules by creating a method that only requires basic tree iteration (for example for calculating infix expressions or something) it would be unfair to ask them to implement all possible methods.

Edit:: I see that Rust only allows trait inheritance. In which scenario would it make more sense to have multiple traits instead? i.e. Tree is a trait that only defines the basic methods of a tree, Rooted only defines methods that make sense for rooted structures and EditableTree defines Tree edit methods. A similar idea would be to not put edit operations in tree traits at all and let them be free floating functions under a tree operations module (the function itself would be the same but we'd replace self with a parameter of Editable or something).

The tree struct makes an opinionated choice, yes, but the tree trait is not so. I would recommend this discussion be moved to #10 as the refactored node and tree traits already tackle most of the issue brought up in your comment.

As for making multiple traits, that sound like a good idea, however I would point out that tree edit operations are to be carried out on a mutable reference to a tree. Making a separate trait for editable tree does not make sense to me (Please elaborate on how you would like to split the tree trait as I suspect I am not getting the full picture of you are trying to convey).