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

#include <Bpp/Phyl/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 contructor. 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 throw (Exception)

int *	getBitBipartition (size_t i) throw (Exception)

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

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

void	deleteBipartition (size_t i) throw (Exception)

bool	isSorted () const

void	sortElements ()

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

bool	areIdentical (size_t k1, size_t k2) const throw (Exception)

void	removeRedundantBipartitions ()

bool	areCompatible (size_t k1, size_t k2) const throw (Exception)
	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 throw (Exception)
	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) throw (Exception)
	Replaces ones by zeros and zeros by ones in the ith bipartition. More...

size_t	getPartitionSize (size_t i) const throw (Exception)
	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...

TreeTemplate< Node > *	toTree () const throw (Exception)
	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 83 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 contructor.

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 104 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 152 of file BipartitionList.cpp.

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

◆ BipartitionList() [3/3]

BipartitionList::BipartitionList ( const BipartitionList & bipl )

Copy-constructor.

Definition at line 182 of file BipartitionList.cpp.

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

◆ ~BipartitionList()

BipartitionList::~BipartitionList ( )

virtual

Definition at line 233 of file BipartitionList.cpp.

References bitBipartitionList_.

Member Function Documentation

◆ addBipartition()

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

Definition at line 294 of file BipartitionList.cpp.

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

Referenced by addTrivialBipartitions().

◆ addTrivialBipartitions()

void BipartitionList::addTrivialBipartitions ( bool checkExisting )

Adds bipartitions corresponding to external branches if missing.

Definition at line 560 of file BipartitionList.cpp.

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

Referenced by bpp::TreeTools::bipartitionOccurrences().

◆ areAllCompatible()

bool BipartitionList::areAllCompatible ( ) const

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

Definition at line 439 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
throw	(	Exception
	)

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

Parameters

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

Definition at line 454 of file BipartitionList.cpp.

◆ areCompatible()

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

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 403 of file BipartitionList.cpp.

References bpp::BipartitionTools::testBit().

Referenced by areAllCompatible(), bpp::BipartitionTools::areCompatible(), and bpp::TreeTools::thresholdConsensus().

◆ areIdentical()

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

Definition at line 369 of file BipartitionList.cpp.

References bpp::BipartitionTools::testBit().

Referenced by bpp::BipartitionTools::areIdentical(), bpp::TreeTools::bipartitionOccurrences(), and 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