Minimum Spanning Forest

Supported Graph Characteristics

Weighted edges

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

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: 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 = "")

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.

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.

Result size

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

Parameters

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)

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.