Tree#

template<typename vertex_t, typename edge_t, typename weight_t>
std::unique_ptr<legacy::GraphCOO<vertex_t, edge_t, weight_t>> minimum_spanning_tree(raft::handle_t const &handle, legacy::GraphCSRView<vertex_t, edge_t, weight_t> const &graph, rmm::device_async_resource_ref mr = rmm::mr::get_current_device_resource())#

Generate edges in a minimum spanning forest of an undirected weighted graph.

A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph. If the graph is connected it returns the minimum spanning tree.

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • edge_t – Type of edge identifiers. Supported value : int (signed, 32-bit)

  • weight_t – Type of edge weights. Supported values : float or double.

Parameters:

  • handle – [in] Library handle (RAFT). If a communicator is set in the handle,

  • graph_csr – [in] input graph object (CSR) expected to be symmetric

  • mr – [in] Memory resource used to allocate the returned graph

Returns:

out_graph Unique pointer to MSF subgraph in COO format

template<typename vertex_t, typename edge_t, bool multi_gpu>
rmm::device_uvector<vertex_t> maximal_independent_set(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, raft::random::RngState &rng_state)#

Find a Maximal Independent Set.

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false)

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • rng_state – The RngState instance holding pseudo-random number generator state.

Returns:

A device vector containing vertices in the maximal independent set.