Strongly Connected Components

SQL function: cugraph_strongly_connected_components

Official cuGraph reference: C API

Label maximal directed subgraphs in which every vertex is reachable from every other vertex.

Signature

cugraph_strongly_connected_components(table_name [, src_col, dst_col [, weight_col [, options_json]]])

Relation inputs

The first positional argument names a registered edge table or view (the edges role). Parenthesized relation subqueries are not accepted; metadata validation uses the same registered name.

Vertex ID types

The edges relation declares the accepted vertex-ID domains. Numeric calls preserve the existing numeric schema. When logical string support is declared, Utf8, LargeUtf8, and Utf8View endpoint columns share one logical domain; their vertex-identity outputs are canonicalized to Utf8.

Domain	Accepted endpoint inputs	Output contract
Numeric edge endpoints	`Int32`, `Int64`	The numeric output schema is used for numeric calls.
Logical string edge endpoints	`Utf8`, `LargeUtf8`, `Utf8View`	Vertex identity columns are canonicalized to `Utf8`; scores, distances, counts, coordinates, and opaque labels remain numeric.

The native mapping type is Int64. Call-specific output schemas come from gpu_validate_call.

Logical string side-input limitations:

edge ID columns and edge-ID predicate side inputs are not supported for logical string graphs

Scalar arguments & JSON options

Positional scalar arguments

src_col and dst_col name the edge endpoint columns; both are optional and default to src and dst.

Argument	Type	Required	Default	Notes
`weight_col`	`Utf8\|null`	no		accepted as an edge-column binding; native algorithm execution does not consume weights; semantic effect: none for this algorithm

JSON options

This function has no algorithm-specific options.

Graph construction options

Graph construction follows the shared defaults (directed=true, renumbering, python_cugraph policy) documented in Graph Construction Options.

Output schema

Column	Type	Nullable	Description
`vertex`	`Int64\|Utf8`	no	Vertex assigned to a strongly connected component.
`label`	`Int64`	no	Strongly connected component identifier for the vertex.

These are generic descriptor schemas; validate the call to get the concrete, table-specific output schema.

Examples

These examples run on the citation network demo dataset.

Count multi-paper strongly connected components

A citation normally points from a newer paper to an older one, so a directed cycle of citations is an anomaly: two or more papers that cite each other directly or transitively. Such a group forms a strongly connected component of more than one vertex. SCC finds every component in one pass. Snapshot the run in the mutable datafusion.public workspace (labels are assigned per execution), then count the multi-paper components:

-- Local workspace snapshot; this does not write to lake.citation_network.
CREATE TABLE scc_snapshot AS
SELECT vertex, label
FROM cugraph_strongly_connected_components('citation_edges', 'src', 'dst', NULL,
                                           '{"directed":true}');

WITH loops AS (
  SELECT label, COUNT(*) AS members FROM scc_snapshot
  GROUP BY label HAVING COUNT(*) > 1)
SELECT COUNT(*) AS loops, MAX(members) AS biggest, SUM(members) AS papers_in_loops
FROM loops;

loops	biggest	papers_in_loops
14,613	1,370,029	1,404,311

The notable result is the largest component: 1.37M papers sit inside one strongly connected component. Preprint/journal duplicate versions, simultaneous publication, and metadata errors introduce enough forward-dated citations — a newer paper cited by an older one — to bind roughly a third of the graph into a single component. These apparent forward-in-time citations are a structural feature of bibliographic data.

Inspect the two-paper cycles

WITH pairs AS (
  SELECT label FROM scc_snapshot GROUP BY label HAVING COUNT(*) = 2)
SELECT c.label, p.year, p.title
FROM pairs x
JOIN scc_snapshot c ON c.label = x.label
JOIN papers p ON p.paper_id = c.vertex
ORDER BY c.label
LIMIT 6;

label	year	title
57	2017	Index Modulation Techniques for Next-Generation Wireless Networks
57	2017	Multidimensional index modulation in wireless communications
210	2017	A Survey of Research into Mixed Criticality Systems
210	2017	Probabilistic analysis for mixed criticality systems using fixed priority…
265	2018	DC programming and DCA: thirty years of developments
265	2018	Convergence Analysis of Difference-of-Convex Algorithm with Subanalytic Data

12,015 of the 14,613 cycles are exactly two papers — same-year companion papers and surveys citing each other, the typical form of mutual citation in practice.

Limitations & lifecycle

No algorithm-specific limitations.

Validate before running

Dry-run validation checks registered relation metadata, column presence, static dtypes, and options only; it does not scan edge data, construct a graph, or prove source-vertex existence:

SELECT * FROM gpu_validate_call(
  'cugraph_strongly_connected_components',
  '{"schema_version":1,"relations":{"edges":{"table":"target_edges"}},"options":{"src_col":"src","dst_col":"dst"}}'
);

See GPU Function Catalog API for the full gpu_validate_call contract.

Signature​

Relation inputs​

Vertex ID types​

Scalar arguments & JSON options​

Positional scalar arguments​

JSON options​

Graph construction options​

Output schema​

Examples​

Count multi-paper strongly connected components​

Inspect the two-paper cycles​

Limitations & lifecycle​

Validate before running​