From ff133bbd33f10b87b5aaf65515453809a3730fe4 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Wed, 8 Jul 2020 14:57:31 +0200 Subject: BLI: add disjoint set data structure This can be used to find separate islands in meshes efficiently (as is done in cycles already). Furthermore, this helps to implement some algorithms on node trees more efficiently. --- source/blender/blenlib/BLI_disjoint_set.hh | 105 +++++++++++++++++++++++++++++ source/blender/blenlib/CMakeLists.txt | 1 + 2 files changed, 106 insertions(+) create mode 100644 source/blender/blenlib/BLI_disjoint_set.hh (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/BLI_disjoint_set.hh b/source/blender/blenlib/BLI_disjoint_set.hh new file mode 100644 index 00000000000..3b8453669aa --- /dev/null +++ b/source/blender/blenlib/BLI_disjoint_set.hh @@ -0,0 +1,105 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#ifndef __BLI_DISJOINT_SET_HH__ +#define __BLI_DISJOINT_SET_HH__ + +/** \file + * \ingroup bli + * + * This implements the disjoint set data structure with path compression and union by rank. + */ + +#include "BLI_array.hh" + +namespace blender { + +class DisjointSet { + private: + Array parents_; + Array ranks_; + + public: + /** + * Create a new disjoint set with the given size. Initially, every element is in a separate set. + */ + DisjointSet(uint size) : parents_(size), ranks_(size, 0) + { + for (uint i = 0; i < size; i++) { + parents_[i] = i; + } + } + + /** + * Join the sets containing elements x and y. Nothing happens when they have been in the same set + * before. + */ + void join(uint x, uint y) + { + uint root1 = this->find_root(x); + uint root2 = this->find_root(y); + + /* x and y are in the same set already. */ + if (root1 == root2) { + return; + } + + /* Implement union by rank heuristic. */ + if (ranks_[root1] < ranks_[root2]) { + std::swap(root1, root2); + } + parents_[root2] = root1; + + if (ranks_[root1] == ranks_[root2]) { + ranks_[root1]++; + } + } + + /** + * Return true when x and y are in the same set. + */ + bool in_same_set(uint x, uint y) + { + uint root1 = this->find_root(x); + uint root2 = this->find_root(y); + return root1 == root2; + } + + /** + * Find the element that represents the set containing x currently. + */ + uint find_root(uint x) + { + /* Find root by following parents. */ + uint root = x; + while (parents_[root] != root) { + root = parents_[root]; + } + + /* Compress path. */ + while (parents_[x] != root) { + uint parent = parents_[x]; + parents_[x] = root; + x = parent; + } + + return root; + } +}; + +} // namespace blender + +#endif /* __BLI_DISJOINT_SET_HH__ */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index b796e893d69..93e5d0a0d79 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -163,6 +163,7 @@ set(SRC BLI_convexhull_2d.h BLI_delaunay_2d.h BLI_dial_2d.h + BLI_disjoint_set.hh BLI_dlrbTree.h BLI_dot_export.hh BLI_dot_export_attribute_enums.hh -- cgit v1.2.3