BFS

SQL function: cugraph_bfs

Official cuGraph reference: C API

Visit reachable vertices in increasing unweighted hop distance from one or more sources, returning distances and optional predecessors.

Quickstart

The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight, and starts from source vertex 123. Substitute your own registered relations.

SELECT * FROM cugraph_bfs(edges => (SELECT src, dst FROM target_edges), source_vertex => 123, depth_limit => 4);

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
string logical vertex-domain BFS rejects edges.edge_id and edge-id predicate relations

Arguments and options

Relation arguments

Argument	Required	Columns	Description
`edges`	yes	`src`, `dst`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View` `weight` (optional): `Float32`, `Float64` `edge_id` (optional): `Int32`, `Int64`	edge relation with canonical src and dst columns, plus optional weight and edge_id columns
`sources`	no	`vertex`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View`	optional BFS source relation; exactly one of sources, source_vertex, and source_vertices is required
`include_vertices`	no	`vertex`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View`	vertices retained by BFS predicate filtering
`exclude_vertices`	no	`vertex`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View`	vertices removed by BFS predicate filtering
`target_vertices`	no	`vertex`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View`	BFS target vertices required for path output or target information
`include_edge_ids`	no	`edge_id`: `Int32`, `Int64`	edge identifiers retained by BFS predicate filtering
`include_edges`	no	`src`, `dst`: `Int32`, `Int64`, `Utf8`, `LargeUtf8`, `Utf8View` `edge_id` (optional): `Int32`, `Int64`	edge predicate relation with src, dst, and optional edge_id columns

Vertex columns of sources, include_vertices, exclude_vertices, target_vertices, include_edges must use the same vertex domain as edges: the integer type of src and dst, or any listed string type when the endpoints are strings. Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.

Named value arguments

Option	Type	Default	Constraints	Description
`depth_limit`	`integer\|null`	`null`	min 0; max 9223372036854776000	optional non-negative BFS depth limit
`output_mode`	`string`	`"raw"`	one of `"raw"`, `"normalized"`, `"path"`	BFS output shape
`return_target_info`	`boolean`	`false`		whether raw or normalized BFS output includes target information
`source_vertex`	`integer\|string`	No default		scalar source vertex; BFS source selectors are mutually exclusive
`source_vertices`	`array`	No default		non-empty homogeneous BFS source vertex array; mutually exclusive with source_vertex and sources

Graph construction options

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

Output

`raw` (default)

Column	Type	Nullable	Description
`vertex`	`Int64\|Utf8`	no	Vertex reached or considered by the BFS traversal.
`distance`	`Int64`	no	Hop-count distance from the nearest selected BFS source vertex.
`predecessor`	`Int64\|Utf8`	yes	Previous vertex on the discovered BFS tree, null for selected source vertices or unreachable vertices depending on output mode.

`normalized`

Column	Type	Nullable	Description
`vertex`	`Int64\|Utf8`	no	Vertex reached or considered by the BFS traversal.
`distance`	`Int64`	yes	Hop-count distance from the nearest selected BFS source vertex.
`predecessor`	`Int64\|Utf8`	yes	Previous vertex on the discovered BFS tree, null for selected source vertices or unreachable vertices depending on output mode.
`reachable`	`Boolean`	no	Whether the vertex is reachable under normalized BFS output.

`normalized_with_target_info`

Column	Type	Nullable	Description
`vertex`	`Int64\|Utf8`	no	Vertex reached or considered by the BFS traversal.
`distance`	`Int64`	yes	Hop-count distance from the nearest selected BFS source vertex.
`predecessor`	`Int64\|Utf8`	yes	Previous vertex on the discovered BFS tree, null for selected source vertices or unreachable vertices depending on output mode.
`reachable`	`Boolean`	no	Whether the vertex is reachable under normalized BFS output.
`target_found`	`Boolean`	no	Whether a requested target vertex was reached by the BFS traversal.
`target_distance`	`Int64`	yes	Hop-count distance to the requested target vertex, null when the target was not reached.

`path`

Column	Type	Nullable	Description
`path_index`	`Int64`	no	Zero-based row position in the reconstructed source-to-target path.
`source`	`Int64\|Utf8`	no	Source vertex for the reconstructed BFS path.
`target`	`Int64\|Utf8`	no	Target vertex for the reconstructed BFS path.
`vertex`	`Int64\|Utf8`	no	Vertex reached or considered by the BFS traversal.
`distance`	`Int64`	no	Hop-count distance from the nearest selected BFS source vertex.

`raw_with_target_info`

Column	Type	Nullable	Description
`vertex`	`Int64\|Utf8`	no	Vertex reached or considered by the BFS traversal.
`distance`	`Int64`	no	Hop-count distance from the nearest selected BFS source vertex.
`predecessor`	`Int64\|Utf8`	yes	Previous vertex on the discovered BFS tree, null for selected source vertices or unreachable vertices depending on output mode.
`target_found`	`Boolean`	no	Whether a requested target vertex was reached by the BFS traversal.
`target_distance`	`Int64`	yes	Hop-count distance to the requested target vertex, null when the target was not reached.

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. Edges point src → dst as "cites"; BFS distance is a hop count.

Reverse the traversal by projecting named edge columns

Following citations forward (src → dst) walks into a paper's reference ancestry. Projecting dst AS src, src AS dst into the named edges relation traverses the same edges in the opposite direction (from a paper to the papers that cite it, and then their citers) without building a new table. The sources relation resolves the start vertex from AlexNet's title and year, so no paper id appears in the query; each BFS generation is one hop outward in citing papers:

SELECT b.distance, COUNT(*) AS papers, ROUND(AVG(p.year), 1) AS avg_year
FROM cugraph_bfs(
  edges => (SELECT dst AS src, src AS dst FROM citation_edges_by_dst),
  sources => (SELECT paper_id AS vertex FROM papers
              WHERE title = 'ImageNet Classification with Deep Convolutional Neural Networks'
                AND year = 2012),
  depth_limit => 3, output_mode => 'normalized') b
JOIN papers p ON p.paper_id = b.vertex
WHERE b.reachable
GROUP BY b.distance
ORDER BY b.distance;

distance	papers	avg_year
0	1	2012.0
1	12,185	2017.5
2	67,517	2017.9
3	71,541	2017.8

Three citation generations reach ~151k papers. (The reversed traversal reads citation_edges_by_dst, which is clustered by dst, so the scan prunes well.)

Path mode with a SQL-defined target

output_mode: "path" reconstructs the shortest hop chain between the source and a target. Both endpoints are relations, so a WHERE clause on papers selects each one by title and year; target_vertices must resolve to exactly one row. This query traces the reference path from BERT (2018) back to LSTM (1997). The year predicate matters here: the corpus also holds a 2019 conference record titled identically to the BERT preprint.

SELECT b.path_index, b.distance, p.year, p.title
FROM cugraph_bfs(
  edges => (SELECT src, dst FROM citation_edges),
  sources => (SELECT paper_id AS vertex FROM papers
              WHERE title = 'BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding'
                AND year = 2018),
  output_mode => 'path',
  target_vertices => (SELECT paper_id AS vertex FROM papers
                      WHERE title = 'Long short-term memory' AND year = 1997)) b
JOIN papers p ON p.paper_id = b.vertex
ORDER BY b.path_index;

path_index	distance	year	title
0	0	2018	BERT: Pre-training of Deep Bidirectional Transformers…
1	1	2015	Semi-supervised Sequence Learning
2	2	1997	Long short-term memory

Two hops of references separate BERT from LSTM. Several two-hop chains exist, and path output returns one of them: other runs pass through SemEval-2017 Task 1 or Aligning Books and Movies instead.

Multi-source BFS from a seed view

Passing the named sources relation starts the traversal from every row of a SQL result. Here the three CNN classics (AlexNet, VGG, ResNet) form one combined frontier, so distance measures hops from the nearest of the three founding papers. Each title is paired with its year because the corpus also holds a 2015 preprint record of the ResNet paper under the same title:

CREATE OR REPLACE VIEW cnn_founders AS
SELECT paper_id AS vertex FROM papers
WHERE (title = 'ImageNet Classification with Deep Convolutional Neural Networks' AND year = 2012)
   OR (title = 'VERY DEEP CONVOLUTIONAL NETWORKS FOR LARGE-SCALE IMAGE RECOGNITION' AND year = 2014)
   OR (title = 'Deep Residual Learning for Image Recognition' AND year = 2016);

SELECT b.distance, COUNT(*) AS papers
FROM cugraph_bfs(
  edges => (SELECT dst AS src, src AS dst FROM citation_edges_by_dst),
  sources => (SELECT vertex FROM cnn_founders), depth_limit => 2,
  output_mode => 'normalized') b
JOIN papers p ON p.paper_id = b.vertex
WHERE b.reachable
GROUP BY b.distance
ORDER BY b.distance;

distance	papers
0	3
1	28,776
2	69,038

Title-keyed vertices on a small subgraph

Logical string endpoints let a graph use titles as vertex IDs, so results come back readable without a join to papers. That is sound only where each title names one paper, and the demo dataset repeats 193,894 titles, which is why the examples above keep paper_id as the vertex domain. On a small subgraph the trade-off can be measured first. The reference ancestry of Attention Is All You Need (the seed, its 22 references, and every paper those cite) spans 370 papers but only 358 distinct titles:

CREATE OR REPLACE VIEW attention_ancestry AS
WITH origins AS (
  SELECT paper_id FROM papers
  WHERE title = 'Attention is all you need' AND year = 2017
  UNION ALL
  SELECT e.dst FROM citation_edges e
  JOIN papers p ON p.paper_id = e.src
  WHERE p.title = 'Attention is all you need' AND p.year = 2017)
SELECT e.src, e.dst
FROM citation_edges e JOIN origins o ON o.paper_id = e.src;

SELECT COUNT(DISTINCT n.paper_id) AS papers, COUNT(DISTINCT p.title) AS titles
FROM (SELECT src AS paper_id FROM attention_ancestry
      UNION SELECT dst FROM attention_ancestry) n
JOIN papers p ON p.paper_id = n.paper_id;

papers	titles
370	358

The 12 missing titles each belong to two records, mostly a preprint and its proceedings version. Keying the edges by title merges every such pair into one vertex. For a reading list that merge is intended, since both records are one work; for unrelated papers that share a generic title it would corrupt the topology. Here BFS starts from a title literal, and vertex comes back as Utf8:

SELECT b.distance, b.vertex
FROM cugraph_bfs(
  edges => (SELECT ps.title AS src, pd.title AS dst
            FROM attention_ancestry a
            JOIN papers ps ON ps.paper_id = a.src
            JOIN papers pd ON pd.paper_id = a.dst),
  source_vertex => 'Attention is all you need', output_mode => 'normalized') b
WHERE b.distance <= 1
ORDER BY b.distance, b.vertex
LIMIT 6;

distance	vertex
0	Attention is all you need
1	A Decomposable Attention Model for Natural Language Inference
1	A Deep Reinforced Model for Abstractive Summarization
1	Adam: A Method for Stochastic Optimization
1	Deep Recurrent Models with Fast-Forward Connections for Neural Machine Translation
1	Deep Residual Learning for Image Recognition

All 358 titles are reachable: 22 at distance 1 and 335 at distance 2. String graphs reject edge_id columns and edge-ID predicate relations; see the Vertex ID support matrix.

Limits

source_vertices and the sources relation are multi-source BFS, not one BFS per source
source_vertices and the sources relation must contain at most one source per connected component
raw/normalized output does not expose origin source per vertex
string logical vertex-domain BFS rejects edges.edge_id and edge-id predicate relations
path output requires exactly one target row at execution time
descriptor option schema is typed registry metadata; validate_call remains the authoritative call-specific checker

To dry-run validate relation metadata, column types, and options without execution, see gpu_validate_call.

Quickstart​

Inputs​

Arguments and options​

Relation arguments​

Named value arguments​

Graph construction options​

Output​

raw (default)​

normalized​

normalized_with_target_info​

path​

raw_with_target_info​

Examples​

Reverse the traversal by projecting named edge columns​

Path mode with a SQL-defined target​

Multi-source BFS from a seed view​

Title-keyed vertices on a small subgraph​

Limits​