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.
Quickstart
The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight. Substitute your own registered relations.
SELECT * FROM cugraph_strongly_connected_components(edges => (SELECT src, dst FROM target_edges));
Inputs
Every relation is a named parenthesized SELECT subquery. The required edges role uses canonical src and dst columns; every role, its canonical columns, and their accepted Arrow types are listed under Relation arguments. Metadata validation resolves registered tables named in its JSON request.
Endpoint columns accept numeric Int32, Int64 vertex IDs or logical string Utf8, LargeUtf8, Utf8View vertex IDs; string vertex-identity outputs are canonicalized to Utf8 (native mapping Int64) while scores, distances, counts, coordinates, and opaque labels stay numeric. The shared vertex-ID contract is summarized in Vertex ID support; the concrete call-specific schema comes 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
Arguments and options
Relation arguments
| Argument | Required | Columns | Description |
|---|---|---|---|
edges | yes |
| edge relation with canonical src and dst columns, plus optional weight and edge_id columns |
Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.
Named value arguments
This function has no algorithm-specific value arguments. Its inputs are the relation arguments above and the graph construction options below.
Graph construction options
Graph construction follows the shared defaults (directed=true, renumbering, python_cugraph policy) documented in Graph Construction Options.
Output
| 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: the minimum vertex id in the component, stable across runs. |
These are generic descriptor schemas; run gpu_validate_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 OR REPLACE TABLE scc_snapshot AS
SELECT vertex, label
FROM cugraph_strongly_connected_components(
edges => (SELECT src, dst FROM citation_edges), 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.
Limits
No algorithm-specific limitations.
To dry-run validate relation metadata, column types, and options without execution, see gpu_validate_call.