GTSAM  4.0.2
C++ library for smoothing and mapping (SAM)
Public Types | Public Member Functions | Protected Types | Protected Member Functions | Static Protected Member Functions | List of all members
gtsam::DSF< KEY > Class Template Reference
Base

#include <DSF.h>

Inheritance diagram for gtsam::DSF< KEY >:
Inheritance graph
[legend]
Collaboration diagram for gtsam::DSF< KEY >:
Collaboration graph
[legend]

Public Types

typedef DSF< KEY > Self
 
typedef std::set< KEY > Set
 
typedef BTree< KEY, KEY > Tree
 
typedef std::pair< KEY, KEY > KeyLabel
 

Public Member Functions

 DSF (const Tree &tree)
 
 DSF (const std::list< KEY > &keys)
 
 DSF (const std::set< KEY > &keys)
 
Self makeSet (const KEY &key) const
 
void makeSetInPlace (const KEY &key)
 
KEY findSet (const KEY &key) const
 
Self makeUnion (const KEY &key1, const KEY &key2) const
 
void makeUnionInPlace (const KEY &key1, const KEY &key2)
 
Self makePair (const KEY &key1, const KEY &key2) const
 
Self makeList (const std::list< KEY > &keys) const
 
DSF flatten () const
 
DSF map (std::function< KEY(const KEY &)> func) const
 
size_t numSets () const
 
size_t size () const
 
std::map< KEY, Set > sets () const
 
std::map< KEY, Set > partition (const std::list< KEY > &keys) const
 
Set set (const KEY &label) const
 
bool operator== (const Self &t) const
 
bool operator!= (const Self &t) const
 
void print (const std::string &name="DSF") const
 

Protected Types

typedef std::pair< KEY, KEY > value_type
 
typedef const_iterator iterator
 

Protected Member Functions

KEY findSet_ (const KEY &key)
 
bool empty () const
 
BTree add (const value_type &xd) const
 
BTree add (const KEY &x, const KEY &d) const
 
bool mem (const KEY &x) const
 
bool same (const BTree &other) const
 
bool operator== (const BTree &other) const
 
bool operator!= (const BTree &other) const
 
const value_type & min () const
 
BTree remove_min () const
 
BTree remove (const KEY &x) const
 
size_t height () const
 
const KEY & find (const KEY &k) 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
 
ACC fold (std::function< ACC(const KEY &, const KEY &, const ACC &)> f, const ACC &a) const
 
const_iterator begin () const
 
const_iterator end () const
 

Static Protected Member Functions

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.

Member Function Documentation

◆ add() [1/2]

BTree gtsam::BTree< KEY, KEY >::add ( const value_type &  xd) const
inlineinherited

add a key-value pair

◆ add() [2/2]

BTree gtsam::BTree< KEY, KEY >::add ( const KEY &  x,
const KEY &  d 
) const
inlineinherited

add a key-value pair

◆ begin()

const_iterator gtsam::BTree< KEY, KEY >::begin ( ) const
inlineinherited

return iterator

◆ empty()

bool gtsam::BTree< KEY, KEY >::empty ( ) const
inlineinherited

Check whether tree is empty

◆ end()

const_iterator gtsam::BTree< KEY, KEY >::end ( ) const
inlineinherited

return iterator

◆ find()

const KEY & gtsam::BTree< KEY, KEY >::find ( const KEY &  k) const
inlineinherited

find a value given a key, throws exception when not found Optimized non-recursive version as [find] is crucial for speed

◆ 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

◆ fold()

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

t.fold(f,a) computes [(f kN dN ... (f k1 d1 a)...)], where [k1 ... kN] are the keys of all bindings in [m], and [d1 ... dN] are the associated data. The associated values are passed to [f] in reverse sort order

◆ height()

size_t gtsam::BTree< KEY, KEY >::height ( ) const
inlineinherited

Return height of the tree, 0 if empty

◆ iter()

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

iterate over tree

◆ map()

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

map key-values in tree over function f that computes a new value

◆ mem()

bool gtsam::BTree< KEY, KEY >::mem ( const KEY &  x) const
inlineinherited

member predicate

◆ merge()

static BTree gtsam::BTree< KEY, KEY >::merge ( const BTree< KEY, KEY > &  t1,
const BTree< KEY, KEY > &  t2 
)
inlinestaticinherited

merge two trees

◆ min()

const value_type& gtsam::BTree< KEY, KEY >::min ( ) const
inlineinherited

minimum key binding

◆ operator!=()

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

inequality

◆ operator==() [1/2]

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

equality

◆ operator==() [2/2]

bool gtsam::BTree< KEY, KEY >::operator== ( const BTree< KEY, KEY > &  other) const
inlineinherited

Check whether trees are structurally the same, i.e., contain the same values in same tree-structure.

◆ remove()

BTree gtsam::BTree< KEY, KEY >::remove ( const KEY &  x) const
inlineinherited

remove a key-value pair

◆ remove_min()

BTree gtsam::BTree< KEY, KEY >::remove_min ( ) const
inlineinherited

remove minimum key binding

◆ same()

bool gtsam::BTree< KEY, KEY >::same ( const BTree< KEY, KEY > &  other) const
inlineinherited

Check whether trees are exactly the same (occupy same memory)

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.13