This class deals with the bipartitions defined by trees. More...

#include <Bpp/Phyl/Tree/BipartitionList.h>

Inheritance diagram for bpp::BipartitionList:

Collaboration diagram for bpp::BipartitionList:

Public Member Functions
	BipartitionList (const Tree &tr, bool sorted=true, std::vector< int > *index=0)
	The main constructor. More...

	BipartitionList (const std::vector< std::string > &elements, const std::vector< int * > &bipl)
	An alternative constructor in which elements and bipartitions are passed directly. More...

	BipartitionList (const BipartitionList &bipl)
	Copy-constructor. More...

BipartitionList &	operator= (const BipartitionList &bipl)
	Assignment operator. More...

virtual	~BipartitionList ()

BipartitionList *	clone () const

size_t	getNumberOfElements () const

const std::vector< std::string > &	getElementNames () const

size_t	getNumberOfBipartitions () const

const std::vector< int * > &	getBitBipartitionList () const

std::map< std::string, bool >	getBipartition (size_t i) const

int *	getBitBipartition (size_t i)

bool	haveSameElementsThan (std::map< std::string, bool > &bipart) const

void	addBipartition (std::map< std::string, bool > &bipart, bool checkElements=1)

void	deleteBipartition (size_t i)

bool	isSorted () const

void	sortElements ()

bool	containsBipartition (std::map< std::string, bool > &bipart, bool checkElements=1) const

bool	areIdentical (size_t k1, size_t k2) const

void	removeRedundantBipartitions ()

bool	areCompatible (size_t k1, size_t k2) const
	Tells whether 2 bipartitions from the list are compatible. More...

bool	areAllCompatible () const
	Tells whether all bipartitions in the list are compatible with each other. More...

bool	areAllCompatibleWith (std::map< std::string, bool > &bipart, bool checkElements=true) const
	Tells whether all bipartitions in the list are compatible with a given bipartition. More...

void	removeTrivialBipartitions ()
	Removes bipartitions corresponding to external branches (1 vs n-1) More...

void	addTrivialBipartitions (bool checkExisting)
	Adds bipartitions corresponding to external branches if missing. More...

void	flip (size_t i)
	Replaces ones by zeros and zeros by ones in the ith bipartition. More...

size_t	getPartitionSize (size_t i) const
	Returns the size of the smallest of the two partitions (e.g. 1 for external branches) More...

void	sortByPartitionSize ()
	Sort bipartitions by partition size. More...

std::unique_ptr< TreeTemplate< Node > >	toTree () const
	Translate into a tree. More...

RowMatrix< int >	toMatrix () const
	Create a matrix representation of the bifurcations. More...

Private Member Functions
std::vector< std::string >	buildBitBipartitions (const Node nd, std::vector< int > &bitbip, const std::vector< std::string > &elements, size_t cpt, std::vector< int > index) const

Private Attributes
std::vector< int * >	bitBipartitionList_

std::vector< std::string >	elements_

bool	sorted_

Detailed Description

This class deals with the bipartitions defined by trees.

Any branch of a tree defines a bipartition, i.e. two non-overlapping subsets of leaves whose union is the whole set of leaves. A tree topology can therefore be represented by the list of bipartitions its branches define - the so-called matrix representation. Coding trees this way is useful for comparing topologies, calculating topological distances, producing consensus trees or super-trees, calculating bootstrap support.

A BipartitionList includes a set of element names (typically leaf names) and a vector of arrays of bits (int*, not bitsets, are used to allow for dynamic memory allocation). Each array of bit codes for one bipartition. Each bit in an array of bit corresponds to one element, so the order of element names matter. Bits set to zero versus bits set to one define the two partitions of elements. A BipartitionList is called sorted if its elements (leaf names) are in alphabetic order (recommended).

BipartitionList objects are typically created from a tree, in which case elements are leaf names. Note that BipartitionList is an unrooted object: a rooted or unrooted versions of the same tree will yield the same BipartitionList in which the root location is ignored. Bipartitions can be accessed as arrays of bits (e.g. getBitBipartition), or as map<string, bool>, in which keys are leaf names and true/false values define the two partitions (e.g. getBipartition, addBipartition).

See also: Tree; BipartitionTools; TreeTools

Definition at line 47 of file BipartitionList.h.

Constructor & Destructor Documentation

◆ BipartitionList() [1/3]

BipartitionList::BipartitionList	(	const Tree &	tr,
		bool	sorted = `true`,
		std::vector< int > *	index = `0`
	)

