Skip to main content

BFS

UDTF: cugraph_bfs

Official cuGraph reference: C API

Run unweighted BFS from one or more sources, returning nullable vertex distances and predecessors with reachable, or one source-to-target path.

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.

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.

The vertex-ID types this UDTF accepts, the numeric types a per-call codebook maps to native ids, and its string-key limits are listed in Vertex ID support; the concrete call-specific schema comes from gpu_validate_call.

Arguments and options​

Relation arguments​

ArgumentRequiredColumnsDescription
edgesyes
  • 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; this algorithm ignores weight
sourcesno
  • vertex: Int32, Int64, Utf8, LargeUtf8, Utf8View
optional BFS source relation; exactly one of sources, source_vertex, and source_vertices is required
include_verticesno
  • vertex: Int32, Int64, Utf8, LargeUtf8, Utf8View
vertices retained by BFS predicate filtering
exclude_verticesno
  • vertex: Int32, Int64, Utf8, LargeUtf8, Utf8View
vertices removed by BFS predicate filtering
target_verticesno
  • vertex: Int32, Int64, Utf8, LargeUtf8, Utf8View
BFS target relation required only for path output; it must contain exactly one row at execution
include_edge_idsno
  • edge_id: Int32, Int64
edge identifiers retained by BFS predicate filtering
include_edgesno
  • 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​

OptionTypeDefaultConstraintsDescription
depth_limitinteger|nullnullmin 0; max 9223372036854776000number of hops to expand; 0 reaches only the sources, and null or absent is unlimited; limits above the vertex type's maximum are unlimited
output_modestring"vertices"one of "vertices", "path"BFS output shape
source_vertexinteger|stringNo defaultscalar source vertex; BFS source selectors are mutually exclusive
source_verticesarrayNo defaultnon-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​

vertices (default)​

ColumnTypeNullableDescription
vertexInt32|Int64|Utf8noVertex reached or considered by the BFS traversal.
distanceInt64yesHop-count distance from the nearest selected BFS source vertex within the predicates and depth limit; null when unreached in vertices output.
predecessorInt32|Int64|Utf8yesPrevious vertex on the discovered BFS tree, null for selected sources and vertices not reached within the predicates and depth limit.
reachableBooleannoWhether the vertex was reached within the predicates and depth limit; equivalent to distance IS NOT NULL.

path​

ColumnTypeNullableDescription
path_indexInt64noZero-based row position in the reconstructed source-to-target path.
sourceInt32|Int64|Utf8noSource vertex for the reconstructed BFS path.
targetInt32|Int64|Utf8noTarget vertex for the reconstructed BFS path.
vertexInt32|Int64|Utf8noVertex reached or considered by the BFS traversal.
distanceInt64noHop-count distance from the nearest selected BFS source vertex within the predicates and depth limit; null when unreached in vertices output.

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.

How does BERT connect to the original LSTM paper?​

Citation edges run from the citing paper to its reference. The query selects BERT and LSTM by title and year, follows those edges with BFS, and joins the path to titles.

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;
  1. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding (2018)
  2. Character-Level Language Modeling with Deeper Self-Attention (2018)
  3. Long short-term memory (1997)

The query took 0.19 s.

Follow-up: compare the other shortest routes. A relational query checks which papers BERT cites that also cite LSTM.

SELECT p.paper_id, p.title, p.year
FROM citation_edges first_step
JOIN papers source ON source.paper_id = first_step.src
JOIN citation_edges second_step ON second_step.src = first_step.dst
JOIN papers target ON target.paper_id = second_step.dst
JOIN papers p ON p.paper_id = first_step.dst
WHERE source.title = 'BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding'
AND source.year = 2018
AND target.title = 'Long short-term memory' AND target.year = 1997
ORDER BY p.year, p.paper_id;

The query took 0.52 s.

It returns ten intermediate papers, including Attention is all you need. The BERT → Transformer → LSTM route is therefore another reading option.

The capture includes all ten records and an independent check of these edges.

How many papers cite AlexNet within three steps?​

