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: http://www-std1.se.cuhk.edu.hk/~hcheng/paper/SIGMOD2014qin.pdf.

Specifications

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 = "")
Characteristic Value

Result

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,

V = number of vertices, c = number of components

Time Complexity

O((V+E) * logV)

Graph Types

Undirected edges

Example

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