The main constructor.

Parameters

tr	The tree to be coded as bipartitions
sorted	Tells whether leave names should be alphabetically sorted (recommended)
index	An output optional vector to keep trace of the nodes id underlying each bipartition.

Definition at line 68 of file BipartitionList.cpp.

References bitBipartitionList_, buildBitBipartitions(), elements_, bpp::Tree::getLeavesNames(), bpp::Tree::getNumberOfNodes(), bpp::TreeTemplate< N >::getRootNode(), bpp::Tree::isRooted(), and bpp::BipartitionTools::LWORD.

Referenced by clone().

◆ BipartitionList() [2/3]

BipartitionList::BipartitionList	(	const std::vector< std::string > &	elements,
		const std::vector< int * > &	bipl
	)

An alternative constructor in which elements and bipartitions are passed directly.

Parameters

elements	Leaf names
bipl	The list of bit-encoded bipartitions

Definition at line 116 of file BipartitionList.cpp.

References bitBipartitionList_, bpp::BipartitionTools::LWORD, and sorted_.

◆ BipartitionList() [3/3]

BipartitionList::BipartitionList ( const BipartitionList & bipl )

Copy-constructor.

Definition at line 146 of file BipartitionList.cpp.

References bitBipartitionList_, getBitBipartitionList(), getNumberOfBipartitions(), getNumberOfElements(), and bpp::BipartitionTools::LWORD.

◆ ~BipartitionList()

BipartitionList::~BipartitionList ( )

virtual

Definition at line 197 of file BipartitionList.cpp.

References bitBipartitionList_.

Member Function Documentation

◆ addBipartition()

void BipartitionList::addBipartition	(	std::map< std::string, bool > &	bipart,
		bool	checkElements = `1`
	)

Definition at line 258 of file BipartitionList.cpp.

References bpp::BipartitionTools::bit0(), bpp::BipartitionTools::bit1(), bitBipartitionList_, elements_, haveSameElementsThan(), and bpp::BipartitionTools::LWORD.

Referenced by addTrivialBipartitions(), and areAllCompatibleWith().

◆ addTrivialBipartitions()

void BipartitionList::addTrivialBipartitions ( bool checkExisting )

Adds bipartitions corresponding to external branches if missing.

Definition at line 524 of file BipartitionList.cpp.

References addBipartition(), containsBipartition(), and elements_.

◆ areAllCompatible()

bool BipartitionList::areAllCompatible ( ) const

Tells whether all bipartitions in the list are compatible with each other.

Definition at line 403 of file BipartitionList.cpp.

References areCompatible(), and bitBipartitionList_.

Referenced by toTree().

◆ areAllCompatibleWith()

bool BipartitionList::areAllCompatibleWith	(	std::map< std::string, bool > &	bipart,
		bool	checkElements = `true`
	)		const

Tells whether all bipartitions in the list are compatible with a given bipartition.

Parameters

bipart	A map representing a bipartition.
checkElements	Check the correspondence of element sets or not.

Definition at line 418 of file BipartitionList.cpp.

References addBipartition(), areCompatible(), bitBipartitionList_, deleteBipartition(), and haveSameElementsThan().

◆ areCompatible()

bool BipartitionList::areCompatible	(	size_t	k1,
		size_t	k2
	)		const

Tells whether 2 bipartitions from the list are compatible.

Let A=A1|A2 and B=B1|B2 be two bipartitions (such that A1 U A2 = B1 U B2 = set of leaves) A and B are said compatible if (A1 contains B1 and B2 contains A2) or (A1 contains B2 and B1 contains A2) or (B1 contains A1 and A2 contains B2) or (B2 contains A1 and A2 contains B1). Only compatible bipartitions can belong to the same tree.

Definition at line 367 of file BipartitionList.cpp.

References bitBipartitionList_, elements_, and bpp::BipartitionTools::testBit().

Referenced by areAllCompatible(), and areAllCompatibleWith().

◆ areIdentical()

bool BipartitionList::areIdentical	(	size_t	k1,
		size_t	k2
	)		const

Definition at line 333 of file BipartitionList.cpp.

References bitBipartitionList_, elements_, and bpp::BipartitionTools::testBit().

Referenced by removeRedundantBipartitions().

◆ buildBitBipartitions()

vector< string > BipartitionList::buildBitBipartitions	(	const Node *	nd,
		std::vector< int * > &	bitbip,
		const std::vector< std::string > &	elements,
		size_t *	cpt,
		std::vector< int > *	index
	)		const