DSF.h
Go to the documentation of this file.
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4  * Atlanta, Georgia 30332-0415
5  * All Rights Reserved
6  * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7 
8  * See LICENSE for the license information
9 
10  * -------------------------------------------------------------------------- */
11 
19 #pragma once
20 
22 #include <iostream>
23 #include <list>
24 #include <set>
25 #include <map>
26 
27 namespace gtsam {
28 
38 template<class KEY>
39 class DSF: protected BTree<KEY, KEY> {
40 
41 public:
42  typedef DSF<KEY> Self;
43  typedef std::set<KEY> Set;
45  typedef std::pair<KEY, KEY> KeyLabel;
46 
47  // constructor
48  DSF() :
49  Tree() {
50  }
51 
52  // constructor
53  DSF(const Tree& tree) :
54  Tree(tree) {
55  }
56 
57  // constructor with a list of unconnected keys
58  DSF(const std::list<KEY>& keys) :
59  Tree() {
60  for(const KEY& key: keys)
61  *this = this->add(key, key);
62  }
63 
64  // constructor with a set of unconnected keys
65  DSF(const std::set<KEY>& keys) :
66  Tree() {
67  for(const KEY& key: keys)
68  *this = this->add(key, key);
69  }
70 
71  // create a new singleton, does nothing if already exists
72  Self makeSet(const KEY& key) const {
73  if (this->mem(key))
74  return *this;
75  else
76  return this->add(key, key);
77  }
78 
79  // create a new singleton, does nothing if already exists
80  void makeSetInPlace(const KEY& key) {
81  if (!this->mem(key))
82  *this = this->add(key, key);
83  }
84 
85  // find the label of the set in which {key} lives
86  KEY findSet(const KEY& key) const {
87  KEY parent = this->find(key);
88  return parent == key ? key : findSet(parent);
89  }
90 
91  // return a new DSF where x and y are in the same set. No path compression
92  Self makeUnion(const KEY& key1, const KEY& key2) const {
93  DSF<KEY> copy = *this;
94  copy.makeUnionInPlace(key1,key2);
95  return copy;
96  }
97 
98  // the in-place version of makeUnion
99  void makeUnionInPlace(const KEY& key1, const KEY& key2) {
100  *this = this->add(findSet_(key2), findSet_(key1));
101  }
102 
103  // create a new singleton with two connected keys
104  Self makePair(const KEY& key1, const KEY& key2) const {
105  return makeSet(key1).makeSet(key2).makeUnion(key1, key2);
106  }
107 
108  // create a new singleton with a list of fully connected keys
109  Self makeList(const std::list<KEY>& keys) const {
110  Self t = *this;
111  for(const KEY& key: keys)
112  t = t.makePair(key, keys.front());
113  return t;
114  }
115 
116  // return a dsf in which all find_set operations will be O(1) due to path compression.
117  DSF flatten() const {
118  DSF t = *this;
119  for(const KeyLabel& pair: (Tree)t)
120  t.findSet_(pair.first);
121  return t;
122  }
123 
124  // maps f over all keys, must be invertible
125  DSF map(std::function<KEY(const KEY&)> func) const {
126  DSF t;
127  for(const KeyLabel& pair: (Tree)*this)
128  t = t.add(func(pair.first), func(pair.second));
129  return t;
130  }
131 
132  // return the number of sets
133  size_t numSets() const {
134  size_t num = 0;
135  for(const KeyLabel& pair: (Tree)*this)
136  if (pair.first == pair.second)
137  num++;
138  return num;
139  }
140 
141  // return the numer of keys
142  size_t size() const {
143  return Tree::size();
144  }
145 
146  // return all sets, i.e. a partition of all elements
147  std::map<KEY, Set> sets() const {
148  std::map<KEY, Set> sets;
149  for(const KeyLabel& pair: (Tree)*this)
150  sets[findSet(pair.second)].insert(pair.first);
151  return sets;
152  }
153 
154  // return a partition of the given elements {keys}
155  std::map<KEY, Set> partition(const std::list<KEY>& keys) const {
156  std::map<KEY, Set> partitions;
157  for(const KEY& key: keys)
158  partitions[findSet(key)].insert(key);
159  return partitions;
160  }
161 
162  // get the nodes in the tree with the given label
163  Set set(const KEY& label) const {
164  Set set;
165  for(const KeyLabel& pair: (Tree)*this) {
166  if (pair.second == label || findSet(pair.second) == label)
167  set.insert(pair.first);
168  }
169  return set;
170  }
171 
173  bool operator==(const Self& t) const {
174  return (Tree) *this == (Tree) t;
175  }
176 
178  bool operator!=(const Self& t) const {
179  return (Tree) *this != (Tree) t;
180  }
181 
182  // print the object
183  void print(const std::string& name = "DSF") const {
184  std::cout << name << std::endl;
185  for(const KeyLabel& pair: (Tree)*this)
186  std::cout << (std::string) pair.first << " " << (std::string) pair.second
187  << std::endl;
188  }
189 
190 protected:
191 
196  KEY findSet_(const KEY& key) {
197  KEY parent = this->find(key);
198  if (parent == key)
199  return parent;
200  else {
201  KEY label = findSet_(parent);
202  *this = this->add(key, label);
203  return label;
204  }
205  }
206 
207 };
208 
209 // shortcuts
210 typedef DSF<int> DSFInt;
211 
212 } // namespace gtsam
DSF< int > DSFInt
Definition: DSF.h:210
std::set< KEY > Set
Definition: DSF.h:43
A insert(1, 2)=0
DSF flatten() const
Definition: DSF.h:117
std::map< KEY, Set > partition(const std::list< KEY > &keys) const
Definition: DSF.h:155
bool mem(const KEY &x) const
Definition: BTree.h:162
DSF(const std::set< KEY > &keys)
Definition: DSF.h:65
Binary tree.
Definition: BTree.h:34
size_t numSets() const
Definition: DSF.h:133
BTree< KEY, KEY > Tree
Definition: DSF.h:44
void makeSetInPlace(const KEY &key)
Definition: DSF.h:80
void print(const std::string &name="DSF") const
Definition: DSF.h:183
size_t size() const
Definition: BTree.h:232
purely functional binary tree
std::pair< KEY, KEY > KeyLabel
Definition: DSF.h:45
Self makeList(const std::list< KEY > &keys) const
Definition: DSF.h:109
KEY findSet_(const KEY &key)
Definition: DSF.h:196
DSF(const std::list< KEY > &keys)
Definition: DSF.h:58
bool operator==(const Self &t) const
Definition: DSF.h:173
Self makePair(const KEY &key1, const KEY &key2) const
Definition: DSF.h:104
std::map< KEY, Set > sets() const
Definition: DSF.h:147
void makeUnionInPlace(const KEY &key1, const KEY &key2)
Definition: DSF.h:99
const Symbol key1('v', 1)
Self makeUnion(const KEY &key1, const KEY &key2) const
Definition: DSF.h:92
Self makeSet(const KEY &key) const
Definition: DSF.h:72
const KEY & key() const
Definition: BTree.h:82
DSF()
Definition: DSF.h:48
KEY findSet(const KEY &key) const
Definition: DSF.h:86
traits
Definition: chartTesting.h:28
DSF map(std::function< KEY(const KEY &)> func) const
Definition: DSF.h:125
int func(const int &a)
Definition: testDSF.cpp:221
bool operator!=(const Self &t) const
Definition: DSF.h:178
BTree add(const value_type &xd) const
Definition: BTree.h:145
DSF< KEY > Self
Definition: DSF.h:42
const KEY & find(const KEY &k) const
Definition: BTree.h:241
Annotation for function names.
Definition: attr.h:48
int EIGEN_BLAS_FUNC() copy(int *n, RealScalar *px, int *incx, RealScalar *py, int *incy)
Definition: level1_impl.h:29
DSF(const Tree &tree)
Definition: DSF.h:53
const KeyVector keys
size_t size() const
Definition: DSF.h:142
Point2 t(10, 10)
Definition: DSF.h:39
const Symbol key2('v', 2)


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:11