generate.mst | R Documentation |
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.
generate.mst(edges.complete.graph)
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. |
Generation of MST graph is performed using the Prim's algorithm.
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. |
Mario Inostroza-Ponta, Jorge Parraga-Alava, Pablo Moscato
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.
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")
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.