Minimum Spanning Forest

Supported Graph Characteristics

Weighted edges

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

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.

Notes

This is an implementation of the algorithm in section 6.2 of Qin et al. 2014: Scalable Big Graph Processing in MapReduce

Specifications

tg_msf ( SET<STRING> v_type_set,  SET<STRING> e_type_set, STRING weight_attribute, STRING weight_type,
BOOL print_results = TRUE, STRING result_attribute = "", STRING file_path = "")

Parameters

Parameter Description Default

Parameter	Description	Default
`SET<STRING> v_type`	Names of vertex types to use	(empty set of strings)
`SET<STRING> e_type`	Names of edge types to use	(empty set of strings)
`STRING weight_attribute`	Name of edge weight attribute	(empty string)
`STRING weight_type`	Data type of edge weight attribute (must be `INT`, `FLOAT`, or `DOUBLE`)	(empty string)
`BOOL print_results`	If True, output JSON to standard output	True
`STRING result_attribute`	If not empty, store result values (`BOOL`) to this attribute	(empty string)
`STRING file_path`	If not empty, write output to this file.	(empty string)

SET<STRING> v_type

Names of vertex types to use

(empty set of strings)

SET<STRING> e_type

Names of edge types to use

(empty set of strings)

STRING weight_attribute

Name of edge weight attribute

(empty string)

STRING weight_type

Data type of edge weight attribute (must be INT, FLOAT, or DOUBLE)

(empty string)

BOOL print_results

If True, output JSON to standard output

True

STRING result_attribute

If not empty, store result values (BOOL) to this attribute

(empty string)

STRING file_path

If not empty, write output to this file.

(empty string)

Output

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_attribute option is selected, the edges which are part of the MSF are tagged True; other edges are tagged False.

Result size

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

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.

Example

Refer to the example for the Minimum Spanning Tree algorithm. This graph has three components. The MSF algorithm finds an MST for each of the three components.