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<STRING> e_type, STRING wt_attr, STRING wt_type,
BOOL print_accum = TRUE, STRING result_attr = "", 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 wt_attr`	Name of edge weight attribute	(empty string)
`STRING wt_type`	Data type of edge weight attribute (must be `INT`, `FLOAT`, or `DOUBLE`)	(empty string)
`BOOL print_accum`	If True, output JSON to standard output	True
`STRING result_attr`	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 wt_attr

Name of edge weight attribute

(empty string)

STRING wt_type

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

(empty string)

BOOL print_accum

If True, output JSON to standard output

True

STRING result_attr

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_attr 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.