Moveable disjoint sets: transfer one shipment without splitting its old tree

Last updated: 4 Oct 20269 min read

tutorial

Ordinary disjoint-set union can merge groups but cannot detach one member from a compressed parent tree. A moveable variant separates a logical shipment ID from the current DSU node representing it. On a move, the old group's active size and ID sum fall by one member; a fresh node is attached to the destination root and the shipment-to-node map changes. The former node remains as a ghost so other paths through it stay valid. Merge still uses union by active size and find still compresses paths. This example tracks group size and the sum of zero-based shipment IDs, not parcel weights. A move inside the same group is a no-op. Ghost nodes are never reclaimed, which is an explicit memory cost rather than a hidden deletion mechanism.

Operational case

Merge shipments 1, 3, and 5 into one group and shipments 2 and 4 into another. Their size and ID-sum pairs are (3,9) and (2,6). Moving shipment 3 to shipment 4's group leaves the old group at (2,6) and the destination at (3,9); shipment 1 is no longer grouped with 3. Reassigning parent[3] directly would be unsafe because other DSU paths might pass through that node. Moving an ID that currently names a root has the same fresh-node rule. A group can retain an old root with zero active members, but no current shipment maps to that empty group.

Working Python program

class MoveableWarehouseGroups:
    def __init__(self, shipment_count):
        if shipment_count < 0:
            raise ValueError("negative shipment count")
        self.shipment_count = shipment_count
        self.node_for = list(range(shipment_count))
        self.parent = list(range(shipment_count))
        self.size = [1] * shipment_count
        self.total = list(range(shipment_count))

    def _check(self, shipment):
        if not 0 <= shipment < self.shipment_count:
            raise IndexError(shipment)

    def _root(self, node):
        while self.parent[node] != node:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node

    def group(self, shipment):
        self._check(shipment)
        root = self._root(self.node_for[shipment])
        return self.size[root], self.total[root]

    def together(self, first, second):
        self._check(first)
        self._check(second)
        return self._root(self.node_for[first]) == self._root(self.node_for[second])

    def merge(self, first, second):
        self._check(first)
        self._check(second)
        first_root = self._root(self.node_for[first])
        second_root = self._root(self.node_for[second])
        if first_root == second_root:
            return False
        if self.size[first_root] < self.size[second_root]:
            first_root, second_root = second_root, first_root
        self.parent[second_root] = first_root
        self.size[first_root] += self.size[second_root]
        self.total[first_root] += self.total[second_root]
        return True

    def move(self, shipment, destination):
        self._check(shipment)
        self._check(destination)
        old_root = self._root(self.node_for[shipment])
        target_root = self._root(self.node_for[destination])
        if old_root == target_root:
            return False
        self.size[old_root] -= 1
        self.total[old_root] -= shipment
        new_node = len(self.parent)
        self.parent.append(target_root)
        self.size.append(1)
        self.total.append(shipment)
        self.node_for[shipment] = new_node
        self.size[target_root] += 1
        self.total[target_root] += shipment
        return True


warehouse_groups = MoveableWarehouseGroups(7)
warehouse_groups.merge(1, 3)
warehouse_groups.merge(3, 5)
warehouse_groups.merge(2, 4)
print("before move:", warehouse_groups.group(1), warehouse_groups.group(2))
warehouse_groups.move(3, 4)
print("after move:", warehouse_groups.group(1), warehouse_groups.group(2))
print("old link:", warehouse_groups.together(1, 3))

Output

before move: (3, 9) (2, 6)
after move: (2, 6) (3, 9)
old link: False

Time, space, and tradeoff

For N initial shipments and M successful moves, storage is O(N+M) nodes because each transfer allocates one new node. With union by active size and path compression, find-based operations have inverse-Ackermann amortized behavior in the expanded node forest; each public merge, move, membership test, or group summary performs a constant number of finds plus O(1) bookkeeping. This is not a persistent snapshot and does not support undo. A rollback DSU offers checkpoint reversal under a different update discipline, while this structure permits individual member transfers without reconstructing whole components.

Common Mistakes

Do not reparent an existing DSU node to move its logical member.
Do not forget to update both active group size and ID sum.
Do not count abandoned ghost nodes as active shipments.
Do not promise that memory stays O(N) after many moves.

Connected lessons

Compare this operation boundary with Block-cut indexes: separate articulation depots from cyclic road blocks, Kruskal reconstruction trees: answer route bottlenecks through merge ancestors, Zero-suppressed diagrams: share sparse dispatch set families, then complete the structure audit and decision quiz.

data structures

graphs-and-disjoint-sets