6
\$\begingroup\$

The Wikipedia article on the union find problem gives a very simple implementation, which I ported to C# and tested.

I know that the code should be, in the aggregate, asymptotically almost linear. But is it a practical implementation? Are there optimizations I should have used? Is there a way to cut down on the worst-case complexity of single operations?

using System;

/// <summary>
/// A UnionFindNode represents a set of nodes that it is a member of.
/// 
/// You can get the unique representative node of the set a given node is in by using the Find method.
/// Two nodes are in the same set when their Find methods return the same representative.
/// The IsUnionedWith method will check if two nodes' sets are the same (i.e. the nodes have the same representative).
///
/// You can merge the sets two nodes are in by using the Union operation.
/// There is no way to split sets after they have been merged.
/// </summary>
public class UnionFindNode {
    private UnionFindNode _parent;
    private uint _rank;

    /// <summary>
    /// Creates a new disjoint node, representative of a set containing only the new node.
    /// </summary>
    public UnionFindNode() {
        _parent = this;
    }

    /// <summary>
    /// Returns the current representative of the set this node is in.
    /// Note that the representative is only accurate untl the next Union operation.
    /// </summary>
    public UnionFindNode Find() {
        if (!ReferenceEquals(_parent, this)) _parent = _parent.Find();
        return _parent;
    }

    /// <summary>
    /// Determines whether or not this node and the other node are in the same set.
    /// </summary>
    public bool IsUnionedWith(UnionFindNode other) {
        if (other == null) throw new ArgumentNullException("other");
        return ReferenceEquals(Find(), other.Find());
    }

    /// <summary>
    /// Merges the sets represented by this node and the other node into a single set.
    /// Returns whether or not the nodes were disjoint before the union operation (i.e. if the operation had an effect).
    /// </summary>
    /// <returns>True when the union had an effect, false when the nodes were already in the same set.</returns>
    public bool Union(UnionFindNode other) {
        if (other == null) throw new ArgumentNullException("other");
        var root1 = this.Find();
        var root2 = other.Find();
        if (ReferenceEquals(root1, root2)) return false;

        if (root1._rank < root2._rank) {
            root1._parent = root2;
        } else if (root1._rank > root2._rank) {
            root2._parent = root1;
        } else {
            root2._parent = root1;
            root1._rank++;
        }
        return true;
    }
}
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$
  1. If I read the wikipedia article correctly then the algorithm should have amortized constant cost - and you have implemented it pretty much 1:1. Given that with your implementation you always start with disjoint nodes and any call to any of the public methods ends up calling Find which will automatically flatten the tree I doubt you can get much better.

  2. UnionFindNode is not a particularly good name for the data structure: intermingles operations with the data structure in the name. Just Node or maybe DisjointSetNode would be better.

  3. You could use == or != instead of ReferenceEquals which would make the code a bit easier to read.

  4. Consider making your node class generic and add a T value property - right now your nodes are not all that useful as they don't hold any data.

\$\endgroup\$
5
  • \$\begingroup\$ Considering that the data structure is commonly called the Union-Find data structure, I think the class name is OK. \$\endgroup\$ Feb 23, 2014 at 7:24
  • \$\begingroup\$ For #4: The idea I had in mind is to put the node inside the target class, to hide implementation details, instead of putting the target inside the node. Because you can't explore the set, given a node, it's not very useful to put the value there. \$\endgroup\$ Feb 23, 2014 at 7:26
  • \$\begingroup\$ @Strilanc: Well, with a little bit more effort and some memory you can explore the set without changing the basic properties of the algorithm. \$\endgroup\$
    – ChrisWue
    Feb 24, 2014 at 6:45
  • \$\begingroup\$ @200_success: Hm, fair enough, I guess in this case the kind of structure and the operations you perform on it are very closely related. \$\endgroup\$
    – ChrisWue
    Feb 24, 2014 at 6:45
  • \$\begingroup\$ Do you think, that the fact that Find method is recursive may be a problem (stack overflow) with deep trees? \$\endgroup\$ Dec 14, 2015 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.