mstknnclust (version 0.3.2)

generate.mst: Generates a MST graph

Description

This function generates the Minimal Spanning Tree (MST) graph which is a connected and acyclic subgraph contains all the nodes of the complete graph (CG) and whose edges sum (distances) has minimum costs. Each node represents an object of the complete graph.

Usage

generate.mst(edges.complete.graph)

Value

A list with the elements

edges.mst.graph

A object of class "data.frame" with three columns (object_i, object_j, d_ij) representing the distance d_ij between object i and object j that are part of the MST graph.

mst.graph

A object of class "igraph" which is the Minimal Spanning Tree (MST) graph generated.

Arguments

edges.complete.graph

A object of class "data.frame" with three columns (object_i, object_j, d_ij) representing the distance d_ij between object i and object j of the complete graph.

Author

Mario Inostroza-Ponta, Jorge Parraga-Alava, Pablo Moscato

Details

Generation of MST graph is performed using the Prim's algorithm.

References

Prim, R.C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 37 1389-1401.

Ignatenkov, E. (2015). Minimum Spanning Tree (MST) for some graph using Prim's MST algorithm. Stanford University course on Coursera.

Examples

set.seed(1987)

##Generates a data matrix of dimension 50X13
n=50; m=13
x <- matrix(runif(n*m, min = -5, max = 10), nrow=n, ncol=m)

##Computes a distance matrix of x.

library("stats")
d <- base::as.matrix(stats::dist(x, method="euclidean"))

##Generates complete graph (CG)

cg <- generate.complete.graph(1:nrow(x),d)

##Generates MST graph

mstree <- generate.mst(cg)

##Visualizing MST graph
plot(mstree$mst.graph, main="MST")