Copyright | (c) Dominik Schrempf 2021 |
---|---|

License | GPL-3.0-or-later |

Maintainer | dominik.schrempf@gmail.com |

Stability | unstable |

Portability | portable |

Safe Haskell | None |

Language | Haskell2010 |

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

## Synopsis

- data Partition a
- pt :: Ord a => [Set a] -> Either String (Partition a)
- ptUnsafe :: Ord a => [Set a] -> Partition a
- bpToPt :: Ord a => Bipartition a -> Partition a
- ptHuman :: Show a => Partition a -> String
- partition :: Ord a => Tree e a -> Either String (Partition a)
- partitions :: Ord a => Tree e a -> Either String (Set (Partition a))
- compatible :: (Show a, Ord a) => Partition a -> Partition a -> Bool

# Data type

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

Ord a => Ord (Partition a) Source # | |

Defined in ELynx.Tree.Partition | |

(Read a, Ord a) => Read (Partition a) Source # | |

Show a => Show (Partition a) Source # | |

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 `Partition`

s

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.

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

`Partition`

s 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