|
|
# 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.
|
|
|
|
|
|
# Available Predicates
|
|
|
|
|
|
* [emst/7](https://gitlab.cs.uni-duesseldorf.de/stups/abschlussarbeiten/prolog-mlpack-libary/-/wikis/PrologMethods/Geometry/emst#emst7)
|
|
|
|
|
|
---
|
|
|
|
|
|
[links/resources](https://gitlab.cs.uni-duesseldorf.de/stups/abschlussarbeiten/prolog-mlpack-libary/-/wikis/PrologMethods/Geometry/emst#connected-linksresources)
|
|
|
|
|
|
## **_emst/7_**
|
|
|
|
|
|
Performs the MST calculation using the Dual-Tree Boruvka algorithm.
|
|
|
|
|
|
```prolog
|
|
|
%% part of the predicate definition
|
|
|
emst( +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.
|
|
|
|
|
|
* [MLpack::emst_C++\_documentation](https://www.mlpack.org/doc/stable/doxygen/classmlpack_1_1emst_1_1DualTreeBoruvka.html)
|
|
|
* [MLpack::emst_Python_documentation](https://www.mlpack.org/doc/stable/python_documentation.html#emst)
|
|
|
|
|
|
added some of the links from the python documentation
|
|
|
|
|
|
* [Minimum spanning tree on Wikipedia](https://en.wikipedia.org/wiki/Minimum_spanning_tree)
|
|
|
* [Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, and Applications (pdf)](http://www.mlpack.org/papers/emst.pdf) |
|
|
\ No newline at end of file |