Fast Euclidean Minimum Spanning Tree
An implementation of the Dual-Tree Boruvka algorithm for computing the Euclidean minimum spanning tree of a set of input points.
:- use_module('path/to/.../src/methods/emst/emst.pl').
%% usage example
TrainData = [5.1,3.5,1.4, 4.9,3.0,1.4, 4.7,3.2,1.3, 4.6,3.1,1.5],
emst(TrainData, 3, 1, ResultsList, _).Available Predicates
emst/5
Performs the MST calculation using the Dual-Tree Boruvka algorithm.
%% predicate definition
emst(DataList, DataRows, Naive, ResultsList, YCols) :-
convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrows, X)),
emstI(X, Xsize, Xrows, Naive, Y, YCols, YRows),
convert_float_array_to_2d_list(Y, YCols, YRows, ResultsList).
%% foreign c++ predicate definition
foreign(emst, c, emstI( +pointer(float_array), +integer, +integer,
+integer,
-pointer(float_array), -integer, -integer)).Parameters
| Name | Type | Description | Default |
|---|---|---|---|
| dataset | +matrix | Dataset to build a tree for. | - |
| naive | +integer(bool) | Wheter the computation should be done in O(n^2) naive mode | (0)false |
| result | -matrix | The results will be a 3xN matrix (with N equal to the number of edges in the minimum spanning tree). The first row will contain the lesser index of the edge; the second row will contain the greater index of the edge; and the third row will contain the distance between the two edges. | - |
Connected Links/Resources
If you want a more detailed explanation, then go to the python documentation. There is most of the time a good explanation on how the methods work and what the parameters do.
added some of the links from the python documentation