ELynx.Tree.Partition

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

Data type

data Partition a

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

Eq a => Eq (Partition a)

Defined in ELynx.Tree.Partition

Methods

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

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

Ord a => Ord (Partition a)

Defined in ELynx.Tree.Partition

Methods

compare :: Partition a -> Partition a -> Ordering

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

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

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

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

max :: Partition a -> Partition a -> Partition a

min :: Partition a -> Partition a -> Partition a

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

Defined in ELynx.Tree.Partition

Methods

readsPrec :: Int -> ReadS (Partition a)

readList :: ReadS [Partition a]

readPrec :: ReadPrec (Partition a)

readListPrec :: ReadPrec [Partition a]

Show a => Show (Partition a)

Defined in ELynx.Tree.Partition

Methods

showsPrec :: Int -> Partition a -> ShowS

show :: Partition a -> String

showList :: [Partition a] -> ShowS

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

Create a partition.

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

Create a partition.

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

Convert a bipartition to a partition.

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

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)

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))

Get all Partitions of a tree.

Return Left if tree contains duplicate leaves.

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

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