Bridge Edges

Enumerate every edge whose removal increases the number of connected components

Category: topology

Syntax

SELECT * FROM graph_bridges(table_name)

Description

A bridge (also called a cut edge or isthmus) is an edge whose removal increases the number of connected components in the graph. Bridges identify single-points-of-failure: a cable, link, road, or relationship whose loss disconnects two regions of the network that previously had no alternative route between them. Use this function for network reliability analysis, infrastructure vulnerability assessment, finding articulation edges in social or biological networks, and validating that a designed network has no critical fragility before deployment. The function loads edge data from a registered Delta table into a Compressed Sparse Row (CSR) representation and runs Tarjan's bridge-finding algorithm: a single depth-first traversal that records each vertex's discovery time and low-link value (the smallest discovery time reachable from the vertex's subtree via at most one back edge). An edge (parent, child) is a bridge if and only if `low[child] > disc[parent]`, meaning the child's subtree contains no back edge that reaches at or above the parent in the DFS tree. The implementation uses an explicit stack to avoid recursion-depth limits on long chains. Multi-edges and self-loops are handled correctly: only the first parent-edge copy is treated as the tree edge, so parallel copies act as back edges that disqualify the bridge predicate, and self-loops never participate. Total cost is O(V + E). The result is the set of bridges of the undirected projection of the input. The implementation matches Neo4j GDS `gds.bridges` semantics, which operates exclusively on UNDIRECTED projections. For directed input, the algorithm walks the union of forward and reverse neighbour lists at each vertex, so an edge that is one-way in the source table contributes to the bridge predicate as though it were two-way; if every truly-directional notion of cut edges is required, build a different predicate over the strongly connected components instead. GPU acceleration is not wired through the SQL surface of this function. The GPU implementation that exists in the engine runs Tarjan's algorithm in a single workgroup with a single active thread, because the low-link relation depends on the strict DFS post-order in which a child's low value propagates back to its parent. A truly parallel approach (Tarjan-Vishkin Euler-tour reduction) would double the working-set size and add two list-ranking passes, which on real graphs is slower than the linear-time CPU traversal at every reasonable scale. The SQL `graph_bridges` table function therefore executes CPU-only. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology so repeated calls do not reload the edge table.

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, if present, are ignored: bridge detection is a structural property of the graph. For directed input the algorithm operates on the undirected symmetrisation of the edge set; the returned bridges are the bridges of the undirected projection.

Examples

CREATE TABLE network AS
SELECT * FROM VALUES
  (1, 2), (2, 3), (1, 3),
  (3, 4),
  (4, 5), (5, 6), (4, 6),
  (6, 7),
  (7, 8), (8, 9), (7, 9)
AS t(src, dst);

SELECT source_node_id, target_node_id
FROM graph_bridges('network')
ORDER BY source_node_id, target_node_id;

SELECT COUNT(*) AS bridge_count
FROM graph_bridges('network');

SELECT DISTINCT node_id
FROM (
  SELECT source_node_id AS node_id FROM graph_bridges('network')
  UNION ALL
  SELECT target_node_id AS node_id FROM graph_bridges('network')
)
ORDER BY node_id;

WITH all_edges AS (SELECT COUNT(*) AS n FROM network),
     bridge_edges AS (SELECT COUNT(*) AS n FROM graph_bridges('network'))
SELECT
  all_edges.n AS total_edges,
  bridge_edges.n AS bridges,
  1.0 - (CAST(bridge_edges.n AS DOUBLE) / all_edges.n) AS redundancy_ratio
FROM all_edges, bridge_edges;

WITH bridge_endpoints AS (
  SELECT source_node_id AS node_id FROM graph_bridges('network')
  UNION
  SELECT target_node_id AS node_id FROM graph_bridges('network')
)
SELECT ap.node_id
FROM graph_articulationpoints('network') ap
JOIN bridge_endpoints be ON ap.node_id = be.node_id
ORDER BY ap.node_id;

Pitfalls

Bridges are computed on the undirected projection of the input, not on the directed graph. For directed input the algorithm walks both outgoing and incoming neighbours at each vertex, so the result is the bridge set of the symmetrised view. A directed-only notion of cut edges does not exist for Tarjan-shaped bridge finding; if direction must be honoured, decompose the graph with graph_scc and inspect inter-component edges instead.
Edge weights are ignored. A bridge that carries 1 unit of traffic and a bridge that carries 1 million units are returned identically; the function reports structural cut edges only. If a weighted criticality score is required, join the result back to the input table and aggregate the weight per bridge.
Output is canonicalised to (min, max) endpoint order, so each bridge appears exactly once even when the input table contains both (a, b) and (b, a) rows or a CSR doubled-edge representation. Downstream JOINs must account for this: matching a bridge against the original edge table requires comparing both orientations.
An empty result set means the graph has no bridges, not that the function failed. Highly connected graphs (any 2-edge-connected component, including a single triangle) have zero bridges; this is a valid and informative answer, not an error.
Self-loops are filtered and never appear in the result regardless of how they are encoded in the source table. Multi-edges are handled correctly: a pair of parallel edges between the same two vertices is never reported as a bridge, because removing one copy still leaves the other.
GPU acceleration is not exposed through the table function. The ON GPU hint is silently ignored. Even at the Cypher CALL surface the GPU dispatch is single-threaded by design because Tarjan low-link cannot be usefully parallelised; the CPU implementation is the canonical fast path.