HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Implementation of disjoint set in Java with linked-list

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
withjavadisjointimplementationlistlinkedset

Problem

I have just wrote a linked list implementation of disjoint sets in Java for the Rainfall Problem. Can you take a look and tell me if there is something missing and also make a judgement in performance?

public class DisJointSet
{
    int rank;
    DNode head;
    DNode tail;

    public DisJointSet(E data)
    {
        DNode node = new DNode<>(data);
        head = node;
        tail = node;
        rank = 1;
        node.represantive = this;
    }

    public void union(DNode x, DNode y)
    {

        DisJointSet xSet = findSet(x);
        DisJointSet ySet = findSet(y);
        if (xSet.rank>= ySet.rank)
            append(xSet, ySet);
        else
            append(ySet, xSet);
    }

    public void append(DisJointSet first, DisJointSet second)
    {

        if (first.rank == 0 || second.rank == 0)
            throw new IllegalArgumentException();

        // Set the representative of each node in the second set to be
        // the first set.
        DNode curr = second.head;

        while(curr!=null)
        {
            curr.represantive = first;
            curr = curr.next;
        }

        first.tail.next = second.head;
        first.tail = second.tail;
        first.rank += second.rank;

        // Invalidate the second set, just to be sure.
        second.head = null;
        second.tail = null;
        second.rank = 0;
    }

    public DisJointSet findSet (DNode x)
    {
        return x.represantive;
    }
}

class DNode
{
    DNode next;
    DisJointSet represantive;
    E data;

    DNode(E val)
    {
        data = val;
    }
}

Solution

Nitpicks

  • Disjoint is a single word, your class should be named DisjointSet



  • The correct spelling for the "sink" is representative



Formatting and Style

  • It's generally recommended to always put braces around blocks in if-else constructs. Yes, even when they only throw an Exception.



  • Binary operators usually have a space on each side. (applies curr != null and xSet.rank >= ySet.rank)



OOP vs. Functional-Style

Your way of writing OOP is... strange. union, append and findSet are defined as instance methods, meaning they need to be called on a certain instance of DisjointSet, but they don't actually use the instance at all.

Overall these could all be completely extracted into a static utility class, and nothing much would change. I strongly advise you to actually do exactly that. It should clarify responsibilities and make the code clearer to follow.

Alternatively you could make these functions actually start working in an OOP way. If you do that I'd furthermore suggest to make DisjointSet something like an immutable class (see String or Path) that will create a new instance when you union or append another Set to it. In fact I recommend you do that, even when you don't rewrite the code into a more OOP fashion.

Additionally your DNode's data could (and should) be declared final to avoid modification.

Context

StackExchange Code Review Q#119771, answer score: 2

Revisions (0)

No revisions yet.