MinimumSpanningTree¶
Defined in header <ArborX_MinimumSpanningTree.hpp>
Warning
MinimumSpanningTree is experimental and its interface may change.
-
template<typename MemorySpace>
class Experimental::MinimumSpanningTree¶ The minimum spanning tree of a set of points, i.e., the set of edges that connect all the points with the smallest possible total weight. By default, the weight of an edge is the Euclidean distance between its two points (Euclidean minimum spanning tree). It can also be the mutual reachability distance, as used by HDBSCAN. The tree is computed with Boruvka’s algorithm, using a
BoundingVolumeHierarchyto find the nearest neighbors [1].- Template Parameters:
MemorySpace – The Kokkos memory space in which the edges reside.
The class has a second, defaulted, template parameter that is an implementation detail used by
hdbscan().-
using memory_space = MemorySpace¶
-
Kokkos::View<Experimental::WeightedEdge*, MemorySpace> edges¶
The
n - 1edges of the tree, wherenis the number of points. The order of the edges, and which of the two points of an edge is thesourceand which is thetarget, are unspecified.
-
template<typename ExecutionSpace, typename Primitives>
MinimumSpanningTree(ExecutionSpace const &space, Primitives const &primitives, int k = 1)¶ Compute the minimum spanning tree of a set of points.
- Parameters:
space – The execution space in which to run the algorithm.
primitives – The points, accessed through
AccessTraits.k – Selects the weight of the edges, see below.
The following requirements must be satisfied.
MemorySpacemust be the memory space ofPrimitivesand must be accessible fromExecutionSpace.A specialization of
AccessTraitsmust matchPrimitivesas the template argument, andAccessTraits<Primitives>::get()must return a point.There must be at least two points.
If
kis 1 or less, the weight of the edge between the points a and b is the distance between them.If
kis greater than 1, it is their mutual reachability distance, i.e., the largest of the distance between a and b, the core distance of a, and the core distance of b. The core distance of a point is the distance to itsk-th nearest neighbor, the point itself being the first one. Ifkis greater than the number of points, it is the distance to the farthest point.
-
struct Experimental::WeightedEdge¶
An edge of a weighted graph.
-
int source¶
-
int target¶
The indices of the two points the edge connects.
-
float weight¶
The weight of the edge.
Edges can be compared with
operator<, which orders them by weight and, for equal weights, by the smaller and then by the larger of their two indices. The comparison ignores which point is thesourceand which is thetarget.Defined in header <ArborX_WeightedEdge.hpp>.
-
int source¶
Deduction guides¶
The MemorySpace template argument is deduced from the Primitives passed
to the constructor through AccessTraits, so it does not need to be
spelled out.
For instance, MinimumSpanningTree mst(space, points) constructs a
MinimumSpanningTree<MemorySpace>, where MemorySpace is the memory space
of points.
-
template<typename ExecutionSpace, typename Primitives>
Experimental::MinimumSpanningTree(ExecutionSpace, Primitives, int = -1) -> Experimental::MinimumSpanningTree<typename AccessTraits<Primitives>::memory_space>¶ Added in version 2.2.
The guide applies whether or not
kis passed. Its value is ignored: it only takes part in deduction, and thekof the constructor, see above for its default, is the one used. The second, defaulted, template parameter keeps its default value.
Example¶
The example below computes the Euclidean minimum spanning tree of six points in 2D and prints its edges in increasing order.
#include <ArborX_MinimumSpanningTree.hpp>
#include <Kokkos_Sort.hpp>
#include <iostream>
template <typename MemorySpace>
void printEdges(
Kokkos::View<ArborX::Experimental::WeightedEdge *, MemorySpace> edges)
{
auto edges_host =
Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, edges);
Kokkos::sort(edges_host);
for (int i = 0; i < (int)edges_host.size(); ++i)
{
auto const &edge = edges_host(i);
auto min_index = std::min(edge.source, edge.target);
auto max_index = std::max(edge.source, edge.target);
printf("#%d: (%d, %d, %.2f)\n", i, min_index, max_index, edge.weight);
}
}
int main(int argc, char *argv[])
{
Kokkos::ScopeGuard guard(argc, argv);
using ExecutionSpace = Kokkos::DefaultExecutionSpace;
using MemorySpace = ExecutionSpace::memory_space;
Kokkos::View<ArborX::Point<2> *, MemorySpace> cloud("Example::point_cloud",
6);
auto cloud_host = Kokkos::create_mirror_view(cloud);
// 4 | 5
// 3 | 2 4
// 2 | 3
// 1 | 1
// 0 | 0
// ----------
// 0 1 2 3 4
cloud_host[0] = {1, 0};
cloud_host[1] = {0, 1};
cloud_host[2] = {1, 3};
cloud_host[3] = {4, 2};
cloud_host[4] = {2, 3};
cloud_host[5] = {2, 4};
Kokkos::deep_copy(cloud, cloud_host);
ArborX::Experimental::MinimumSpanningTree emst(ExecutionSpace{}, cloud);
auto edges = emst.edges;
// Expected output:
// #0: (2, 4, 1.00)
// #1: (4, 5, 1.00)
// #2: (0, 1, 1.41)
// #3: (1, 2, 2.24)
// #4: (3, 4, 2.24)
printEdges(edges);
return 0;
}