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.

Signature

cugraph_bfs(table_name, source_vertex_or_vertices [, 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
• string logical vertex-domain BFS rejects edge_id_col, include_edge_ids_*, and include_edge_id_col

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
source_vertex_or_vertices	Int64|Utf8|List<Int64>|List<Utf8>|null-with-source_vertices_table	yes		selector: literal scalar/list source selector, or NULL with source_vertices_table/source_vertex_col options
weight_col	Utf8|null	no		accepted as an edge-column binding but ignored by BFS traversal; semantic effect: none for traversal; BFS distance is a hop count

JSON options

Option	Type	Default	Constraints	Description
depth_limit	Int64|null	null	min 0	Maximum BFS depth in hops; null means unbounded traversal.
edge_id_col	Utf8|null	null	valid when integer vertex domain only	Edge-id column in the edge relation used by edge-id predicate options.
exclude_vertex_col	Utf8|null	null	required when exclude_vertices_table is set; column of exclude_vertices_table; type ref vertex_domain	Column in exclude_vertices_table containing excluded vertex identifiers.
exclude_vertices_table	Utf8|null	null	side input (exclude_vertices, cols: exclude_vertex_col)	Optional relation containing the vertex denylist.
include_edge_dst_col	Utf8|null	null	required when include_edges_table is set; column of include_edges_table; type ref vertex_domain	Destination endpoint column in include_edges_table.
include_edge_id_col	Utf8|null	null	valid when edge_id_col is set; column of include_edges_table; type ref edge_id_domain	Optional edge-id column in include_edges_table; when omitted, include_edges matching uses only endpoint columns.
include_edge_ids_col	Utf8|null	null	defaults to edge_id_col when omitted and include_edge_ids_table is set; column of include_edge_ids_table; type ref edge_id_domain	Column in include_edge_ids_table containing allowed edge identifiers.
include_edge_ids_table	Utf8|null	null	required with edge_id_col; side input (include_edge_ids, cols: include_edge_ids_col)	Optional relation containing allowed edge identifiers.
include_edge_src_col	Utf8|null	null	required when include_edges_table is set; column of include_edges_table; type ref vertex_domain	Source endpoint column in include_edges_table.
include_edges_table	Utf8|null	null	side input (include_edges, cols: include_edge_src_col, include_edge_dst_col, include_edge_id_col)	Optional relation containing allowed edge endpoints and, when edge_id_col is configured, optional edge identifiers.
include_vertex_col	Utf8|null	null	required when include_vertices_table is set; column of include_vertices_table; type ref vertex_domain	Column in include_vertices_table containing allowed vertex identifiers.
include_vertices_table	Utf8|null	null	side input (include_vertices, cols: include_vertex_col)	Optional relation containing the vertex allowlist.
output_mode	Utf8	"raw"	one of "raw", "normalized", "path"	Selects the BFS result shape: raw traversal rows, normalized reachability rows, or one reconstructed source-to-target path.
return_target_info	Boolean	false	valid when output_mode in [raw, normalized]	Adds target_found and target_distance columns when target_vertices_table is supplied.
source_vertex_col	Utf8|null	null	required with source_vertices_table; column of source_vertices_table; type ref vertex_domain	Column in source_vertices_table containing BFS source vertex identifiers.
source_vertices_table	Utf8|null	null	required with source_vertex_col; side input (source_vertices, cols: source_vertex_col)	Optional relation containing BFS source vertices. Use source_vertex=NULL in the positional SQL argument when this option is set.
target_vertex_col	Utf8|null	null	required when output_mode=path or return_target_info=true; column of target_vertices_table; type ref vertex_domain	Column in target_vertices_table containing target vertex identifiers.
target_vertices_table	Utf8|null	null	required when output_mode=path or return_target_info=true; side input (target_vertices, cols: target_vertex_col)	Optional relation containing target vertices for path output or target reachability metadata.

Graph construction options

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

Output schema

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; validate the 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 swapping two arguments

Following citations forward ('src', 'dst') walks into a paper's reference ancestry. Swapping the two column arguments ('dst', 'src') 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. Starting from AlexNet (2012), 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('citation_edges_by_dst', 2163605009, 'dst', 'src', NULL,
                 '{"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. The target is not a literal; it is a relation that must resolve to exactly one row, so a WHERE clause on papers is enough to select the paper titled Long short-term memory. This query traces the reference path from BERT (2018) back to LSTM (1997).

CREATE VIEW lstm_target AS
SELECT paper_id AS vertex FROM papers WHERE title = 'Long short-term memory';

SELECT b.path_index, b.distance, p.year, p.title
FROM cugraph_bfs('citation_edges', 2896457183, 'src', 'dst', NULL,
                 '{"output_mode":"path",
                   "target_vertices_table":"lstm_target",
                   "target_vertex_col":"vertex"}') 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.

Multi-source BFS from a seed view

Passing NULL as the source and pointing source_vertices_table at a view 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:

CREATE VIEW cnn_founders AS
SELECT paper_id AS vertex FROM papers
WHERE paper_id IN (2163605009, 1686810756, 2194775991);

SELECT b.distance, COUNT(*) AS papers
FROM cugraph_bfs('citation_edges_by_dst', NULL, 'dst', 'src', NULL,
                 '{"source_vertices_table":"cnn_founders",
                   "source_vertex_col":"vertex",
                   "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

Limitations & lifecycle

• source lists and source_vertices_table are multi-source BFS, not one BFS per source
• source lists and source_vertices_table 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 edge_id_col, include_edge_ids_*, and include_edge_id_col
• path output requires exactly one target row at execution time
• options_schema_json is typed registry metadata; validate_call remains the authoritative call-specific checker

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_bfs',
  '{"schema_version":1,"relations":{"edges":{"table":"target_edges"}},"options":{"source_vertex":123,"src_col":"src","dst_col":"dst","depth_limit":4}}'
);

See GPU Function Catalog API for the full gpu_validate_call contract.