Public Types | Public Member Functions | Protected Member Functions | List of all members
gtsam::DSF< KEY > Class Template Reference

#include <DSF.h>

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

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, Setpartition (const std::list< KEY > &keys) const
 
void print (const std::string &name="DSF") const
 
Set set (const KEY &label) const
 
std::map< KEY, Setsets () 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_typemin () const
 
bool operator!= (const BTree &other) const
 
BTreeoperator= (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:


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:46:17