Articulation Points (Cut Vertices)

Identify vertices whose removal disconnects a connected component of the graph

Category: topology

Syntax

SELECT * FROM graph_articulationpoints(table_name)

Description

Articulation points are vertices whose removal increases the number of connected components in the graph. They are the nodes through which traffic must pass to keep the surrounding network in one piece, so they are the canonical signal for single points of failure in supply chains, power grids, social ego networks, transit topologies, and any infrastructure modelled as a graph. Bridges identify the same fragility at the edge level; articulation points identify it at the vertex level. The function loads edge data from a registered Delta table into a Compressed Sparse Row (CSR) representation and runs an iterative Tarjan low-link DFS. Each vertex receives a discovery timestamp `disc[v]` and a low-link value `low[v]` equal to the minimum discovery time reachable from `v` through its DFS subtree using at most one back edge. A non-root vertex `v` is an articulation point if it has a DFS-tree child `u` with `low[u] >= disc[v]`. The DFS root is an articulation point if it has two or more DFS-tree children. Column names for source and target are auto-detected from standard conventions (src/source/src_id, dst/target/dst_id). The time complexity is O(V + E), linear in the graph size, with O(V) auxiliary memory for the discovery, low-link, visited, and is-articulation arrays plus an explicit stack used in place of recursion. The implementation walks every component independently from each unvisited start node in one outer loop, so disconnected graphs are handled in a single pass. GPU acceleration is intentionally not provided. The articulation-point predicate `low[u] >= disc[v]` is defined only on the DFS spanning tree's finish order, and no level-synchronous frontier expansion (the only shape WGSL can express efficiently) preserves that order. The GPU port of Tarjan's algorithm therefore runs in a single workgroup with a single active thread and consistently loses to the CPU walk on every measured graph, so the dispatch table never routes articulation points to the GPU. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology, so repeated invocations skip the graph build.

Parameters

Name	Type	Description
`table_name`		Specify the name of the registered Delta table containing edge data. The table must include source and target columns (auto-detected as src/source/src_id and dst/target/dst_id). Edge weights are loaded if present but are ignored: articulation points are a purely structural property. The graph is analysed as undirected for the purpose of the cut-vertex predicate, even when the source table encodes directed edges.

Examples

CREATE TABLE bridge_demo AS
SELECT * FROM VALUES
  (1, 2, 1.0),
  (2, 3, 1.0),
  (3, 4, 1.0),
  (4, 5, 1.0),
  (5, 3, 1.0)
AS t(src, dst, weight);

SELECT node_id FROM graph_articulationpoints('bridge_demo') ORDER BY node_id;

SELECT COUNT(*) AS cut_vertex_count FROM graph_articulationpoints('bridge_demo');

SELECT e.src, e.dst, e.weight
FROM bridge_demo e
JOIN graph_articulationpoints('bridge_demo') ap
  ON e.src = ap.node_id OR e.dst = ap.node_id
ORDER BY e.src, e.dst;

SELECT ap.node_id, d.degree
FROM graph_articulationpoints('bridge_demo') ap
JOIN graph_degree('bridge_demo') d
  ON ap.node_id = d.node_id
ORDER BY d.degree DESC;

SELECT DISTINCT ap.node_id
FROM graph_articulationpoints('bridge_demo') ap
JOIN graph_bridges('bridge_demo') br
  ON ap.node_id = br.source_node_id OR ap.node_id = br.target_node_id
ORDER BY ap.node_id;

Pitfalls

Articulation points are defined on the undirected projection of the graph, exactly like bridges. If the source table encodes directed edges, the algorithm symmetrises them (combining forward and reverse adjacency) before running the DFS. Vertices that look like cut points in the directed sense (e.g. the only path of in-edges to a sink) will not appear unless they also cut the undirected projection. Use graph_scc to reason about directed reachability.
Articulation points are a structural property; edge weights play no role. Filtering the source table by weight before invocation is the only way to scope the analysis to a subgraph (for example, a minimum spanning subset or a thresholded similarity graph). The function itself accepts no predicate arguments.
Isolated nodes and degree-1 leaves are never articulation points. Removing a leaf cannot disconnect the rest of the network, and an isolated vertex has no incident edges to cut. If your downstream join expects every input vertex to appear in the result, left-join against the node universe explicitly.
The DFS root receives a special rule: it is an articulation point if and only if it has two or more children in the DFS spanning tree. The choice of root depends on graph loading order, but the set of articulation points is invariant under that choice; only the internal `(disc, low)` numbering changes. Do not interpret the order of returned rows as a centrality ranking.
There is no GPU path. Adding `ON GPU` (or any execution hint that forces GPU) on a query that joins against graph_articulationpoints does not accelerate the articulation-point scan itself; the engine evaluates the function on the CPU regardless and then ships the result into the GPU pipeline for the rest of the plan. Plan accordingly when budgeting latency on very large graphs.