Return an imbalanced (comb-like) tree topology.
334413
def imbtree(ntips, treeheight=1.0):
        
        rtree = toytree.tree()
        rtree.treenode.add_child(name="0")
        rtree.treenode.add_child(name="1")

        for i in range(2, ntips):
            # empty node
            cherry = toytree.tree()
            # add new child
            cherry.treenode.add_child(name=str(i))
            # add old tree
            cherry.treenode.add_child(rtree.treenode)
            # update rtree
            rtree = cherry
        
        # get toytree from newick            
        tre = toytree.tree(rtree.write(tree_format=9))
        tre = tre.mod.make_ultrametric()
        self = tre.mod.node_scale_root_height(treeheight)
        self._coords.update()
        return self
807107
def from_dict(cls, tree_dict, previous=None):
        """"""
        instance = cls(tree_dict['tree_type'])

        fitted = tree_dict['fitted']
        instance.fitted = fitted
        if fitted:
            instance.level = tree_dict['level']
            instance.n_nodes = tree_dict['n_nodes']
            instance.tau_matrix = np.array(tree_dict['tau_matrix'])
            instance.previous_tree = cls._deserialize_previous_tree(tree_dict, previous)
            instance.edges = [Edge.from_dict(edge) for edge in tree_dict['edges']]

        return instance
738625
function(tree, n, m) {
    return tree[n].fc < tree[m].fc ||
      (tree[n].fc == tree[m].fc && zip_depth[n] <= zip_depth[m]);
}
404650
def tree_to_graph(bbltree:BubbleTree) -> Graph or Digraph:
    
    GraphObject = Digraph if bbltree.oriented else Graph
    def create(name:str):
        """Return a graphviz graph figurating a powernode"""
        ret = GraphObject('cluster_' + name)
        # dirty hack to get links between clusters: add a blank node inside
        # so the subgraph don't take it's name directly, but the blank node do.
        # ret.body.append('label = "{}"'.format(name))  # replaced by:
        ret.node(name, style='invis', shape='point')
        # ret.body.append('style=plaintext')
        ret.body.append('color=lightgrey')
        ret.body.append('label=""')
        ret.body.append('shape=ellipse')
        ret.body.append('penwidth=2')
        ret.body.append('pencolor=black')
        return ret
    nodes = frozenset(bbltree.nodes())
    subgraphs = {}
    # build for each powernode the associated subgraph, and add its successors
    for powernode in bbltree.powernodes():
        if powernode not in subgraphs:
            subgraphs[powernode] = create(powernode)
        for succ in bbltree.inclusions[powernode]:
            if succ not in subgraphs:
                if succ not in nodes:
                    subgraphs[succ] = create(succ)
                else:
                    subgraphs[powernode].node(succ)
    # add to Graph instances the Graph of successors as subgraphs 
    for powernode, succs in bbltree.inclusions.items():
        for succ in succs:
            if succ not in nodes:
                subgraphs[powernode].subgraph(subgraphs[succ])
    # build the final graph by adding to it subgraphs of roots
    graph = GraphObject('graph', graph_attr={'compound': 'true'})
    for root in bbltree.roots:
        if root in subgraphs:
            graph.subgraph(subgraphs[root])
    # add the edges to the final graph
    for source, targets in bbltree.edges.items():
        for target in targets:
            if source <= target:
                attrs = {}
                if source not in nodes:
                    attrs.update({'ltail': 'cluster_' + source})
                if target not in nodes:
                    attrs.update({'lhead': 'cluster_' + target})
                graph.edge(source, target, **attrs)
    # print(graph)  # debug line
    # graph.view()  # debug line
    return graph
1010877
def __calculate_adjacency_lists(graph):
    """"""
    adj = {}
    for node in graph.get_all_node_ids():
        neighbors = graph.neighbors(node)
        adj[node] = neighbors
    return adj
440556
def _precompute(self, tree):
        
        d = {}
        for n in tree.preorder_internal_node_iter():
            d[n] = namedtuple('NodeDist', ['dist_from_root', 'edges_from_root'])
            if n.parent_node:
                d[n].dist_from_root = d[n.parent_node].dist_from_root + n.edge_length
                d[n].edges_from_root = d[n.parent_node].edges_from_root + 1
            else:
                d[n].dist_from_root = 0.0
                d[n].edges_from_root = 0
        return d
