Loading...
Searching...
No Matches
DSFMap.h
Go to the documentation of this file.
/* ----------------------------------------------------------------------------
* GTSAM Copyright 2010, Georgia Tech Research Corporation,
* Atlanta, Georgia 30332-0415
* All Rights Reserved
* Authors: Frank Dellaert, et al. (see THANKS for the full author list)
* See LICENSE for the license information
* -------------------------------------------------------------------------- */
#pragma once
#include <cstdlib> // Provides size_t
#include <map>
#include <set>
#include <vector>
namespace gtsam {
template <class KEY>
class DSFMap {
protected:
struct Entry {
typename std::map<KEY, Entry>::iterator parent_;
size_t rank_;
Entry() {}
};
typedef typename std::map<KEY, Entry> Map;
typedef typename Map::iterator iterator;
mutable Map entries_;
iterator find__(const KEY& key) const {
static const Entry empty;
iterator it = entries_.find(key);
// if key does not exist, create and return itself
if (it == entries_.end()) {
it = entries_.insert(std::make_pair(key, empty)).first;
it->second.parent_ = it;
it->second.rank_ = 0;
}
return it;
}
iterator find_(const iterator& it) const {
// follow parent pointers until we reach set representative
iterator& parent = it->second.parent_;
if (parent != it) parent = find_(parent); // not yet, recurse!
return parent;
}
inline iterator find_(const KEY& key) const {
iterator initial = find__(key);
return find_(initial);
}
public:
typedef std::set<KEY> Set;
DSFMap() {}
inline KEY find(const KEY& key) const {
iterator root = find_(key);
return root->first;
}
void merge(const KEY& x, const KEY& y) {
// straight from http://en.wikipedia.org/wiki/Disjoint-set_data_structure
iterator xRoot = find_(x);
iterator yRoot = find_(y);
if (xRoot == yRoot) return;
// Merge sets
if (xRoot->second.rank_ < yRoot->second.rank_)
xRoot->second.parent_ = yRoot;
else if (xRoot->second.rank_ > yRoot->second.rank_)
yRoot->second.parent_ = xRoot;
else {
yRoot->second.parent_ = xRoot;
xRoot->second.rank_ = xRoot->second.rank_ + 1;
}
}
std::map<KEY, Set> sets() const {
std::map<KEY, Set> sets;
iterator it = entries_.begin();
for (; it != entries_.end(); it++) {
iterator root = find_(it);
sets[root->first].insert(it->first);
}
return sets;
}
};
class IndexPair : public std::pair<size_t,size_t> {
public:
inline IndexPair(): std::pair<size_t,size_t>(0,0) {}
inline IndexPair(size_t i, size_t j) : std::pair<size_t,size_t>(i,j) {}
inline size_t i() const { return first; };
inline size_t j() const { return second; };
};
typedef std::vector<IndexPair> IndexPairVector;
typedef std::set<IndexPair> IndexPairSet;
inline IndexPairVector IndexPairSetAsArray(IndexPairSet& set) { return IndexPairVector(set.begin(), set.end()); }
typedef std::map<IndexPair, IndexPairSet> IndexPairSetMap;
typedef DSFMap<IndexPair> DSFMapIndexPair;
} // namespace gtsam
gtsam
Global functions in a separate testing namespace.
Definition chartTesting.h:28
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 iterator &it) const
Given iterator to initial entry, find the root Entry.
Definition DSFMap.h:61
gtsam::DSFMap::find_
iterator find_(const KEY &key) const
Given key, find the root Entry.
Definition DSFMap.h:69
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::DSFMap
DSFMap()
constructor
Definition DSFMap.h:78
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::merge
void merge(const KEY &x, const KEY &y)
Merge two sets.
Definition DSFMap.h:87