def test_index_tree(self):
        """index_tree should produce correct index and node map"""
        # test for first tree: contains singleton outgroup
        t1 = TreeNode.from_newick('(((a,b),c),(d,e))')
        t2 = TreeNode.from_newick('(((a,b),(c,d)),(e,f))')
        t3 = TreeNode.from_newick('(((a,b,c),(d)),(e,f))')

        id_1, child_1 = t1.index_tree()
        nodes_1 = [n.id for n in t1.traverse(self_before=False,
                   self_after=True)]
        self.assertEqual(nodes_1, [0, 1, 2, 3, 6, 4, 5, 7, 8])
        self.assertEqual(child_1, [(2, 0, 1), (6, 2, 3), (7, 4, 5), (8, 6, 7)])

        # test for second tree: strictly bifurcating
        id_2, child_2 = t2.index_tree()
        nodes_2 = [n.id for n in t2.traverse(self_before=False,
                   self_after=True)]
        self.assertEqual(nodes_2, [0, 1, 4, 2, 3, 5, 8, 6, 7, 9, 10])
        self.assertEqual(child_2, [(4, 0, 1), (5, 2, 3), (8, 4, 5), (9, 6, 7),
                                   (10, 8, 9)])

        # test for third tree: contains trifurcation and single-child parent
        id_3, child_3 = t3.index_tree()
        nodes_3 = [n.id for n in t3.traverse(self_before=False,
                   self_after=True)]
        self.assertEqual(nodes_3, [0, 1, 2, 4, 3, 5, 8, 6, 7, 9, 10])
        self.assertEqual(child_3, [(4, 0, 2), (5, 3, 3), (8, 4, 5), (9, 6, 7),
                                   (10, 8, 9)])

    def test_compare_subsets(self):
        """compare_subsets should return the fraction of shared subsets"""
        t = TreeNode.from_newick('((H,G),(R,M));')
        t2 = TreeNode.from_newick('(((H,G),R),M);')
        t4 = TreeNode.from_newick('(((H,G),(O,R)),X);')

        result = t.compare_subsets(t)
        self.assertEqual(result, 0)

        result = t2.compare_subsets(t2)
        self.assertEqual(result, 0)

        result = t.compare_subsets(t2)
        self.assertEqual(result, 0.5)

        result = t.compare_subsets(t4)
        self.assertEqual(result, 1 - 2. / 5)

        result = t.compare_subsets(t4, exclude_absent_taxa=True)
        self.assertEqual(result, 1 - 2. / 3)

        result = t.compare_subsets(self.TreeRoot, exclude_absent_taxa=True)
        self.assertEqual(result, 1)

        result = t.compare_subsets(self.TreeRoot)
        self.assertEqual(result, 1)

    def test_DndParser(self):
        """DndParser tests"""
        t_str = "(A_a,(B:1.0,C),'D_e':0.5)E;"
        tree_unesc = TreeNode.from_newick(t_str, unescape_name=True)
        tree_esc = TreeNode.from_newick(t_str, unescape_name=False)

        self.assertEqual(tree_unesc.name, 'E')
        self.assertEqual(tree_unesc.children[0].name, 'A a')
        self.assertEqual(tree_unesc.children[1].children[0].name, 'B')
        self.assertEqual(tree_unesc.children[1].children[0].length, 1.0)
        self.assertEqual(tree_unesc.children[1].children[1].name, 'C')
        self.assertEqual(tree_unesc.children[2].name, 'D_e')
        self.assertEqual(tree_unesc.children[2].length, 0.5)

        self.assertEqual(tree_esc.name, 'E')
        self.assertEqual(tree_esc.children[0].name, 'A_a')
        self.assertEqual(tree_esc.children[1].children[0].name, 'B')
        self.assertEqual(tree_esc.children[1].children[0].length, 1.0)
        self.assertEqual(tree_esc.children[1].children[1].name, 'C')
        self.assertEqual(tree_esc.children[2].name, "'D_e'")
        self.assertEqual(tree_esc.children[2].length, 0.5)

        reload_test = tree_esc.to_newick(with_distances=True,
                                         escape_name=False)
        obs = TreeNode.from_newick(reload_test, unescape_name=False)
        self.assertEqual(obs.to_newick(with_distances=True),
                         tree_esc.to_newick(with_distances=True))
        reload_test = tree_unesc.to_newick(with_distances=True,
                                           escape_name=False)
        obs = TreeNode.from_newick(reload_test, unescape_name=False)
        self.assertEqual(obs.to_newick(with_distances=True),
                         tree_unesc.to_newick(with_distances=True))

    def test_majority_rule(self):
        trees = [
            TreeNode.from_newick("(A,(B,(H,(D,(J,(((G,E),(F,I)),C))))));"),
            TreeNode.from_newick("(A,(B,(D,((J,H),(((G,E),(F,I)),C)))));"),
            TreeNode.from_newick("(A,(B,(D,(H,(J,(((G,E),(F,I)),C))))));"),
            TreeNode.from_newick("(A,(B,(E,(G,((F,I),((J,(H,D)),C))))));"),
            TreeNode.from_newick("(A,(B,(E,(G,((F,I),(((J,H),D),C))))));"),
            TreeNode.from_newick("(A,(B,(E,((F,I),(G,((J,(H,D)),C))))));"),
            TreeNode.from_newick("(A,(B,(E,((F,I),(G,(((J,H),D),C))))));"),
            TreeNode.from_newick("(A,(B,(E,((G,(F,I)),((J,(H,D)),C)))));"),
            TreeNode.from_newick("(A,(B,(E,((G,(F,I)),(((J,H),D),C)))));")]

        exp = TreeNode.from_newick("(((E,(G,(F,I),(C,(D,J,H)))),B),A);")
        obs = majority_rule(trees)
        self.assertEqual(exp.compare_subsets(obs[0]), 0.0)
        self.assertEqual(len(obs), 1)

        tree = obs[0]
        exp_supports = sorted([9.0, 9.0, 9.0, 6.0, 6.0, 6.0])
        obs_supports = sorted([n.support for n in tree.non_tips()])
        self.assertEqual(obs_supports, exp_supports)

        obs = majority_rule(trees, weights=np.ones(len(trees)) * 2)
        self.assertEqual(exp.compare_subsets(obs[0]), 0.0)
        self.assertEqual(len(obs), 1)

        tree = obs[0]
        exp_supports = sorted([18.0, 18.0, 12.0, 18.0, 12.0, 12.0])
        obs_supports = sorted([n.support for n in tree.non_tips()])

        with self.assertRaises(ValueError):
            majority_rule(trees, weights=[1, 2])

 def test_compare_tip_distances(self):
     t = TreeNode.from_newick('((H:1,G:1):2,(R:0.5,M:0.7):3);')
     t2 = TreeNode.from_newick('(((H:1,G:1,O:1):2,R:3):1,X:4);')
     obs = t.compare_tip_distances(t2)
     # note: common taxa are H, G, R (only)
     m1 = np.array([[0, 2, 6.5], [2, 0, 6.5], [6.5, 6.5, 0]])
     m2 = np.array([[0, 2, 6], [2, 0, 6], [6, 6, 0]])
     r = pearsonr(m1.flat, m2.flat)[0]
     self.assertAlmostEqual(obs, (1 - r) / 2)

    def test_walk_clades(self):
        trees = [TreeNode.from_newick("((A,B),(D,E));"),
                 TreeNode.from_newick("((A,B),(D,(E,X)));")]
        exp_clades = [
            (frozenset(['A']), 2.0),
            (frozenset(['B']), 2.0),
            (frozenset(['A', 'B']), 2.0),
            (frozenset(['D', 'E']), 1.0),
            (frozenset(['D', 'E', 'A', 'B']), 1.0),
            (frozenset(['D']), 2.0),
            (frozenset(['E']), 2.0),
            (frozenset(['X']), 1.0),
            (frozenset(['E', 'X']), 1.0),
            (frozenset(['D', 'E', 'X']), 1.0),
            (frozenset(['A', 'B', 'D', 'E', 'X']), 1.0)]

        exp_lengths_nolength = {
            frozenset(['A']): None,
            frozenset(['B']): None,
            frozenset(['A', 'B']): None,
            frozenset(['D', 'E']): None,
            frozenset(['D', 'E', 'A', 'B']): None,
            frozenset(['D']): None,
            frozenset(['E']): None,
            frozenset(['X']): None,
            frozenset(['E', 'X']): None,
            frozenset(['D', 'E', 'X']): None,
            frozenset(['A', 'B', 'D', 'E', 'X']): None}

        exp_lengths = {
            frozenset(['A']): 2.0,
            frozenset(['B']): 2.0,
            frozenset(['A', 'B']): 2.0,
            frozenset(['D', 'E']): 1.0,
            frozenset(['D', 'E', 'A', 'B']): 1.0,
            frozenset(['D']): 2.0,
            frozenset(['E']): 2.0,
            frozenset(['X']): 1.0,
            frozenset(['E', 'X']): 1.0,
            frozenset(['D', 'E', 'X']): 1.0,
            frozenset(['A', 'B', 'D', 'E', 'X']): 1.0}

        obs_clades, obs_lengths = _walk_clades(trees, np.ones(len(trees)))
        self.assertEqual(set(obs_clades), set(exp_clades))
        self.assertEqual(obs_lengths, exp_lengths_nolength)

        for t in trees:
            for n in t.traverse(include_self=True):
                n.length = 2.0

        obs_clades, obs_lengths = _walk_clades(trees, np.ones(len(trees)))

        self.assertEqual(set(obs_clades), set(exp_clades))
        self.assertEqual(obs_lengths, exp_lengths)

 def test_missing_tip_name(self):
     """DndParser should produce the correct tree when missing a name"""
     obs = TreeNode.from_newick(missing_tip_name)
     exp = TreeNode()
     exp.append(TreeNode())
     exp.append(TreeNode())
     exp.children[0].append(TreeNode(name='a'))
     exp.children[0].append(TreeNode(name='b'))
     exp.children[1].append(TreeNode(name='c'))
     exp.children[1].append(TreeNode())
     self.assertEqual(str(obs), str(exp))

    def test_pre_and_postorder_no_children(self):
        t = TreeNode('brofist')

        # include self
        exp = ['brofist']
        obs = [n.name for n in t.pre_and_postorder()]
        self.assertEqual(obs, exp)

        # do not include self
        obs = list(t.pre_and_postorder(include_self=False))
        self.assertEqual(obs, [])

 def test_data(self):
     """DndParser should work as expected on real data"""
     t = TreeNode.from_newick(sample)
     self.assertEqual(
         str(t), '((xyz:0.28124,(def:0.24498,mno:0.03627):0.1771):0.0487,'
                 'abc:0.05925,(ghi:0.06914,jkl:0.13776):0.09853);')
     tdata = TreeNode.from_newick(node_data_sample, unescape_name=True)
     self.assertEqual(
         str(tdata), "((xyz:0.28124,(def:0.24498,mno:0.03627)A:0.1771)"
                     "B:0.0487,abc:0.05925,(ghi:0.06914,jkl:0.13776)"
                     "C:0.09853);")

 def test_nonames(self):
     """DndParser should produce the correct tree when there are no names"""
     obs = TreeNode.from_newick(no_names)
     exp = TreeNode()
     exp.append(TreeNode())
     exp.append(TreeNode())
     exp.children[0].append(TreeNode())
     exp.children[0].append(TreeNode())
     exp.children[1].append(TreeNode())
     exp.children[1].append(TreeNode())
     self.assertEqual(str(obs), str(exp))

    def setUp(self):
        data1 = [[0, 5, 9, 9, 8], [5, 0, 10, 10, 9], [9, 10, 0, 8, 7], [9, 10, 8, 0, 3], [8, 9, 7, 3, 0]]
        ids1 = list("abcde")
        self.dm1 = DistanceMatrix(data1, ids1)
        # this newick string was confirmed against http://www.trex.uqam.ca/
        # which generated the following (isomorphic) newick string:
        # (d:2.0000,e:1.0000,(c:4.0000,(a:2.0000,b:3.0000):3.0000):2.0000);
        self.expected1_str = "(d:2.000000, (c:4.000000, (b:3.000000," " a:2.000000):3.000000):2.000000, e:1.000000);"
        self.expected1_TreeNode = TreeNode.from_newick(self.expected1_str)

        # this example was pulled from the Phylip manual
        # http://evolution.genetics.washington.edu/phylip/doc/neighbor.html
        data2 = [
            [0.0000, 1.6866, 1.7198, 1.6606, 1.5243, 1.6043, 1.5905],
            [1.6866, 0.0000, 1.5232, 1.4841, 1.4465, 1.4389, 1.4629],
            [1.7198, 1.5232, 0.0000, 0.7115, 0.5958, 0.6179, 0.5583],
            [1.6606, 1.4841, 0.7115, 0.0000, 0.4631, 0.5061, 0.4710],
            [1.5243, 1.4465, 0.5958, 0.4631, 0.0000, 0.3484, 0.3083],
            [1.6043, 1.4389, 0.6179, 0.5061, 0.3484, 0.0000, 0.2692],
            [1.5905, 1.4629, 0.5583, 0.4710, 0.3083, 0.2692, 0.0000],
        ]
        ids2 = ["Bovine", "Mouse", "Gibbon", "Orang", "Gorilla", "Chimp", "Human"]
        self.dm2 = DistanceMatrix(data2, ids2)
        self.expected2_str = (
            "(Mouse:0.76891, (Gibbon:0.35793, (Orang:0.28469"
            ", (Gorilla:0.15393, (Chimp:0.15167, Human:0.117"
            "53):0.03982):0.02696):0.04648):0.42027, Bovine:"
            "0.91769);"
        )
        self.expected2_TreeNode = TreeNode.from_newick(self.expected2_str)

        data3 = [
            [0, 5, 4, 7, 6, 8],
            [5, 0, 7, 10, 9, 11],
            [4, 7, 0, 7, 6, 8],
            [7, 10, 7, 0, 5, 8],
            [6, 9, 6, 5, 0, 8],
            [8, 11, 8, 8, 8, 0],
        ]
        ids3 = map(str, range(6))
        self.dm3 = DistanceMatrix(data3, ids3)
        self.expected3_str = (
            "((((0:1.000000,1:4.000000):1.000000,2:2.000000"
            "):1.250000,5:4.750000):0.750000,3:2.750000,4:2."
            "250000);"
        )
        self.expected3_TreeNode = TreeNode.from_newick(self.expected3_str)

        # this dm can yield negative branch lengths
        data4 = [[0, 5, 9, 9, 800], [5, 0, 10, 10, 9], [9, 10, 0, 8, 7], [9, 10, 8, 0, 3], [800, 9, 7, 3, 0]]
        ids4 = list("abcde")
        self.dm4 = DistanceMatrix(data4, ids4)

    def test_find_by_id(self):
        """Find a node by id"""
        t1 = TreeNode.from_newick("((,),(,,));")
        t2 = TreeNode.from_newick("((,),(,,));")

        exp = t1.children[1]
        obs = t1.find_by_id(6)  # right inner node with 3 children
        self.assertEqual(obs, exp)

        exp = t2.children[1]
        obs = t2.find_by_id(6)  # right inner node with 3 children
        self.assertEqual(obs, exp)

        with self.assertRaises(MissingNodeError):
            t1.find_by_id(100)

    def test_lowest_common_ancestor(self):
        """TreeNode lowestCommonAncestor should return LCA for set of tips"""
        t1 = TreeNode.from_newick("((a,(b,c)d)e,f,(g,h)i)j;")
        t2 = t1.copy()
        t3 = t1.copy()
        t4 = t1.copy()
        input1 = ['a']  # return self
        input2 = ['a', 'b']  # return e
        input3 = ['b', 'c']  # return d
        input4 = ['a', 'h', 'g']  # return j
        exp1 = t1.find('a')
        exp2 = t2.find('e')
        exp3 = t3.find('d')
        exp4 = t4
        obs1 = t1.lowest_common_ancestor(input1)
        obs2 = t2.lowest_common_ancestor(input2)
        obs3 = t3.lowest_common_ancestor(input3)
        obs4 = t4.lowest_common_ancestor(input4)
        self.assertEqual(obs1, exp1)
        self.assertEqual(obs2, exp2)
        self.assertEqual(obs3, exp3)
        self.assertEqual(obs4, exp4)

        # verify multiple calls work
        t_mul = t1.copy()
        exp_1 = t_mul.find('d')
        exp_2 = t_mul.find('i')
        obs_1 = t_mul.lowest_common_ancestor(['b', 'c'])
        obs_2 = t_mul.lowest_common_ancestor(['g', 'h'])
        self.assertEqual(obs_1, exp_1)
        self.assertEqual(obs_2, exp_2)

        # empty case
        with self.assertRaises(ValueError):
            t1.lowest_common_ancestor([])

 def test_invalidate_attr_caches(self):
     tree = TreeNode.from_newick("((a,b,(c,d)e)f,(g,h)i)root;")
     f = lambda n: [n.name] if n.is_tip() else []
     tree.cache_attr(f, 'tip_names')
     tree.invalidate_caches()
     for n in tree.traverse(include_self=True):
         self.assertFalse(hasattr(n, 'tip_names'))

    def test_adopt(self):
        """Adopt a node!"""
        n1 = TreeNode(name='n1')
        n2 = TreeNode(name='n2')
        n3 = TreeNode(name='n3')

        self.simple_t._adopt(n1)
        self.simple_t.children[-1]._adopt(n2)
        n2._adopt(n3)

        # adopt doesn't update .children
        self.assertEqual(len(self.simple_t.children), 2)

        self.assertIs(n1.parent, self.simple_t)
        self.assertIs(n2.parent, self.simple_t.children[-1])
        self.assertIs(n3.parent, n2)

 def test_get_max_distance(self):
     """get_max_distance should get max tip distance across tree"""
     tree = TreeNode.from_newick(
         "((a:0.1,b:0.2)c:0.3,(d:0.4,e:0.5)f:0.6)root;")
     dist, nodes = tree.get_max_distance()
     nptest.assert_almost_equal(dist, 1.6)
     self.assertEqual(sorted([n.name for n in nodes]), ['b', 'e'])

 def test_find_by_func(self):
     """Find nodes by a function"""
     t = TreeNode.from_newick("((a,b)c,(d,e)f);")
     func = lambda x: x.parent == t.find('c')
     exp = ['a', 'b']
     obs = [n.name for n in t.find_by_func(func)]
     self.assertEqual(obs, exp)

 def test_gonenest(self):
     """DndParser should work correctly with nested data"""
     t = TreeNode.from_newick(onenest)
     self.assertEqual(len(t), 2)
     self.assertEqual(len(t[0]), 0)  # first child is terminal
     self.assertEqual(len(t[1]), 2)  # second child has two children
     self.assertEqual(str(t), '(abc:3.0,(def:4.0,ghi:5.0):6.0);')

 def test_from_newick_empty(self):
     obs = TreeNode.from_newick('')
     self.assertTrue(obs.name is None)
     self.assertTrue(obs.length is None)
     self.assertTrue(obs.parent is None)
     self.assertEqual(obs.children, [])
     self.assertTrue(obs.id is None)

 def test_accumulate_to_ancestor(self):
     """Get the distance from a node to its ancestor"""
     t = TreeNode.from_newick("((a:0.1,b:0.2)c:0.3,(d:0.4,e)f:0.5)root;")
     a = t.find('a')
     exp_to_root = 0.1 + 0.3
     obs_to_root = a.accumulate_to_ancestor(t)
     self.assertEqual(obs_to_root, exp_to_root)