Potential disjoint sets: preserve numeric differences across merges

Operational case

Depot zero is 47 units below depot one, while depot two is 19 units below depot one. The derived difference from zero to two is 28. A new constraint claiming 29 is rejected. The service can still answer the earlier difference 28 afterward. A disconnected depot returns None rather than a made-up zero; zero is a valid known difference for two equal-level depots. If path compression copied a parent link without accumulating its previous offset, a later query might return the wrong sign even though basic connectivity still looks correct. Randomized checks compare each response with a small explicit graph of accepted equations.

Working Python program

class DepotOffsetConstraints:
    def __init__(self, count):
        self.parent = list(range(count))
        self.size = [1] * count
        self.offset = [0] * count  # value[node] - value[parent]

    def find(self, depot):
        if self.parent[depot] == depot:
            return depot, 0
        previous = self.parent[depot]
        root, parent_offset = self.find(previous)
        self.offset[depot] += parent_offset
        self.parent[depot] = root
        return root, self.offset[depot]

    def constrain(self, first, second, difference):
        """Require value[second] - value[first] == difference."""
        first_root, first_offset = self.find(first)
        second_root, second_offset = self.find(second)
        if first_root == second_root:
            return second_offset - first_offset == difference
        if self.size[first_root] >= self.size[second_root]:
            self.parent[second_root] = first_root
            self.offset[second_root] = difference + first_offset - second_offset
            self.size[first_root] += self.size[second_root]
        else:
            self.parent[first_root] = second_root
            self.offset[first_root] = second_offset - first_offset - difference
            self.size[second_root] += self.size[first_root]
        return True

    def difference(self, first, second):
        first_root, first_offset = self.find(first)
        second_root, second_offset = self.find(second)
        return None if first_root != second_root else second_offset - first_offset


network = DepotOffsetConstraints(5)
print(network.constrain(0, 1, 47), network.constrain(1, 2, -19))
print(network.difference(0, 2), network.constrain(0, 2, 29))

Output

True True
28 False

Time, space, and tradeoff

With union by size and path compression, each accepted merge or difference query takes inverse-Ackermann amortized time over a sequence of operations, often treated as nearly constant; it stores O(N) parents, sizes, and offsets. The caveat is important: this version cannot remove a constraint or roll back a compression. It also assumes exact integer differences, so it does not model floating measurement tolerance or overflow in fixed-width integer languages. Rejected constraints can still compress paths but do not change the represented differences. For a system that needs to explain which earlier equations caused a contradiction, maintain a separate provenance graph or use an offline algorithm.

Common Mistakes

• Do not attach a root without solving the offset sign.
• Do not return zero for two disconnected depots.
• Do not forget to add the old parent offset during path compression.
• Do not treat a rejected contradiction as an accepted edge.

Connected lessons

• Graphs
• Data Structures
• Disjoint sets: merge connectivity without tracing every path
• Parity disjoint set: maintain same-or-different constraints
• Disjoint-set rollback: restore an earlier connectivity checkpoint
• Projects
• Quizzes

Compare its update and query contract with Eytzinger arrays: store a search tree in breadth-first order, Cartesian trees: preserve sequence order under a heap minimum, Leftist heaps: keep the right spine short for meld, then complete the structure audit and decision quiz.