Minimum Spanning Tree

SQL function: cugraph_minimum_spanning_tree

Official cuGraph reference: Python API

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

Signature

cugraph_minimum_spanning_tree(table_name, 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	Vertex identity output columns remain numeric.
Logical string edge endpoints	Not supported	No canonical string output is declared.

This is a legacy Int32-only vertex-ID contract; logical string endpoints are not supported.

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
weight_col	Utf8|null	yes		required edge weight column; semantic effect: required edge weights define the spanning-tree objective

JSON options

This function has no algorithm-specific options.

Graph construction options

This function builds an undirected graph by default (directed=false); all other graph construction options follow the shared defaults documented in Graph Construction Options.

Output schema

Column	Type	Nullable	Description
src	Int64	no	Source vertex of an edge selected for the minimum spanning tree.
dst	Int64	no	Destination vertex of an edge selected for the minimum spanning tree.

These are generic descriptor schemas; validate the call to get the concrete, table-specific output schema.

Examples

This example runs on the citation network demo dataset.

The backbone with the least time travel

An MST needs a weight worth minimizing, and SQL can derive one: weight each citation by the year gap between the two papers, and the minimum spanning tree becomes the backbone that keeps every paper connected through the most era-local links available. The graph is the AI literature across all years (same ten field-of-study labels as the Louvain example, no year filter); cugraph_minimum_spanning_tree needs Int32 vertex ids, so the renumbering pattern from the demo-dataset page applies:

CREATE 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 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 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;

The interesting rows are the links the tree could not avoid: the largest year gaps that survive minimization are places where a modern paper's only connection to the rest of the field runs through a decades-older one.

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('ai_era_edges', 'src', 'dst', 'year_gap') 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_a	paper_a	year_b	paper_b	gap
1972	Results Obtained Using a Simple Charac	2019	Comparison of Feature Extraction Techn	47
2015	A two-level classifier for automatic m	1973	The Analysis of Radiographic Images	42
1978	Image Segmentation and Feature Extract	2018	Texture description using multi-scale	40
2015	A survey of fingerprint classification	1976	Feature extraction for fingerprint cla	39
1982	On the Difficulties Involved in the Se	2018	An Accurate Modeling Technology Based	36

Character recognition, radiographic imaging, and fingerprint classification: half-century-old pattern-recognition work is still the shortest bridge between some modern niches and everything else. Overall the 204,472-edge input reduces to 49,263 backbone links over 50,300 connected papers (a forest of ~1,000 similarity families; the output is symmetrized, which m.src < m.dst de-duplicates), and minimization pulls the average year gap from 3.9 down to 2.5 years. The MST output carries only src/dst, so every attribute in the result — years, titles, the gap itself — comes from joining SQL tables back onto the tree.

Limitations & lifecycle

• 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

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_minimum_spanning_tree',
  '{"schema_version":1,"relations":{"edges":{"table":"target_edges"}},"options":{"src_col":"src","dst_col":"dst","weight_col":"weight"}}'
);

See GPU Function Catalog API for the full gpu_validate_call contract.