ELynx.Tree.Bipartition

Creation date: Fri Aug 30 15:28:17 2019.

Documentation

groups :: Tree e a -> Tree e [a]

Each node of a tree is root of an induced subtree. Set the node labels to the leaves of the induced subtrees.

Data type

data Bipartition a

A bipartition of a tree is a grouping of the leaves of the tree into two non-overlapping, non-empty sub sets.

For unrooted trees:

• Each branch partitions the leaves of the tree into two subsets, or a bipartition.

For rooted trees:

• A bifurcating root node induces a bipartition; see bipartition.
• Each inner node induces a bipartition by taking the leaves of the sub tree and the complement leaf set of the full tree.

The order of the two subsets of a Bipartition is meaningless. That is, Bipartitions are weird in that

Bipartition x y == Bipartition y x

is True. Also,

Bipartition x y > Bipartition y x

is False, even when x > y. That's why we have to make sure that for

Bipartition x y

we always have x >= y. We ensure by construction that the larger subset comes first, and so that equality checks are meaningful; see bp and bpUnsafe.

Instances

Eq a => Eq (Bipartition a)

Defined in ELynx.Tree.Bipartition

Methods

(==) :: Bipartition a -> Bipartition a -> Bool

(/=) :: Bipartition a -> Bipartition a -> Bool

Ord a => Ord (Bipartition a)

Defined in ELynx.Tree.Bipartition

Methods

compare :: Bipartition a -> Bipartition a -> Ordering

(<) :: Bipartition a -> Bipartition a -> Bool

(<=) :: Bipartition a -> Bipartition a -> Bool

(>) :: Bipartition a -> Bipartition a -> Bool

(>=) :: Bipartition a -> Bipartition a -> Bool

max :: Bipartition a -> Bipartition a -> Bipartition a

min :: Bipartition a -> Bipartition a -> Bipartition a

(Read a, Ord a) => Read (Bipartition a)

Defined in ELynx.Tree.Bipartition

Methods

readsPrec :: Int -> ReadS (Bipartition a)

readList :: ReadS [Bipartition a]

readPrec :: ReadPrec (Bipartition a)

readListPrec :: ReadPrec [Bipartition a]

Show a => Show (Bipartition a)

Defined in ELynx.Tree.Bipartition

Methods

showsPrec :: Int -> Bipartition a -> ShowS

show :: Bipartition a -> String

showList :: [Bipartition a] -> ShowS

NFData a => NFData (Bipartition a)

Defined in ELynx.Tree.Bipartition

Methods

rnf :: Bipartition a -> ()

bp :: Ord a => Set a -> Set a -> Either String (Bipartition a)

Create a bipartition from two sets.

Ensure that the larger set comes first.

Return Left if one set is empty.

bpUnsafe :: Ord a => Set a -> Set a -> Bipartition a

Create a bipartition from two sets.

Ensure that the larger set comes first.

toSet :: Ord a => Bipartition a -> Set a

Conversion to a set containing both partitions.

bpHuman :: Show a => Bipartition a -> String

Show a bipartition in a human readable format. Use a provided function to extract information of interest.

Work with Bipartitions

bipartition :: Ord a => Tree e a -> Either String (Bipartition a)

For a bifurcating root, get the bipartition induced by the root node.

Return Left if - the root node is not bifurcating; - a leave set is empty.

bipartitions :: Ord a => Tree e a -> Either String (Set (Bipartition a))

Get all bipartitions of the tree.

Return Left if the tree contains duplicate leaves.

getComplementaryLeaves :: Ord a => Set a -> Tree e (Set a) -> [Set a]

Report the complementary leaves for each child.

bipartitionToBranch :: (Semigroup e, Ord a) => Tree e a -> Either String (Map (Bipartition a) e)

Convert a tree into a Map from each Bipartition to the branch inducing the respective Bipartition.

Since the induced bipartitions of the daughter branches of a bifurcating root node are equal, the branches leading to the root have to be combined in this case. See http://evolution.genetics.washington.edu/phylip/doc/treedist.html and how unrooted trees are handled.

Further, branches connected to degree two nodes also induce the same bipartitions and have to be combined.

For combining branches, a binary function is required. This requirement is encoded in the Semigroup type class constraint (see prune).

Return Left if the tree contains duplicate leaves.