#include <DSF.h>

Inheritance diagram for gtsam::DSF< KEY >:

Public Types
typedef std::pair< KEY, KEY >	KeyLabel

typedef DSF< KEY >	Self

typedef std::set< KEY >	Set

typedef BTree< KEY, KEY >	Tree

Public Member Functions
	DSF ()

	DSF (const Tree &tree)

	DSF (const std::list< KEY > &keys)

	DSF (const std::set< KEY > &keys)

KEY	findSet (const KEY &key) const

DSF	flatten () const

Self	makeList (const std::list< KEY > &keys) const

Self	makePair (const KEY &key1, const KEY &key2) const

Self	makeSet (const KEY &key) const

void	makeSetInPlace (const KEY &key)

Self	makeUnion (const KEY &key1, const KEY &key2) const

void	makeUnionInPlace (const KEY &key1, const KEY &key2)

DSF	map (std::function< KEY(const KEY &)> func) const

size_t	numSets () const

bool	operator!= (const Self &t) const

bool	operator== (const Self &t) const

std::map< KEY, Set >	partition (const std::list< KEY > &keys) const

void	print (const std::string &name="DSF") const

Set	set (const KEY &label) const

std::map< KEY, Set >	sets () const

size_t	size () const

Protected Member Functions
KEY	findSet_ (const KEY &key)

Protected Member Functions inherited from gtsam::BTree< KEY, KEY >
BTree	add (const value_type &xd) const

BTree	add (const KEY &x, const KEY &d) const

const_iterator	begin () const

	BTree ()

	BTree (const BTree &other)

	BTree (const value_type &keyValue)

	BTree (const BTree &l, const value_type &keyValue, const BTree &r)

bool	empty () const

const_iterator	end () const

const KEY &	find (const KEY &k) const

ACC	fold (std::function< ACC(const KEY &, const KEY &, const ACC &)> f, const ACC &a) const

size_t	height () const

void	iter (std::function< void(const KEY &, const KEY &)> f) const

BTree< KEY, TO >	map (std::function< TO(const KEY &, const KEY &)> f) const

bool	mem (const KEY &x) const

const value_type &	min () const

bool	operator!= (const BTree &other) const

BTree &	operator= (const BTree &other)

bool	operator== (const BTree &other) const

void	print (const std::string &s="") const

BTree	remove (const KEY &x) const

BTree	remove_min () const

bool	same (const BTree &other) const

size_t	size () const

Additional Inherited Members
Protected Types inherited from gtsam::BTree< KEY, KEY >
typedef const_iterator	iterator

typedef std::pair< KEY, KEY >	value_type

Static Protected Member Functions inherited from gtsam::BTree< KEY, KEY >
static BTree	merge (const BTree &t1, const BTree &t2)

Detailed Description

template<class KEY>
class gtsam::DSF< KEY >

Disjoint Set Forest class

Quoting from CLR: A disjoint-set data structure maintains a collection S = {S_1,S_2,...} of disjoint dynamic sets. Each set is identified by a representative, which is some member of the set.

Definition at line 39 of file DSF.h.

Member Typedef Documentation

◆ KeyLabel

template<class KEY>

typedef std::pair<KEY, KEY> gtsam::DSF< KEY >::KeyLabel

Definition at line 45 of file DSF.h.

◆ Self

template<class KEY>

typedef DSF<KEY> gtsam::DSF< KEY >::Self

Definition at line 42 of file DSF.h.

◆ Set

template<class KEY>

typedef std::set<KEY> gtsam::DSF< KEY >::Set

Definition at line 43 of file DSF.h.

◆ Tree

template<class KEY>

typedef BTree<KEY, KEY> gtsam::DSF< KEY >::Tree

Definition at line 44 of file DSF.h.

Constructor & Destructor Documentation

◆ DSF() [1/4]

template<class KEY>

gtsam::DSF< KEY >::DSF ( )

inline

Definition at line 48 of file DSF.h.

◆ DSF() [2/4]

template<class KEY>

gtsam::DSF< KEY >::DSF ( const Tree & tree )

inline

Definition at line 53 of file DSF.h.

◆ DSF() [3/4]

template<class KEY>

gtsam::DSF< KEY >::DSF ( const std::list< KEY > & keys )

inline

Definition at line 58 of file DSF.h.

◆ DSF() [4/4]

template<class KEY>

