deehzee/unionfind

A union-find disjoint sets data structure implemented in Python with the "Weighted Quick Union with Path Compression" algorithm.

unionfind's Issues

components and component_mapping methods can be speed up by a factor of len(distinct_roots)

When you group elements into components (in methods components and component_mapping), the time complexity of your current way of doing it is O(N x M) (where N is len(self._elts) and M is len(distinct_roots)).
O(N x M) because looping over distinct roots is O(M) and boolean indexing over elements elts[roots == root] is O(N).
The optimized code below using a defaultdict (hashmap) has time complexity O(N). The higher M is, the bigger is the speed up.

from collections import defaultdict

def components(self):
	dict_components = defaultdict(list)
	for elem in self._elts:
		root = self.find(elem)
		dict_components[root].append(elem)
	return dict_components

Tuples don't work as keys

There is some issue with numpy.vectorize when using tuples as keys and this class doesn't work

pip package support

Hi, thanks for your helpful codes at first. I'm wondering if you are interested in upload your code into a pip installable package. Maybe I can offer help on this.