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 BoundingVolumeHierarchy to 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 - 1 edges of the tree, where n is the number of points. The order of the edges, and which of the two points of an edge is the source and which is the target, 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.

  • MemorySpace must be the memory space of Primitives and must be accessible from ExecutionSpace.

  • A specialization of AccessTraits must match Primitives as the template argument, and AccessTraits<Primitives>::get() must return a point.

  • There must be at least two points.

If k is 1 or less, the weight of the edge between the points a and b is the distance between them.

If k is 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 its k-th nearest neighbor, the point itself being the first one. If k is 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 the source and which is the target.

Defined in header <ArborX_WeightedEdge.hpp>.

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 k is passed. Its value is ignored: it only takes part in deduction, and the k of 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;
}

See also

References