gtsam::DSF< KEY >::DSF ( const std::set< KEY > & keys )

inline

Definition at line 65 of file DSF.h.

Member Function Documentation

◆ findSet()

template<class KEY>

KEY gtsam::DSF< KEY >::findSet ( const KEY & key ) const

inline

Definition at line 86 of file DSF.h.

◆ findSet_()

template<class KEY>

KEY gtsam::DSF< KEY >::findSet_ ( const KEY & key )

inlineprotected

same as findSet except with path compression: After we have traversed the path to the root, each parent pointer is made to directly point to it

Definition at line 196 of file DSF.h.

◆ flatten()

template<class KEY>

DSF gtsam::DSF< KEY >::flatten ( ) const

inline

Definition at line 117 of file DSF.h.

◆ makeList()

template<class KEY>

Self gtsam::DSF< KEY >::makeList ( const std::list< KEY > & keys ) const

inline

Definition at line 109 of file DSF.h.

◆ makePair()

template<class KEY>

Self gtsam::DSF< KEY >::makePair	(	const KEY &	key1,
		const KEY &	key2
	)		const

inline

Definition at line 104 of file DSF.h.

◆ makeSet()

template<class KEY>

Self gtsam::DSF< KEY >::makeSet ( const KEY & key ) const

inline

Definition at line 72 of file DSF.h.

◆ makeSetInPlace()

template<class KEY>

void gtsam::DSF< KEY >::makeSetInPlace ( const KEY & key )

inline

Definition at line 80 of file DSF.h.

◆ makeUnion()

template<class KEY>

Self gtsam::DSF< KEY >::makeUnion	(	const KEY &	key1,
		const KEY &	key2
	)		const

inline

Definition at line 92 of file DSF.h.

◆ makeUnionInPlace()

template<class KEY>

void gtsam::DSF< KEY >::makeUnionInPlace	(	const KEY &	key1,
		const KEY &	key2
	)

inline

Definition at line 99 of file DSF.h.

◆ map()

template<class KEY>

DSF gtsam::DSF< KEY >::map ( std::function< KEY(const KEY &)> func ) const

inline

Definition at line 125 of file DSF.h.

◆ numSets()

template<class KEY>

size_t gtsam::DSF< KEY >::numSets ( ) const

inline

Definition at line 133 of file DSF.h.

◆ operator!=()

template<class KEY>

bool gtsam::DSF< KEY >::operator!= ( const Self & t ) const

inline

inequality

Definition at line 178 of file DSF.h.

◆ operator==()

template<class KEY>

bool gtsam::DSF< KEY >::operator== ( const Self & t ) const

inline

equality

Definition at line 173 of file DSF.h.

◆ partition()

template<class KEY>

std::map<KEY, Set> gtsam::DSF< KEY >::partition ( const std::list< KEY > & keys ) const

inline

Definition at line 155 of file DSF.h.

◆ print()

template<class KEY>

void gtsam::DSF< KEY >::print ( const std::string & name = "DSF< KEY >" ) const

inline

Definition at line 183 of file DSF.h.

◆ set()

template<class KEY>

Set gtsam::DSF< KEY >::set ( const KEY & label ) const

inline

Definition at line 163 of file DSF.h.

◆ sets()

template<class KEY>

std::map<KEY, Set> gtsam::DSF< KEY >::sets ( ) const

inline

Definition at line 147 of file DSF.h.

◆ size()

template<class KEY>

size_t gtsam::DSF< KEY >::size ( ) const

inline

Definition at line 142 of file DSF.h.

The documentation for this class was generated from the following file:

DSF.h

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

template<class KEY> class gtsam::DSF< KEY >

Member Typedef Documentation

◆ KeyLabel

◆ Self

◆ Set

◆ Tree

Constructor & Destructor Documentation

◆ DSF() [1/4]

◆ DSF() [2/4]

◆ DSF() [3/4]

◆ DSF() [4/4]

Member Function Documentation

◆ findSet()

◆ findSet_()

◆ flatten()

◆ makeList()

◆ makePair()

◆ makeSet()

◆ makeSetInPlace()

◆ makeUnion()

◆ makeUnionInPlace()

◆ map()

◆ numSets()

◆ operator!=()

◆ operator==()

◆ partition()

◆ print()

◆ set()

◆ sets()

◆ size()

template<class KEY>
class gtsam::DSF< KEY >