diff options
author | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2019-09-23 15:43:17 -0400 |
---|---|---|
committer | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2019-09-23 15:43:17 -0400 |
commit | d00d4896955c38818685802de42b4e79e6ef933c (patch) | |
tree | 1ed9dbe88f60b59a6569176eda5bec5b0177b4dd /lib/include/clusters.hpp | |
parent | a16864d468d58576f0525b58007b96f5d045d945 (diff) | |
download | fuse_networks-d00d4896955c38818685802de42b4e79e6ef933c.tar.gz fuse_networks-d00d4896955c38818685802de42b4e79e6ef933c.tar.bz2 fuse_networks-d00d4896955c38818685802de42b4e79e6ef933c.zip |
started migration away from boost algorithms is the backbone trimming code
Diffstat (limited to 'lib/include/clusters.hpp')
-rw-r--r-- | lib/include/clusters.hpp | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/lib/include/clusters.hpp b/lib/include/clusters.hpp new file mode 100644 index 0000000..4cc9073 --- /dev/null +++ b/lib/include/clusters.hpp @@ -0,0 +1,52 @@ + +#include <vector> +#include "graph.hpp" + +class ClusterTree { +private: + std::vector<signed> p; + std::vector<unsigned> o; + +public: + std::vector<unsigned> c; + + ClusterTree(unsigned n) : p(n, -1), o(n, 1), c(n, 0) { c[0] = n; } + + unsigned findroot(unsigned i) { + if (p[i] < 0) + return i; + else + return p[i] = this->findroot(p[i]); + } + + void join(unsigned i, unsigned j) { + c[o[i] - 1]--; + c[o[j] - 1]--; + + if (o[i] < o[j]) { + p[i] = j; + o[j] += o[i]; + c[o[j] - 1]++; + } else { + p[j] = i; + o[i] += o[j]; + c[o[i] - 1]++; + } + } + + void add_bond(const graph::edge& b) { + unsigned i = this->findroot(b.v[0]); + unsigned j = this->findroot(b.v[1]); + + if (i != j) { + this->join(i, j); + } + } + + bool same_component(unsigned v0, unsigned v1) { + unsigned i = this->findroot(v0); + unsigned j = this->findroot(v1); + + return i == j; + } +}; |