# 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 = "")``````

### 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

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 where V is the number of vertices and c is the number of components.

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.