Skip to main content

Minimum Spanning Tree

UDTF: cugraph_minimum_spanning_tree

Official cuGraph reference: C API

Select a minimum-total-weight acyclic edge set, producing a spanning tree for a connected graph or a spanning forest otherwise.

Quickstart​

The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight.

SELECT *
FROM cugraph_minimum_spanning_tree(
edges => (SELECT src, dst, weight 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.

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: Float32, Float64
  • edge_id (optional): Int32, Int64
weighted edge relation with canonical src, dst, and required weight columns

Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.

Graph construction options​

This UDTF requires directed=false (undirected/symmetric graph). All other graph construction options follow the shared defaults documented in Graph Construction Options.

Output​

ColumnTypeNullableDescription
srcInt64|Utf8noSource vertex of an edge selected for the minimum spanning tree.
dstInt64|Utf8noDestination vertex of an edge selected for the minimum spanning tree.

These are generic descriptor schemas. Run gpu_validate_call to get the concrete, table-specific output schema.

Examples​

This example runs on the citation network demo dataset.

Which large publication-year gaps remain in a minimal map of AI citations?​

Each citation receives a weight equal to the absolute publication-year gap. The query finds a minimum spanning forest that minimizes the total gap within each connected component, then shows its five largest selected gaps. The graph covers 1900 to 2020 and the ten field-of-study labels below. The query passes the Int64 paper IDs directly. The vertex codebook maps them to Int32 ids internally and decodes the result:

CREATE OR REPLACE VIEW ai_all_nodes AS
SELECT paper_id, year FROM papers
WHERE year BETWEEN 1900 AND 2020 AND primary_fos IN (
'Deep learning', 'Artificial neural network', 'Convolutional neural network',
'Recurrent neural network', 'Natural language processing',
'Reinforcement learning', 'Image segmentation', 'Feature extraction',
'Object detection', 'Speech recognition');

CREATE OR REPLACE VIEW ai_era_edges AS
SELECT e.src, e.dst, CAST(ABS(a.year - b.year) AS DOUBLE) AS year_gap
FROM citation_edges e
JOIN ai_all_nodes a ON a.paper_id = e.src
JOIN ai_all_nodes b ON b.paper_id = e.dst;

SELECT pa.year AS year_a, substr(pa.title, 1, 38) AS paper_a,
pb.year AS year_b, substr(pb.title, 1, 38) AS paper_b,
ABS(pa.year - pb.year) AS gap
FROM cugraph_minimum_spanning_tree(
edges => (SELECT src, dst, year_gap AS weight FROM ai_era_edges)) m
JOIN papers pa ON pa.paper_id = m.src
JOIN papers pb ON pb.paper_id = m.dst
WHERE m.src < m.dst
ORDER BY gap DESC, year_a
LIMIT 5;
year_apaper_ayear_bpaper_bgap
1972Results Obtained Using a Simple Charac2019Comparison of Feature Extraction Techn47
2015A two-level classifier for automatic m1973The Analysis of Radiographic Images42
1978Image Segmentation and Feature Extract2018Texture description using multi-scale40
2015A survey of fingerprint classification1976Feature extraction for fingerprint cla39
1982On the Difficulties Involved in the Se2018An Accurate Modeling Technology Based36

The input has 204,472 edges and the symmetrized forest returns 49,263 links over 50,300 papers. These rows show one minimum forest. They do not establish that an individual link is unique or unavoidable.

Limits​

  • the native graph type indexes Int32 vertices only; Int64 and string vertex columns run through a per-call codebook that fails when the distinct vertex count exceeds Int32::MAX
  • edge_id columns are rejected when Int64 vertices are mapped to Int32 ids
  • cuGraph requires directed=false so the graph is constructed as an undirected/symmetric view