gtsam
base
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
{
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
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