gtsam  4.1.0
gtsam
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;
44  typedef BTree<KEY, KEY> Tree;
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(boost::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
gtsam::DSF
Definition: DSF.h:39
gtsam::BTree< KEY, KEY >::mem
bool mem(const KEY &x) const
member predicate
Definition: BTree.h:160
gtsam::BTree
Definition: BTree.h:32
gtsam::BTree< KEY, KEY >::find
const KEY & find(const KEY &k) const
find a value given a key, throws exception when not found Optimized non-recursive version as [find] i...
Definition: BTree.h:239
gtsam::DSF::operator==
bool operator==(const Self &t) const
equality
Definition: DSF.h:173
gtsam::DSF::operator!=
bool operator!=(const Self &t) const
inequality
Definition: DSF.h:178
gtsam::DSF::findSet_
KEY findSet_(const KEY &key)
same as findSet except with path compression: After we have traversed the path to the root,...
Definition: DSF.h:196
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::BTree< KEY, KEY >::size
size_t size() const
return size of the tree
Definition: BTree.h:230
BTree.h
purely functional binary tree
gtsam::BTree< KEY, KEY >::add
BTree add(const value_type &xd) const
add a key-value pair
Definition: BTree.h:143