The query counts papers at each distance from AlexNet without counting one paper repeatedly. Reversing the edges follows papers that cite AlexNet and then papers that cite those 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 => 'vertices') b
JOIN papers p ON p.paper_id = b.vertex
WHERE b.reachable
GROUP BY b.distance
ORDER BY b.distance;
Shortest distance from AlexNetPapersMean publication year
1 step12,1852017.5
2 steps67,5172017.9
3 steps71,5412017.8

The query took 0.17 s.

The three layers contain 151,243 papers, excluding AlexNet itself. Each paper appears at its shortest distance.

The count describes reach within the April 2020 snapshot.

How many papers are within two citation steps of AlexNet, VGG, or ResNet?​

The three papers form one source set. Each result's distance is the number of reverse citation steps from its nearest source. Title and year identify the 2016 ResNet record because a 2015 preprint shares its 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 => 'vertices') b
JOIN papers p ON p.paper_id = b.vertex
WHERE b.reachable
GROUP BY b.distance
ORDER BY b.distance;
distancepapers
03
128,776
269,038

Would using paper titles as graph IDs merge different records?​

This query compares record IDs with titles in the reference ancestry of Attention Is All You Need, then runs BFS with string titles as vertex IDs. The count shows whether this subgraph contains repeated titles. Identical titles alone do not establish that records describe the same work.

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;

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 => 'vertices') b
WHERE b.distance <= 1
ORDER BY b.distance, b.vertex
LIMIT 6;
paperstitles
370358

This subgraph has 370 records and 358 distinct titles. A title-keyed graph collapses records that share a title, including unrelated works when their titles collide. Use that grouping only when merging every record with the same title matches the question. Here BFS returns the title as a Utf8 vertex:

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

String graphs reject edge_id columns and edge-ID predicate relations. See the Vertex ID support matrix.

How far are several target papers from one source?​

Join targets to the default vertices result to retain every requested ID, including targets absent from the graph. This example follows references from BERT for at most four hops. A null distance means the search did not reach the target within that depth; it does not establish that the target is unreachable in the full graph.

WITH bfs AS (
SELECT vertex, distance
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),
depth_limit => 4)
), targets AS (
SELECT paper_id AS vertex FROM papers
WHERE (title = 'Attention is all you need' AND year = 2017)
OR (title = 'Long short-term memory' AND year = 1997)
), target_distances AS (
SELECT t.vertex AS target, b.distance,
b.distance IS NOT NULL AS reachable
FROM targets t LEFT JOIN bfs b ON b.vertex = t.vertex
)
SELECT target, distance, reachable
FROM target_distances
ORDER BY target;

To return one summary row, replace the final SELECT with SELECT COUNT(distance) > 0 AS target_found, MIN(distance) AS target_distance FROM target_distances. The summary describes the target set rather than each BFS vertex. The search completes the specified depth or exhausts the frontier, which can process more vertices than stopping at the first target hit. Latency and memory use can therefore differ from the former target calls.

Calls using output_mode => 'normalized' or 'raw' must switch to vertices or omit output_mode. Use distance IS NULL or reachable instead of comparing sentinels. Remove return_target_info; express summaries with the join and aggregate above. Use target_vertices inside cugraph_bfs only with output_mode => 'path', which requires exactly one target row at execution.

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
  • vertices output does not expose origin source per vertex
  • sources have distance 0 and null predecessor; unreached graph vertices remain in vertices output with null distance and predecessor
  • reachable describes arrival within the predicates and depth limit; vertices beyond that limit and disconnected vertices both return false
  • string logical vertex-domain BFS rejects edges.edge_id and edge-id predicate relations
  • target_vertices is required for path output and rejected for vertices output; join target relations to vertices output for multiple target distances
  • path output requires exactly one target row at execution time
  • vertices output searches until the depth limit or frontier exhaustion; path output stops after completing the target's BFS depth
  • descriptor option schema is typed registry metadata; validate_call remains the authoritative call-specific checker
  • distances and reachability repeat between runs; when a vertex has several shortest-path parents, the returned predecessor can differ