ELynx.Data.Tree.Multipartition

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

A multifurcation induces a Multipartition, similar to branches inducing Bipartitions.

The Multipartition data type.

data Multipartition a

Each branch of a bifurcating tree partitions the leaves of the tree into three Subsets, see Bipartition. In a similar way, each internal node induces a tripartition. Tripartitions are not yet implemented (December 2019) because it is usually sufficient to work with bipartitions. If, however, 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, and a Multipartition. Multipartitions are interesting in that we can use them for calculating incompatible splits, see Distance. The order of the partitions within a multipartition is unimportant, .

Instances

Eq a => Eq (Multipartition a)

Defined in ELynx.Data.Tree.Multipartition

Methods

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

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

Ord a => Ord (Multipartition a)

Defined in ELynx.Data.Tree.Multipartition

Methods

compare :: Multipartition a -> Multipartition a -> Ordering

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

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

(>) :: Multipartition a -> Multipartition a -> Bool

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

max :: Multipartition a -> Multipartition a -> Multipartition a

min :: Multipartition a -> Multipartition a -> Multipartition a

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

Defined in ELynx.Data.Tree.Multipartition

Methods

readsPrec :: Int -> ReadS (Multipartition a)

readList :: ReadS [Multipartition a]

readPrec :: ReadPrec (Multipartition a)

readListPrec :: ReadPrec [Multipartition a]

Show a => Show (Multipartition a)

Defined in ELynx.Data.Tree.Multipartition

Methods

showsPrec :: Int -> Multipartition a -> ShowS

show :: Multipartition a -> String

showList :: [Multipartition a] -> ShowS

mps :: Multipartition a -> Set (Subset a)

Set of partitions

mp :: Ord a => [Subset a] -> Multipartition a

Create a multipartition.

mpmap :: (Ord a, Ord b) => (a -> b) -> Multipartition a -> Multipartition b

Map a function over all elements in the multipartitions.

mphuman :: (a -> String) -> Multipartition a -> String

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

fromBipartition :: Ord a => Bipartition a -> Multipartition a

Convert bipartition to multipartition.

Working with Multipartitions.

multipartitions :: Ord a => Tree a -> Set (Multipartition a)

Get all multipartitions of a tree.

findSubset :: Ord a => a -> Multipartition a -> Subset a

Find the multipartition containing a given element.

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

Multipartitions are compatible if they do not contain conflicting information. This function checks if two multipartitions are compatible with each other. Thereby, following algorithm is used:

1. Take each subset of the first multipartition.

2a. Determine the overlap: For each leaf of the chosen subset, add the subset of the second multipartition containing the leaf. The result is a set of subsets, which is the union of the added subsets.

The data type "set of subsets" is actually the same data type as a multipartition. However, it is not a partition, because it may and will not span the whole set of leaves, and so, I use S.Set (Subset a). One could define a multiset data type to improve comprehensibility.

2b. Collect the set of subsets from point 1.

1. Each set of subsets needs to be either equal or disjoint with any other set of subsets in the collection. If so, the first multipartition is compatible with the second.
2. Exchange the first with the second multipartition and go through steps 1 to 3.

See also compatible.