Copyright | (c) Dominik Schrempf 2020 |
---|---|
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.
A multifurcation induces a Partition
, similar to branches inducing
Bipartition
s.
Synopsis
- data Partition a
- mp :: Ord a => [Set a] -> Either String (Partition a)
- mpUnsafe :: Ord a => [Set a] -> Partition a
- bpToMp :: Ord a => Bipartition a -> Partition a
- mpHuman :: 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
Each branch of a tree partitions the leaves of the tree into two subsets
(see Bipartition
). In a similar way, each internal node
(excluding the root node) partitions the leaves into three (or more) subsets
which is called 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 # | |
mpHuman :: 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:
mp1compatible
mp2 for set1 in mp1: for set2 in mp2: if set1isSubSetOf
set2: remove set1 from mp1 if set2isSubSetOf
set1: remove set2 from mp2 if either mp2 or mp2 is empty, they are compatible