Block-cut indexes: separate articulation depots from cyclic road blocks

A block-cut index exposes how an undirected network separates when one vertex is removed. Depth-first discovery times and low values identify edges that belong to the same vertex-biconnected block. An edge stack collects a block whenever a child cannot reach an ancestor of its parent; the parent is an articulation vertex when that separation disconnects remaining vertices. The root has the special rule of needing more than one DFS child. This model accepts a simple undirected graph: self-loops and parallel roads are rejected, while isolated depots receive singleton blocks. Blocks are sets of vertex IDs, and an articulation depot appears in more than one block. The stored incidence list links articulation IDs to block numbers, producing the two node types of a block-cut forest.

Operational case

Roads connect a triangle among depots 0, 1, and 2, a bridge from 2 to 3, another triangle among 3, 4, and 5, and a bridge from 5 to 6. Depot 7 is isolated. The resulting blocks are [0,1,2], [2,3], [3,4,5], [5,6], and [7]; the cut depots are 2, 3, and 5. Depot 5 belongs to the triangle block and the last bridge block. A bridge is a two-vertex block in this representation. The block's numeric position is a build artifact, not a durable road ID. Adding or removing a road can change both the blocks and articulation set, so the static index must be rebuilt.

Working Python program

class DepotBlockCutIndex:
    def __init__(self, vertex_count, roads):
        if vertex_count < 0:
            raise ValueError("negative vertex count")
        self.vertex_count = vertex_count
        adjacency = [[] for _ in range(vertex_count)]
        seen = set()
        for source, target in roads:
            if not (0 <= source < vertex_count and 0 <= target < vertex_count) or source == target:
                raise ValueError("road endpoints must be distinct known vertices")
            edge = (min(source, target), max(source, target))
            if edge in seen:
                raise ValueError("parallel roads are outside this simple-graph model")
            seen.add(edge)
            adjacency[source].append(target)
            adjacency[target].append(source)
        for neighbors in adjacency:
            neighbors.sort()
        discovery = [-1] * vertex_count
        low = [0] * vertex_count
        edge_stack = []
        blocks = []
        articulations = set()
        clock = 0

        def walk(vertex, parent):
            nonlocal clock
            discovery[vertex] = low[vertex] = clock
            clock += 1
            child_count = 0
            for neighbor in adjacency[vertex]:
                if discovery[neighbor] == -1:
                    child_count += 1
                    edge_stack.append((vertex, neighbor))
                    walk(neighbor, vertex)
                    low[vertex] = min(low[vertex], low[neighbor])
                    if low[neighbor] >= discovery[vertex]:
                        if parent != -1 or child_count > 1:
                            articulations.add(vertex)
                        block = set()
                        while edge_stack:
                            edge_source, edge_target = edge_stack.pop()
                            block.update((edge_source, edge_target))
                            if (edge_source, edge_target) == (vertex, neighbor):
                                break
                        blocks.append(frozenset(block))
                elif neighbor != parent and discovery[neighbor] < discovery[vertex]:
                    low[vertex] = min(low[vertex], discovery[neighbor])
                    edge_stack.append((vertex, neighbor))

        for start in range(vertex_count):
            if discovery[start] == -1:
                walk(start, -1)
                if not adjacency[start]:
                    blocks.append(frozenset((start,)))
        self.blocks = sorted(blocks, key=lambda block: (min(block), len(block), sorted(block)))
        self.articulations = articulations
        self.block_neighbors = {
            articulation: [index for index, block in enumerate(self.blocks) if articulation in block]
            for articulation in sorted(articulations)
        }

    def blocks_for(self, vertex):
        if not 0 <= vertex < self.vertex_count:
            raise IndexError(vertex)
        return [index for index, block in enumerate(self.blocks) if vertex in block]


depot_index = DepotBlockCutIndex(
    8, [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6)]
)
print("blocks:", [sorted(block) for block in depot_index.blocks])
print("cut depots:", sorted(depot_index.articulations))
print("depot five blocks:", depot_index.blocks_for(5))

Output

blocks: [[0, 1, 2], [2, 3], [3, 4, 5], [5, 6], [7]]
cut depots: [2, 3, 5]
depot five blocks: [2, 3]

Time, space, and tradeoff

The DFS and edge-stack decomposition scan O(V+E) vertices and roads and store O(V+E) graph and stack state. This Python implementation also sorts adjacency lists and output blocks for repeatable display and scans blocks to produce articulation incidence lists, so its total postprocessing can exceed the linear decomposition bound. Recursive DFS uses O(V) call depth and may hit Python's recursion limit on a long path. No online road update is supported. A strongly connected component index solves directed mutual reachability; block-cut decomposition instead describes failure at a single vertex in an undirected graph.

Common Mistakes

Do not use the non-root articulation rule for the DFS root.
Do not treat a bridge as though it belongs to a cycle block.
Do not conflate directed strongly connected groups with undirected blocks.
Do not keep old block numbers after editing roads.

Connected lessons

Compare this operation boundary with Moveable disjoint sets: transfer one shipment without splitting its old tree, 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.