Grab Bag Release: Union-Find

It’s been quite a while since my last post, and that is mostly because of the lot of hard work Christian and me have put into our very first project at slash games, which I’m going to tell you more about soon.

In the meantime, I’ve started to entirely rework my Grab Bag of Useful Stuff: While the old version was a loose compilation of unrelated Java and C# classes, the new one is organized as a collection of .NET libraries, all of which have been developed according to the best practices presented in Framework Design Guidelines by Cwalina and Abrams. They fully adhere to the C# Code Conventions, are all CLS-compliant and come with a load of unit tests to ensure code quality.

I’m going to release a new part of the Grab Bag every week now – head over to the Grab Bag page and check out the development roadmap now. For the first release, I’m gonna start with union-find structures.

Union-Find Structures

Union-find structures provide two operations for manipulating disjoint sets:

  • Find(x) finds the unique set containing the element x.
  • Union(A, B) combines the sets A and B into a new set.

My implementation is based on Efficiency of a Good But Not Linear Set Union Algorithm by Robert Endre Tarjan. Given a union-find universe with n elements, each in a singleton set, a sequence of m > n finds and n-1 intermixed unions has a worst-case running time of O(ma(m, n)), where a(m, n) is related to a functional inverse of Ackermann’s function and is very slow-growing.

Union-find structures are useful in many contexts, including the computation of minimum spanning trees.

Author: npruehs

Nick Pruehs is a Co-Founder of Slash Games, Hamburg. In 2009, he graduated as “Best Bachelor” in computer science at Kiel University. Two years later Nick finished his master’s degree in “Sound, Vision, Games” at Hamburg University of Applied Sciences, becoming the Lead Programmer of Daedalic Entertainment shortly after.

2 thoughts on “Grab Bag Release: Union-Find”

Questions? Comments? Suggestions? Your turn! :)