Kruskal reconstruction trees: answer route bottlenecks through merge ancestors

A Kruskal reconstruction tree turns sorted undirected road insertions into a hierarchy of component merges. Original depots are leaves. Whenever an edge joins two previously separate components, a new internal node becomes the parent of their current component-tree roots and carries that edge weight. The least common ancestor of two depot leaves records the smallest threshold at which the depots become connected; equivalently, it is the minimum possible maximum road weight along a path between them. The model builds binary-lifting ancestors for static queries. Repeated edge weights are ordered reproducibly by endpoints. Self-loops and edges that join an already connected component add no merge node. Weights must be nonnegative, and a depot queried against itself has the documented bottleneck value zero.

Operational case

Road weights 19 between depots 0 and 1, 47 between 1 and 2, 29 between 0 and 2, 61 between 2 and 3, and 83 between 3 and 4 make the bottleneck from 0 to 2 equal 29: the direct edge improves on the two-edge route whose largest weight is 47. From 0 to 4 the answer is 83. Depot 5 stays disconnected, so its query against 0 returns no value. A merge node's numeric ID is incidental. A new road can change the merge hierarchy; this is a frozen graph index and should not answer from an obsolete tree after edge updates.

Working Python program

class BottleneckRouteTree:
    def __init__(self, depot_count, roads):
        if depot_count < 0:
            raise ValueError("negative depot count")
        self.depot_count = depot_count
        dsu_parent = list(range(depot_count))
        dsu_size = [1] * depot_count
        tree_root = list(range(depot_count))
        self.weight = [None] * depot_count
        self.parent = [-1] * depot_count
        children = [[] for _ in range(depot_count)]

        def find(vertex):
            while dsu_parent[vertex] != vertex:
                dsu_parent[vertex] = dsu_parent[dsu_parent[vertex]]
                vertex = dsu_parent[vertex]
            return vertex

        for weight, source, target in sorted(roads):
            if not (0 <= source < depot_count and 0 <= target < depot_count) or weight < 0:
                raise ValueError("roads need known vertices and nonnegative weights")
            first, second = find(source), find(target)
            if first == second:
                continue
            merge_node = len(self.weight)
            self.weight.append(weight)
            self.parent.append(-1)
            children.append([tree_root[first], tree_root[second]])
            self.parent[tree_root[first]] = merge_node
            self.parent[tree_root[second]] = merge_node
            if dsu_size[first] < dsu_size[second]:
                first, second = second, first
            dsu_parent[second] = first
            dsu_size[first] += dsu_size[second]
            tree_root[first] = merge_node
        self.component = [find(vertex) for vertex in range(depot_count)]
        node_count = len(self.weight)
        self.depth = [0] * node_count
        roots = [node for node, parent in enumerate(self.parent) if parent == -1]
        for root in roots:
            pending = [root]
            while pending:
                node = pending.pop()
                for child in children[node]:
                    self.depth[child] = self.depth[node] + 1
                    pending.append(child)
        levels = max(1, node_count.bit_length())
        self.up = [self.parent[:]]
        for _ in range(1, levels):
            previous = self.up[-1]
            self.up.append([-1 if ancestor == -1 else previous[ancestor] for ancestor in previous])

    def bottleneck(self, source, target):
        if not (0 <= source < self.depot_count and 0 <= target < self.depot_count):
            raise IndexError("unknown depot")
        if source == target:
            return 0
        if self.component[source] != self.component[target]:
            return None
        if self.depth[source] < self.depth[target]:
            source, target = target, source
        difference = self.depth[source] - self.depth[target]
        for level in range(len(self.up)):
            if difference & (1 << level):
                source = self.up[level][source]
        if source != target:
            for level in range(len(self.up) - 1, -1, -1):
                if self.up[level][source] != self.up[level][target]:
                    source = self.up[level][source]
                    target = self.up[level][target]
            source = self.parent[source]
        return self.weight[source]


route_tree = BottleneckRouteTree(6, [(19, 0, 1), (47, 1, 2), (29, 0, 2), (61, 2, 3), (83, 3, 4)])
print("zero to two:", route_tree.bottleneck(0, 2))
print("zero to four:", route_tree.bottleneck(0, 4))
print("zero to five:", route_tree.bottleneck(0, 5))

Output

zero to two: 29
zero to four: 83
zero to five: None

Time, space, and tradeoff

Sorting E roads costs O(E log E). Successful DSU unions create at most V minus one internal nodes, and binary-lifting tables over fewer than 2V nodes require O(V log V) build space and time. Each bottleneck query lifts two leaves toward their common ancestor in O(log V) time, after an O(1) component check. The constructor keeps a sorted copy of the roads, so working space also includes O(E). A single Dijkstra-style minimax search avoids the index build for a few queries. The reconstruction tree pays for many queries against the same unchanged weighted graph.

Common Mistakes

Do not use the sum of road weights when the query asks for a path maximum.
Do not create a merge node for an edge inside an existing component.
Do not answer disconnected pairs with a numeric threshold.
Do not reuse a static ancestor table after road edits.

Connected lessons

Compare this operation boundary with Moveable disjoint sets: transfer one shipment without splitting its old tree, Block-cut indexes: separate articulation depots from cyclic road blocks, Zero-suppressed diagrams: share sparse dispatch set families, then complete the structure audit and decision quiz.