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({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 {
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 
129 
130 typedef std::map<IndexPair, IndexPairSet> IndexPairSetMap;
132 } // namespace gtsam
set
Definition: pytypes.h:2232
gtsam::IndexPairVector
std::vector< IndexPair > IndexPairVector
Definition: DSFMap.h:125
gtsam::IndexPair::i
size_t i() const
Definition: DSFMap.h:121
gtsam::IndexPair::j
size_t j() const
Definition: DSFMap.h:122
gtsam::DSFMap::DSFMap
DSFMap()
constructor
Definition: DSFMap.h:78
x
set noclip points set clip one set noclip two set bar set border lt lw set xdata set ydata set zdata set x2data set y2data set boxwidth set dummy x
Definition: gnuplot_common_settings.hh:12
gtsam::DSFMapIndexPair
DSFMap< IndexPair > DSFMapIndexPair
Definition: DSFMap.h:131
gtsam::DSFMap::find_
iterator find_(const KEY &key) const
Given key, find the root Entry.
Definition: DSFMap.h:69
iterator
Definition: pytypes.h:1460
gtsam::DSFMap::Entry
We store the forest in an STL map, but parents are done with pointers.
Definition: DSFMap.h:37
gtsam::DSFMap::Set
std::set< KEY > Set
Definition: DSFMap.h:75
gtsam::DSFMap::Entry::parent_
std::map< KEY, Entry >::iterator parent_
Definition: DSFMap.h:38
gtsam::IndexPairSet
std::set< IndexPair > IndexPairSet
Definition: DSFMap.h:126
gtsam::DSFMap::Entry::rank_
size_t rank_
Definition: DSFMap.h:39
gtsam::DSFMap::Map
std::map< KEY, Entry > Map
Definition: DSFMap.h:43
gtsam::IndexPair::IndexPair
IndexPair()
Definition: DSFMap.h:119
gtsam::IndexPairSetAsArray
IndexPairVector IndexPairSetAsArray(IndexPairSet &set)
Definition: DSFMap.h:128
gtsam::IndexPair::IndexPair
IndexPair(size_t i, size_t j)
Definition: DSFMap.h:120
gtsam::DSFMap::sets
std::map< KEY, Set > sets() const
return all sets, i.e. a partition of all elements
Definition: DSFMap.h:105
size_t
std::size_t size_t
Definition: wrap/pybind11/include/pybind11/detail/common.h:490
test_KarcherMeanFactor.KEY
int KEY
Definition: test_KarcherMeanFactor.py:22
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::Entry::Entry
Entry()
Definition: DSFMap.h:40
gtsam::DSFMap::merge
void merge(const KEY &x, const KEY &y)
Merge two sets.
Definition: DSFMap.h:87
gtsam::DSFMap
Definition: DSFMap.h:34
y
Scalar * y
Definition: level1_cplx_impl.h:124
key
const gtsam::Symbol key('X', 0)
gtsam::DSFMap::find_
iterator find_(const iterator &it) const
Given iterator to initial entry, find the root Entry.
Definition: DSFMap.h:61
empty
Definition: test_copy_move.cpp:19
gtsam
traits
Definition: SFMdata.h:40
std
Definition: BFloat16.h:88
gtsam::DSFMap::find__
iterator find__(const KEY &key) const
Given key, find iterator to initial entry.
Definition: DSFMap.h:48
gtsam::IndexPair
Small utility class for representing a wrappable pairs of ints.
Definition: DSFMap.h:117
initial
Definition: testScenarioRunner.cpp:148
gtsam::IndexPairSetMap
std::map< IndexPair, IndexPairSet > IndexPairSetMap
Definition: DSFMap.h:130
gtsam::DSFMap::entries_
Map entries_
Definition: DSFMap.h:45
gtsam::DSFMap::iterator
Map::iterator iterator
Definition: DSFMap.h:44


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:32:27