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 DSFVector.h
14 * @date Jun 25, 2010
15 * @author Kai Ni
16 * @brief A faster implementation for DSF, which uses vector rather than btree.
17 */
18
19#pragma once
20
21#include <gtsam/dllexport.h>
22#include <gtsam/global_includes.h>
23
24#include <memory>
25
26#include <vector>
27#include <set>
28#include <map>
29
30namespace gtsam {
31
32/**
33 * A fast implementation of disjoint set forests that uses vector as underly data structure.
34 * This is the absolute minimal DSF data structure, and only allows size_t keys
35 * Uses rank compression but not union by rank :-(
36 * @ingroup base
37 */
38class GTSAM_EXPORT DSFBase {
39
40public:
41 typedef std::vector<size_t> V; ///< Vector of ints
42
43private:
44 std::shared_ptr<V> v_;///< Stores parent pointers, representative iff v[i]==i
45
46public:
47 /// Constructor that allocates new memory, allows for keys 0...numNodes-1.
48 DSFBase(const size_t numNodes);
49
50 /// Constructor that uses an existing, pre-allocated vector.
51 DSFBase(const std::shared_ptr<V>& v_in);
52
53 /// Find the label of the set in which {key} lives.
54 size_t find(size_t key) const;
55
56 /// Merge the sets containing i1 and i2. Does nothing if i1 and i2 are already in the same set.
57 void merge(const size_t& i1, const size_t& i2);
58};
59
60/**
61 * DSFVector additionally keeps a vector of keys to support more expensive operations
62 * @ingroup base
63 */
64class GTSAM_EXPORT DSFVector: public DSFBase {
65
66private:
67 std::vector<size_t> keys_; ///< stores keys to support more expensive operations
68
69public:
70 /// Constructor that allocates new memory, uses sequential keys 0...numNodes-1.
71 DSFVector(const size_t numNodes);
72
73 /// Constructor that allocates memory, uses given keys.
74 DSFVector(const std::vector<size_t>& keys);
75
76 /// Constructor that uses existing vectors.
77 DSFVector(const std::shared_ptr<V>& v_in, const std::vector<size_t>& keys);
78
79 // All operations below loop over all keys and hence are *at least* O(n)
80
81 /// Find whether there is one and only one occurrence for the given {label}.
82 bool isSingleton(const size_t& label) const;
83
84 /// Get the nodes in the tree with the given label
85 std::set<size_t> set(const size_t& label) const;
86
87 /// Return all sets, i.e. a partition of all elements.
88 std::map<size_t, std::set<size_t> > sets() const;
89
90 /// Return all sets, i.e. a partition of all elements.
91 std::map<size_t, std::vector<size_t> > arrays() const;
92};
93
94}
95