Minimum Spanning Forest

Algorithm link: Minimum Spanning Forest

Given an undirected graph with one or more connected components, a minimum spanning forest is a set of minimum spanning trees, one for each component. The library implements the algorithm in section 6.2 of Qin et al. 2014:


tg_msf (SET<STRING> v_type, SET<STRING> e_type, STRING wt_attr, STRING wt_type,
BOOL print_accum = TRUE, STRING result_attr = "", STRING file_path = "")

Time complexity

This algorithm has a time complexity of \$O((V+E) * log(V))\$, where \$V\$ is equal to the number of vertices and \$E\$ is equal to the number of edges.

Characteristic Value


Computes a minimum spanning forest. If the JSON or file output selected, the output is the set of edges that form the MSF. If the result_attr option is selected, the edges which are part of the MSF are tagged True; other edges are tagged False.

Input Parameters

  • SET<STRING> v_type: Names of vertex types to use

  • SET<STRING> e_type: Names of edge types to use

  • STRING wt_attr: Name of edge weight attribute

  • STRING wt_type: Data type of edge weight attribute: "INT", "FLOAT", or "DOUBLE"

  • BOOL print_accum: If True, output JSON to standard output

  • STRING result_attr: If not empty, store result values (BOOL) to this attribute

  • STRING file_path: If not empty, write output to this file.

Result Size

\$V - c\$ where \$V\$ is the number of vertices and \$c\$ is the number of components.

Graph Types

Undirected edges


Refer to the example for the MST algorithm. This graph has 3 components. MSF will find an MST for each of the three components.