elynx-tree-0.6.0.0: Handle phylogenetic trees
Copyright(c) Dominik Schrempf 2021
LicenseGPL-3.0-or-later
Maintainerdominik.schrempf@gmail.com
Stabilityunstable
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

ELynx.Tree.Partition

Description

Creation date: Thu Dec 12 12:58:49 2019.

Synopsis

Data type

data Partition a Source #

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

For unrooted trees:

  • For example, each branch of an unrooted tree partitions the leaves of the tree into two subsets (see Bipartition).

For rooted trees:

  • In a similar way, each bifurcating internal node (excluding the root node) partitions the leaves into three subsets called a Partition. If the tree is multifurcating, and a specific node has more than two children, the number of subsets induced by this node is larger than three. Partitions are interesting in that we can use them for calculating incompatible splits, see Distance.

The order of the subsets of a Partition is meaningless. We ensure by construction that the subsets are ordered, and hence, that equality checks are meaningful.

Instances

Instances details
Eq a => Eq (Partition a) Source # 
Instance details

Defined in ELynx.Tree.Partition

Methods

(==) :: Partition a -> Partition a -> Bool #

(/=) :: Partition a -> Partition a -> Bool #

Ord a => Ord (Partition a) Source # 
Instance details

Defined in ELynx.Tree.Partition

(Read a, Ord a) => Read (Partition a) Source # 
Instance details

Defined in ELynx.Tree.Partition

Show a => Show (Partition a) Source # 
Instance details

Defined in ELynx.Tree.Partition

pt :: Ord a => [Set a] -> Either String (Partition a) Source #

Create a partition.

ptUnsafe :: Ord a => [Set a] -> Partition a Source #

Create a partition.

bpToPt :: Ord a => Bipartition a -> Partition a Source #

Convert a bipartition to a partition.

ptHuman :: Show a => Partition a -> String Source #

Show a partition in a human readable form. Use a provided function to extract the valuable information.

Work with Partitions

partition :: Ord a => Tree e a -> Either String (Partition a) Source #

Get partition defined by the root of the tree.

Return Left if: - the tree is a leaf; - the tree contains duplicate leaves.

partitions :: Ord a => Tree e a -> Either String (Set (Partition a)) Source #

Get all Partitions of a tree.

Return Left if tree contains duplicate leaves.

compatible :: (Show a, Ord a) => Partition a -> Partition a -> Bool Source #

Partitions are compatible if they do not contain conflicting information. This function checks if two partitions are compatible with each other. Thereby, a variation of the following algorithm is used:

mp1 compatible mp2
for set1 in mp1:
  for set2 in mp2:
    if set1 isSubSetOf set2:
      remove set1 from mp1
    if set2 isSubSetOf set1:
      remove set2 from mp2
if either mp2 or mp2 is empty, they are compatible