gtsam  4.1.0
gtsam
DSFMap.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 
21 #include <cstdlib> // Provides size_t
22 #include <map>
23 #include <set>
24 #include <vector>
25 
26 namespace gtsam {
27 
33 template <class KEY>
34 class DSFMap {
35  protected:
37  struct Entry {
38  typename std::map<KEY, Entry>::iterator parent_;
39  size_t rank_;
40  Entry() {}
41  };
42 
43  typedef typename std::map<KEY, Entry> Map;
44  typedef typename Map::iterator iterator;
45  mutable Map entries_;
46 
48  iterator find__(const KEY& key) const {
49  static const Entry empty;
50  iterator it = entries_.find(key);
51  // if key does not exist, create and return itself
52  if (it == entries_.end()) {
53  it = entries_.insert(std::make_pair(key, empty)).first;
54  it->second.parent_ = it;
55  it->second.rank_ = 0;
56  }
57  return it;
58  }
59 
61  iterator find_(const iterator& it) const {
62  // follow parent pointers until we reach set representative
63  iterator& parent = it->second.parent_;
64  if (parent != it) parent = find_(parent); // not yet, recurse!
65  return parent;
66  }
67 
69  inline iterator find_(const KEY& key) const {
70  iterator initial = find__(key);
71  return find_(initial);
72  }
73 
74  public:
75  typedef std::set<KEY> Set;
76 
78  DSFMap() {}
79 
81  inline KEY find(const KEY& key) const {
82  iterator root = find_(key);
83  return root->first;
84  }
85 
87  void merge(const KEY& x, const KEY& y) {
88  // straight from http://en.wikipedia.org/wiki/Disjoint-set_data_structure
89  iterator xRoot = find_(x);
90  iterator yRoot = find_(y);
91  if (xRoot == yRoot) return;
92 
93  // Merge sets
94  if (xRoot->second.rank_ < yRoot->second.rank_)
95  xRoot->second.parent_ = yRoot;
96  else if (xRoot->second.rank_ > yRoot->second.rank_)
97  yRoot->second.parent_ = xRoot;
98  else {
99  yRoot->second.parent_ = xRoot;
100  xRoot->second.rank_ = xRoot->second.rank_ + 1;
101  }
102  }
103 
105  std::map<KEY, Set> sets() const {
106  std::map<KEY, Set> sets;
107  iterator it = entries_.begin();
108  for (; it != entries_.end(); it++) {
109  iterator root = find_(it);
110  sets[root->first].insert(it->first);
111  }
112  return sets;
113  }
114 };
115 
117 class IndexPair : public std::pair<size_t,size_t> {
118  public:
119  inline IndexPair(): std::pair<size_t,size_t>(0,0) {}
120  inline IndexPair(size_t i, size_t j) : std::pair<size_t,size_t>(i,j) {}
121  inline size_t i() const { return first; };
122  inline size_t j() const { return second; };
123 };
124 
125 typedef std::vector<IndexPair> IndexPairVector;
126 typedef std::set<IndexPair> IndexPairSet;
127 
128 inline IndexPairVector IndexPairSetAsArray(IndexPairSet& set) { return IndexPairVector(set.begin(), set.end()); }
129 
130 typedef std::map<IndexPair, IndexPairSet> IndexPairSetMap;
131 typedef DSFMap<IndexPair> DSFMapIndexPair;
132 } // namespace gtsam
gtsam::DSFMap::find
KEY find(const KEY &key) const
Given key, find the representative key for the set in which it lives.
Definition: DSFMap.h:81
gtsam::DSFMap::DSFMap
DSFMap()
constructor
Definition: DSFMap.h:78
gtsam::DSFMap::sets
std::map< KEY, Set > sets() const
return all sets, i.e. a partition of all elements
Definition: DSFMap.h:105
gtsam::DSFMap
Definition: DSFMap.h:34
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::IndexPair
Small utility class for representing a wrappable pairs of ints.
Definition: DSFMap.h:117
gtsam::DSFMap::find_
iterator find_(const iterator &it) const
Given iterator to initial entry, find the root Entry.
Definition: DSFMap.h:61
gtsam::DSFMap::merge
void merge(const KEY &x, const KEY &y)
Merge two sets.
Definition: DSFMap.h:87
gtsam::DSFMap::Entry
We store the forest in an STL map, but parents are done with pointers.
Definition: DSFMap.h:37
gtsam::DSFMap::find__
iterator find__(const KEY &key) const
Given key, find iterator to initial entry.
Definition: DSFMap.h:48
gtsam::DSFMap::find_
iterator find_(const KEY &key) const
Given key, find the root Entry.
Definition: DSFMap.h:69