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. Substitute your own registered relations.

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.

Endpoint columns accept Int32 vertex IDs only; logical string endpoints are not supported (legacy Int32-only contract). The shared vertex-ID contract is summarized in Vertex ID support; the concrete call-specific schema comes from gpu_validate_call.

Arguments and options​

Relation arguments​

ArgumentRequiredColumnsDescription
edgesyes
  • src, dst: Int32
  • weight: Float32, Float64
  • edge_id (optional): Int32
weighted edge relation with canonical src, dst, and required weight columns

Every edge_id column must have the integer type of src and dst.

Named value arguments​

This UDTF has no algorithm-specific value arguments. Its inputs are the relation arguments above and the graph construction options below.

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
srcInt64noSource vertex of an edge selected for the minimum spanning tree.
dstInt64noDestination 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. cugraph_minimum_spanning_tree requires Int32 vertex IDs. The query builds a dense mapping because AMiner IDs can exceed the Int32 range:

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 TABLE ai_era_vertex_ids AS
SELECT paper_id, CAST(ROW_NUMBER() OVER (ORDER BY paper_id) AS INT) AS vid
FROM (SELECT e.src AS paper_id 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
      UNION
      SELECT e.dst 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);

CREATE OR REPLACE VIEW ai_era_edges AS
SELECT va.vid AS src, vb.vid AS 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
JOIN ai_era_vertex_ids va ON va.paper_id = e.src
JOIN ai_era_vertex_ids vb ON vb.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 ai_era_vertex_ids va ON va.vid = m.src
JOIN ai_era_vertex_ids vb ON vb.vid = m.dst
JOIN papers pa ON pa.paper_id = va.paper_id
JOIN papers pb ON pb.paper_id = vb.paper_id
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

Among the selected links, the largest gaps connect papers in character recognition, radiographic imaging, and fingerprint classification. 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. The UDTF returns src and dst, so SQL joins the IDs back to years and titles.

Limits​

  • cuGraph C API edge-type dispatch requires Int32 source and destination vertex columns
  • cuGraph requires directed=false so the graph is constructed as an undirected/symmetric view

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

On this page