729752
def map_tree(visitor, tree):
    """"""
    newn = [map_tree(visitor, node) for node in tree.nodes]
    return visitor(tree, newn)
701422
def _build_tree(self, side):
        
        if not self.nn_ready[side]:
            self.kdtree[side]   = scipy.spatial.cKDTree(self.data[side], compact_nodes=False, balanced_tree=False) # Those options are required with scipy >= 0.16
            self.nn_ready[side] = True
1012861
def inc_nbrs(self, node):
        
        l = map(self.head, self.inc_edges(node))
        #l.sort()
        return l
376475
def fixed(self):
    """"""
    for key, child in self._root.children.items():
      if key == '^':
        return list(child.subpatterns())
    return []
520970
private Node balance(Node node) {
        if (node == null) {
            return null;
        }

        int imbalance = getHeight(node.left) - getHeight(node.right);
        if (imbalance > MAX_IMBALANCE) {
            // Left subtree has higher height than right subtree.
            if (getHeight(node.left.left) < getHeight(node.left.right)) {
                // Double rotate binary tree node: first left child with its right child; then the node with new left child.
                node.left = rotateRight(node.left);
            }

            return rotateLeft(node);
        } else if (-imbalance > MAX_IMBALANCE) {
            // Right subtree has higher height than left subtree.
            if (getHeight(node.right.right) < getHeight(node.right.left)) {
                // Double rotate binary tree node: first right child with its left child; then the node with new right child.
                node.right = rotateLeft(node.right);
            }

            return rotateRight(node);
        } else {
            // No rotation needed, just update current node's height, as an update may have changed it.
            node.height = calculateHeight(getHeight(node.left), getHeight(node.right));
            return node;
        }
    }
1085243
def roots(cls, degree, domain, kind):
        """"""
        basis_coefs = cls._basis_monomial_coefs(degree)
        basis_poly = cls.functions_factory(basis_coefs, domain, kind)
        return basis_poly.roots()
318334
def split_bezier(bpoints, t):
    """"""
    def split_bezier_recursion(bpoints_left_, bpoints_right_, bpoints_, t_):
        if len(bpoints_) == 1:
            bpoints_left_.append(bpoints_[0])
            bpoints_right_.append(bpoints_[0])
        else:
            new_points = [None]*(len(bpoints_) - 1)
            bpoints_left_.append(bpoints_[0])
            bpoints_right_.append(bpoints_[-1])
            for i in range(len(bpoints_) - 1):
                new_points[i] = (1 - t_)*bpoints_[i] + t_*bpoints_[i + 1]
            bpoints_left_, bpoints_right_ = split_bezier_recursion(
                bpoints_left_, bpoints_right_, new_points, t_)
        return bpoints_left_, bpoints_right_

    bpoints_left = []
    bpoints_right = []
    bpoints_left, bpoints_right = \
        split_bezier_recursion(bpoints_left, bpoints_right, bpoints, t)
    bpoints_right.reverse()
    return bpoints_left, bpoints_right
603006
def _balanced_strand_gen(base_aligns, limit):
    ''''''
    predicate=lambda align: align.is_reverse
    gen1, gen2 = itertools.tee((predicate(align), align) for align in base_aligns)
    for_strand_gen = (align for pred, align in gen1 if not pred)
    rev_strand_gen = (align for pred, align in gen2 if pred)
    combined_gen = iter_zip(for_strand_gen, rev_strand_gen)
    interleaved_gen = (align for for_rev_aligns in combined_gen for align in for_rev_aligns)
    return itertools.islice(interleaved_gen, limit)
147725
def root_and_children_to_graph(self,root):
     """"""
     g = Graph()
     g.add_node(root)
     edges = []
     edges += self.get_node_edges(root,"outgoing")
     for c in self.get_children(root):
           g.add_node(c)
           edges += self.get_node_edges(c,"outgoing")
     for e in edges: g.add_edge(e)
     return g
1048639
def find_minimum_spanning_tree_as_subgraph(graph):
    """"""
    edge_list = find_minimum_spanning_tree(graph)
    subgraph = get_subgraph_from_edge_list(graph, edge_list)

    return subgraph
421434
def branchScale(self):
        """"""
        bscales = [m.branchScale for m in self._models]
        return (self.catweights * bscales).sum()