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.