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
12/**
13 * @file DSF.h
14 * @date Mar 26, 2010
15 * @author Kai Ni
16 * @brief An implementation of Disjoint set forests (see CLR page 446 and up)
17 */
18
19#pragma once
20
21#include <gtsam_unstable/base/BTree.h>
22#include <iostream>
23#include <list>
24#include <set>
25#include <map>
26
27namespace gtsam {
28
29/**
30 * Disjoint Set Forest class
31 *
32 * Quoting from CLR: A disjoint-set data structure maintains a collection
33 * S = {S_1,S_2,...} of disjoint dynamic sets. Each set is identified by
34 * a representative, which is some member of the set.
35 *
36 * @ingroup base
37 */
38template<class KEY>
39class DSF: protected BTree<KEY, KEY> {
40
41public:
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(key: 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_(key: key2), findSet_(key: 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(key: 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(key: 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(key: pair.second) == label)
167 set.insert(pair.first);
168 }
169 return set;
170 }
171
172 /** equality */
173 bool operator==(const Self& t) const {
174 return (Tree) *this == (Tree) t;
175 }
176
177 /** inequality */
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
190protected:
191
192 /**
193 * same as findSet except with path compression: After we have traversed the path to
194 * the root, each parent pointer is made to directly point to it
195 */
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_(key: parent);
202 *this = this->add(key, label);
203 return label;
204 }
205 }
206
207};
208
209// shortcuts
210typedef DSF<int> DSFInt;
211
212} // namespace gtsam
213